Hello Folks
Today, I’m going to write my first blog on Interactive problems and all you need to know about them.
First of all, Let us understand what are interactive problems.
Interactive problem is nothing but a problem where your solution should interact (send output to and receive input from) with a grader problem (also called problem judge). If your solution makes the queries to find out the answer or make the queries in a specific way as required in the problem statement, you get an accepted verdict. Otherwise, you get Wrong Answer or other verdicts. Usually, we have an upper limit on the number of queries too. Making queries in excess lead to the Wrong Answer.
Now, the Important thing about Interactive problems is flushing output.
In most languages, printing output to console/output screen is an expensive operation and thus, languages keep collecting the output (called buffered output), printing all the collected output in one go at the end of the program to improve efficiency. But this may cause us trouble with Interactive problems as we want our output to be sent to output console before terminating the program.
Fortunately, we have tools for this, called manually flushing output. Flushing output means, that you ask your program to print all buffered output and clear the buffer. This way, the output is sent to console before termination of the program, and only then we can receive input from the grader program since it returns the next input only after receiving previous output.
Flushing in c++ can be done using fflush(stdout) and in java, System.out.flush() or out.flush() where out represent our outputstream.
An example interactive problem.
I shall take probably the most popular interactive problem to explain how things work with interactive problems.
We have an array A of length N hidden from us, which is sorted in ascending order. We are given only N and a value Val. We are allowed to make logN queries of the form ? x y.
The answer of query shall be 0 if A[x] == y, -1 if A[x] < y and 1 if A[x] > y.
In the end, we are required to print output by printing ! x where x is the index of position such that A[x] = val. If no position contain value val, print -1.
The simple solution is to iterate over all position, make a query and if any position matches, print that position. It shall take N queries in the worst case which violate the query limit.
Let us utilize the ascending order of A to use binary search.
We have range [l,r] initially [0,N-1] which may contain value Val. Let mid = (l+r)/2 and make a query ? mid val. If we get 0, we have found the required position. Otherwise, if the answer to the query is -1, we are sure that no value in the range [mid, r] contain answer since all values in this range are greater than Val. So, we change the right end to (mid-1). Similar way, we change left end to (mid+1) if the answer to the query is 1. We are bound to find the required position in log_2 N queries due to dividing search space by half at each step.
Making query/Printing output
In interactive problems, we make query/print output in two steps.
Print the output in the normal manner (like non-interactive problems.) Using cout or scanf or any other method in c++ or out.println() in Java or similar ways in other languages.
Flush the output using following commands in various languages.
fflush(stdout) in C++.
System.out.flush() in Java.
stdout.flush() in Python.
flush(output) in Pascal.
See the documentation for other languages.
Important point Remember to close the output stream after the program completes. The reason is, that your program may keep waiting for grader while grader has completed its execution. It may lead to an unexpected verdict.
Note 1: Submissions sometimes get a Wrong Answer verdict, but the execution time is displayed as -1 seconds. This should be interpreted as a TLE.
Note 2: A Judge Error usually means that Interactive Judge was waiting for user input and User’s code didn’t give it, and so the resulting Time Limit Exceeded is shown as Judge Error.
So this concludes our blog for interactive problems. I shall try to write more blogs soon. Let me know of any interesting topic you want the blog for. Discuss in comments.
For trying interactive problems, Codechef December Long Challenge 2018 has a lot of interactive problems. A recent interactive problem on codeforces can be found here.
Until then, see you all!
PS: Special Thanks to @mgch for inspiring me to write this blog.