shiny_shine's blog

By shiny_shine, history, 8 days 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, 4 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, 5 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, 5 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, 6 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, 6 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, 14 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