Hey everyone!

At the Google Kick Start Round B 2021 I faced a very strange thing. After submitting solution for problem B "Longest Progression" I got RE on the large test. That was weird, because for my solution there was no much difference between small and large tests. But there was one static array in my solution of size (1 << 17). I double-checked that $$$N$$$ is not greater than $$$10^5$$$ in the problem statement. I had no idea, but finally I replaced the array with std::vector of dynamic size and the solution passed.

Then I submitted a question: "Some of my solutions got RE on the large test. After changing the static size of (1 << 17) which is larger than 10^5 to dynamic STL vector of size N the same solution passed this test. Probably something is wrong with the limits specified in the problem statement. Is that so?".

And the response was: "There is no problem with the limit. Please read the problem statement more carefully. Consider looking at the limits and the sample cases if those might help.".

After that I've looked at the problem statement again and the limit for $$$N$$$ was $$$3 \times 10^5$$$. I cannot believe I haven't noticed the $$$3 \times$$$ in the problem statement so many times.

Is there anyone, who faced the same problem during the contest? Or is it time for me to see a doctor?

UPD. I've finally managed to find out what happened. I've picked the wrong problem while asking a question. And for this problem the limits were initially incorrect. That explains everything except for three things:

• Why the one who responded to me haven't guessed that I'm probably talking about another problem? The was only one problem with wrong limits in the problem statement.

• How could I know that I need to refresh the problem statement (without going to questions tab)?

• What is the logic behind ordering the problems in the following order B, A, D, C at the questions tab?

Probably I expect too much from Google Kick Start, but I was left with a lot of questions.

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: pkhaustov (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!

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₀ + p₁ + ... + p_t >  = 10⁶. 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²) sorting or any other O(N²) 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⁴) solution got Accepted. The authors solution has complexity O(N³·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.

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 (pkhaustov), Olesya Golub (Taube), Nickolay Kuzivanov (Carups), 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!

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.