shiny_shine's blog

By shiny_shine, history, 3 months ago, In English

UPD: tourist registered for this contest. What we should do, is to participate it, and to testify the new legend.

UPD: tourist is $$$4009$$$ now. Congratulations to him, the tourist tourist.

Full text and comments »

  • Vote: I like it
  • +214
  • Vote: I do not like it

By shiny_shine, 4 months ago, In English

1. Up to the Clouds

Hint 1
Hint 2
Hint 3
Solution
Code

2. Song of Silent River

Hint 1
Hint 2
Solution
Code

3. Drifting Clouds' Rhythm

Hint 1
Hint 2
Hint 3
Solution
Code

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By shiny_shine, 4 months ago, In English

1. Strong Password

Hint 1
Solution
Code

2. Make Three Regions

Hint 1
Hint 2
Hint 3
Solution
Code

3. Even positions

Hint 1
Solution
Code

4. Maximize the root

Hint 1
Hint 2
Hint 3
Solution
Code

5. Level Up

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code during the contest with an unnecessary sort of queries
Code after optimization

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By shiny_shine, 4 months ago, In English

UPD: The full version is here.

1. Strong Password

It's obvious that the best insertion method is to find two same adjacent characters and add a difference to it, and that increases the time by $$$3$$$.

If there isn't a pair like that, we can simply add a character different to the back of the string, to increase the time by $$$2$$$.

2. Make Three Regions

Since there is at most $$$1$$$ connected component in the input graph, and there are only $$$2$$$ rows, so a legal construction only acts like this:

.0.
x.x

or you can flip it by the x-axis.

3. Even Positions

Define $$$n$$$ is size of $$$s$$$, $$$s'$$$ is $$$s$$$ after restoration, and

