Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

MikeMirzayanov's blog

By MikeMirzayanov, 3 years ago, translation, In English,

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

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

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

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, # ^ |
      Vote: I like it +19 Vote: I do not like it

    You can use cin/cout but still you should flush the output.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    "endl" flushes automatically for you. cout<<endl is more or less the same as cout<<"\n", fflush(stdout) (already written by Mike, but I think that needs emphasizing).

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

      I suspect that if you don't write cin.tie(0), cin >> x also flushes automatically.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Do we need to flush cin?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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, # |
  Vote: I like it +5 Vote: I do not like it

how would you test these kinds of problems on your local computer?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh I was looking for a faster automated method like ./a.out<input.txt>output.txt but that method is also ok.

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

Here is another interactive problem to try from (2012-2013 ACM-ICPC, NEERC, Moscow Subregional Contest):

J. Just Another Disney Problem

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

You don't need "return 0;" for interactive problems?

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

    In C++ main can be left without a return value at which point it defaults to returning 0.

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

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, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

My solution gets Idleness Limit Exceeded, even though I flush the buffer. Where do you think the problem is?

18300219

UPD: I've found the error! I should've printed one query per line.

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

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, # ^ |
      Vote: I like it +4 Vote: I do not like it

    if l+1==r then your code runs forever.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If response were <= and > then mid=(l+r)/2 would work, right?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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<r is true forever.

        This is why the above code does (l+r+1)/2

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mid = (l+r+1)>>1

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

why in this round ? you could use it in the educational first

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

Getting Idleness limit exceeded on test 1 in the first given problem. Here is my code. How can I fix it?

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

    Read the task.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the example code by Mike.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ohh... I missed the example code. I am not used to this system. why this???

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

      Because it is very interesting and new for CF community

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        please clear me 2 things.

        1. the given output is my input

        2. 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   Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oww.. thats interesting. sounds different. Thank you for explanation :)

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You should use flush for correct interactive work.

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

An Educational Round on this type of Problems would be better to understand the Submit / Hacking System .

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

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, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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   Vote: I like it +6 Vote: I do not like it

what will be the verdict for making more than 25 queries???!!

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

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # ^ |
        Vote: I like it +10 Vote: I do not like it

      This is not TL;DR, it's FL;DU (Foreign language; didn't understand) :D

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually I don't get your comment ;p

        Did I write something not clear? If yes then I will rewrite it.

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

    So, what do you think about the format we used? There were tables in the Notes section. Any better solution?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do l = mid + 1 and ans = mid. And print ans in the end.

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

I recommend not to penalize errors on 1 test for the interactive problem as many people might get confused initially.

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

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Input and Output are displayed swapped in this problem, sorry. It will be displayed correctly during the round.

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

All the problems will be "Interactive"? All 5 from today's contest?

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

Would it be possible to hack an interactive problem?

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

All the problems will be interactive?

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

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You have different loop condition, lol

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops, sorry :D

      That’s what happens when one doesn’t write contests for a long time!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, but I made mistake in the understanding of the task.

    I should to go on a new line after flush.

    I mean: cout<<flush<<Something<<endl;

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

      Actually, flush before Something just flushes an empty buffer, so it can be omitted.

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

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +13 Vote: I do not like it

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, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        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.

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

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 .

Problem: http://codeforces.com/gym/101021/problem/A

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 .

»
2 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

in the name of allah, most mercifull

hi

my question about question A that exist in blog and my logic is true

i don't know why this code doesn't work.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is writing fflush(stdout); at the end of main() necessary or redundant?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to use 'flush' operation only after every print.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Yes, you need.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea what this error means

wrong output format Unexpected end of file - token expected

submission

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are outputting nothing.

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Yeah, I just realized my code skips all ifs. I am new to this type of problem.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Even this works

cout.flush();

»
12 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Can some one explain why this

int mid = (r+1+l)/2;  (work)
int mid = l+(r-l)/2;  (not work)
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    It isn't equivalent. One rounds up, the other rounds down. Consider what happens when l + 1 = r.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In the just concluded contest, I couldn't accept the input in python 2.

Problem: https://codeforces.com/contest/1011/problem/D

My simple solution:

n, m = map(int, raw_input().split())
print 1
raw_input()

The verdict: Idleness limit exceeded.

Any help is appreciated.

»
4 days ago, # |
  Vote: I like it -16 Vote: I do not like it

What are the changes if conditions are "<=" and ">" instead of "<" and ">=" ?