MGAME timeout

general
, , ,
1

Can you please explain why my solution timed out for the second subtask? I used the same method described in the editorial:

https://www.codechef.com/viewsolution/22454513

I even submitted a DP solution with precalculated values:

https://www.codechef.com/viewsolution/22467759

This was a contest solution, it affects my score.

Edit:

I have tested I/O speed on the Enormous Input Test problem:

https://www.codechef.com/viewsolution/22491210

https://www.codechef.com/viewsolution/22491207

Both of them were accepted, the Console.WriteLine(count) version is little bit faster. How was I supposed to know my output is not fast enough?

2

Did you try to use BufferedReader?

For details, see https://discuss.codechef.com/questions/55818/faster-input-in-java

3

It’s C#, not Java. I’m using the standard Console.ReadLine() as always.

4

Apologies for the language mix-up.

The issue is definitely with the I/O speed.

If you change your line


Console.WriteLine(count);

to


Console.WriteLine("{0}", count);

then you get an AC.

5

Thanks a lot! I should’ve tested my I/O speed. It’s really annoying to lose points because of that.

6

Once the input/output size reaches 10^5, the I/O should always be a concern, and it may take non-trivial amount of time just to read the problem data and write the answers. It’s just one thing to keep in mind always.

7

Also, printing each answer one by one is not a good idea for this problem, unfortunately. If T = 10^6, your code prints the answer 10^6 times, which may lead to TLE. I also had this issue and fixed it by collecting them in StringBuilder. See here: https://www.codechef.com/viewsolution/22199707
It somehow works in 1.65 sec. By the way, I/O speed is another concern as well.

8

I can’t view your solution for some reason, but yes, it makes sense to output like that. But it’s not necessary, if you just want to gain 100 points.

9

Already fixed the link. Yeah, I understand that. I got this issue in some long contest before and it is so annoying. Using Buffered Reader and do not print too often are always the best options.

10

plz anyone explain the logic i cannot understand editorial

11

plz anyone explain the logic i cannot understand editorial

12

You need to understand how modulo arithmetic works. Counting the possibilities is just a matter of combinatorics.