$$$ p_i=\sum_{i=1}^n [s'_i=\text{'('}]-\sum_{i=1}^n [s'_i=\text{')'}]\\ r_n=0\\ r_i=\max(r_{i+1}-(-1)^{[s_{i+1}=\text{')'}]},0) $$$

Then, for all integers $$$i$$$ in range $$$[1,n]$$$, $$$p_i$$$ shouldn't less than $$$r_i$$$.

So, just greedily construct $$$s'$$$ by checking each $$$r_i$$$ in time.

4. Maximize the root

The overall strategy is able to be called "maximize the minimum". Apply depth-first search on the tree, and when you finish all "maximize the minimum" for vertex $$$x$$$'s childs, if $$$a_x$$$ is lower than all $$$a_i$$$ where $$$i$$$ is in $$$x$$$'s subtree and $$$x\neq i$$$, then set $$$a_x$$$ to the floor average of $$$a_x$$$ and $$$\min(a_i)$$$. Otherwise, don't perform operations.

Answer is $$$a_1+\min_{i=2}^n a_i$$$.

5. Level Up

Observed that for each $$$i$$$, there exists a constant $$$c_i$$$ that $$$i$$$-th monster always fight with Monocarp when $$$k\ge c_i$$$.

Apply binary search with a BIT to find $$$c_i$$$, which has a time complexity of $$$O(n\log^2 (2\times 10^5))$$$, then we can answer each query in constant time.

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By shiny_shine, 4 months ago, In English

Abstract

After I participated in Pinely Round 4 yesterday, my rating dropped down a lot.

BUT, I learnt something useful.

1. Check your initialization — AND Reconstruction

After I solved A in a minute and saw the statement of B, I quickly realized that there's an efficient construction which is simply set $$$a_i=b_i|b_{i-1}$$$. The code is below.

code

Can you recognize what's wrong with the code?

answer

2. It's never guaranteed that former problems are easier than others — Absolute Zero

$$$40$$$ minutes after I submitted the second wrong submission of B, I gave up and came to check C.

And, literally the moment I understood the problem statement, I came up with an efficient solution.

In each of the $$$k$$$ operations, sort $$$a$$$, then set $$$x=\lceil a_1+a_n\rceil$$$. If the legal operation sequence exists, my method always reduce $$$\max(a)-\min(a)$$$ for a half.

So I quickly implemented my method successfully, and got accepted. However, it was already an hour from the beginning, so I lost a lot of points.

3. Think about the probability that you're rickrolled by the problem when you struggled solving it — Prime XOR Coloring

From I solved C to the end of the contest, I struggled solving D because I believed that it was easier to solve D than to solve B (because I didn't find that silly bug). I tried to find a pattern what a legal construction has, but I failed. Because I tried to make every color as small as possible.

However, I forgot that it's not necessary to make every color the smallest. Making the number of colors smallest is enough. And in the editorial, the proposer told us, "Why not try to make all $$$\operatorname{xor}$$$ values of the positions with same color an composite number?"

In fact, the sample given in the problem statements is already a hint. It hints us to think about $$$4$$$. As we know, $$$(4)_{10}=(100)_2$$$. There's only one $$$1$$$ in its binary expression. If we make sure that $$$2$$$ lowest bits of two different positions with a same color are always the same, then their $$$\operatorname{xor}$$$ value is always divisible by $$$4$$$, which is a composite number.

Then, for $$$n\ge 6$$$, we can simply set $$$c_i=i\bmod 4+1$$$.

What a rickrolling problem, but I like it!

4. Maybe the answer resides in the boundary condition — Coloring Game

Since I spent all the rest of the time solving D, I only took a look at E and had no idea.

The statement says Alice chooses two different colors each time. So, in order to decrease the probability of Bob winning, she can only choose two colors all the time.

And in this worst case, Bob is possible to win only when the graph is a bipartite graph, which is able to be colored by only two colors.

So the instruction to win is obvious. If the graph is a bipartite graph, choose Bob, since he can always win with at least $$$2$$$ colors. Otherwise, choose Alice, since only a bipartite graph can be colored by only two colors, and it's impossible for Bob to find a legal coloring.

5. Range queries may not lead to a range data structure such as Segment Tree — Triangle Formation

When I took my first look at this problem, I thought about segment tree. However, it's unnecessary in this problem because the densiest sequence ("densiest" means the smallest maximum value) with no non-degenerate triangle formable is the fibonacci sequence. If you do a simple implementation, you'll discover that the $$$45$$$-th term of that sequence already exceeds $$$10^9$$$. So, under the constraint, a subsequence of $$$a$$$ with a size not less than $$$45$$$ always generates a non-degenerate triangle.

But the problem asks us to make $$$2$$$ non-degenerate triangle. How can we do that? In fact, we can simply add $$$3$$$ more numbers into that sequence. because after we extract one of the non-degenerate triangles, there are still $$$45$$$ elements in it, we can still extract another one.

For those subsequences with less than $$$45$$$ elements? Well, since it's obviously easier to get a non-degenerate triangle with closer elements if we sort that sequence, we can forcefully search all the possible combinations in subintervals in the sorted subsequence with a size of $$$6$$$, or all the consecutive subintervals with no intersections and a size of $$$3$$$.

But, if you do that without optimizations, you will get a TLE.

So how to optimize?

Add break to your code, as many as you can.

code

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By shiny_shine, history, 4 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By shiny_shine, history, 8 months ago, In English

As you know, in this reason, 64-bit C++ compilers are temporarily disabled.

In order to keep using __int128 (at least partially) in 32-bit compilers, I'm trying writing a template of the unsigned version of __int128.

On 2024/3/15, I completed writing the alpha version of it.

If you find bugs in my code, please leave a comment below. Thanks!

UPD:

2024/3/14: added (maybe) all operators that an __int128 has except for operator/ / fixed infinite-recursion bug in several operators

2024/3/15: added operator/ / fixed many bugs in almost all arithmetic operators / completed first (buggy) version of this handmade __int128

Here's it:

integer_128_impl.cpp

Full text and comments »

  • Vote: I like it
  • +19
  • Vote: I do not like it

By shiny_shine, history, 9 months ago, In English

Abstract

After I post some wrong advice and got a number of downvotes, I came up with this idea to recollect some upvotes. When I heard that Luogu will release their international version with problem statements translated with LLM, I imagined how would these models translate them.

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

By shiny_shine, history, 9 months ago, In English

Abstract

Suspend participating in Codeforces Rounds for a long time (at least a few months). During this time, try to participate in contests on other websites (AtCoder/Luogu/CodeChef or other). After that, when you participate in Codeforces Rounds again, your rating will surprisingly increase (at least for me). Here's why.

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it

By shiny_shine, history, 10 months ago, In English

Abstract

Never use reference value on std::priority_queue, otherwise it will be affected when you push in something "greater" than it.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By shiny_shine, history, 10 months ago, In English

Abstract

  1. Never apply a binary search on std::list.
  2. If you want to make a custom _Comp function for std::set , write down as many instructions to distinguish elements in the set as possible.

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By shiny_shine, history, 18 months ago, In English

There are 3 unrated contests in AtCoder after I registered my account

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it