solved.ac Grand Arena Party × NEXON (onsite, rated)

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 2) - A - Editorial

For the subarray to be sorted starting from the $i$-th integer to the $j$-th integer, for all $k$ such that $i \le k < j$, the condition $A_k < A_{k+1}$ should be satisfied.
This condition can be checked by simply checking all adjacent elements. That is, if we set $B_k$ as `True` or `False` based on whether $A_k < A_{k+1}$ is true, for the subarray to be ascending starting from the $i$-th integer to the $j$-th integer,  $B_i, B_{i+1}, \cdots, B_{j-1}$ must all be true.

There are multiple ways to count such $(i, j)$ pairs.

- For the case $i = j$, the subarray is always sorted. There are $N$ possible cases like this.
- For the case $i \ne j$, take a contiguous `True` block. For any possible combination of starting and ending points within the block, the condition is satisfied. If the length of the block is $k$, there are $\frac{k(k+1)}{2}$ combinations.

The answer is the sum of $\frac{k(k+1)}{2}$ for each continuous block of length $k$ in $B$. All calculations can be performed in $\mathcal O (N)$ time.

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 2) - B - Editorial

To determine whether the robot vacuum cleaner will stop at a certain point or not, we need to simulate its actions after that. 
In the simulation, even if the stop condition is met, the robot will move either infintely or until it exits the grid. 
Here, the answer is the point the robot last cleaned during the simulation.

You can determine whether the robot has left the grid or not by simply following through the simulation.

In the event that the robot works inifinitely, it will repeatedly cycle through cells without dust on them. Let's run the simulation while keeping track of positions visited after the robot has last cleaned dust. Here, position means the pair formed by the robot'ss coordinates $(r, c)$ and direction $d$.
Once an already visited position is visited again, a cycle is formed.

There are some things to note while actually implementing this solution.

- Re-visiting the same coordinates $(r, c)$ does not necessarily form a cycle. The robot must visit the same coordinates in the same direction.
- You must reset the list of visited positions each time the robot cleans dust. This is because even if the starting position is the same, the path may change because the robot has cleaned dust.
- Maintaining the list by adding visited positions each time is too slow since it requires you to traverse through the list in order to determine whether a cycle is formed.
    - Instead, let's use a 3d array which uses $(r, c, d)$ as its indices.

The time complexity analysis is as follows. Each time the robot cleans dust, the number of positions it can visit without repetition until it next cleans dust is $\mathcal O(HW)$.
The robot cleaner can clean dust $\mathcal O(HW)$ times. Thus, the total time complexity is $\mathcal O((HW)^2)$.

### Alternate Solution 1

Given the robot cleaner's position, its next position as well as its previous position is uniquely determined.
Thus, when a cycle is formed, it returns to its position right after it last cleaned dust.
If not, the position where the cycle is first formed would have two previous positions (before entering the cycle and before one loop is completed).


We can use this fact to determine whether a cycle is formed without maintaining a visited array.

### Alternate Solution 2

If the robot has cleaned dust $x$ times so far, it can visit at most $4x$ positions before it next cleans dust. Thus, the number of times the robot moves until it stops operating cannot exceed $4 (1 + 2 + \cdots + (HW-1)) + 1 \le 2(HW)^2$. Simply simulate the $2(HW)^2$ moves, and print the last point when dust was cleaned.

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 2) - C - Editorial

First, let's think of how to calculate the area of a triangle. For the triangle formed by three points in counter clockwise order $(x_1, y_1); (x_2, y_2); (x_3; y_3)$ 


$$
\frac{(x_2-x_1)(y_3-y_1) - (y_2 - y_1)(x_3 - x_1)}{2}
$$

the area can be calculated using the above formula.

Now to find the area of an arbitrary polygon, we can think of splitting the polygon into triangles. If we draw lines starting from point $1$ to all other points, we get $N-2$ triangles consisting of points $1, 2, 3$; $1, 3, 4$; $\cdots$; $1, (N-1), N$. The sum of the areas of these triangles is the area of the polygon.

