MikeMirzayanov's blog

By MikeMirzayanov, 18 months 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  

»
18 months 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 ?

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

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

  • »
    »
    18 months 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).

    • »
      »
      »
      18 months 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.

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

        Do we need to flush cin?

        • »
          »
          »
          »
          »
          12 months 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

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

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

  • »
    »
    18 months 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 >=.

    • »
      »
      »
      18 months 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.

»
18 months 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

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

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

  • »
    »
    18 months 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.

»
18 months 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.

  • »
    »
    18 months 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.

»
18 months 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

»
18 months 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.

»
18 months 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.

»
18 months 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; }
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        12 months 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

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

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

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

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

»
18 months 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?

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

    Read the task.

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

    Read the example code by Mike.

  • »
    »
    18 months 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???

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

      Because it is very interesting and new for CF community

      • »
        »
        »
        »
        18 months 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.

        • »
          »
          »
          »
          »
          18 months 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.

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

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

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

          You should use flush for correct interactive work.

»
18 months 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 .

»
18 months 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.

:)

  • »
    »
    18 months 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.. :)

»
18 months 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???!!

»
18 months 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.

  • »
    »
    18 months 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).

    • »
      »
      »
      18 months 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

      • »
        »
        »
        »
        18 months 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.

  • »
    »
    18 months 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?

    • »
      »
      »
      18 months 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.)

      • »
        »
        »
        »
        18 months 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.

»
18 months 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?

  • »
    »
    18 months 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

  • »
    »
    18 months 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.

  • »
    »
    18 months 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.

»
18 months 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.

»
18 months 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?

  • »
    »
    18 months 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.

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

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

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

Would it be possible to hack an interactive problem?

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

All the problems will be interactive?

»
18 months 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;

}

»
18 months 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.

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

    You have different loop condition, lol

    • »
      »
      »
      18 months 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!

  • »
    »
    18 months 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;

    • »
      »
      »
      18 months 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.

»
18 months 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".

  • »
    »
    18 months 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.

»
18 months 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.

  • »
    »
    18 months 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?

    • »
      »
      »
      18 months 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.

      • »
        »
        »
        »
        18 months 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.

»
15 months 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 .

»
15 months 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.

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

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

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

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

    • »
      »
      »
      15 months 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?

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

        Yes, you need.

        • »
          »
          »
          »
          »
          15 months 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.

»
12 months 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!

»
7 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)

»
6 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

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

Even this works

cout.flush();

»
2 weeks 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)
  • »
    »
    2 weeks 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.