My approach during CodeForces Round 959

Revision en4, by shiny_shine, 2024-07-19 06:09:00

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

Code

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

Code

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

Code

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

Code

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\log n)$$$.

Code

6. After

Man!

What can I say?

74TrAkToR out!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English shiny_shine 2024-07-19 09:07:49 6
en6 English shiny_shine 2024-07-19 06:46:24 217
en5 English shiny_shine 2024-07-19 06:40:09 34
en4 English shiny_shine 2024-07-19 06:09:00 6 Tiny change: 'ty is $O(n)$.\n\n<s' -> 'ty is $O(n\log n)$.\n\n<s'
en3 English shiny_shine 2024-07-19 05:58:50 2 Tiny change: 'j>x$, add 将 $d_i+1$ t' -> 'j>x$, add $d_i+1$ t'
en2 English shiny_shine 2024-07-19 05:55:08 38
en1 English shiny_shine 2024-07-19 05:54:22 6611 Initial revision (published)