ALE-Bench

Story

Takahashi manages a transit warehouse for transporting containers. Today, many containers are scheduled to be brought into this warehouse, and tomorrow, all of these containers will be loaded onto trucks in a predetermined order for transportation. The order in which the containers will arrive is unknown, so please flexibly store them in appropriate locations in the warehouse, taking into account the order in which they will be transported out.

Problem Statement

There is a warehouse with a grid of $D\times D$ squares. Let $(0,0)$ be the coordinates of the northwesternmost square and $(i,j)$ be the coordinates of the squares located $i$ squares to the south and $j$ squares to the east from there. The warehouse entrance is in the square $(0,(D-1)/2)$, where $D$ is an odd number. There are impassable obstacles placed in $N$ squares out the $D^2-4$ squares except for the entrance and its $3$ adjacent squares.

$D^2-1-N$ containers are brought into the warehouse one by one. Each container is assigned a unique number from $0$ to $D^2-2-N$ which indicates the order in which the containers are to be transported out. Information on the order of containers is not given in advance, and the number assigned to a container is revealed at the time it is brought in. Each $D\times D-1-N$ square other than the entrance and obstacles can hold at most $1$ container. Each time a container is brought in, choose a square to store it. The chosen square must satisfy the following conditions.

1. It is neither the entrance nor an obstacle square, and there are no other containers stored at the chosen square.
2. It must be reachable from the entrance by only passing through adjacent empty squares in the four directions.

After all the containers are stored, please transport out all of them one by one. The container to be transported out must satisfy the following conditions.

1. The square containing the container to be transported out must be reachable from the entrance by only passing through adjacent empty squares in the four directions.

Optimize the storage location of the containers and the order in which they are transported out so that the order is as close as possible to the specified order.

Scoring

Let $b_i (0\leq b_i\leq D^2-2-N)$ be the number assigned to the container transported out for the $i$-th time ($0\leq i\leq D^2-2-N$). Let $B$ be the number of inversions of $b_0,\cdots,b_{D^2-2-N}$, that is, the total number of pairs $(i,j)$ such that $i < j$ and $b_i>b_j$. Then, you will obtain the following score.

\[ \mathrm{round}\left(10^9\times \frac{(D^2-N)(D^2-1-N)/2-B}{(D^2-N)(D^2-1-N)/2}\right) \]

There are $30$ test cases for each $N=0,1,\cdots,9$, for a total of 300 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Wrong Answer">WA</span> or <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Time Limit Exceeded">TLE</span> , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input and Output

First, the size of the warehouse, $D$, the number of obstacles $N$, and the coordinates $(ri_0,rj_0),\cdots,(ri_{N-1},rj_{N-1})$ of obstacles are given from Standard Input in the following format.

$D$ $N$
$ri_0$ $rj_0$
$\vdots$
$ri_{N-1}$ $rj_{N-1}$

For all test cases, we fix $D = 9$. The number of obstacles $N$ satisfies $0\leq N\leq D$. The coordinates of each obstacle $(ri_k,rj_k)$ are different from the entrance and any of its three adjacent squares, furthermore, all squares except the obstacles are guaranteed to be reachable from the entrance.

After reading the above information, repeat the following process $D^2-1-N$ times.

In the $d$-th process ($0\leq d\leq D^2-2-N$), the number $t_d$ assigned to the $d$-th container brought in is given on a single line from Standard Input. Each $t_d$ is an integer value between $0$ and $D^2-2-N$, and each container has a unique number.

After reading the information of $t_d$, output the coordinates $(pi_d,pj_d)$ of the square to store the container to Standard Output on a single line in the following format.

<font color="red">The output must be followed by a new line, and you have to flush Standard Output.</font> Otherwise, the submission might be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Time Limit Exceeded">TLE</span>. <font color="red">**Note that the input for the $d+1$-th container will not be given until the $d$-th output is given. **</font>

After all containers have been stored, determine the order in which the containers are to be transported out. Let $(qi_k, qj_k)$ be the coordinates of the $k$-th container to be transported out. Then, output to Standard Output in the following format.

$qi_0$ $qj_0$
$qi_1$ $qj_1$
$\vdots$
$qi_{D^2-2-N}$ $qj_{D^2-2-N}$

Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines at the corresponding timing, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.

例

<a href="https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.html?lang=en&seed=0&output=sample">Show example</a>

Input Generation

The number of obstacles $N$ is generated uniformly at random from integers between $0$ and $D$, inclusive. A distinct set of $N$ coordinates for the obstacles are randomly chosen from squares other than the entrance and its three adjacent squares. The numbers $t_0,\cdots,t_{D^2-2-N}$ assigned to the containers are generated by randomly shuffling $0,1,\cdots,D^2-2-N$.

Tools (Input generator and visualizer)

