saliii's blog

By saliii, history, 2 years ago, In English,

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

Events

There was a difficulty with 805E - Ice cream coloring/804C - Ice cream coloring. 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 - Fake NP

hint1

805B - 3-palindrome

hint1

805C - Find Amir / 804A - Find Amir

hint1
hint2

805D - Minimum number of steps / 804B - Minimum number of steps

hint1
hint2
hint3
hint4

805E - Ice cream coloring / 804C - Ice cream coloring

hint1
hint2
hint3

805F - Expected diameter of a tree / 804D - Expected diameter of a tree

hint1
hint2

804E - The same permutation

hint1
hint2
hint3

804F - Fake bullions

hint1
hint2
hint3
hint4
hint5
hint6

Solutions

Tutorial is loading...

From: Chamran, Writer: Chamran

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: Chamran, Writer: Chamran

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: Chamran, Writer: Chamran

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: MohammadJA, Writer: MohammadJA

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: Chamran, Writer: Chamran

Time Complexity:

Memory complexity:

C++

Time Complexity:

Memory complexity:

C++
Tutorial is loading...

From: MohammadJA, Writer: MohammadJA

Time Complexity:

Memory complexity:

C++
Tutorial is loading...

From: Chamran, Writer: Chamran

Time Complexity:

Memory complexity:

C++
Tutorial is loading...

From: Chamran, Writer: Hifdah

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.

Read more »

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

By saliii, 3 years ago, In English,

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.

Link

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.

Read more »

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

By saliii, 3 years ago, In English,

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.

Link

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

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

Read more »

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