Is overflow happening? To use smaller numbers as an example, if A was 5, B was 95, C was 10 and D was 90, and the largest number we could store was 100, then
min(A,B) = min(5, 95) = 5 min(C,D) = min(10, 90) = 10 min(A,B) + min(C,D) = 5 + 10 = 15. but min (A+C, A+D, B+C, B+D) = min (15, 95, 105, 185) which overflows. I have no idea if the constraints of the problem allow this. On Tue, 17 Jul 2018 at 22:57 <[email protected]> wrote: > I was trying to solve the Card Game problem of Round G, Kickstart 2017. > While solving the small dataset, I used two codes, and got two different > answers. However, the logic behind both the codes is same. > > Code 1: > long long int f(map<int, vector<long long int>> v, int N) > { > if(v.size() <= 1) > return 0; > int i = 0, j; > long long int R_1, B_1, R_2, B_2, A, B, C, D, output = -1; > while(i < N) > { > j = i+1; > while(j < N) > { > if((v.find(i+1) != v.end()) && (v.find(j+1) != v.end())) > { > R_1 = v[i+1].at(0); > B_1 = v[i+1].at(1); > R_2 = v[j+1].at(0); > B_2 = v[j+1].at(1); > map<int, vector<long long int>> u_1(v.begin(), v.end()); > u_1.erase(i+1); > A = R_1^B_2 + f(u_1,N); > map<int, vector<long long int>> u_2(v.begin(), v.end()); > u_2.erase(j+1); > B = R_1^B_2 + f(u_2,N); > map<int, vector<long long int>> u_3(v.begin(), v.end()); > u_3.erase(i+1); > C = R_2^B_1 + f(u_3,N); > map<int, vector<long long int>> u_4(v.begin(), v.end()); > u_4.erase(j+1); > D = R_2^B_1 + f(u_4,N); > > long long int F = min(min(min(A,B),C),D); > if(output == -1) > { > output = F; > } > if(output > F) > { > output = F; > } > } > j++; > } > i++; > } > return output; > } > > Output from Code 1: > > Case #1: 2774879 > > Code 2: > > long long int f(map<int, vector<long long int>> v, int N) > { > if(v.size() <= 1) > return 0; > int i = 0, j; > long long int R_1, B_1, R_2, B_2, A, B, C, D, output = -1; > while(i < N) > { > j = i+1; > while(j < N) > { > if((v.find(i+1) != v.end()) && (v.find(j+1) != v.end())) > { > R_1 = v[i+1].at(0); > B_1 = v[i+1].at(1); > R_2 = v[j+1].at(0); > B_2 = v[j+1].at(1); > map<int, vector<long long int>> u_1(v.begin(), v.end()); > u_1.erase(i+1); > A = f(u_1,N); > map<int, vector<long long int>> u_2(v.begin(), v.end()); > u_2.erase(j+1); > B = f(u_2,N); > > long long int F = min(R_1^B_2, R_2^B_1) + min(A,B); > if(output == -1) > { > output = F; > } > if(output > F) > { > output = F; > } > } > j++; > } > i++; > } > return output; > } > > Output from Code 2: > > Case #1: 260399187 > > I am quite confused at the two different outputs. > > After all, what's the difference between, > > min(a,b) + min(c,d) and min(a+c,a+d,b+c,b+d)? > > I am completely blank. Any help from your side will be highly appreciated. > > Waiting for a response. > > -- > 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/b78cbe8a-b6ac-4c6e-934f-af431a219f71%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- 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/CAJej63JaSQUNZgpYVCrRiwqLyOWoNDgoV9b1MJaJe4e9BqUMOw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
