### MikeMirzayanov's blog

By MikeMirzayanov, 3 years ago, translation, ,

Sometimes you can meet interactive problems on programming contests (including Codeforces).

In problems of this type, the input data given to your program may be not predetermined but is built specifically for your solution. Jury writes a special program — interactor, such that its output is tranferred to the input of your solution, and the output of your program is sent to interactor’s input. In the other words, your solution and the interactor exchange the data and my decide what to print based on the "history of communication".

When you write the solution for the interactive problem it is important to keep in mind that if you output some data it is possible that this data is first placed to some internal buffer and may be not directly transferred to the interactor. In order to avoid such situation you have to use special flush operation each time you output some data. There are these flush operations in standard libraries of almost all languages. For example, in C++ you may use fflush(stdout) or cout << flush (it depends on what do you use for output data — scanf/printf or cout). In Java you can use method flush for output stream, for example, System.out.flush(). In Python you can use stdout.flush(). In Pascal you can use flush(output).

There are some features for interactive problems:

• Input/output in interactive problems works much slower than in usual problems — try to use scanf/printf instead of cin/cout in С++, BufferedReader/PrintWriter in Java and etc.
• Usually, manual testing of the solutions for interactive problems much more difficult, because the participant needed to be in the role of interactor during testing.
• The "Custom invocation" tab does not know about the interactor for the problem, so you can't fully testing your solution.
• Sometimes on the Codeforces Rounds interactive problems will use. In this case the fromat of tests for hacks will described in the statements of the problems.
• Output endl in cout in C++ performs flush operation automatically.

Let's consider the following interactive problem. You can try to solve it here http://codeforces.com/gym/101021/problem/A

## Problem

Guess the number

##### Statement

In this problem there is some hidden number and you have to interactively guess it. The hidden number is always an integer from 1 and to 1 000 000.

You can make queries to the testing system. Each query is one integer from 1 to 1 000 000. Flush output stream after printing each query. There are two different responses testing program can provide:

• string < (without quotes), if the hidden number is less than the integer in your query;
• string >= (without quotes), if the hidden number is greater than or equal to the integer in your query.

When your program wants to guess the hidden number, print string ! x, where x is the answer, and terminate your program immediately after flushing the output stream.

Your program is allowed to make no more than 25 queries (not including printing the answer) to the testing system.

##### Input

Use standard input to read the responses to the queries.

The input will contain responses to your queries — strings < and >=. The i-th string is a response to the i-th your query. When your program will guess the number print ! x, where x is the answer and terminate your program.

The testing system will allow you to read the response on the query only after your program print the query for the system and perform flush operation.

##### Output

To make the queries your program must use standard output.

Your program must print the queries — integer numbers xi (1 ≤ xi ≤ 106), one query per line. After printing each line your program must perform operation flush.

Each of the values xi mean the query to the testing system. The response to the query will be given in the input file after you flush output. In case your program guessed the number x, print string ! x, where x — is the answer, and terminate your program.

## Solution

Of course, this problem can be solved using binary search. Here is an example of the C++ solution:

#include <cstdio>
#include <cstring>

using namespace std;

int main() {
int l = 1, r = 1000000;
while (l != r) {
int mid = (l + r + 1) / 2;
printf("%d\n", mid);
fflush(stdout);

char response[3];
scanf("%s", response);
if (strcmp(response, "<") == 0)
r = mid - 1;
else
l = mid;
}

printf("! %d\n", l);
fflush(stdout);
}


We wish you accepted solutions. Once again, you can solve simple interactive problem here http://codeforces.com/gym/101021/problem/A

•
• +293
•

 » 3 years ago, # |   +20 can i use "ios::sync_with_stdio(false)" with cin/cout instead of scanf/printf in c++ or it's Better to Use scanf/printf ?
•  » » 3 years ago, # ^ |   +19 You can use cin/cout but still you should flush the output.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +2 Okay , Thank You Errichto
•  » » » 7 months ago, # ^ |   -8 It is said that it's slow, may it get TLE??
•  » » 3 years ago, # ^ | ← Rev. 2 →   +19 "endl" flushes automatically for you. cout<
•  » » » 3 years ago, # ^ |   +9 I suspect that if you don't write cin.tie(0), cin >> x also flushes automatically.
•  » » » » 2 years ago, # ^ |   +8 Do we need to flush cin?
•  » » » » » 2 years ago, # ^ |   +5 No, we need to flush cout only because the output is buffered and not actually printed sometimes.So, you do NOT need to flush cin
 » 3 years ago, # |   +5 how would you test these kinds of problems on your local computer?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 You can take a solution from the blog above and run it on your computer. The program will ask you queries and you should print responses < and >=.
