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

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. 1) - A - 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. 1) - B - Editorial

For an arbitrary point $P$ on a polygon, the point $Q$ at a distance of half the perimeter along the sides of the polygon from $P$ can be found using Pythagoras' Theorem.

Now let's draw a line segment from $P$ **towards** $Q$, and denote the area of the left polygon minus the area of the right polygon as $f(P)$. $f(P)$ has a few important properties.

- $f(P)$ is a continuous function on the position of $P$.
    - In simple words, if the positions of $P$ and $Q$ change by a small amount, so does the area.
- $f(P) = -f(Q)$
    - $f(P)$ is the the area of the left polygon minus the area of the right polygon when you draw a line segment from $P$ towards $Q$. If you draw the line segment from $Q$ to $P$, the positions of the two polygons are reversed. Hence, $f(P)$ and $f(Q)$ have the same absolute value but different signs.

Now we have found the points where $f$ is greater than or equal to zero and points where $f$ is less than or equal to $0$. (To determine which one of $P$ and $Q$ is positive, you can directly calculate $f$.) Now, by the intermediate value theorem, there exists a point between $P$ and $Q$ such that $f(x) = 0$. Below is how you can actually find such a point.

- Let $M$ be the midpoint of $P$ and $Q$.
- If the signs of $f(P)$ and $f(M)$ are equal, change $P$ to $M$. Otherwise, change $Q$ to $M$.
- Repeat the above until $P$ and $Q$ are close enough.

Each time this process is repeated, the distance between $P$ and $Q$ reduces by half. Since $f$ is a continuous function, we can find $P_1, P_2, \cdots$ and $Q_1, Q_2, \cdots$ such that $f(P_i)$ and $f(Q_i)$ have opposite signs. Since the two sequences converge to the same value, the corresponding point is where $f(x) = 0$.

When actually implementing this solution, you can repeat the above process a sufficiently large number of iterations, or until $f$ is within the error range. Since the above process can be completed in $\mathcal O(N)$, the total time complexity is around $\mathcal O(N \log (N/\varepsilon))$.

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

Instead of refueling just the amount we need, let's assume we take all fuel available from each gas station, then get rid of what we don't need. However, in order to know which gas station the fuel is from, we must not mix the fuel up. During the drive, we just need to refuel less by the amount we got rid of at each corresponding gas station.

To minimize the cost, let's use two strategies.

- The car uses the cheapest fuel it has first.
- If the total amount of fuel taken exceeds $F$, we get rid of the most expensive fuel first.

If we maintain the (price, amount) pair in data structures such as a balanced BST or a priority queue, we can perform the two operations above in amortized $\mathcal{O}(\log N)$ time. The total time complexity is $\mathcal{O}(N \log N)$.

solved.ac Grand Arena Party × NEXON (onsite, rated) (Div. 1) - D - 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.

Let's denote the position of the robot using the pair formed by its coordinates $(r, c)$ and direction $d$. For a cell with no dust, its next position is always uniquely determined. Thus, from a given point, the robot always follows the same path until it arrives at a cell with dust.

Instead of calculating the same path every time, let's maintain a Union-Find data structure. We will use nodes to denote all $4HW$ possible positions and outside the grid. If we set the next position as the parent node for each position without dust, we can use the find operation to find the end of the path. Using path compression, this can be done in amortized $O(\log (HW))$ time.

Now let's run the simulation.

- If there is no dust at the current position, we follow the path using the find operation.
- If there is dust at the current position, clean the dust, and then perform the union operation on the $4$ possible next positions. Here, if the current position and next position are already in the same connected component, it means that a cycle is formed so we will store this information in the current component.
- If the current position is outside the grid or part of a component with a cycle, the robot stops.

If we store the distance to the parent node and update it when compressing the path for each node, we can calculate the number of movements required when following the path too. The answer is the total number of movements until the last point when dust is cleaned. Total time complexity is $O(HW \log (HW))$.

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