• <a href="https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.html?lang=en">Web version</a>: This is more powerful than the local version providing animations and manual play.
• <a href="https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.zip">Local version</a>: You need a compilation environment of <a href="https://www.rust-lang.org/">Rust language</a>.
  • <a href="https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG_windows.zip">Pre-compiled binary for Windows</a>: If you are not familiar with the Rust language environment, please use this instead.

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Story

AtCoder, a big tech company, has many offices. In order to securely share super-secret information of problem statements for future contests, we decided to set up private lines using quantum cryptography between the offices. There are several candidates for office pairs that can be connected by private lines, and we want to make sure that all offices are connected by private lines. The cost of setting up a private line is proportional to the length of the line, but due to physical limitations, it is not always possible to set up a straight line, so we have asked vendors to estimate the exact cost for each candidate. Since CEO Takahashi is impatient, once he receives the estimate for one candidate, he immediately decides whether to set up that line or not. Please support Takahashi and help him achieve his goal at a lower cost as possible.

Problem Statement

You are given an undirected graph with $N$ vertices and $M$ edges. Each vertex is on a two-dimensional plane, and the coordinates of the $i$-th vertex is $(x_i, y_i)$. The $i$-th edge connects vertices $u_i$ and $v_i$, and we know in advance that its length $l_i$ satisfies $d_i \leq l_i \leq 3 d_i$, where $d_i=\mathrm{round}(\sqrt{(x_{u_i}-x_{v_i})^2+(y_{u_i}-y_{v_i})^2})$ is the Euclidean distance between the endpoints rounded to the nearest integer.

The true edge length $l_i$ will be given one by one in order from $i=0$ to $i=M-1$. After receiving the length $l_i$ of the $i$-th edge, you have to decide whether to adopt that edge or not before receiving the length $l_{i+1}$ of the next edge.

Let $S$ be the set edges you eventually adopt, then for every vertex pair $(u,v)$, $S$ must contain a path between $u$ and $v$. Please make decisions so that the total length of the adopted edges is as short as possible.

Input and Output

For all test cases, we fix $N=400$ and $M=1995$.

At the start of the execution, the coordinates of $N$ vertices $(x_0,y_0), \cdots, (x_{N-1},y_{N-1})$ and the endpoints of $M$ edges $(u_0,v_0), \cdots, (u_{M-1},v_{M-1})$ are given from Standard Input in the following format.

$x_0$ $y_0$
$\vdots$
$x_{N-1}$ $y_{N-1}$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$

It is guaranteed to satisfy the following.

• $0\leq x_i,y_i\leq 800$
• $0\leq u_i<v_i\leq N-1$
• The same $(u_i,v_i)$ pair never appears more than once.
• The graph is connected.

Then, repeat the following process $M$ times.

In the $i$-th ($0\leq i\leq M-1$) process, the length $l_i$ of the $i$-th edge is generated uniformly at random from integers between $d_i$ and $3 d_i$, and given to Standard Input in a single line. After reading $l_i$, output 1 if you adopt the $i$-th edge, or 0 if you don't, in one line to Standard Output. <font color="red">Note that the next input is not given until your program outputs 0 or 1. After the output, you have to flush Standard Output.</font> Otherwise, the submission might be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Time Limit Exceeded">TLE</span> .

Example

Scoring

Let $A$ be the total length of the set of adopted edges, $B$ be the total length of the optimal set of edges under the condition that the true length $l_i$ of every edge is known in advance (<a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree">minimum spanning tree</a>). Then, you will get a score of $\mathrm{round}(10^8\times B/A)$. When the set of adopted edges does not make the graph connected, your submission will be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="不正解">WA</span>. Note that if your program terminates abnormally, it may be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Wrong Answer">WA</span> instead of <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Runtime Error">RE</span>.

There are 150 test cases, and the score of a submission is the total score for each test case. If you get a result other than <span class='label label-success' data-toggle='tooltip' data-placement='top' title="Accepted">AC</span> for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.

Input Generation

Let $\mathrm{rand}(L,U)$ be a function that generates a uniform random integer between $L$ and $U$, inclusive.

Generation of $(x_i,y_i)$

For each $i=0,\cdots,N-1$, we generate $x_i=\mathrm{rand}(0,800)$ and $y_i=\mathrm{rand}(0,800)$. If the Euclidean distance to the coordinates $(x_j,y_j)$ of an already generated vertex $(j<i)$ is less than or equal to $5$, we regenerate $(x_i,y_i)$.

Generation of $(u_i,v_i)$

Let $G$ be a complete graph with edge length $\mathrm{round}(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2})$ between vertex $i$ and $j$. By repeating the following process $5$ times, we generate a set $E$ of $M=5(N-1)$ edges.

We compute a minimum spanning tree $T$ of $G$, and remove all edges in $T$ from $G$ and insert them to $E$.

Finally, by randomly shuffling the order of edges in $E$, we generate the list of edges $(u_0,v_0),\cdots,(u_{M-1},v_{M-1})$.

Generation of $l_i$

