# Interactive MST solution codechef

## Interactive MST solution codechef

There is a hidden undirected connected graph GG with nn nodes and mm edges numbered 0,1,m10,1,…m−1, and a hidden permutation p0,p1,,pm1p0,p1,…,pm−1 of edges. The graph doesn’t contain any self loops or multiple edges.

You only know the value of nn and mm. You can ask queries. In one query, you give the judge a vector w=[w0,w1,,wm1]w=[w0,w1,…,wm−1] of size mm consisting of integers in the range [1,m][1,m]. The judge returns n1n−1 integers e0,e1,,en2e0,e1,…,en−2, such that the edges numbered e0,e1,,en2e0,e1,…,en−2 form a minimum spanning tree of the graph, if the edge numbered pipi had a weight wiwi for each i=0,1,m1i=0,1,…m−1. Note that the judge can print the edges in any order, and if there are multiple minimum spanning trees, the judge may print any one of them.

You need to find the hidden permutation in at most mm queries, or claim that it can’t be found uniquely no matter how many queries you’re allowed to make.

We have a proof that if it’s possible to find the permutation in finitely many queries, then it is possible in at most mm queries.

### Interaction Interactive MST solution codechef

• First, you should read a line containing the subtask number (1122, or 33).
• Then, read the number of test cases.
• For each test case, first read the values of nn and mm.
• To make a query, you should output a question mark, followed by mm space-separated integers denoting the weights: ?w0w1wm1?w0w1…wm−1.
• If the query format is incorrect, or if some weight exceeds mm, or the number of queries (including this query) has exceeded mm, the judge prints a single integer 1−1 and quits with a wrong answer verdict. In this case, you must also terminate your program.
• Otherwise, the judge prints n1n−1 space-separated integers : e0e1en2e0e1…en−2.
• If you have found the permutation pp, you should output an exclamation mark followed by mm space-separated integers : !p0p1pm1!p0p1…pm−1. Else, if you have reached the conclusion that the hidden permutation pp can not be found, print exclamation mark followed by 1−1 : !1!−1.
• If your answer is incorrect, the judge prints1−1 and exits. In this case, you must terminate your program as well. Else, the judge prints 11, and you should move to the next testcase(if any).

Note that whenever the judge prints 1−1, you should immediately terminate your program to receive a Wrong Answer verdict; otherwise, you may receive any verdict. Don’t forget to flush the output after printing each line!

### Constraints Interactive MST solution codechef

• 1m10001≤m≤1000
• The sum of mm over all test cases doesn’t exceed 10001000.

### Subtasks Interactive MST solution codechef

• Subtask 1(8 points) : GG is a tree
• Subtask 2(21 points) : GG is a cycle
• Subtask 3(71 points) : No additional constraints.

### Example Interactive MST solution codechef

In this example, the hidden graph has edges (0,1)(0,1)(1,2)(1,2) and (2,0)(2,0) numbered 0,1,20,1,2 respectively, in all testcases. In the first testcase, p=[2,0,1]p=[2,0,1] and in the second, p=[0,1,2]p=[0,1,2]. The third testcase shouldn’t be read as the judge prints 1−1 in testcase 22.

You                     Grader
2           # Subtask 2
3           # 3 testcases
3 3         # n = 3, m = 3
? 2 3 2
2 1         # The permuted weights would be [3, 2, 2]
? 2 3 2
1 2         # For the  same vector w, judge's output can be different.
! 2 0 1
1           # Correct output. Note that this is merely a lucky guess

3 3         # Next testcase, n = 3, m = 3
? 2 2 1
0 2
! 1 0 2
-1          # Incorrect output! Judge exits now.
You should also
terminate here.

# SOLUTION

#### What’s in it for you?

The idea behind these programming contests is that we want you to learn while competing. Also we believe that it is alright to refer to tutorials, books and other materials, learn a concept and then apply the same to solve a problem during a contest. But it is not alright to copy other people’s solutions or seek other people’s help to solve a problem without understanding it.

The dividing line may seem to be thin but it can be captured by the spirit of learning. If whatever you are doing is making you learn while you do so, we tend to believe that it is alright. Our sole intention lies in making our users learn new concepts while competing. However, all the participants are expected to abide to

#### What’s new in CodeChef?

You may now play with our new groups & LaTex feature on discuss.

• Please do not discuss strategy, suggestions or tips in the comments during a live contest. Posting questions clarifying the problem statement is ok. If you are unsure, email us at [email protected] .
• Discussing CodeChef’s problems or any aspect of problem, on any other platform on web, on identification, could lead to disabling of respective account and banning from the community.
• You can also send in your queries in an email to [email protected], during the contest.
• You will receive one point for solving a problem (passing all test cases – no partial credit), regardless of the level of difficulty of that problem.
• Users are ranked according to the most problems solved. Ties will be broken by the total time for each user in ascending order of time.
• The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the first accepted run plus 10 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved.
• You shall not possess more than one account on CodeChef. If you have, then do let us know, so that we can deactivate the insignificant one. If you do not report it and we come to know about it, we may deactivate both the accounts permanently.
• If anyone is using code from some other source in his submission, he should provide proper attribution. Failing this, it may be considered plagiarism and the submission will be subject to disqualification.
• The number of submissions that one can make during the contest on a single problem will be limited to 500.
• Residents of the following countries and territories are not eligible to win cash prizes/laddus/goodies due to legal restrictions: Albania, The Bahamas, Barbados, Botswana, Cambodia, Crimea region of Russia, Cuba, Ghana, Iceland, Iran, Jamaica, Mauritius, Mongolia, Myanmar, Nicaragua, North Korea, Pakistan, Panama, Sudan, Syria, Uganda, Yemen, Zimbabwe.

Note: You can now “Code, Compile, and Run” your codes on our Online IDE.

However, if you are using any other online development environment, make sure that other contestants don’t have access to your code. As a contestant, you are responsible for making sure others don’t access the code that you submit. If you use Ideone, make sure to mark your submission “private” (not secret)”.