Interactive Equivalency solution codechef
Two arraysand of size are equivalent if for every , if and only if . For example, , , are equivalent, while , are not.
There is a hidden array ofintegers, where the elements are numbered from , , \dots, . Your task is to guess any array which is equivalent to the hidden array by asking the following query at most times. The elements of the guessed array must be within the range .
In each query, you give a subset of indicesin the array i.e some subset of and the judge returns the frequency of most frequent element among . Note that the indices must be distinct and the order doesn’t matter.
For example, consider the array. Interactive Equivalency solution codechef
- The ouput of query is . ( occurs maximum number of times i.e times)
- Ouput of query is . (Both and occur times)
First, you should read the number of test cases.
For each test case, you should read two integersand .
Then you may ask questions:
- Output followed by an integer denoting the number of elements in subset followed by the indices .
- Read an integer 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 characterfollowed by space-separated integers denoting the array . 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
- For the given constraints, it is guaranteed that the answer can be found in the given number of queries.
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= .
- We ask a query for subset . The grader responds with since both and occur time.
- Then we query for . The grader responds with because frequency of is .
- Then we query for . Grader responds with since both elements are distinct.
- Lastly we query for and the grader responds with i.e frequency of