Help in Gamenumb from February Lunchtime 2018

I can not figure out why my implementation is giving WA, the implementation passes only the first subtask.

Here is what I did:-

  1. Made an array of pairs of A[i] and D[i] for all the n values.
  2. Sorted the above array on the basis of value of A[i]. Also initialised a variable sum to 0.
  3. Took integer variables, say lp(denoting left-pointer) and rp(right-pointer). The final sum will thus be given by number written on all the cards lying in the range [lp, rp] (rp and lp inclusive).
  4. Initialised lp to 1 and rp to total number of cards. That is assumed, initially all cards were selected. Now for each turn of Chef, I selected the last B[i] cards, that is assigned lp to rp - B[i] + 1 or lp = rp + B[i] - 1 and left rp untouched. Similarly for each turn of Chefu, I selected the first B[i] cards, that is assigned rp tp lp + B[i] - 1 or rp = lp + B[i] - 1 keeping lp untouched.
    In this way finally sum can be obtained by summing up numbers written on all the cards in the range [lp, rp].
  5. Made a prefix sum array(say pr) of size n, indicating the sum of cards ending at the i’th index, using the value of D[i], that is:- pr[0] = D[0], pr[1] = D[0] + D[1], pr[2] = D[2] + pr[1], … so on. Found at what index j, pr[j] >= lp.
  6. Finally ran a while loop until lp equals to rp. Inside the loop if rp > pr[j] then collected all cards from lp to pr[j]. That is sum += (pr[j] - lp + 1) * D[j] (total cards to selected multiplied by their value), and set lp to pr[j] + 1(indicating all cards till pr[j] have been selected) and also incremented j. Else if (rp <= pr[j]) then collected all cards till rp using the formula sum += (rp - lp + 1) * D[j], set lp = rp + 1(indicating all cards have been selected), this will also break the loop.
  7. Finally printed the value of sum.

Here is the C++ implementation, which is passing the sample test case given in the question and all the test cases manually made by me. But when submitted only passes the first subtask.

I’m using the exact same logic and facing the exact same situation. Did you find the error?


1 Like

I found the error. I was summing up the total no. of cards in an int which led to overflow.
Same is happening with your solution. You need to typecast the third parameter of accumulate to long long int as accumulate returns the value according to its type.

1 Like

Thanks @Fukra… I have no words, how to thank you.