First, let's observe how the mushrooms move in this problem.

- If we ignore the number on each mushroom, when two mushrooms meet, instead of the mushrooms going opposite directions, we can think of it as the mushrooms passing through each other.
- If we think about the number on each mushroom, we can observe that the order the mushrooms are arranged from left to right is unchanged.

Thus, we can maintain the position of each mushroom and the number on each mushroom separately.

Now when the mushrooms move, all mushrooms move together either forward or backward depending on the direction it is facing. When Mushmom gives the order, the direction of movement switches.
For two mushrooms, one initially facing right at position $x$, and the other facing left at position $4L-x$, they exit the field once they move either $4L-x$ units forward or $x$ units backward. Ultimately, what really matters here is the direction, the distance moved to the left, and the distance moved to the right. (Using this, it can also be proven that there are only $\mathcal O (N^2L)$ possible states in total.)

The goal is to make the mushrooms exit the field by moving mushrooms facing left forward, and mushrooms facing right backward. Since the order in which the mushrooms exit the field as they move forward is fixed, it is possible to move the mushrooms forward up to a certain distance and have the remaining mushrooms in the field exit by moving backward. Using this, it can be proven that there always exists an answer such that $K=1$.

The number of such mushrooms can be found using prefix sum. We will consider mushrooms facing left to be $+1$, and the mushrooms facing right to be $-1$. Then we find the prefix sum in the order in which the mushrooms exit the field. Find the point where the prefix sum is maximum. To track the number on a mushroom when you want to switch the direction after a certain number of mushrooms have exitted the field, you can use the above observations to simulate the direction in which the mushrooms exit the field.

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

First let's assume there was no limitation on the length. What form does a set which can be expressed using 'Subtract-It' take?

**Claim 1**. 'Subtract-It' cannot express a set including sets that are not included in the original expression(`~A&~B&...&~T` etc.).

**Proof**. We need to show that all 'Subtract-It' expressions are subsets of the union of all sets in the original expression (`A|B|...|T` etc.). Let's denote this union as $V$ and use mathematical induction.

- (Base Case) All sets $S$ in the expression are subsets of $V$.
- (Inductive Case) There are three types of operations.
  - `X|Y`: If $X \subseteq V$ and $Y \subseteq V$, $X \cup Y \subseteq V$.
  - `X&Y`: If $X \subseteq V$, $X \cap Y \subseteq V$.
  - `X\Y`: If $X \subseteq V$, $X \setminus Y \subseteq V$.

$\square$

From now on, we will denote "the union of all sets in the expression" as $V$, and "the sets not included in the original expresion" as $\mathcal{C}$. Note that $V$ and $\mathcal{C}$ are partitions ($V \cap \mathcal{C} = \emptyset$, $V \cup \mathcal{C}$ is the universal set) of the universal set. 

**Claim 2**. For an arbitrary set $X$, if $\mathcal{C} \not\subseteq X$, $X$ can be represented in 'Subtract-It'.

**Proof**. We will call the intersection of all sets or their complements (`~`) in a 'Subtract-It' expression a **basis set**. For example, if there is an expression consisting of sets from `A` through `C`, there are $2^{3} = 8$ basis sets such as `A&B&C`, `A&B&~C`, `~A&B&~C`. What's important here is that $\mathcal{C}$ is a basis set. We can show the two following to be true.

- This expression can be expressed as a union of basis sets excluding $\mathcal{C}$.
  - This is easy to prove if you consider the fact that all elements of a basis set are either all included or all excluded from this set.
  - Since $\mathcal{C} \not\subseteq X$, $\mathcal{C}$ cannot be included in the union expressing $X$.