•  » » » 3 years ago, # ^ |   0 oh I was looking for a faster automated method like ./a.outoutput.txt but that method is also ok.
 » 3 years ago, # |   0 Here is another interactive problem to try from (2012-2013 ACM-ICPC, NEERC, Moscow Subregional Contest):J. Just Another Disney Problem
 » 3 years ago, # |   0 You don't need "return 0;" for interactive problems?
•  » » 3 years ago, # ^ |   +16 In C++ main can be left without a return value at which point it defaults to returning 0.
•  » » » 3 years ago, # ^ |   0 I see. Thanks.
 » 3 years ago, # |   0 In hacks, how would the "output" of model/participant solution be shown? For some problem like this or this it seems we can see the whole process (look at some submissions), but the example problem from this post just shows the hidden number and the number of queries.
•  » » 3 years ago, # ^ |   +16 In the problem above (from this blog) the input for hacking would be the hidden number. In the round today, the information about hacking will be in the statement.
 » 3 years ago, # |   +3 It is very funny :D using binary search (the exact code of blog) with L = 1, R = 1e6+6 got wrong answer on test 6, but L = 1, R = 1e6 got Accepted!L = 1, R = 1e6+6: submission L = 1, R = 1e6: submission
•  » » 3 years ago, # ^ |   -8
•  » » 3 years ago, # ^ |   +8 Your program must print the queries — integer numbers xi (1 ≤ xi ≤ 10**6), one query per line.
•  » » 3 years ago, # ^ |   +10 Range of the input numbers is 1 to 1000000. That's why.
•  » » 3 years ago, # ^ |   0 That's because, 1e6+6 = (1e6)+6 = 1000006, not 1000000.
•  » » » 3 years ago, # ^ |   0 Why the downvotes?! If I'm wrong, do let me know.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Why I always can't see other's people submission by links like this http://codeforces.com/gym/101021/submission/18299998?
 » 3 years ago, # |   0 Here's another interactive problem. https://www.codechef.com/MAY16/problems/CHBLLS Anyone interested may take a look. My first interactive problem. I enjoyed the solution but didn't like that flushing part somehow :v Even if someone understands the logic, he has the chance to get a wrong verdict for the syntax.
 » 3 years ago, # | ← Rev. 2 →   0 My solution gets Idleness Limit Exceeded, even though I flush the buffer. Where do you think the problem is?18300219UPD: I've found the error! I should've printed one query per line.
 » 3 years ago, # | ← Rev. 2 →   0 hello, any one could tell me why this code gets TLE on test 2 whilst the same code in the blog gets AC which just differs in reckoning of mid, while I make r equals to 1e6+1 to evade that . any help would be highly appreciated int main() { int l = 1, r = 1e6+1; while(l < r){ int mid = (l+r)>>1; printf("%d\n",mid); fflush(stdout); char s[10]; scanf("%s",s); if(s[0]=='<') r = mid-1; else l = mid; } printf("! %d\n",l); fflush(stdout); return 0; } 
•  » » 3 years ago, # ^ |   +4 if l+1==r then your code runs forever.
•  » » » 3 years ago, # ^ |   0 If response were <= and > then mid=(l+r)/2 would work, right?
•  » » » » 2 years ago, # ^ |   0 It doesnt work beacuse of overflow. For instance if l=9 and r=10, (l+r)/2 will be 9 So mid doesnt change and l
•  » » 3 years ago, # ^ |   0 mid = (l+r+1)>>1
 » 3 years ago, # |   +69 why in this round ? you could use it in the educational first
 » 3 years ago, # |   0 Getting Idleness limit exceeded on test 1 in the first given problem. Here is my code. How can I fix it?