Now let's try and find where the area becomes half. We will fix one end of the line segment at point $1$ and find the areas with respect to point $1$. As we add up the areas of the triangles up to $1, i, (i+1)$, there will be a point where the sum exceeds half the area of the polygon. That is, if we add up the areas of the triangles up to $1, (k-1), k$, the sum does not exceed half but if we add up to $1, k, (k+1)$, the sum exceeds half. Here, we can observe that the other end of the line segment for our answer lies on the line segment connecting points $k, (k+1)$.

Now we must find the ratio of the internally dividing point. Since for two triangles whose heights are equal, the ratio of their areas is equal to the ratio of the lengths of their bases, we can find the ratio by dividing the area we must add to make the sum exactly half by the area of the triangle $1, k, (k+1)$.

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 2) - D - Editorial

We are going to maintain $x$, denoting which folder the cursor is currently pointing at, and whether each folder is folded or expanded.

We can use the DFS algorithm to list all visible folders. We perform the DFS recursively, not searching folders that are folded. If we add folders to an array $L$ as we visit them, we get the folders in the order they are listed in the array.

First we use DFS to find $L$, and perform the following for each query.

- `toggle`: Find the $x$-th folder in $L$, and flip its folded/expanded state. Use DFS to find $L$ again. The time complexity is $O(N)$.
- `move` $k$: Add $k$ to $x$, and readjust its value to be within the range of the index of $L$. The time complexity is $O(1)$.

The total time complexity is $O(NQ)$.

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 2) - E - Editorial

This solution uses Paramateric search to convert the optimization problem to a decision problem.

First, let's try to determine if it's possible to connect $x$ out of $M$ electronic devices. We use the following greedy property.

- When selecting electronic devices, it is optimal to select $x$ devices with the highest $D_i$, the maximum allowed distance (distance limit) from the wall.
- When connecting plug boards, it is optimal to select a board with a higher number of sockets $A_i$ first.

To determine whether a connection can be made, let's try forming a connection as follows.

Initially, $K$ sockets that are $0$ distance away from the wall are open. Where $d$ is the distance the currently open sockets are away from the wall, we first connect the electronic devices whose distance limit is $d$ among the $X$ devices. Next, to the remaining open sockets, we connect the remaining plug boards starting from the one with the most sockets. Now, the open sockets are $d+1$ distance away from the wall, so we repeat this process.

If we run out of sockets during this process, then it is impossible to connect all $X$ devices. If we run out of devices to connect, then we succeeded in forming the connection. If we run out of plug boards, we can determine whether we have succeeded by comparing the number of open sockets and remaining electronic devies.

Now let's use the above algorithm to determine the largest possible number of electronic devices we can connect. We run a binary search on the values of $X$, and use the above algorithm to deterine whether it is possible to connect all $X$ devices. If we can connect the devices, we search the higher range of numbers, and if we cannot, we search the lower range. Then, in $O(\log M)$ searches, we can determine the largest possible $X$. Total time complexity is $\mathcal{O}((N+M) \log M)$.

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 2) - F - Editorial

We can implement code which runs the simulation given in the problem each second. Each step of the simulation takes about $O(N+L)$ time. Now, for each choice, we can run through all possible choices using backtracking, there are $\mathcal O (2^N)$ choices we can totally make, so the simulation takes $\mathcal O(2^N \times (N+L))$ time.

However, we can observe that the number of possible states for the mushrooms does not actually go up to $\mathcal O (2^N)$. The number of possible states is actually around $\mathcal O(N^2L)$. Thus, if we optimize our backtracking process using methods such as memoization, the simulation takes $\mathcal O(N^2L(N+L))$ time.

As an alternate solution, it is possible to observe that there is always a solution such that $K=1$. We can use this observation to solve the problem in $\mathcal O(N(N+L))$ time.

Proving that the number of possible states for the mushrooms is $\mathcal O (N^2L)$, and that there is always an answer such that $K=1$ requires additional observations. Please refer to the editorial of Div1F.