- Basis sets except $\mathcal{C}$ can be represented as an equivalent 'Subtract-It' expression.
  - Since this basis set is not $\mathcal{C}$, it contains at least one set that is not in its complement (that is without `~`).
  - We put these sets without `~` at the front.
  - Now excluding the first set, if the set has `~` on it, rewrite it to `\`, and otherwise rewrite it to `&`.
  - For example, `~A&B&~C&D` can be rewritten as `B&D\A\C`.

Now, if we express $X$ as a union of basis sets excluding $\mathcal{C}$, and then express each basis set as a 'Subtract-It' expression, and then apply `|` to all of them (with parentheses where necessary), we get the 'Subtract-It' expression corresponding to $X$. 

That is, expressions which can be represented as a 'Subtract-It' expression are exactly those that do not contain $\mathcal{C}$, and if a set $X$ contains $\mathcal{C}$, `~X` does not contain $\mathcal{C}$, and can thus be represented as a 'Subtract-It' exprssion. Now let's call the language which expresses expressions of the form below as 'Subtract-It++'!

```
Expression = OldExpr | "~" OldExpr
OldExpr = (A 'Subtract-It' Expression)
```

'Subtract-It++' can express all 'Not-a-Set' expressions. Now we can think of a transpiler which converts a 'Not-a-Set' expression to a 'Subtract-It++' expression. This can be done inductively.

- (Base Case) Simply, a set can just be expressed as a set.
- (Inductive Case) There are three cases.
  - `X&Y`: Let's denote the expression corresponding to `X` as `E_X`, and the expression corresponding to `Y` as `E_Y`.
    - If both `E_X` and `E_Y` are `OldExpr`, `E_X&E_Y` is a 'Subtract-It++' expression.
    - If either of `E_X` or `E_Y` is `OldExpr` and the other is `"~" OldExpr` (WLOG `E_Y = "~" F_Y`), `E_X\F_Y` is a 'Subtract-It++' expression.
    - If both `E_X` and `E_Y` are `"~" OldExpr` such that `E_X = "~" F_X`, `E_Y = "~" F_Y`, `~(F_X|F_Y)` is a 'Subtract-It++' expression.
  - `X|Y`: Let's denote the expression corresponding to `X` as `E_X`, and the expression corresponding to `Y` as `E_Y`.
    - If both `E_X` and `E_Y` are `OldExpr`, `E_X|E_Y` is a 'Subtract-It++' expression.
    - If either of `E_X` or `E_Y` is `OldExpr` and the other is `"~" OldExpr` (WLOG `E_Y = "~" F_Y`), `~(E_X\F_Y)` is a 'Subtract-It++' expression.
    - If both `E_X` and `E_Y` are `"~" OldExpr` such that `E_X = "~" F_X`, `E_Y = "~" F_Y`, `~(F_X&F_Y)` is a 'Subtract-It++' expression.
  - `"~" X`: Let's denote the expression corresponding to `X` as `E_X`.
    - If `E_X` is `OldExpr`, `OldExpr` is a 'Subtract-It++' expression.
    - If `E_X` is `"~" OldExpr` such that `E_X = "~" F_X`, `F_X` is a 'Subtract-It++' expression.

We can summarize the inductive case in a table as follows.

<table>
  <thead>
    <tr>
      <th rowspan=2></th>
      <th colspan=2><code>E_X</code> is <code>OldExpr</code></th>
      <th colspan=2><code>E_X</code> is <code>"~" OldExpr</code><br />(<code>E_X = "~" F_X</code>)</th>
    </tr>
    <tr>
      <th><code>E_Y</code> is <code>OldExpr</code></th>
      <th><code>E_Y</code> is <code>"~" OldExpr</code><br />(<code>E_Y = "~" F_Y</code>)</th>
      <th><code>E_Y</code> is <code>OldExpr</code></th>
      <th><code>E_Y</code> is <code>"~" OldExpr</code><br />(<code>E_Y = "~" F_Y</code>)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td><b><code>X&Y</code></b></td>
      <td align="center"><code>E_X&E_Y</code></td>
      <td align="center"><code>E_X\F_Y</code></td>
      <td align="center"><code>E_Y\F_X</code></td>
      <td align="center"><code>~(F_X|F_Y)</code></td>
    </tr>
    <tr>
      <td><b><code>X|Y</code></b></td>
      <td align="center"><code>E_X|E_Y</code></td>
      <td align="center"><code>~(F_Y\E_X)</code></td>
      <td align="center"><code>~(F_X\E_Y)</code></td>
      <td align="center"><code>~(F_X&F_Y)</code></td>
    </tr>
    <tr>
      <td><b><code>X&Y</code></b></td>
      <td align="center" colspan=2><code>~E_X</code></td>
      <td align="center" colspan=2><code>F_X</code></td>
    </tr>
  </tbody>
</table>

We can make a few observations from this solution.
- First, if the final converted expression is of the form `"~" OldExpr`, this expression contains $\mathcal{C}$, and it is thus impossible to represent it as a 'Subtract-It' expression. In all other cases, this expression is already a 'Subtract-It' expression.
- If the number of operators excluding `~` in the original expression is $k$, this method uses $k$ operators excluding `~`.
  - This is because in all cases, the number of operators excluding `~` is unchanged.
- If the length of the original expression is $n$, the length of the resultant expression converted using this method never exceeds $2n$.
  - The fact that there are $k$ operators excluding `~` means there are $(k+1)$ set symbols, so $k + (k+1) = 2k + 1\leq n$.
  - If the expression is not of the form `"~" OldExpr`, there is no `~` in the expression, so it is the same as using $k$ operators.
  - Even if we enclose each operator in parentheses, we use no more than $3$ letters per operator.
  - In this case, the length of the expression is $(k + 1) + 3k = 4k + 1 < 4k + 2 \leq 2n$.

Therefore, if the final converted expression is of the form `"~" OldExpr`, print `NO`, and if it is of the form `OldExpr`, print `YES`, along with each sub-expression enclosed in parantheses.

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

First we can use DFS to order the folders. This allows us to represent subfolders inside a folder as a continuous interval (Euler Tour Technique).

For each folded folder, let's try coloring the corresponding interval. This way, all folders that are visible are folders that are not colored. We need a data structure that stores this information while performing the following operations efficiently.

- Each time a folders is folded or expanded, insert or remove an interval.
- Where the cursor's location is $x$, find the $x$-th folder among visible folders.

For this, we will maintain a segment tree that stores two values $\mathrm{cnt}, \mathrm{vis}$. For the sake of convenience, we will denote a node of the segment tree as $n$, and its two children nodes as $2n$ and $2n+1$.

$\mathrm{cnt}[n]$ stores how many times the current node was colored. When inserting an interval, increase the $\mathrm{cnt}[n]$ values of the corresponding nodes of the segment tree by $1$. Decrease by $1$ on removal.

$\mathrm{vis}[n]$ stores the number of nodes in the subtree rooted at $n$ that are not colored. If $\mathrm{cnt}[n] \geq 1$, $\mathrm{vis}[n] = 0$, and if $\mathrm{cnt}[n] = 0$, $\mathrm{vis}[n] = \mathrm{vis}[2n] + \mathrm{vis}[2n+1]$.

To find the $x$-th folder, we compare $x$ and $\mathrm{vis}$ of the left subtree. If $x$ is equal or smaller, traverse the left subtree. Otherwise, subtract $\mathrm{vis}[2n]$ from $x$ then traverse the right subtree recursively.

Now we are ready to process each query. We are going to maintain $x$, denoting which folder the cursor is currently pointing at, and whether each folder is folded or expanded.

- `toggle`: Find the folder number of the $x$-th folder in the segment tree, fold or expand the folder based on its state, then insert or remove the interval accordingly. The time complexity is $\mathcal O(\log N)$.
- `move` $k$: Add $k$ to $x$, and if it exceeds the range $[1, \mathrm{vis}[1]]$, set it to a value within the range accordingly. The time complexity is $\mathcal O(1)$.

Total time complexity is $\mathcal O((N+Q)\log N)$.