### saliii's blog

By saliii, history, 6 years ago,

We were waiting several weeks to setting this contest and hope the problem was good enough.

#### Events

There was a difficulty with 805E - Раскраска мороженого/804C - Раскраска мороженого. A little bug in the checker fortunately yields accepting an incorrect solution of only one person during the contest. I should apologize all of you because of this.

For this sentence, Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph. You can find the meaning of "connected subgraph" with connected and subgraph, thus it can be empty as it is more logical. How ever, I should apologize all of the participants because of weak sample tests in the statement.

I will write the full editorial in the few next days, now some hints and short solutions exist here.

## Hints

805A - Не NP

hint1

805B - 3-палиндром

hint1
hint1
hint2
hint1
hint2
hint3
hint4
hint1
hint2
hint3
hint1
hint2

804E - Та же перестановка

hint1
hint2
hint3

804F - Фальшивые слитки

hint1
hint2
hint3
hint4
hint5
hint6

# Solutions

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

python3
C++

From: saliii, Writer: saliii

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++

From: saliii, Writer: saliii

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

C++

Time Complexity:

Memory complexity:

C++

Time Complexity:

Memory complexity:

C++

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

C++

From: saliii, Writer: amsen

Time Complexity:

Memory complexity:

Java8
C++
C++

As my good friend, Arpa, did, let me share with you a perfect poem of one of our best poet you might know, Molavi:

.......................................................................................بند بگسل، باش آزاد ای پسر ** چند باشی بند سیم و بند زر

O son,  burst thy chains and be free! How long wilt thou be a bondsman to silver and gold?

.......................................................................................گر بریزی بحر را در کوزه‌‌ای ** چند گنجد قسمت یک روزه‌‌ای‌‌

If thou pour the sea into a pitcher,  how much will it hold? One day's store.

..................................................................................... کوزه‌‌ی چشم حریصان پر نشد ** تا صدف قانع نشد پر در نشد

The pitcher,  the eye of the covetous,  never becomes full:  the oyster - shell is not filled with pearls until it is contented.

.............................................................................. هر که را جامه ز عشقی چاک شد ** او ز حرص و عیب کلی پاک شد

He (alone) whose garment is rent by a (mighty) love is purged entirely of covetousness and defect.

• +81

By saliii, 6 years ago,

I appreciate if anyone can help me share his good problems of POIs, just list them in the comments and I'll check them all.

Given a string S of size n. We define as follows:

In other hand, is a set of sizes of periods A such that S = AAA...AB(B is a prefix of A).

Now, we want to create the minimum lexicographically string C of size n such that .

There are k such tests.

1 ≤ k ≤ 20, 1 ≤ n ≤ 250000

________________
3
ABIABUABIAB
BABBAB
BABURBAB
________________
01001101001
010010
01000010
________________


Some of hints only make a good look and may not solve the problem. When you look in that way, you'll come close to the solution. And if you didn't look in that way, you won't get the next hints and you'll get confused in 13 spoilers.

hint1
hint2

Some problem just used this idea : 526D - Om Nom and Necklace

hint3
hint4

Tell me if you come up with a easier and shorter answer, I'll become glad.

Code

Hope you enjoy the problem :) and it helped you.

• -19

By saliii, 6 years ago,

I appreciate if anyone can help me share his good problems of POIs, just list them in the comments and I'll check them all.

We are given a set of positive integers A. Consider a set of non-negative integers B, such that a number x belongs to B if and only if x is a sum of some elements from A(the elements may be repeated).

Given A and an integer q. Then q integers Bi, determine whether it belongs to B or not. (YES=>"TAK", NO=>"NIE")

n ≤ 5000,  Ai ≤ 50000,  q ≤ 10000,  Bi ≤ 1000000000

Ai < Ai + 1

___________________
3
2 5 7
6
0 1 4 12 3 2
___________________
TAK
NIE
TAK
TAK
NIE
TAK
___________________

hint1
hint2
hint3
code

Seems There is another approach coding it.

code
Problems like this:

You can see next great problem here Maybe these problems helps someone!!!

• -3