Codeforces Round 1136 (Div. 1, Div. 2) Editorial
Разница между en2 и en3, 86 символ(ов) изменены
Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the overly simplistic Div2D and the trivial Div1D(and the statements with poor readability). I think that the whole difficulty of Div1D lies in how people hack the solutions of other participants: if nobody hacks, this problem is easier than Div1C, but if somebody hacks, it becomes hard. I will explain this in more detail in the tutorial below.↵
↵
### [problem:2288A]↵
↵
<spoiler summary="Hint 1">↵
The last operation can only be an Attack.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
You can only Charge several times first and then Attack several times.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
If your sequence of operations contains a segment [Attack, several Charges, several Attacks], move the leading Attack behind those Charges. The total damage cannot decrease.↵
↵
Therefore we may assume that all Attacks are performed after all Charges. Then you can enumerate how many Charges are performed at the very beginning, and simulate how many Attacks are needed to defeat the youkai.↵
↵
Depending on the implementation, your time complexity is either $O(x)$ or $O(x\log x)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4874999085]↵
</spoiler>↵
↵
### [problem:2288B1] / [problem:2287A1]↵
↵
<spoiler summary="Hint 1">↵
Use dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288B1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4875399159]↵
</spoiler>↵
↵
### [problem:2288B2] / [problem:2287A2]↵
↵
<spoiler summary="Hint 1">↵
We need $k$ to take at least $n+1$ different values. What do we need for that?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
In the vast majority of cases the returned $k$ points at a \texttt{+}, and either $k$ is already the end of the string or $k+1$ points at a \texttt{-}.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
A repeated structure \texttt{+-} is useless.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
To make good use of every character, a naive idea is to spread the possible values of $k$ as evenly as possible. For that we should use more \texttt{-} characters.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288B2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
487599227]↵
</spoiler>↵
↵
### [problem:2288C]↵
↵
<spoiler summary="Hint 1">↵
We only need to track how many attacks a youkai needs before it leaves the field, which is $c_i = \left\lceil \frac{a_i}{x} \right\rceil$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Sort $c$ and ignore the maximum.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4876199294]↵
</spoiler>↵
↵
### [problem:2288D] / [problem:2287B]↵
↵
<spoiler summary="Hint 1">↵
At least one of the two trains must stop at every station. Why?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The other train only stops at a prefix and a suffix. Why?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4876299503]↵
</spoiler>↵
↵
### [problem:2288E] / [problem:2287C]↵
↵
<spoiler summary="Hint 1">↵
It is obvious that we should use bitsets.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The final time complexity is $O\left(\frac{n_{\max} m_{\max} \log m_{\max}}{w}\right)$, where $w = 64$. Do not worry about TLE: this code runs fast and is completely fine.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4876799592]↵
</spoiler>↵
↵
### [problem:2287D]↵
↵
<spoiler summary="Hint 1">↵
How would you solve this problem if there were no hacks?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Is there any way to compute the hashes of the length-$\ell$ prefixes of $a_0, a_1, \dots, a_{n-1}$ quickly?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Classic string hashing is great: it supports rolling hashes, but it also makes us fragile when facing attacks.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287D]↵
↵
PS: This problem accepts using a high-resolution clock as the RNG seed. Among the approaches known today, if you do not use it, you have to use a cryptographic hash (such as SHA-256). Also, banning timers is technically unrealistic, and it would expose the intended solution of this problem.↵
↵
PS: During testing, Codex used **fixed seeds** and **one** RNG-generated weight array, and compared every character naively whenever the hashes were equal. I successfully constructed data that hacks this approach (a 120s TLE), and I proved that even with **four** independent RNGs, this approach is still fragile as long as the seeds are fixed (I constructed a 20s TLE). But I guess that during the Div1 contest nobody will try to hack this approach.↵
</spoiler>↵
↵
<spoiler summary="Code with high-resolution clock">↵
[submission:3993
4880899731]↵
</spoiler>↵
↵
<spoiler summary="Code with sha-256">↵
[submission:3993
4880999760]↵
</spoiler>↵
↵
### [problem:2287E1]↵
↵
My initial problem only had an $n \le 10^5$ version and an $n \le 500$ version; thanks to [user:Error_Yuan,2026-11-21] for proposing this $n \le 10^4$ version.↵
↵
<spoiler summary="Hint 1">↵
If the two maxima differ, or if they are equal with different multiplicities, the position is already trivial: keep attacking the opponent's maximum, and the outcome is decided by whose maximum is larger and, on a tie, by who owns more copies of it.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
A player has only two useful attack targets: the opponent's maximum value and the opponent's strict second maximum. Attacking anything smaller brings no extra profit.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Both players may play optimally without ever skipping a turn: skipping never turns a lost position into a non-lost one, so every move may be assumed to be a real attack.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287E1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4881699865]↵
</spoiler>↵
↵
The idea comes from the power level settings of some fantasy works. In many fantasy works every character has a power level, and the levels differ wildly (for example, Tier 10 is an ordinary human, while Tier 9 is a superhuman). In this setting I created this problem, so that you can see how a battle between two groups should happen in such a fantasy world, and what the best arrangement is if a group wants to defeat another group.↵
↵
### [problem:2287E2]↵
↵
Codex did not pass this problem during testing, which surprised me a lot.↵
↵
Before reading, please go through the hints of [problem:2287E1], but no need read its tutorial, because what follows is completely different.↵
↵
<spoiler summary="Hint 1">↵
Sort the input. You can see that at any moment both players hold a prefix plus $k$ copies of the maximum value. This is already an $O(n^3)$-level DP.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We focus on the case $k = 0$: at this moment both players hold only a prefix, and we enter a subproblem.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Recall Hint 1 of the easy version: only $O(n)$ subproblems are not trivial.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Every state with $k > 0$ can be derived from the states with $k = 0$, and we only need to find the derivation rule.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287E2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:3993
4882599973]↵
</spoiler>↵
↵
This problem was originally conceived as a two-attribute version (attack power and defense power), but I only know an $O(2^n)$ solution for it.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский LNight121 2026-11-21 21:06:13 78255
en3 Английский LNight121 2026-11-21 20:36:42 86
en2 Английский LNight121 2026-11-21 20:00:56 42 (published)
en1 Английский LNight121 2026-11-21 19:35:56 7560 Initial revision (saved to drafts)