[Turorial] Codeforces Round 939 (Div. 2)

Правка en1, от 0doO, 2024-04-13 20:09:59

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

Hint

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

Hint

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

Hint

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

Hint1
Hint2
Hint3

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

Hint

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$$$.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en14 Английский Otomachi_Una 2024-04-17 08:00:54 30
en13 Английский 0doO 2024-04-14 09:24:43 4 Tiny change: '\n\nIf $x=n$ or $y=m$, the con' -> '\n\nIf $x=m$ or $y=n$, the con'
en12 Английский lichenghan 2024-04-14 08:45:47 4 i'th -> i-th in order to prevent auto-highlighting
en11 Английский lichenghan 2024-04-14 08:39:03 31 Fix grammatical errors
en10 Английский 0doO 2024-04-14 08:11:07 158
en9 Английский 0doO 2024-04-14 07:59:14 4 Tiny change: 'ou for taking part in o' -> 'ou for take part in o' (published)
en8 Английский 0doO 2024-04-14 07:39:12 146
en7 Английский 0doO 2024-04-14 07:34:56 9
en6 Английский 0doO 2024-04-14 07:34:24 5732
en5 Английский 0doO 2024-04-14 07:25:51 70 Tiny change: 'gy:\n\n > When you p' -> 'gy:\n\n >When you p'
en4 Английский 0doO 2024-04-14 07:21:44 4 Tiny change: '+1,2n]\cap\Z$.\n\nTha' -> '+1,2n]\cap Z$.\n\nTha'
en3 Английский 0doO 2024-04-14 07:20:05 1454
en2 Английский 0doO 2024-04-13 20:20:47 252
en1 Английский 0doO 2024-04-13 20:09:59 7054 Initial revision (saved to drafts)