Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

KhaustovPavel's blog

By KhaustovPavel, 6 years ago, translation, In English,

Hi, everyone!

Regular Codeforces round #273 for participants from the second division will take place on 16 October, 19:30 MSK. Participants from the first division are able to participate out of the contest.

Problem setter: KhaustovPavel (Khaustov Pavel, Russia, Tomsk, Tomsk Polytechnic University)

Special thanks to Codeforces team and, in particular, Maxim Akhmedov (zlobober) for help in round preparations and Maria Belova (Delinur) for translations.

Participants will be given five problems and two hours to solve this problems.

Points distribution: 500-1000-1500-2000-2500

UPD: +10 minutes to start

Good luck!

Read more »

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

By KhaustovPavel, 6 years ago, In English,

424A - Squats

The problem is to find the number of standing hamsters. If it is less than half, we should make the required number of hamsters standing. Otherwise we should make some hamsters sitting.

424B - Megacity

We can sort all the cities by their distance to the Tomsk city d i. After that we are to find the smallest index t for which the total population p 0 + p 1 + ... + p t >  = 106. In such case the answer is d t. We can sort all cities in O(NlogN) and find the value of t in O(N). Limits for N allow O(N 2) sorting or any other O(N 2) solution.

424C - Magic Formulas

Consider the following formulas:

Let . Lets compute the following function for each i (0 ≤ i ≤ n). One can do it in O(n) using .

Lets transform c i:

Also:

Thus:

That means, if n / i is odd, , otherwise — . c i can be computed in O(1), that's why the complexity of the whole solution — O(n).

424D - Biathlon Track

Due to the time limit for Java some of O(N 4) solution got Accepted. The authors solution has complexity O(N 3·logN). The main idea is to fix the top-border and bottom-border. Then, using some abstract data type, for each right-border we can find the most suitable left-border in O(logN) time. For example we can use set in C++ and its method lower_bound. For better understanding lets have a look at the following figure:

For such rectangle we fix the upper-border as row number 2 and bottom-border as row number 5. Also, we fix right-border as column number 6, and now we are to find some left-border. Now we can split the time value for any rectangle for two summands. One of them depends only on left-border and another one — on the right-border.

With the blue color the summand that depends only on the right-border is highlighted. With the red and yellow color — the other summand is highlighted. The red-colored value should be subtracted and the yellow-colored should be added. For any blue right-border's value we are to find the closest red-yellow left-border. That is the problem to be solved with the help of STL Set or any other similar abstract data type.

424E - Colored Jenga

A classical DP-problem on finding expected number.

Lets define some function F(S) for some state — the expected number of minutes to finish the game from this state. For each color we can compute the probability of showing this color by the simple formula , where c — the number of dice's faces of this color. Now we are to find the probability P L to stay in this state for the next minutes. That is the probabilty of showing black color plus the probabilities of showing colors with no blocks of that color to be removed from the tower. Now we can find the value via the following formula:

The only problem is to find how to encode the state. To reduce the number of states we can assume that there is only 18 different type of levels, but not 27. For better time-performance it is better to use hashing. The solution for this problem requires good understanding of DP and quite good implementing skills.

Read more »

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

By KhaustovPavel, 6 years ago, translation, In English,

Hi, everyone!

Regular Codeforces round #242 for participants from the second division will take place on 25 April, 11:00 MSK. Participants from the first division are able to participate out of the competition.

The contest is prepared by programmers from Tomsk Polytechnic University: Pavel Khaustov (KhaustovPavel), Olesya Golub (Taube), Nickolay Kuzivanov (bnick), Dmitry Savvinov (dsavvinov), Alexey Vetrov (noxwell).

Special thanks to Vladimir Chalyshev (cmd) and Alexey Dergunov (dalex) for their impact.

Also, thanks to Codeforces team and, especially, to Gerald Agapov (Gerald) and Maria Belova (Delinur).

Points distribution: 500-1000-1500-2500-3000

Good luck!

Read more »

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

By KhaustovPavel, 8 years ago, translation, In English,

Hi, everyone!

The authors of Codeforces Round #152 are am-real, max777alex and me.

Special thanks to Gerald who helped us to prepare this round. Also, we want to thank Delinur for english statements. And we'd like to thank Seyaua and sdya for reading and testing problems of this round.

The round will be held on 25th of november at 19:30 in Moscow time, and it will take place in both divisions.

Score distribution div1: 1000 1000 1500 1500 2500

Score distribution div2: 500 1000 2000 2000 2500

Contest is over.

We appologize for ambiguity in the statement of the problem A. It was not clear whether it is possible to touch the goal post when the ball crosses the goal line. However, both ways to understand the problem statement were accepted. These solutions differ by an infinitesimal amount. The only thing that this ambiguity has effected a lot — hacks. All the hacks, which were based on the assumption that such touching is impossible, will be removed. Please, those who have done these hacks inform Gerald Agapov (Gerald).

We also apologize for the interuptions and problems with statements rendering.

Far from unanimous decision of the jury, it was decided to make this round rated. The rating will be recalculated on 26/11/2012 after removing of all relevant hacks.

Read more »

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