Hello everyone! At the time I am writing this, there is still no editorial for Round #662. I did very well on this contest and I think my solutions are interesting, so hopefully this can help some people. ↵
↵
[problem:1393A]:↵
↵
<spoiler summary="Problem A">↵
Consider the center column (or column closest to the center if $n$ is even). For that column, you get closer to the center from the edge each time. For even columns, the first turn gets one block, while every turn after that gets two blocks, until the last turn, which fills in the last block, so that takes $\frac{n}{2}+1$ turns. For odd columns, every turn fills two blocks, except for the last turn, which fills in the last block, so that takes $\lfloor \frac{n}{2} \rfloor +1$ turns. The other columns are filled at least as fast. ↵
↵
The answer is thus $\lfloor \frac{n}{2} \rfloor+1$. ↵
</spoiler>↵
↵
Code (Java): [submission:89214023]↵
↵
[problem:1393B]:↵
↵
<spoiler summary="Problem B">↵
There are a few different cases that would allow you to make a square and rectangle:↵
You can have at least $8$ of one number, which would allow you to make two squares.↵
You can have at least $6$ of one number and at least $2$ of another number.↵
You can have at least $4$ of $2$ different numbers.↵
You can have at least $4$ of one number, and at least $2$ of two different numbers.↵
↵
At any given point, you can store the number of numbers that have at least $2$, $4$, $6$, and $8$ occurrences. You can just use $4$ different variables. To start, make a frequency table of the original array and every time a number exceeds $2$, $4$, $6$, or $8$, increment the corresponding variable. For plus queries, increment the corresponding frequency and increment the corresponding variable if the frequency now equals $2$, $4$, $6$, or $8$. For minus queries, decrement the corresponding frequency and decrement the corresponding variable if the frequency was equal to $2$, $4$, $6$, $8$ (and is now lower because you had to decrement it).↵
↵
Using those four variables, you can calculate if it is possible to make a square and rectangle using the cases described above. Note that in my implementation, for the second case for example, I had to check that there were at least $2$ numbers with at least $2$ occurrences because the number that occurs at least $6$ times is included in the count of numbers that occur $2$ times.↵
</spoiler>↵
↵
Code (Java): [submission:89220791]↵
↵
[problem:1393C]↵
↵
<spoiler summary="Problem C">↵
Count the maximum number of times that a number appears, let’s call that $max$. Count the number of numbers that appear $max$ times, let’s call that $maxfreq$. The answer is $\lfloor \frac{n-maxfreq}{max-1} \rfloor -1$. ↵
↵
Intuition/how this works: Logically, the numbers that occur the most number of times would have to be closest together, so let’s set those first. We want to make blocks of all the numbers that occur a max number of times and set those as far apart as possible.↵
↵
Say the numbers that occur a max number of times are $a$, $b$, and $c$. We would want to make a sequence that looks like `abc...abc...abc`. ↵
↵
The distance between the a’s is the formula I mentioned above. $n-maxfreq$ subtracts that last block, so you have something like `abc...abc…...`. There are now $max-1$ blocks of abc, because there used to be $max$, and you just cut one off. Dividing, $\lfloor \frac{n-maxfreq}{max-1} \rfloor$ gives `abc…...`. The distance that you want is `bc…...` because that is the distance between the two $a$’s, so you have to subtract $1$ to get $\lfloor \frac{n-maxfreq}{max-1} \rfloor -1$. The distance between the $b$’s and $c$’s and all the other numbers occur $max$ number of times is the same thing.↵
↵
You are always able to place the remaining numbers in such a way that there are no two numbers closer than the distance between the $a$’s. I do not have a rigorous proof at the moment, but if someone can provide one, that would be great. Intuitively speaking, there are $max-1$ number of gaps between the blocks, and no remaining number occurs more than $max-1$ times, so you never have to place more than $1$ of the same number in the same gap.↵
</spoiler>↵
↵
Code (Java): [submission:89231755]↵
↵
[problem:1393D]↵
↵
<spoiler summary="Problem D">↵
We can think of a rhombus as $4$ triangles (that overlap). The upper left triangle is the triangle between the topmost point, leftmost point, and center. The upper right triangle is the triangle between the topmost point, rightmost point, and center. Each triangle forms what looks like a staircase.↵
↵
For every cell, we calculate the maximum triangle with that cell as the center going in each direction (up left, up right, down left, and down right). The answer is the minimum of the maximum triangle going in each direction.↵
↵
We can calculate the maximum triangle going in each direction using dp. Let’s say we are calculating the upper left triangle. We need to loop from up to down ($k$ goes from $0$ to $n$ and left to right, $j$ goes from $0$ to $m$ for my implementation). If $\verb#board#[k-1][j] == \verb#board#[k][j]$ and $\verb#board#[k][j-1] == \verb#board#[k][j]$, then $\verb#upperleft#[k][j] = \min{(\verb#upperleft#[k-1][j],\verb#upperleft#[k][j-1])} +1$ because you can extend the two upper left triangles to a triangle that is one bigger. If $\verb#board#[k-1][j] \neq \verb#board#[k][j]$ or $\verb#board#[k][j-1] \neq \verb#board#[k][j]$, then $\verb#upperleft#[k][j] = 1$ because you cannot extend any triangle, so you have to start over at $1$.↵
↵
The direction that you loop for each direction is important. For the down right triangle, you need to loop from down to up and right to left ($k$ goes from $n-1$ to $0$ and $j$ goes from $m-1$ to $0$ for my implementation). For the up right triangle, you need to loop from up to down and right to left, and so on.↵
</spoiler>↵
↵
Code (Java): [submission:89257786]↵
↵
↵
↵
↵
[problem:1393A]:↵
↵
<spoiler summary="Problem A">↵
Consider the center column (or column closest to the center if $n$ is even). For that column, you get closer to the center from the edge each time. For even columns, the first turn gets one block, while every turn after that gets two blocks, until the last turn, which fills in the last block, so that takes $\frac{n}{2}+1$ turns. For odd columns, every turn fills two blocks, except for the last turn, which fills in the last block, so that takes $\lfloor \frac{n}{2} \rfloor +1$ turns. The other columns are filled at least as fast. ↵
↵
The answer is thus $\lfloor \frac{n}{2} \rfloor+1$. ↵
</spoiler>↵
↵
Code (Java): [submission:89214023]↵
↵
[problem:1393B]:↵
↵
<spoiler summary="Problem B">↵
There are a few different cases that would allow you to make a square and rectangle:↵
You can have at least $8$ of one number, which would allow you to make two squares.↵
You can have at least $6$ of one number and at least $2$ of another number.↵
You can have at least $4$ of $2$ different numbers.↵
You can have at least $4$ of one number, and at least $2$ of two different numbers.↵
↵
At any given point, you can store the number of numbers that have at least $2$, $4$, $6$, and $8$ occurrences. You can just use $4$ different variables. To start, make a frequency table of the original array and every time a number exceeds $2$, $4$, $6$, or $8$, increment the corresponding variable. For plus queries, increment the corresponding frequency and increment the corresponding variable if the frequency now equals $2$, $4$, $6$, or $8$. For minus queries, decrement the corresponding frequency and decrement the corresponding variable if the frequency was equal to $2$, $4$, $6$, $8$ (and is now lower because you had to decrement it).↵
↵
Using those four variables, you can calculate if it is possible to make a square and rectangle using the cases described above. Note that in my implementation, for the second case for example, I had to check that there were at least $2$ numbers with at least $2$ occurrences because the number that occurs at least $6$ times is included in the count of numbers that occur $2$ times.↵
</spoiler>↵
↵
Code (Java): [submission:89220791]↵
↵
[problem:1393C]↵
↵
<spoiler summary="Problem C">↵
Count the maximum number of times that a number appears, let’s call that $max$. Count the number of numbers that appear $max$ times, let’s call that $maxfreq$. The answer is $\lfloor \frac{n-maxfreq}{max-1} \rfloor -1$. ↵
↵
Intuition/how this works: Logically, the numbers that occur the most number of times would have to be closest together, so let’s set those first. We want to make blocks of all the numbers that occur a max number of times and set those as far apart as possible.↵
↵
Say the numbers that occur a max number of times are $a$, $b$, and $c$. We would want to make a sequence that looks like `abc...abc...abc`. ↵
↵
The distance between the a’s is the formula I mentioned above. $n-maxfreq$ subtracts that last block, so you have something like `abc...abc
↵
You are always able to place the remaining numbers in such a way that there are no two numbers closer than the distance between the $a$’s. I do not have a rigorous proof at the moment, but if someone can provide one, that would be great. Intuitively speaking, there are $max-1$ number of gaps between the blocks, and no remaining number occurs more than $max-1$ times, so you never have to place more than $1$ of the same number in the same gap.↵
</spoiler>↵
↵
Code (Java): [submission:89231755]↵
↵
[problem:1393D]↵
↵
<spoiler summary="Problem D">↵
We can think of a rhombus as $4$ triangles (that overlap). The upper left triangle is the triangle between the topmost point, leftmost point, and center. The upper right triangle is the triangle between the topmost point, rightmost point, and center. Each triangle forms what looks like a staircase.↵
↵
For every cell, we calculate the maximum triangle with that cell as the center going in each direction (up left, up right, down left, and down right). The answer is the minimum of the maximum triangle going in each direction.↵
↵
We can calculate the maximum triangle going in each direction using dp. Let’s say we are calculating the upper left triangle. We need to loop from up to down ($k$ goes from $0$ to $n$ and left to right, $j$ goes from $0$ to $m$ for my implementation). If $\verb#board#[k-1][j] == \verb#board#[k][j]$ and $\verb#board#[k][j-1] == \verb#board#[k][j]$, then $\verb#upperleft#[k][j] = \min{(\verb#upperleft#[k-1][j],\verb#upperleft#[k][j-1])} +1$ because you can extend the two upper left triangles to a triangle that is one bigger. If $\verb#board#[k-1][j] \neq \verb#board#[k][j]$ or $\verb#board#[k][j-1] \neq \verb#board#[k][j]$, then $\verb#upperleft#[k][j] = 1$ because you cannot extend any triangle, so you have to start over at $1$.↵
↵
The direction that you loop for each direction is important. For the down right triangle, you need to loop from down to up and right to left ($k$ goes from $n-1$ to $0$ and $j$ goes from $m-1$ to $0$ for my implementation). For the up right triangle, you need to loop from up to down and right to left, and so on.↵
</spoiler>↵
↵
Code (Java): [submission:89257786]↵
↵
↵
↵
