shiny_shine's blog

By shiny_shine, history, 2 weeks ago,

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
• +5

 » 2 weeks ago, # |   +5 Auto comment: topic has been updated by shiny_shine (previous revision, new revision, compare).
 » 2 weeks ago, # |   +5 Auto comment: topic has been updated by shiny_shine (previous revision, new revision, compare).