Interactive Problems and the way to deal with them!

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.

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.

14 Likes

A related article on codeforces https://codeforces.com/blog/entry/45307

2 Likes

There is no need to use fflush(stdout) in c++ if you use cout<<endl; instead of cout<<"
"; because endl automatically flushes.

2 Likes

I have AC in all tasks of INTXOR but getting WA(-1.0000) in only one task of the 3rd Sub-Task and I have no clue why I m getting this and I m using python 3.6, any idea ???

2 Likes

please anyone provide some more understandable example of interactive problem

@carnage17, endl might not always work. It’s possible that you don’t require to go to the new line. You can use cout.flush() or fflush(stdout)

how to close the output stream after program completes in c++?

for c++ , I do
cout << endl;
whenever I want judge to read my answers.

“Every contest has an end… and a blog from @taran_1407.” - Anonymous

2 Likes

Yes, I wasn’t aware of that article when I wrote this. Thanks for sharing

Yes… I told the same…

No…

The running time -1.000 is wrong but the verdict WA is correct. Ignore running time here.

I thought binary search problem was easy enough. Please share the problem which shall be easy, though should not belong to any running contest.

@taran_1407, how did you get 6* if you can not tell what does every verdict mean? After 20 random hit & trial submissions, I found out it’s a TLE, not WA. In C++, my same solution got accepted. I’m new to python perhaps I m not aware of optimized read and write functions of python. This is really disappointing, I wasted my 2 days just bcoz of that fucking incorrect verdict.

@taran_1407, Btw thanks, at least you replied.

I would prefer to say more about it only after the end of the contest.

Won’t that also output a newline? What’s the difference between them?

endl makes sure that the printed text is not in buffer and \n doesn’t.
Generally code does optimization by not printing data unless there is good amount of data to print. That makes it faster. It will strore it in temp buffer( say storage like queue) before printing.

1 Like