Hey guys!! Can anyone help me solve this problem, please? I tried solving it but I keep getting Wrong Answer!! I also viewed a few solutions but I was not able to understand them!!
Link to the problem: https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p2 My code: #include <bits/stdc++.h> using namespace std; void getMinMax(vector<pair<int, int> >& V, int& mini, int& maxi) { mini = V[0].first; maxi = V[0].second; for(int i = 1; i < V.size(); i++) { mini = min(mini, V[i].first); maxi = max(maxi, V[i].second); } } bool isValid(vector<pair<int, int> >& X, vector<pair<int, int> >& Y, vector<pair<int, int> >& Z, long long len, int minx, int maxx, int miny, int maxy, int minz, int maxz) { int n = X.size(); bool included[n]; for(int i = 0; i < n; i++) { if((X[i].first >= minx && X[i].first <= minx + len && X[i].second >= minx && X[i].second <= minx + len && Y[i].first >= miny && Y[i].first <= miny + len && Y[i].second >= miny && Y[i].second <= miny + len && Z[i].first >= minz && Z[i].first <= minz + len && Z[i].second >= minz && Z[i].second <= minz + len) || (X[i].first <= maxx && X[i].first >= maxx - len && X[i].second <= maxx && X[i].second >= maxx - len && Y[i].first <= maxy && Y[i].first >= maxy - len && Y[i].second <= maxy && Y[i].second >= maxy - len && Z[i].first <= maxz && Z[i].first >= maxz - len && Z[i].second <= maxz && Z[i].second >= maxz - len)) included[i] = true; else included[i] = false; } for(int i = 0; i < n; i++) if(!included[i]) return false; return true; } int solve(vector<pair<int, int> >& X, vector<pair<int, int> >& Y, vector<pair<int, int> >& Z) { int n = X.size(); int minx, maxx, miny, maxy, minz, maxz; getMinMax(X, minx, maxx); getMinMax(Y, miny, maxy); getMinMax(Z, minz, maxz); int maxlen = max(max(maxx - minx, maxy - miny), (maxz - minz)); long long lo = 1, hi = maxlen, mid, ans; while(lo <= hi) { mid = lo + (hi - lo)/2; if(isValid(X, Y, Z, mid, minx, maxx, miny, maxy, minz, maxz)) { cerr << "valid mid=" << mid << endl; ans = mid; hi = mid - 1; } else { cerr << "invalid mid=" << mid << endl; lo = mid + 1; } } return ans; } int main() { freopen("star.in", "r", stdin); freopen("star.out", "w", stdout); freopen("star.err", "w", stderr); int T; cin >> T; for(int tnum = 1; tnum <= T; ++tnum) { int n, x, y, z, r; cin >> n; vector<pair<int, int> > X, Y, Z; for(int i = 0; i < n; i++) { cin >> x >> y >> z >> r; X.push_back(make_pair(x - r, x + r)); Y.push_back(make_pair(y - r, y + r)); Z.push_back(make_pair(z - r, z + r)); } cerr << "Case #" << tnum << ": " << endl; int ans = solve(X, Y, Z); cout << "Case #" << tnum << ": " << ans << endl; } return 0; } -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/ef2ac81e-ffe8-479c-b46e-014468bee6a5%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
