chrs's blog

Can someone explain this question to me? From yesterday's contest D.rocket
By chrs, history, 8 years ago, In English

Hi friends,

I am so lost and frustrated about this problem that took place in yesterday's contest. http://mirror.codeforces.com/contest/1011/problem/D

Here is the solution I am looking at http://mirror.codeforces.com/contest/1011/submission/40824907

And here is my code, clearly showing that my understanding of the problem is incorrect http://mirror.codeforces.com/contest/1011/submission/40855182

The input in the problem statement clearly shows

5 2 1 -1 -1 1 0

But the actual input is like this:

5 2 3 1 0

I understand what the question wants me to do. But for the life of me, I cannot figure out how the solution of this problem works and why is the input in the problem and the actual input different?

The thing I am most stuck on are 3 things

Line 3: ask() function and what it's suppose to do

Line 22: for(int i=1;i<=n;i++)op[i]=ask(1); //what this op[] array is

Line 25: Why do we need a binary search for this question

line 27: if(ask(mid)^op[k%n+1])r=mid; // what is this trying to accomplish

Can someone explain this question/solution to me? I really appreciate any help!

Thank you!

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I mean, it doesn't seem like your solution is doing anything, or printing out any output... This is an interactive problem, which means the input changes depending on what you output. The input given in the sample statement is an example back and forth between a user's solution and the judge. The input given in the feedback is an input to initialize the judge, and is based off the "hacking"section of the problem statement.

→ Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    In the editorial that was posted here http://mirror.codeforces.com/blog/entry/60851

    The author says "First we learn the sequence p[]. For this print the query "1" n times."

    Why do we have to do this? If the sequence of P is already given, why can I just read it directly into a vector?

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Read the problem statement carefully: "The first line contains two integers m and n ( 1 ≤ m ≤ 10 9 , 1 ≤ n ≤ 30) — the maximum distance to Mars and the number of elements in the sequence p."

      All the initial input contains is two integers, M and N.

      All the rest of the input comes in an interactive form.

      You might want to try out the problem here to understand what's going on: https://mirror.codeforces.com/blog/entry/45307

      → Reply
      • »
        »
        »
        »
        8 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I checked out the question you sent.

        Same thing, I cannot figure out how to reproduce the output with the given input... zzzzzzzzzzzz

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Do you understand the concept of an interactive problem? You might get some initial input, then you output something, then the judge outputs something in response to your output, then you read the judge's output, etc.

          → Reply