•  » » 3 years ago, # ^ |   +10 Read the task.
•  » » 3 years ago, # ^ |   0 Read the example code by Mike.
•  » » 3 years ago, # ^ |   0 ohh... I missed the example code. I am not used to this system. why this???
•  » » » 3 years ago, # ^ |   +3 Because it is very interesting and new for CF community
•  » » » » 3 years ago, # ^ |   0 please clear me 2 things. the given output is my input I need to use flash after every output. right? anything else?I have not idea about it. so please clear me.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Your program must send requests(input) to interactor,and interactor answers for request(output). If you test your code local, you should answer for request by using input.
•  » » » » » » 3 years ago, # ^ |   0 Oww.. thats interesting. sounds different. Thank you for explanation :)
•  » » » » » 3 years ago, # ^ |   0 You should use flush for correct interactive work.
 » 3 years ago, # |   +6 An Educational Round on this type of Problems would be better to understand the Submit / Hacking System .
 » 3 years ago, # |   +37 Mike don't get me wrong it sounds like this contest is gonna be brilliant but couldn't you post this earlier like a day or two earlier.or you could have tried it with educational rounds first like Deathly_Hallows said.Nevertheless I wish happy coding for everyone and high ratings good luck.:)
•  » » 3 years ago, # ^ |   +14 hi.. actually users facing interacting problems for the first time may experience significant drop in ratings.. so please make the announcements a bit before or we can have a testing round or educational for such purposes.. its nice that codeforces comes up with newer challenges.. thanks.. :)
 » 3 years ago, # | ← Rev. 2 →   +6 what will be the verdict for making more than 25 queries???!!
•  » » 3 years ago, # ^ |   +10 should be WA but you can check it.
•  » » 3 years ago, # ^ |   +10 Wrong Answer
 » 3 years ago, # |   +8 The example section looks a bit misleading: why ">=" / "<" are output instead of input? And I think it'd be better to arrange them chronologically, like this.
•  » » 3 years ago, # ^ |   +5 TL;DR — you are right, but it isn't important, right?You are right that it's misleading and should be other way around. It's my mistake. It will be displayed correctly in the round (with ">=" as input in this case).
•  » » » 3 years ago, # ^ |   +10 This is not TL;DR, it's FL;DU (Foreign language; didn't understand) :D
•  » » » » 3 years ago, # ^ |   0 Actually I don't get your comment ;pDid I write something not clear? If yes then I will rewrite it.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +20 The link which cgy4ever provided is FL;DU not TL;DR :D
•  » » 3 years ago, # ^ |   +3 So, what do you think about the format we used? There were tables in the Notes section. Any better solution?
•  » » » 3 years ago, # ^ |   0 It looks perfect. (The only issue may be that we can't copy-paste since it is a picture, but for that specific problem it is ok.)
•  » » » » 3 years ago, # ^ |   0 Huh. I've just realized that it's impossible to copy-paste. Strange — because it's not a picture, it's an HTML table.
 » 3 years ago, # |   0 Why's that "r = mid - 1" and "l = mid" gets AC and "r = mid - 1" and "l = mid + 1" gets WA? Can someone explain it?
•  » » 3 years ago, # ^ |   0 for mid if response is < then hidden number is less than mid so r = mid - 1 if response is >= then hidden number is mid or greater than mid so l = mid
•  » » » 3 years ago, # ^ |   0 Got it, thank you
•  » » 3 years ago, # ^ |   0 because on doing l==mid+1 , you are ignoring the current mid value which is giving boolean value 1 for objective function.
•  » » 3 years ago, # ^ |   0 You can do l = mid + 1 and ans = mid. And print ans in the end.
 » 3 years ago, # |   +9 I recommend not to penalize errors on 1 test for the interactive problem as many people might get confused initially.
•  » » 3 years ago, # ^ |   +34 Errors on 1st test are not penalized even for other problems
•  » » » 3 years ago, # ^ |   0 Nice to know, thanks.
 » 3 years ago, # |   0 I guess Input and Output were mutually misplaced?I need to Input '<=' and '>' and let computer to guess and Output the number?
•  » » 3 years ago, # ^ |   0 Input and Output are displayed swapped in this problem, sorry. It will be displayed correctly during the round.
 » 3 years ago, # |   0 All the problems will be "Interactive"? All 5 from today's contest?
•  » » 3 years ago, # ^ |   +3 No.
•  » » » 3 years ago, # ^ |   0 thanks
•  » » 3 years ago, # ^ |   +1 only 1 out of 5 !
•  » » » 3 years ago, # ^ |   0 thanks
•  » » 3 years ago, # ^ |   +1 I don't think so because it's not quite easy to solve an interactive problem especially with the difficulty of A and B div 2.
 » 3 years ago, # |   +4 Would it be possible to hack an interactive problem?
