0. Feeling
Welcome to the easiest Div.1 + Div.2 ever.
Got accepted on ABCDE.
And there's also a version in Chinese here.
1. Diverse Game
Given a permutation with a size of $$$nm$$$, construct another permutation with a size of $$$nm$$$ satisfies that it's different to the previous permutation in each position.
$$$a_i=a_i\bmod nm+1$$$. The time complexity is $$$O(nm)$$$.
2. Fun Game
Given two binary sequences $$$a$$$ and $$$b$$$,unlimited operation to make from $$$a_l$$$ to $$$a_r$$$ simultaneously xor $$$a_1$$$ to $$$a_{r-l+1}$$$。Determine if it's able to turn $$$a$$$ into $b$。
Because I was watching Zenless Zone Zero videos on Bilibili, I suddenly realized that, it's able to consider the prefix zeros in $$$a$$$ and $$$b$$$ as "hollow". Because, under the constriants of the problem, regardless how many operations you do, the size of their "hollow" won't decrease.
With only one $$$1$$$, we can freely modify the following zeros and ones.
Only one line of code to solve this problem. The time complexity is $$$O(n)$$$.
3. Hungry Games
Too lazy to write the statement again.
Answer = total number of possible ranges — ranges with final toxicity of $$$0$$$.
Looks like topological sort.
Define $$$d_i$$$ as the number of left borders $$$j$$$ when set $$$i$$$ as the right border satisfying the final toxicity of the range $$$[j,i]$$$ equals zero.
When enumerating $$$i$$$, find the first $$$t$$$ safisfies $$$\sum_{j=i}^t a_j>x$$$, add $$$d_i+1$$$ to $$$d_t$$$. because, $$$d_i$$$ ranges satisfying the final toxicity equals zero, and the range $$$[i,t]$$$ also makes zero, it's able to combine these two ranges together, that the final toxicity is still zero.
The time complexity is $$$O(n)$$$.
4. Funny Game
In a complete graph with $$$n$$$ nodes, each node has a value $$$a_i$$$. The weight of the edge connecting node $$$i$$$ and $$$j$$$ is $$$|a_i-a_j|$$$. Find a spanning tree in this graph satisfying $$$i$$$ divides the weight of the $$$i$$$-th edge.
I didn't realize the pigeonhole here, so I had a different approach.
A smaller $$$i$$$ has an expectational bigger number of edges satisfying $$$i$$$ divides its weight.
So, enumerate $$$i$$$ in decreasing order, then use union-find to handle connected components.
The time complexity is $$$O(n^2)$$$.
5. Wooden Game
Too lazy to rewrite the statement again.
The contribution of a tree with a size of $$$x$$$ is able to be any integer in range $$$[1,x]$$$, regardless its structure, because we can remove its leaves one by one.
When I realized that, I f**ked up.
The time complexity is $$$O(n)$$$.
6. After
Man!
What can I say?
74TrAkToR out!