You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 21 Aug '17, 21:36

dkyriakidis's gravatar image

3★dkyriakidis
72
accept rate: 0%

1

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.

(21 Aug '17, 21:44) utkalsinha6★

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

(22 Aug '17, 03:31) dkyriakidis3★

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 :)

link

answered 21 Aug '17, 21:49

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

edited 21 Aug '17, 22:03

@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!

(22 Aug '17, 03:06) dkyriakidis3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×193
×9

question asked: 21 Aug '17, 21:36

question was seen: 276 times

last updated: 22 Aug '17, 03:31