•  » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ |   +3 Sometimes on the Codeforces Rounds interactive problems will use. In this case the fromat of tests for hacks will described in the statements of the problems.
 » 3 years ago, # |   0 All the problems will be interactive?
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 If you have a question{ for (int i = 0; i < 100; i++) { reread the blog; reread all comments; if you have found the answer goodbye; } ask your question in comments; goodbye;}
 » 3 years ago, # |   0 Doesn’t std::endl flush the output buffer in C++ and doesn’t std::cin flush it as well? I’m pretty much surprised that 18314320 fails while 18315037 gets accepted.
•  » » 3 years ago, # ^ |   +13 You have different loop condition, lol
•  » » » 3 years ago, # ^ |   0 Oops, sorry :DThat’s what happens when one doesn’t write contests for a long time!
•  » » 3 years ago, # ^ |   0 Thanks, but I made mistake in the understanding of the task.I should to go on a new line after flush.I mean: cout<
•  » » » 3 years ago, # ^ |   +8 Actually, flush before Something just flushes an empty buffer, so it can be omitted.
 » 3 years ago, # |   +31 It's very important to specify whether the system actually "hides" a fixed integer before interaction starts or the interactor can change the number (or any other information, in general) during testing in a way consistent with previous answers. In the former case, some probabilistic solutions to some problems can pass. In the latter, they won't.As far as I can see, the only place in the example problem which mentions it is "it's fine to guess — if you guess correctly".
•  » » 3 years ago, # ^ |   0 The second sample clearly shows it. But yes, I agree that it should also be written in the statement. We adjusted this problem in hurry and it isn't perfect (we decided to show the guide in the day of the contest).Also, in some problems the system may be smarter/malicious and answer to more likely fail a participant. But we didn't want it in "prime 100" problem.
 » 3 years ago, # |   +13 Maybe there should be another status for protocol failure (e.g. query limit exceeded)? Even Runtime Error would be much better than WA.
•  » » 3 years ago, # ^ |   +9 I don't see a reason. In standard problems there shouldn't be "WA because your answer is too small" or "WA because an edge you printed doesn't exist". So, why should we get extra info here?
•  » » » 3 years ago, # ^ |   +3 But there is in fact presentation error if you violate output protocol (e.g. give less integers than needed)I'd really like to see query limit as PE than as WA, because you're actually violating protocol by printing more queries than it was possible.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Are you sure about PE? I thought that there is no PE in CF rounds — source.And I don't think it's possible to create some exact rules what is PE and what is WA. For example, a participant should print the number of vertices satisfying something — then what if he/she prints  - 1 or n + 1? Should it be WA or PE? It's only an example.
 » 3 years ago, # | ← Rev. 2 →   +1 Please Help Me Out .. I am trying to solve the Interactive Problem given in the above Link as there may be an Interactive Problem in today's Round . I have submitted a Code for practice several times. But Its showing WA at Test 1 . Don't know why .Here is My code: http://pastebin.ubuntu.com/23172422/It'd be very helpful if you please point me out the erroneous point of my Code . Thanks in Advance .
•  » » 3 years ago, # ^ |   0 Just Got AC .
 » 3 years ago, # | ← Rev. 2 →   -13 in the name of allah, most mercifullhimy question about question A that exist in blog and my logic is truei don't know why this code doesn't work.
 » 3 years ago, # |   0 Is writing fflush(stdout); at the end of main() necessary or redundant?
•  » » 3 years ago, # ^ |   0 You need to use 'flush' operation only after every print.
•  » » » 3 years ago, # ^ |   +8 I meant, what about the last print. eg: in the code given in the blog,printf("! %d\n", l); fflush(stdout);is fflush(stdout) needed here?
•  » » » » 3 years ago, # ^ |   -11 Yes, you need.
•  » » » » » 3 years ago, # ^ |   0 Actually not. At the shutdown of the program stdout is automatically flushed. Though it is a good practise in an interactive problem to flush after any print because it doesn't make anything worse but prevents you from forgetting about some important flush.More details.
 » 2 years ago, # |   0 I don't understand the interactive process clearly. Can someone explain who gives the input, who gives output, who writes the code....it seems confusing to me. Thanks!
 » 23 months ago, # |   0 In Python 3, print() is a function and it has an optional parameter "flush" with a default value false. So you can just set it to true when needed to flush the output stream. print("blah blah", flush = True)
