Interactive Equivalency solution codechef- Two arrays AA and BB of size NN are equivalent if for every (i,j)(i,j) (1≤i

Interactive Equivalency solution codechef

Two arrays AA and BB of size NN are equivalent if for every (i,j)(i,j) (1i<jN)(1≤i<j≤N)Bi=BjBi=Bj if and only if Ai=AjAi=Aj. For example, [1,2,2][1,2,2][10,11,11][10,11,11][5,1,1][5,1,1] are equivalent, while [1,2,3,1][1,2,3,1][10,20,10,10][10,20,10,10] are not.

There is a hidden array of NN integers, where the elements are numbered from A1A1A2A2, \dots, ANAN. Your task is to guess any array which is equivalent to the hidden array by asking the following query at most QQ times. The elements of the guessed array must be within the range [1,109][1,109].

In each query, you give a subset of indices {i1,i2,,ik}{i1,i2,…,ik} in the array i.e some subset of {1,2,,N}{1,2,…,N} and the judge returns the frequency of most frequent element among {Ai1,Ai2,,Aik}{Ai1,Ai2,…,Aik}. Note that the indices must be distinct and the order doesn’t matter.

For example, consider the array [10,3,1,10,1,1,3][10,3,1,10,1,1,3]. Interactive Equivalency solution codechef

  • The ouput of query {2,3,4,7}{2,3,4,7} is 22. (33 occurs maximum number of times i.e 22 times)
  • Ouput of query {2,3,1,4,5}{2,3,1,4,5} is 22. (Both 11 and 1010 occur 22 times)

Interaction

First, you should read the number of test cases TT.

For each test case, you should read two integers NN and QQ.

Then you may ask questions:

  • Output ?? followed by an integer denoting the number of elements in subset followed by the indices ?ki1i2ik?ki1i2…ik.
  • Read an integer xx denoting the answer to your query.
  • If the query was invalid or you have exceeded the query limit, judge prints '-1' and exits with wrong answer verdict. In this case, you must also terminate your program.

When you have determined the answer, print the character !! followed by NN space-separated integers denoting the array !A1A2AN!A1A2…AN. Note that this does not count towards a query.

Now you must read an integer denoting that your answer is correct or not.

  • If your answer is correct, judge prints '1'. In this case, you should continue solving the remaining test cases.
  • If your answer is incorrect, judge prints '-1' and exits with wrong answer verdict. You must also terminate your program in this case otherwise, you may receive any verdict.

Constraints Interactive Equivalency solution codechef

  • 1T101≤T≤10
  • 2N1002≤N≤100
  • Q=6NQ=6N
  • For the given constraints, it is guaranteed that the answer can be found in the given number of queries.

Sample interaction

You       Grader
          1
          3 18
? 2 1 2
          1
? 3 1 2 3 
          2
? 2 2 3
          1
? 2 1 3
          2
! 3 4 3
          1

Explanation Interactive Equivalency solution codechef

The hidden array was AA = [10,20,10][10,20,10].

  • We ask a query for subset {1,2}{1,2}. The grader responds with 11 since both 1010 and 2020 occur 11 time.
  • Then we query for {1,2,3}{1,2,3}. The grader responds with 22 because frequency of 1010 is 22.
  • Then we query for {2,3}{2,3}. Grader responds with 11 since both elements are distinct.
  • Lastly we query for {1,3}{1,3} and the grader responds with 22 i.e frequency of 1010
  • For Solution

    Click Here!

Leave a Reply

Your email address will not be published. Required fields are marked *

*