Shisuko's blog

By Shisuko, history, 3 years ago, In English

In an interactive problem that I plan on setting, the interactor will have to do some nontrivial amount of work (say ~500ms). This only happens once, at the start of the interaction. On the one hand, 500ms isn't that long, but on the other hand... it's not an insignificant amount either, and could feasibly make or break whether a solution is AC or TLE.

Does anyone know how the Time Limit of interactive problems is computed on Polygon/Codeforces?

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

According to the problem statement of problem 1091G - New Year and the Factorisation Collaboration, "the run time of the interactor is also counted towards the time limit." So, I'm pretty sure that the TL includes the time taken by the interactor.

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Both the interactor and the participant's solution run simultaneously and none of them can proceed without the other's response. So, the execution time for both of them must be equal to the total time of the complete interaction. In your case, any participant's solution will have to wait (stay idle) for the 500ms that the interactor will take and this will probably be counted towards the execution time of the participant's solution.
SPOJ takes care of these issues by assigning the actual time limit as 2 times the given time limit plus some constant for both participant's solution and interactor. You can read about it here. I am not sure if Polygon does the same thing or not but if I have to guess then it probably doesn't as the intended solution for one of the interactive problem which I had set on Codechef took around 1500ms on Polygon and around 400ms on Codechef (which uses SPOJ libraries).

»
3 years ago, # |
Rev. 3   Vote: I like it +23 Vote: I do not like it

I've checked that in Polygon.

Problem statement: given a number $$$n$$$, you need to print $$$\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^n i \cdot j \right) \mod (10^9+7)$$$. You can ask query ? any number of times, then each time interactor will calculate the answer and give it to solution. At the end you need to print ! ans.

Interactor

I have few solutions, they start with the following code:

code

They differ with main function:

1-ask-read.cpp
2-calc.cpp
3-calc-ask-read.cpp
4-ask-calc-read.cpp
5-ask-read-calc.cpp

Problem has $$$14$$$ tests, $$$i$$$-th of them is $$$n=5000 \cdot i$$$. TL is 5 s.

Invocation results

My conclusions (I am not sure, but it looks like this):

  • displayed time is just solution's runtime;

  • if just solution's runtime is bigger than TL then you get TL;

  • if just interactor's runtime is bigger than some value then you get IL;

  • some value is a bit (2 times?) bigger than TL;

  • sum of just solution's runtime and just interactor's runtime isn't calculated.