Let $d_i=\mathrm{round}(\sqrt{(x_{u_i}-x_{v_i})^2+(y_{u_i}-y_{v_i})^2})$ be the Euclidean distance between the endpoints rounded to the nearest integer. Then we generate $l_i=\mathrm{rand}(d_i,3 d_i)$.

Tools (Input generator and visualizer)

• <a href="https://img.atcoder.jp/ahc007/a855b6a456c9892b747e147001b0f89.zip">Local version</a>: You need a compilation environment of <a href="https://www.rust-lang.org/">Rust language</a>.
• <a href="https://img.atcoder.jp/ahc007/a855b6a456c9892b747e147001b0f89.html?lang=en">Web version</a>: This is more powerful than the local version and can display animations.

<font color="red">You are allowed to share output images (png or gif) of the provided visualizer for seed=0 on twitter during the contest.</font> You have to use the specified hashtag and public account. <a href="https://twitter.com/search?q=%23AHC007%20%23visualizer&src=typed_query&f=live">List of shared images.</a>

Story

AtCoder's CEO, Takahashi, loves animals and has a number of pets running free in the AtCoder office. AtCoder's employees have trouble with the pets interrupting their work, so they have decided to place partitions in the office to create a space where pets cannot come in. Please create as large a space as possible.

Problem Statement

There are $N$ pets and $M$ people in a room with a floor of $30 \times 30$ squares. All squares are initially passable, and outside of the $30 \times 30$ squares are impassable. Let $(x, y)$ be the coordinates of the square in row $x$ from the top ($1\leq x\leq 30$) and column $y$ from the left ($1\leq y\leq 30$). Repeat the following process for $300$ turns.

First, you choose each person's action from the following three types, and perform each action simultaneously.

• Do nothing and stay in the current position.
• Choose a square adjacent to the current position and make it impassable. You cannot choose a square that contains pets or humans at the start of this turn. <b>You cannot choose a square whose adjacent square contains a pet, either.</b> If you choose a square that is already impassable, nothing happens.
• Move to an adjacent passable square. It is not possible to move to a square that becomes impassable by another person's action in this turn.

After all the people have completed their actions for that turn, each pet moves independently. Rules for pet movement depend on the type of pet, and some pets may move multiple squares in a single turn. Details are described later.

Squares containing humans or pets are also passable, and each square can contain any number of humans and pets.

Scoring

At the end of $300$ turn, for each $i=1,\cdots,M$, let $R_i$ be the set of squares reachable from the final position of person $i$ through only passable squares, and $n_i$ be the number of pets whose final position is in $R_i$. Then, person $i$ obtains satisfaction of $s_i=\frac{|R_i|}{900}\times 2^{-n_i}$. The score for the test case is $\mathrm{round}\left(10^8\times\frac{1}{M}\sum_{i=1}^M s_i\right)$.

Number of test cases

• Provisional test: 100
• System test: 2000. We will publish <a href="https://img.atcoder.jp/ahc008/seeds.txt">seeds.txt</a> (md5=27bf0702bbe0265900374c3b6b9846b4, sha256=33973e4ded08e3a607fc2e841e14751ff110ae10154b286e7fd5f766ff86d706) after the contest is over.

The score of a submission is the total scores for each test case. In the provisional test, if your submission produces illegal output or exceeds the time limit for some test cases, the submission itself will be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Wrong Answer">WA</span> or <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Time Limit Exceeded">TLE</span> , and the score of the submission will be zero. In the system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero. Note that if your program terminates abnormally, it may be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Wrong Answer">WA</span> instead of <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Runtime Error">RE</span>.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Time Limit Exceeded">TLE</span> in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Input and Output

First, the initial position and type of each pet, and the initial position of each person are given from Standard Input in the following format

$N$
$px_1$ $py_1$ $pt_1$
$\vdots$
$px_N$ $py_N$ $pt_N$
$M$
$hx_1$ $hy_1$
$\vdots$
$hx_M$ $hy_M$

$N$ is an integer between $10$ and $20$ representing the number of pets. $(px_i,py_i)$ represents the coordinates of the initial position of the $i$-th pet, and $pt_i$ is an integer between $1$ and $5$ representing the type of the $i$-th pet. $M$ is an integer between $5$ and $10$ representing the number of humans. $(hx_i,hy_i)$ represents the coordinates of the initial position of the $i$-th human. The initial positions of all pets and humans are guaranteed to be distinct.

After reading the above information, repeat the following process $300$ turns.

First, output a string of length $M$ where the $i$-th character represents the action of the $i$th person as follows on a single line to Standard Output. <font color="red">After the output, you have to flush Standard Output.</font> Otherwise, the submission might be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' tit le="Time Limit Exceeded">TLE</span> .

• .: Do nothing and stay in the current position.
• u, d, l, r: Let $(x,y)$ be the current position. Make the square $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, or $(x,y+1)$ impassable, respectively.
• U, D, L, R: Let $(x,y)$ be the current position. Move to the the square $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, or $(x,y+1)$, respectively.