roycf123's blog

How to solve problems involving interactive tasks?
By roycf123, history, 2 years ago, In English

Hi Everyone,

Today I encountered a new type of problem which involved an interactive task. The problem link is as follows:

https://atcoder.jp/contests/abc269/tasks/abc269_e

These kind of problems are new to me. Nevertheless, I tried solving it and here is my solution (in C++):

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    ll t,i,n,a[4];
    cin>>n;
    while(true){
        for(i=0;i<4;i++) a[i]=(rand()%n)+1;
        cout<<"? "<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
        // cout<<flush;
        cin>>t;
        if(t==0){
            cout<<"! "<<a[1]<<" "<<a[3]<<endl;
            // cout<<flush;
            exit(0);
        }
        if(t==-1) exit(0);
    }
    return 0;
}

I received WA after submitting this solution. I also tried adding "cout<<flush" which are commented now, but that did not help.

Can someone pls help me to correct the solution?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Why do you think random numbers can be a solution?

There can be 1000 rows and 1000 columns, but you are only allowed to make 20 queries at most.

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

    I actually do not know, I interpreted the question as asking random numbers to the judge. Please let me know what it should be if it is wrong.

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

      What you have to do in this question is figure out the only square (i, j) where there is no rook in the i(th) row and j(th) column. You can do this by asking the judge queries about the board as described int he question. The difficulty of this question lies in the fact that you can only ask 20 queries. So you have to create a program that will manufacture queries which will give the maximum possible information no matter the result.

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

      I would actually suggest not doing interactive questions at the moment since they are quite tricky and have some nuances in implementation.

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

I haven't read this problem but generally binary search is useful in interactive problems

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

Interactive Problems: Guide for Participants

→ Reply