WA in only one test case of CHEFMOVR

My solution to “Chef and Mover”, from the August 2017 Challenge, is getting WA in one testcase of the second subtask: https://www.codechef.com/viewsolution/14986168.
Could someone please provide the input of this testcase, or at least explain why I am getting WA, even though the rest of the solves are accepted? Thanks.

There could be some issues with the logic as it is taking too much long time even for small inputs (which is why you are getting TLE in one test case). Try with fast IO (though I doubt fast IO would make such drastic change). Also, try with long long integers. Currently, you are trying with integer variables. Final answer could overflow, in which case you get WA.

1 Like

Hi @dkyriakidis, you are getting WA because you are using int datatype for all calculations, however as each element in the array can be upto 109, the sum of the elements can reach 105×109, which easily exceeds the maximum limit for the int datatype (exactly 231-1, approximately 2×109), resulting in integer overflow. One such test case here.
To avoid this you should use a datatype with higher capacity, which is long long int (maximum value exactly 263-1, approximately 9×1018). This will not cause a WA, but you will still get a TLE. This is because you are moving the values one at a time. You can speed it up by moving as much as needed at once. Hope this makes it clear, feel free to ask if something isn’t :slight_smile:

2 Likes

@meooow I changed the data type, and I am getting the correct output in the example you so kindly provided. At this point, I don’t care about TLE, as long as my solution is theoretically correct. Thank you very much for the quick response!

@utkalsinha Thanks for responding. I eliminated the WA issue by changing the datatype. Getting rid of TLE would probably require some optimization.

//