•  » » 8 months ago, # ^ |   0 4076985440769788In real test, the print works even with "flush = False",I don't know why..
 » 22 months ago, # |   0 Any idea what this error meanswrong output format Unexpected end of file - token expectedsubmission
•  » » 22 months ago, # ^ |   0 You are outputting nothing.
•  » » » 22 months ago, # ^ | ← Rev. 3 →   0 Yeah, I just realized my code skips all ifs. I am new to this type of problem.
 » 18 months ago, # |   0 Even this workscout.flush();
 » 16 months ago, # | ← Rev. 2 →   -10 Can some one explain why this int mid = (r+1+l)/2; (work) int mid = l+(r-l)/2; (not work) 
•  » » 16 months ago, # ^ |   +9 It isn't equivalent. One rounds up, the other rounds down. Consider what happens when l + 1 = r.
 » 9 months ago, # | ← Rev. 2 →   0 Input have t tests with structure : - n - a1 a2 ... an For each test, user write on output x1,x2,...,xn, then judge write y1,y2,...,yn (this must be read by user) How can do this?
 » 8 months ago, # | ← Rev. 2 →   0 In the just concluded contest, I couldn't accept the input in python 2.My simple solution: n, m = map(int, raw_input().split()) print 1 raw_input() `The verdict: Idleness limit exceeded.Any help is appreciated.
•  » » 8 months ago, # ^ | ← Rev. 3 →   +3 have you tried reading the post you comment (or problem description)? You need to flush each time you print something. 40814436
•  » » » 8 months ago, # ^ |   0 Yes sir, I've got my answer. Thanks a lot.
 » 4 months ago, # |   -16 What are the changes if conditions are "<=" and ">" instead of "<" and ">=" ?
»
3 months ago, # |
0

Why is this solution wrong?

/* _______ _______ _______ _______ _______ _______ ( ____ ( ____ ( )( ____ )( ____ ( ____ ) | ( \/| ( \/| () () || ( )|| ( \/| ( )| | (_____ | (__ | || || || (____)|| (__ | (____)| (_____ )| ) | |(_)| || _____)| ) | __) ) || ( | | | || ( | ( | (\ (
/_
) || (
__/| ) ( || ) | (____/| ) \ __ _______)(_______/|/ ||/ (_______/|/ __/

_______ _________ ______ _______ _ _________ _______ ( ____ __ /( __ \ ( ____ ( \ __ /( ____ \ | ( \/ ) ( | ( \ )| ( \/| ( ) ( | ( \/ | ( | | | | ) || ( | | | | | (_____ | ) | | | | | || ) | | | | (_ ) | ( | | | | ) || ( | | | | ) | | ) ) (| (__/ )| (____/| (____/___) (___/____) | |/ _______/(______/ (_______/(_______/_______/_______)

*/

# include <bits/stdc++.h>

using namespace std;

# define S second

int main() { int repeat=25; string tans; int start=0; int end=1000000; int mid=(start+end)/2; cout << mid << "\n"; cin >> tans; map<int,int> v; while(repeat--){ if(tans=="<"){ v[mid]=10; if(v[mid]==10 && v[mid+1]==11){ cout << "! " << mid+1 << endl; fflush(stdout); return 0; } start=mid; mid=(start+end)/2; cout << mid << "\n"; fflush(stdout); cin >> tans; } else if(tans==">="){ v[mid]=11; if(v[mid]==11 && v[mid-1]==10){ cout << "! " << mid << endl; fflush(stdout); return 0; } end=mid; mid=(start+end)/2; cout << mid << "\n"; fflush(stdout); cin >> tans; } } return 0; }

// >=

 » 3 months ago, # |   0 Why is this solution wrong?http://codeforces.com/gym/101021/submission/47026197
•  » » 3 months ago, # ^ |   0 you messed up with "<" and ">="
•  » » » 3 months ago, # ^ |   0 Yes. I realized. Thanks. But this still won't work due to some other reason I don't understand.
 » 3 months ago, # | ← Rev. 2 →   -8 Can someone explain why "L" is printed and not MID? And also when to print L , MID and R in binary search problems?
•  » » 3 months ago, # ^ |   -8 Errichto can you please explain this?
•  » » 3 months ago, # ^ |   0 They are all equal at the end.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Are mid and l equal in all cases in this problem?
•  » » » » 3 months ago, # ^ |   0 They are.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Ok I understood , thank you so much.