monopoly2

After you helped Deni to make the perfect playing map for monopoly in 2021, she needs your help again! We recall that the playing map for monopoly consists of $N$ spaces (numbered from $1$ to $N$) and $M$ directed connections between them. Here $M=N-1$. The directed connections fulfill the following conditions - there isn’t a connection from a space to itself and there aren’t different connections between the same pair of spaces. Also the connections have the property that every space is reachable from space $1$.

Definition: Let us have a permutation of the numbers from $1$ to $N$. We call the permutation an appropriate ordering of the spaces if the following condition holds - for every connection from space $i$ to space $j$, $i$ has to be before $j$ in the permutation.

The problem for Deni is that she lost the perfect map for playing monopoly. Fortunately, her friend Bobi remembers the map but he decided to have some fun with her before letting her know the connections. Firstly, Bobi tells Deni that an appropriate ordering of the spaces is the sequence $1, 2, ..., N$. After that Bobi will answer some questions from Deni to help her find out what are the connections between the spaces. Each question will be about how appropriate is some permutation of the numbers from $1$ to $N$ (for more details see section ”Implementation details”). Our heroine requests your assistance to come up and implement a strategy with the fewest questions possible.

Task

Write the program monopoly2 that determines the unknown connections with the fewest possible questions to Bobi. It must have the function find_connections which will be compiled with the jury’s program (for the role of Bobi).

Implementation details

Your function find_connections must have the following format:

std::vector <std::pair <int, int> > find_connections (int N);

It will be called once by the jury’s program with one parameter - the number of spaces. The function should return a list of ordered pairs describing the found connections between the spaces. The order of the ordered pairs in the list doesn’t matter.

The function for asking questions to Bobi has the following format:

std::vector <bool> check (std::vector <int> p);

The parameter $p$ is the permutation of the numbers from $1$ to $N$ in the question. The result is a boolean vector $b$ of size $N$, where $b_i = 1 \ (0 \leq i < N)$ if and only if one of these holds:

• there is a connection from space $p_j$ to space $p_i$ with $i < j$;
• there is a space $p_j$ for which $b_j=1$ and you can walk along the connections from $p_j$ to $p_i$.

Note that the unambiguity of the values follows from the properties of the connections.

If the sequence is not a valid permutation of the numbers from $1$ to $N$, you will get Wrong answer for the test. The complexity of the function is $O(N)$. You can call this function at most $\frac{10^8}{N}$ times, otherwise you will get Wrong answer.

Your program monopoly2 must implement the function find_connections. It can also contain other code, functions, and global variables, but it must not contain the main function. Also, you should not read from the standard input or print to the standard output. Your program must include the header file monopoly2.h by instruction to the preprocessor:

#include "monopoly2.h"

Restrictions

• $1 \leq N \leq 1 \ 000$
• $M = N - 1$

Scoring

Each test receives a score that is a fractional number between $0$ and $1$ inclusive. If a test has a positive score, it is considered successful for your solution. A test has a positive score if you successfully find the connections between the spaces.

If $cnt$ is the number of calls to the function check for a particular test, then the score of the test is calculated in the following way:

• For all subtasks: if $cnt > \frac{10^8}{N}$, then the score is equal to $0$.
• Subtasks $0$, $1$, and $2$.
  • If $cnt \leq \frac{10^8}{N}$, then the score is equal to $1$.
• Subtask $3$.
  • If $cnt \leq 10 \ 000$, then the score is equal to $1$.
  • If $10 \ 000 < cnt \leq 15 \ 000$, then the score is equal to $min(\frac{1 \ 000}{cnt - 9 \ 000}, 1)$.
  • If $15 \ 000 < cnt \leq \frac{10^8}{N}$, then the score is equal to $0.1$.
• Subtask $4$.
  • If $cnt \leq 50 \ 000$, then the score is equal to $1$.
  • If $50 \ 000 < cnt \leq 200 \ 000$, then the score is equal to $min(\frac{25 \ 000}{cnt - 25 \ 000}, 1)$.
  • If $200 \ 000 < cnt \leq \frac{10^8}{N}$, then the score is equal to $0.1$.
• Subtask $5$.
  • If $cnt \leq 170$, then the score is equal to $1$.
  • If $170 < cnt \leq 1 \ 000$, then the score is equal to $min((\frac{170+3000}{cnt+3000})^{\frac{3000}{cnt}},1)$.
  • If $1 \ 000 < cnt \leq 20 \ 000$, then the score is equal to $min(\frac{170}{cnt}^{0.4},0.5)$.
  • If $20 \ 000 < cnt \leq \frac{10^8}{N}$, then the score is equal to $0.1$..

Sample communication

Let we have the following illustration of a map with $5$ spaces and $4$ connections.

Local testing

For local testing the following files are provided: monopoly2.h, Lgrader.cpp, sample file monopoly2.cpp for your program and file with the map from the sample communication. When the provided files are in the same folder, you can compile together your program monopoly2.cpp and Lgrader.cpp. This will make a program to check the correctness of your function.

The program will require from the standard input the following sequence of numbers:

• on the first line: one positive integer - the number of spaces $N$;
• on each of the following $N-1$ lines two positive integers which describe the directed connections.

If you don't follow the protocol for communication, you will get an appropriate error message. Otherwise, if the program is successful, you will get the message "Correctly found connections.".