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?
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.
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).
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
.I have few solutions, they start with the following code:
They differ with
main
function: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 thanTL
then you get TL;if
just interactor's runtime
is bigger thansome value
then you get IL;some value
is a bit (2 times?) bigger thanTL
;sum of
just solution's runtime
andjust interactor's runtime
isn't calculated.