A. Nene's Game
Idea: Otomachi_Una
Solution
Obviously, a person at place $$$p$$$ will be kicked out if and only if $$$p \ge a_1$$$.
Therefore, the answer is $$$\min(n,a_1-1)$$$.
B. Nene and the Card Game
Idea: Otomachi_Una
Solution
For each color (in the following text, "this point" refers to the point someone got by playing a card with this color):
If you have both cards of this color in your hand, you will be able to get this point.
If Nene has both cards, you will not be able to get this point.
If you have only one card, you cannot get this point when Nene is using the following strategy:
> When you play one of your paired cards, Nene also plays one of her paired cards; > Otherwise, Nene will have the card with the same color. She can play it and get this point.
Therefore, the answer will be the amount of pairs in your hand.
C. Nene's Magical Matrix
Idea: Otomachi_Una
Solution
The optimal matrix would be:
1 2 3 ... n
2 2 3 ... n
3 3 3 ... n
..... ... n
n n n n n n
Construction method:
for i in [n, n-1, ..., 1]:
set the i'th column to [1, 2, ..., n];
set the i'th row to [1, 2, ..., n];
This takes exactly $$$2n$$$ operations.
Proof
For the final matrix, we define $$$f(x)$$$ as the number of elements greater or equal to $$$x$$$. The sum of all elements in the matrix is $$$\sum_{i=1}^n f(i)$$$ because an element with value $$$x$$$ will be counted $$$x$$$ times in the formula before.
Now, we proof that $$$f(x) \le n^2-(x-1)^2$$$:
Let's rewrite the problem to make it a little simpler:
You have an $$$n\times n$$$ matrix. In each operation, you can paint exactly $$$x-1$$$ cells white and $$$n-(x-1)$$$ cells black in a row or a column. Proof that there will be at most $$$n^2-(x-1)^2$$$ black cells.
Try to strengthen the conclusion by stating that:
For any matrix of size $$$n\times m$$$, each operation can paint a row into $$$x$$$ white cells and $$$m-x$$$ black cells, or a column into $$$y$$$ white cells and $$$n-y$$$ black cells. No matter how we paint, the final matrix will have at most $$$nm-xy$$$ black cells.
We will prove this by induction.
If $$$x=n$$$ or $$$y=m$$$, the conclusion holds.
Otherwise, if the last operation is to paint a row, then this row has exactly $$$m-x$$$ black cells. And, by induction, other rows will contain at most $$$(n-1)m-x(y-1)$$$ black cells. Painting a column in the last step is similar.
Then, we have proven the conclusion above.
Since the construction above maximizes each $$$f(x)$$$, it is the optimal answer.
D. Nene and the Mex Operator
Idea: Otomachi_Una
Solution
When $$$a_i =0$$$, the sum can hit $$$n^2$$$ with making $$$a_i = n$$$ at last. Construction:
//! a function which sets a_1 ... a_k into k.
function solve(k):
if k is 1:
operate [1,1]
return
end if
solve(k-1);
for i in [k-2, ..., 1]:
operate [1,i] //! this sets a_1 ... a_i into 0
solve(i)
//! here, a should be [i, i, ..., i, i+1, i+2, ..., k-1, 0]
end for
//! here, a should be [1, 2, 3, ..., k-1, 0]
operate [1,k]
return
Here, solve(k) will take about $$$2^k$$$ operations.
Since doing operation $$$[l,r]$$$ will make $$$a_l,\cdots,a_r \le r-l+1$$$, if for all $$$l\le i\le r$$$, $$$a_i$$$ is included in at least one of the operations and $$$a_{l-1},a_{r+1}$$$ are not, the optimal strategy will be setting $$$a_i = r-l+1$$$ for $$$i\in[l,r]$$$ using the construction above.
Finally, we can use DFS or DP to determine whether each element is included in operations.
The number of operations used will not exceed $$$2^n$$$.
E. Nene vs. Monsters
idea: Otomachi_Una
Solution
If four consecutive monsters have energy level $$$x,y,z,w\ (x,y,z,w>0)$$$ and they did not die after $$$t$$$ rounds of spells, then $$$y$$$ will receive at least $$$t$$$ points of damage, $$$z$$$ will receive at least $$$(t-1) +(t-2)+\cdots=O(t^2)$$$ of damage, and $$$w$$$ will receive at least $$$O(t^3)$$$ of damage.
That is to say, let $$$V=\max_{i=1}^n a_i$$$, after $$$O(\sqrt[3]{V})$$$ rounds, at least one of $$$x,y,z,w$$$ will die.
So, we can simulate the process by brute force until there are no four consecutive alive monsters, and then the problem is reduced to the one described in Hint 2.
If four consecutive monster have energy level $$$0,x,y,z\ (x,y,z>0)$$$, $$$x$$$ will remain alive, $$$y$$$ will die at last and sending $$$D=(y-x)+(y-2x)+\cdots+(y\bmod x)$$$ damage to $$$z$$$ before that. Therefore, $$$z$$$ will remain alive if and only if $$$z>D$$$.
The time complexity is $$$O(n\sqrt[3]{V})$$$.
Bonus: Actually, it can be shown that after $$$O(\sqrt[k]{V})$$$ rounds, there will be no $$$k$$$ consecutive alive monsters. Making $$$k$$$ bigger than $$$3$$$ can further reduce the time complexity, but it will be harder to implement and optimize little on actual performance.
F. Nene and the Passing Game
idea: Otomachi_Una
Solution
Let $$$L_j={i|i-r_i\le j\le i-l_i},R_j={i|i-l_i\le j\le i+r_i}$$$.
If $$$L_j$$$ and $$$R_j$$$ are both nonempty, then all players in both sets are connected (i.e. can pass the ball to each other).
Consider iterating $$$j$$$ from $$$1$$$ to $$$n$$$, and obtain $$$L$$$ and $$$R$$$ during the process. player $$$i$$$ will enter $$$L$$$ when $$$j=i-r_i$$$, and will exit when $$$j=i-l_i+1$$$. Obtaining $$$R$$$ is similar.
If std::set in C++ is used, This will take $$$O(n\log n)$$$. It can be reduced to $$$O(n)$$$ with some simple tricks.
Then, we can use a disjoint-union set for the connectivity, and the problem is solved in $$$O(n\alpha(n))$$$.
Note that we can't afford to create $$$O(n^2)$$$ edges, so we can record the "root" in the disjoint-union set of each element instead of the element itself in sets $$$L,R$$$.
