Errichto's blog

By Errichto, 4 weeks ago, ,

You can download my codes to all problems here.

I will write a full editorial in the next few days. Now you can read hints and short solutions.

750B - New Year and North Pole

hint

750C - New Year and Rating

hint1
hint2

750D - New Year and Fireworks

hint1
hint2
solution

750E - New Year and Old Subsequence

hint1
hint2
hint3
hint4

750F - New Year and Finding Roots

part1
part2
part3
part4
part5

750G - New Year and Binary Tree Paths

hint1
hint2
hint3
hint4
hint5
hint6

750H - New Year and Snowy Grid

hint1
hint2

750A - New Year and Hurry

Do you see what is produced by the following piece of code?

``````int total = 0;
for(int i = 1; i <= n; ++i) {
total += 5 * i;
printf("%d\n", total);
}
``````

We iterate over problems (a variable `i` denotes the index of problem) and in a variable `total` we store the total time needed to solve them. The code above would print numbers 5, 15, 30, 50, ... — the i-th of these numbers is the number of minutes the hero would spend to solve easiest i problems.

Inside the loop you should also check if there is enough time to make it to the party, i.e. check if `total + k <= 240`.

simple C++ code:24067296
shorter but harder C++ code: 24067301
python: 24067479

750B - New Year and North Pole

Our goal is to simulate Limak's journey and to check if he doesn't make any forbidden moves. To track his position, it's enough to store one variable denoting his current distance from the North Pole. To solve this problem, you should implement checking three conditions given in the statement.

Updating `dist_from_north` variable is an easy part. Moving ti kilometers to the North increases the distance from the North Pole by ti, while moving South decreases that distance by ti. Moving to the West or East doesn't affect the distance from Poles, though you should still check if it doesn't happen when Limak is on one of two Poles — you must print "NO" in this case.

Let's proceed to checking the three conditions. First, Limak can't move further to the North if he is already on the North Pole "at any moment of time (before any of the instructions or while performing one of them)". So you should print "NO" if `direction == "North"` and either `dist_from_north == 0` or `dist_from_north < t[i]`. The latter case happens e.g. if Limak is 150 kilometers from the North Pole and is supposed to move 170 kilometers to the North — after 150 kilometers he would reach the North Pole and couldn't move further to the North. In the intended solution below you will see an alternative implementation: after updating the value of `dist_from_north` we can check if `dist_from_north < 0` — it would mean that Limak tried to move North from the North Pole. Also, you should print "NO" if `dist_from_north == 0` (i.e. Limak is on the North Pole) and the direction is West or East.

You should deal with the South Pole case in a similar way. Limak is on the South Pole when `dist_from_north == M`.

Finally, you must check if Limak finished on the North Pole, i.e. `dist_from_north == 0`.

There were two common doubts about this problem: 1) "Limak is allowed to move 40 000 kilometers to the South from the North Pole and will be again on the North Pole." 2) "Moving West/East may change the latitude (equivalently: the distance from Poles) and this problem is hard 3d geometry problem." Both doubts make sense because they come from misinterpreting a problem as: Limak looks in the direction represented by the given string (e.g. to the North) and just goes straight in that direction (maybe after some time he will start moving to the South but he doesn't care about it). What organizers meant is that Limak should be directed in the given direction at any moment of time, i.e. he should continuously move in that direction. It's a sad thing that many participants struggled with that. I should have written the statement better and I'm sorry about it.

C++ code: 24067685
python code: 24067669

750C - New Year and Rating

We don't know the initial or final rating but we can use the given rating changes to draw a plot of function representing Limak's rating. For each contest we also know in which division Limak was.

Red and blue points denote contests in div1 and div2. Note that we still don't know exact rating at any moment.

Let's say that a border is a horizontal line at height 1900. Points above the border and exactly on it should be red, while points below should be blue. Fixing the placement of the border will give us the answer (because then we will know height of all points). Let's find the highest blue point and the lowest red point — the border can lie anywhere between them, i.e. anywhere between these two horizontal lines:

Small detail: the border can lie exactly on the upper line (because rating 1900 belongs to div1) but it can't lie exactly on the lower line (because 1900 doesn't belong to div2).

The last step is to decide where exactly it's best to put the border. The answer will be 1900 + d where d is the difference between the height of the border and the height of the last point (representing the last contest), so we should place the border as low as possible: just over the lower of two horizontal lines we found. It means that the highest blue point should be at height 1899.

There is an alternative explanation. If Limak never had rating exactly 1899, we could increase his rating at the beginning by 1 (thus moving up the whole plot of the function by 1) and everything would still be fine, while the answer increased.

To implement this solution, you should find prefix sums of rating changes (what represents the height of points on drawings above, for a moment assuming that the first point has height 0) and compute two values: the smallest prefix sum ending in a div1 contest and the greatest prefix sum ending in a div2 contest. If the first value is less than or equal to the second value, you should print "Impossible" — it means that the highest blue point isn't lower that the lowest red point. If all contests were in div1, we should print "Infinity" because there is no upper limit for Limak's rating at any time (and there is no upper limit for the placement of the border). Otherwise we say that the highest blue point (a div2 contest with the greatest prefix sum) is a contest when Limak had rating 1899 and we easily compute the final rating.

O(n) code in C++: 24069564
code in C++, with binary search: 24069586

750D - New Year and Fireworks

A trivial O(2n) solution is to simulate the whole process and mark visited cells. Thanks to a low constraint for ti, a backtrack with memoization has much better complexity. Let's understand the reason.

Parts of the firework move by ti in the i-th level of recursion so they can't reach cells further than from the starting cell. That sum can't exceed n·max_t = 150. We can't visit cells with bigger coordinates so there are only O((n·max_t)2) cells we can visit.

As usually in backtracks with memoization, for every state we can do computations only once — let's think what that "state" is. We can't say that a state is defined by the current cell only, because maybe before we visited it going in a different direction and now we would reach new cells. It also isn't correct to say that we can skip further simulation if we've already been in this cell going in the same direction, because maybe it was the different level of recursion (so now next step will in in a different direction, what can allow us to visit new cells). It turns out that a state must be defined by four values: two coordinates, a direction and a level of recursion (there are 8 possible directions). One way to implement this approach is to create `set<vector<int>> visitedStates` where each vector contains four values that represent a state.

The complexity is what is enough to get AC. It isn't hard to get rid of the logarithm factor what you can see in the last code below.

If implementing the simulation part is hard for you, see the first code below with too slow exponential solution. It shows an easy way to deal with 8 directions and changing the direction by 45 degrees — you can spend a moment to hardcode changes of x and y for each direction and clockwise or counter-clockwise order and then keep an integer variable and change its value by 1 modulo 8. You can add memoization to this slow code yourself and try to get AC.

too slow O(2n) approach (TLE): 24070543
the same code with memoization (AC): 24070548
faster memoization without logarithm (AC): 24070567

750E - New Year and Old Subsequence

It's often helpful to think about an algorithm to solve some easier problem. To check if a string has a subsequence "2017", we can find the find the first '2', then to the right from that place find the first '0', then first '1', then first '7'. If in some of these 4 steps we can't find the needed digit on the right, the string doesn't have "2017" as a subsequence. To additionally check if there is a subsequence "2016", after finding '1' (before finding '7') we should check if there is any '6' on the right. Let's refer to this algorithm as Algo.

It turns out that the problem can be solved with a segment tree (btw. the solution will also allow for queries changing some digits). The difficulty is to choose what we want to store in its nodes. Let's first use the Algo to answer simpler queries: "for the given segment check if it's nice".

There is only one thing that matters for segments represented by nodes. For a segment we want to know for every prefix of "2017" (e.g. for "20"): assuming that the Algo already got this prefix as a subsequence, what is the prefix we have after the Algo processes this segment. Let's see an example.

TODO

Tutorial of Good Bye 2016

•
• +168
•

By Errichto, 4 weeks ago, ,

Hello everybody!

On December 30 at 14:05 UTC/17:05 MSK (check your time zone here) Codeforces will host the New Year's contest Good Bye 2016. The contest is combined for both divisions, lasts 2.5 hours and contains 8 problems. Thanks to Harbour.Space and Barcelona ACM-ICPC Programming Bootcamp 2017 sponsoring the contest, winners can expect really cool prizes:

• 5 best participants (not ACM ICPC veterans) will win free participation in Hello Barcelona programming bootcamp.
• 30 best participants (not ACM ICPC veterans) will receive a 30% discount for participation in Hello Barcelona programming bootcamp.
• 100 best participants will receive t-shrits by organizers and Codeforces.

Hello Barcelona programming bootcamp in collaboration with Moscow Workshops ACM ICPC is a competitive programming training camp to be held between February 6-14, 2017 at Harbour.Space University in Barcelona. Note that lecturers and coaches are: GlebsHP, MikeMirzayanov, Endagorion, Michael, Jacob and snarknews, so the camp must be valuable. The registration is open up to January 20th, 2017.

More information can be found here: http://in.harbour.space/icpc/

I'm an author of problems. I want to thank several people. MikeMirzayanov for creating Codeforces and Polygon and for allowing me to prepare this contest. GlebsHP for his help in everything (hope to work with you again!). mareksom for testing (other testers TBA). My sister for drawing. I also want to thank the Hello Barcelona organizers for providing nice prizes for you.

I'm proud of the problem set and I think that everybody will find something interesting for themselves. I tried to keep statements shorter than usually so it may be a good idea for you to read more problems and choose one that fits you. Obviously, problems will be about the New Year and a little polar bear whom you might know. Since you will face one interactive problem, please read the Interactive Problem Guide in advance.

Don't forget to register. I wish you great fun and no frustrating bugs.

UPD1: The points drop will be adjusted to the round length. It means that for submitting e.g. at the end of the contest gives the same percent of points as in usual 2-hour rounds. Also, I remind you that there will be an interactive problem (as mentioned above).

UPD2: In 750F - New Year and Finding Roots the interactor was printing neibhours in format "k t1 ... tk" instead of "k\nt1 ... tk" (in one line instead of two lines). It's my fault and I'm sorry for the inconvenience. If you were heavily affected, please write to me or GlebsHP. And thanks for noticing/guessing, Gassa!

UPD3, WINNERS

Congratulations!

Thanks for participating. If you want to know intended solutions, see the editorial (it isn't completely ready yet though). See you next time and have an awesome New Year!

Announcement of Good Bye 2016

•
• +556
•

By Errichto, 4 months ago, ,

Both a participant and a contest organizer sometimes wants to stress test their solution with the brute force. Sometimes random tests are quite weak and one needs many thousands (and sometimes millions) of them to become sure about the correctness. The thing is that running a program is quite slow itself, what may hurt if the computation part is fast. On my laptop running a C++ program with empty main() one thousand times takes 1.3s, what doesn't satisfy me. How to make it faster?

I recently prepared a problem with a binary grid (SRM 699, div1-hard TwoSquares) and I wanted to be very careful about the correctness. I wrote slow solutions in C++ and the intended one in Java. Only then I realized how slow usual stress testing is. If they all were in one language, I would quite easily get everything into one program with classes (structs) and I would just run it once, without any overheads. But since the languages were different, I had to rewrite one solution, what not only requires time, but also is a possible place for a mistake.

Does running a program on Windows take the similar amount of time? Is it possible to run a program on Ubuntu or Windows faster than in a milisecond? Given two programs in C++, how to automatically merge them into one program and test them (this feature would be awesome in Polygon I think, where stress testing is able to process only thousands of tests too)?

Regarding my last question (automatically merging two programs) some idea is to wrap everything except includes into a struct and creating one global instance of such a struct. It should be automatically zero-ed (all global variables should be 0, as the user intended).

code

The good thing is that the memory doesn't become huge if we process many tests (or does it?). But mnbvmar noticed that it won't work for `static` variables. Any way to make it work? Any other ideas?

•
• +58
•

By Errichto, 5 months ago, ,

Four participants will advance to the finals. Check the exact time.

EDIT: 15 minutes to the start.

•
• +110
•

By Errichto, 7 months ago, ,

Remember to register.

--- EDIT, the contest is over ---

BearBall, 250 points

There is a special case when all points are in one line. Otherwise, for any pair of bears the number of throws is 1 or 2.

So, for each points you should count how many points are directly reachable from this one. You achieve it by sorting other points. The complexity should be .

Proof that 2 throws are enough
code for BearBall

BearGridRect, 600 points

Hint: use flows, maybe mincost.

what graph?
code for BearGridRect

BearCircleGame, 800 points

Dynamic programming. Iterate over the number of remaining players, from n to 1. In each moment, you need an array of size with probabilities — for each number of bears what is the probability that Limak is this far from the starting bear. Then, for each bear we need probability that he loses and thus we will know the next array (for remaining - 1 remaining bears).

a loses with probability .

Try to first write O(n3) approach — find cycle in a sequence of indices a + 1 - k, a + 1 - 2k, a + 1 - 3k... and then over indices in the cycle sum up where c is the size of cycle and d says which place this index has in the cycle.

To make it faster, notice that the answer for a and for a + k will be similar. It's enough to multiply (or divide, whatever) by the sum by two, and then add one value.

code for BearCircleGame

WINNERS

1. liymsheep, who solved all three problems
2. ACRush
3. kriii

And congratulations to Petr for solving all problems and thus winning the parallel round.

•
• +66
•

By Errichto, 8 months ago, ,

680A - Медвежонок и пять карт

Iterate over all pairs and triples of numbers, and for each of them check if all two/three numbers are equal. If yes then consider the sum of remaining numbers as the answer (the final answer will be the minimum of considered sums). Below you can see two ways to implement the solution.

code1
code2

680B - Медвежонок и поиск преступников

Limak can't catch a criminal only if there are two cities at the same distance and only one of them contains a criminal. You should iterate over the distance and for each distance d check if a - d and a + d are both in range [1, n] and if only one of them has ti = 1.

code1
code2

679A - Медвежонок и простота за 100

If a number is composite then it's either divisible by p2 for some prime p, or divisible by two distinct primes p and q. To check the first condition, it's enough to check all possible p2 (so, numbers 4, 9, 25, 49). If at least one gives "yes" then the hidden number if composite.

If there are two distinct prime divisors p and q then both of them are at most 50 — otherwise the hidden number would be bigger than 100 (because for p ≥ 2 and q > 50 we would get p·q > 100). So, it's enough to check primes up to 50 (there are 15 of them), and check if at least two of them are divisors.

code1
code2, Python

679B - Медвежонок и башни из кубиков

Let's find the maximum a that a3 ≤ m. Then, it's optimal to choose X that the first block will have side a or a - 1. Let's see why.

• If the first block has side a then we are left with m2 = m - first_block = m - a3.
• If the first block has side a - 1 then the initial X must be at most a3 - 1 (because otherwise we would take a block with side a), so we are left with m2 = a3 - 1 - first_block = a3 - 1 - (a - 1)3
• If the first blocks has side a - 2 then the initial X must be at most (a - 1)3 - 1, so we are left with m2 = (a - 1)3 - 1 - first_block = (a - 1)3 - 1 - (a - 2)3.

We want to first maximize the number of blocks we can get with new limit m2. Secondarily, we want to have the biggest initial X. You can analyze the described above cases and see that the first block with side (a - 2)3 must be a worse choice than (a - 1)3. It's because we start with smaller X and we are left with smaller m2. The situation for even smaller side of the first block would be even worse.

Now, you can notice that the answer will be small. From m of magnitude a3 after one block we get m2 of magnitude a2. So, from m we go to m2 / 3, which means that the answer is O(loglog(m)). The exact maximum answer turns out to be 18.

The intended solution is to use the recursion and brutally check both cases: taking a3 and taking (a - 1)3 where a is maximum that a3 ≤ m. It's so fast that you can even find a in O(m1 / 3), increasing a by one.

code1
code2
code3

679C - Медвежонок и клетчатое поле

Let's first find CC's (connected components) in the given grid, using DFS's.

We will consider every possible placement of a k × k square. When the placement is fixed then the answer is equal to the sum of k2 the the sum of sizes of CC's touching borders of the square (touching from outside), but for those CC's we should only count their cells that are outside of the square — not to count something twice. We will move a square, and at the same time for each CC we will keep the number of its cells outside the square.

We will used a sliding-window technique. Let's fix row of the grid — the upper row of the square. Then, we will first place the square on the left, and then we will slowly move a square to the right. As we move a square, we should iterate over cells that stop or start to belong to the square. For each such empty cell we should add or subtract 1 from the size of its CC (ids and sizes of CC's were found at the beginning).

And for each placement we consider, we should iterate over outside borders of the square (4k cells — left, up, right and down side) and sum up sizes of CC's touching our square. Be careful to not count some CC twice — you can e.g. keep an array of booleans and mark visited CC's. After checking all 4k cells you should clear an array, but you can't do it in O(number_of_all_components) because it would be too slow. You can e.g. also add visited CC's to some vector, and later in the boolean array clear only CC's from the vector (and then clear vector).

The complexity is O(n2·k).

code1
code2
code3, Java

679D - Медведь и преследование

Check my code below, because it has a lot of comments.

First, in O(n3) or faster find all distances between pairs of cities.

Iterate over all g1 — the first city in which you use the BCD. Then, for iterate over all d1 — the distance you get. Now, for all cities calculate the probability that Limak will be there in the second day (details in my code below). Also, in a vector `interesting` let's store all cities that are at distance d1 from city g1.

Then, iterate over all g2 — the second city in which you use the BCD. For cities from `interesting`, we want to iterate over them and for each distinct distance from g2 to choose the biggest probability (because we will make the best guess there is).

Magic: the described approach has four loops (one in the other) but it's O(n3).

Proof is very nice and I encourage you to try to get it yourself.

Proof here
code1

679E - Медвежонок и плохие степени числа 42

The only special thing in numbers 1, 42, ... was that there are only few such numbers (in the possible to achieve range, so up to about 1014).

Let's first solve the problem without queries "in the interval change all numbers to x". Then, we can make a tree with operations (possible with lazy propagation):

• add on the interval
• find minimum in the whole tree

In a tree for each index let's keep the distance to the next power of 42. After each "add on the interval" we should find the minimum and check if it's positive. If not then we should change value of the closest power of 42 for this index, and change the value in the tree. Then, we should again find the minimum in the tree, and so on. The amortized complexity is O((n + q) * log(n) * log42(values)). It can be proved that numbers won't exceed (n + q) * 1e9 * log.

Now let's think about the remaining operation of changing all interval to some value. We can set only one number (the last one) to the given value, and set other values to INF. We want to guarantee that if t[i] ≠ t[i + 1] then the i-th value is correctly represented in the tree. Otherwise, it can be INF instead (or sometimes it may be correctly represented, it doesn't bother me). When we have the old query of type "add something to interval [a, b]" then if index a - 1 or index b contains INF in the tree then we should first retrieve the true value there. You can see that each operation changes O(1) values from INF to something finite. So, the amortized complexity is still O((n + q) * log(n) * log42(values).

One thing regarding implementation. In my solution there is "set < int > interesting" containing indices with INF value. I think it's easier to implemement the solution with this set.

code1
code2

•
• +99
•

By Errichto, 8 months ago, ,

Hello Codeforces.

The CF Round #356 will happen on 8-th June (exact time). You will get five problems to solve in two hours. The round is rated.

I encourage you to read other problems if you don't like or can't solve something. The scoring distribution will be announced.

MikeMirzayanov and GlebsHP make the round possible. Also, thanks for Stonefeang, kostka, johnasselta, AlexFetisov and (more to be added?) for their amazing help. And I want to thank my girlfriend because there would be no Limak without her.

It's my first standard round. Still, you should get nice interesting problems. You will meet Limak, who is usually a little polar bear. Here he is, preparing one of problems.

I wish you great fun and no frustrating bugs.

EDIT — It's recommended for both divisions to read the Interactive Problems Guide before the round.

EDIT2, SCORING

div2: 500-1000-1750-2250-2750
div1: 750-1250-1500-2000-2500

EDIT3

The editorial with codes is ready.

WINNERS, congratulations!

and Division 2:

Thank you all for participation and see you next time. And regards from Limak, a bear.

•
• +687
•

By Errichto, 8 months ago, ,

I'm not able to find any link. I think that this problem was used in the last day of the camp (Petrozavodsk, Winter 2015). I didn't manage to solve it during the contest and I still don't see a solution.

Given n ≤ 106, find the standard deviation (or variance) of an, with allowed precision 10 - 6. A sequence a1, a2, ..., an is generated as follows:

``````a[1] = 1
for(int i = 2; i <= n; i++) {
int j = rand(1, i-1); // random integer from interval [1, i-1]
int k = rand(1, i-1);
a[i] = a[j] + a[k];
}
``````

I'm not sure about constraints but I think it doesn't matter (I would appreciate any polynomial solution). Also, maybe the answer was required modulo some number, instead of a real number with some precision — I don't know, sorry. And yes, the expected value is n.

•
• +66
•

By Errichto, 8 months ago, ,

Hi everybody.

May Clash 2016 has just started. You have 24 hours to solve 6 problems, including an approximation one (tie breaker). The submission time doesn't matter so you can join whenever you want.

You get points for each test passed so do your best even if you can't solve the problem for the given constraints. Remember that not all tests are max-tests.

This time, problems are invented by niyaznigmatul so you can expect a very high quality of the problemset. I was a tester. Also, thanks to YakutovDmitriy and lightning for ideas for problems.

Top3 gets amazon gift cards, top5 gets t-shirts, top50 gets their handles showed in the first page of the leaderboard (I know, it's awesome).

I wish you great fun and no frustrating bugs.

WINNERS

So much red.

Top3 got nice scores in an approximation problem, congrats. Not only top5 solved all non-aproximation problems so I want to also mention fcdkbear, rajat1603 and eatmore.

Thank you for participating!

•
• +93
•

By Errichto, 9 months ago, ,

Hi everybody.

The VK Cup Round 3 is coming (exact time).

The duration will be longer than usual, likely 3 hours.

As usually in VK Cup, there will be three contests — div1, div2, official one. All of them are rated. Div1 and div2 versions are for individual participants, not for teams.

Setters are Stonefeang, Errichto and qwerty787788. I think that (some) problems are extremely interesting and I really wish I could participate. Thanks to GlebsHP and MikeMirzayanov, we wouldn't have a round without them. Also, thanks to AlexFetisov and winger for testing.

We will later inform about the final duration. Maybe we will inform about the number of problems and scoring.

I wish you great fun and no frustrating bugs. And Limak wishes you good luck!

UPD

• The contest will last 3 hours.
• ADJUSTED POINTS DROP — Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hour rounds.
• I updated testers above.
• Top50 in the "Div1 Edition" contest will get t-shirts. Have I already said "I wish I could participate"?

UPD 2

There are 9 problems. Div2 gets problems 1 - 6, and Div1+R3 gets 3 - 9. It means that there are 4 shared problems.
Division 2: 500 750 1000 1500 2250 3000
R3 & Div1: 500 1000 1750 2250 2250 3000 3000

UPD 3

Enjoy the editorial

UPD 4

The system testing is over. Congratulations to winners. Later I will try to put winners here in some nice format.

 VK Round 3 Div. 1 Div. 2 1. subscriber, tourist 1. Endagorion 1. Bus 2. eduardische, Alex_2oo8 2. eatmore 2. Herzu 3. AlexDmitriev, Kostroma 3. ikatanic 3. co_farmer 4. LHiC, overtroll 4. izrak 4. TDL9 5. KAN, vepifanov 5. rowdark 5. polingy

Announcement of VK Cup 2016 - Round 3

•
• +327
•

By Errichto, 10 months ago, ,

Codes in nicer format will be uploaded later.
658A - Медвежонок и развёрнутый Радевуш and 639A - Медвежонок и отображаемые друзьяcodes.
639B - Медвежонок и забытое дерево 3 and 639C - Медвежонок и многочленыcodes.
639D - Медвежонок и вкладcodes.
639E - Медведь и парадоксcodes.
639F - Медведь и химияcodes.

658A - Медвежонок и развёрнутый Радевуш — Iterate once from left to right to calculate one player's score and then iterate from right to left. It's generally good not to write something similar twice because you are more likely to make mistakes. Or maybe later you will find some bug and correct it only in one place. So, try to write calculating score in a function and run them twice. Maybe you will need to reverse the given arrays in some moment.

639A - Медвежонок и отображаемые друзья — You should remember all friends displayed currently (in set or list) and when you add someone new you must check whether there are at most k people displayed. If there are k + 1 then you can iterate over them (over k + 1 people in your set/list) and find the worst one. Then — remove him. The intended complexity is O(n + q*k).

639B - Медвежонок и забытое дерево 3 — You may want to write some special `if` for n = 2. Let's assume n ≥ 3. If d = 1 or d > 2h then there is no answer (it isn't hard to see and prove). Otherwise, let's construct a tree as follows.

We need a path of length h starting from vertex 1 and we can just build it. If d > h then we should also add an other path from vertex 1, this one with length d - h. Now we have the required height and diameter but we still maybe have too few vertices used. But what we built is one path of length d where d ≥ 2. You can choose any vertex on this path other than ends of the path (let's call him v), and add new vertices by connecting them all directly with v. You can draw it to see that you won't increase height or diameter this way. In my code I sometimes had v = 1 but sometimes (when d = h) I needed some other vertex and v = 2 was fine.

639C - Медвежонок и многочлены, my favorite problem in this contest. Let's count only ways to decrease one coefficient to get the required conditions (you can later multiply coefficient by  - 1 and run your program again to also calculate ways to increase a coefficient).

One way of thinking is to treat the given polynomial as a number. You can find the binary representation — a sequence with 0's and 1's of length at most . Changing one coefficient affects up to consecutive bits there and we want to get a sequence with only 0's. We may succeed only if all 1's are close to each other and otherwise we can print 0 to the output. Let's think what happens when 1's are close to each other.

Let's say that we got a sequence with two 1's as follows: ...00101000.... Decreasing by 5 one coefficient (the one that was once in a place of the current first bit 1) will create a sequence of 0's only. It's not complicated to show that decreasing coefficients on the right won't do a job (because the first 1 will remain there) but you should also count some ways to change coefficients on the left. We can decrease by 10 a coefficient on the left from first 1, or decrease by 20 a coefficient even more on the left, and so on. Each time you should check whether changing the original coefficient won't exceed the given maximum allowed value k.

One other solution is to go from left to right and keep some integer value — what number should be added to the current coefficient to get sum equal to 0 on the processed prefix. Then, we should do the same from right to left. In both cases maybe in some moment we should break because it's impossible to go any further. In one case it happens when we should (equally) divide an odd number by 2, and in the other case it happens when our number becomes too big (more than 2·109) because we won't be able to make it small again anyway.

639D - Медвежонок и вклад — It isn't enough to sort the input array and use two pointers because it's not correct to assume that the optimal set of people will be an interval. Instead, let's run some solution five times, once for each remainder after dividing by 5 (remainders 0, 1, 2, 3, 4). For each remainder r we assume that we should move k people to some value x that (and at the end we want at least k people to have contribution x). Note that x must be close to some number from the input because otherwise we should decrease x by 5 and for sure we would get better solution. The solution is to iterate over possible values of x from lowest to highest (remember that we fixed remainder ). At the same time, we should keep people in 5 vectors/lists and do something similar to the two pointers technique. We should keep two pointers on each of 5 lists and always move the best among 5 options. The complexity should be O(n·5).

639E - Медведь и парадокс — It's good to know what to do with problems about optimal order. Often you can use the following trick — take some order and look at two neighbouring elements. When is it good to swap? (When does swapping them increase the score?) You should write some simple formula (high school algebra) and get some inequality. In this problem it turns out that one should sort problems by a fraction and it doesn't depend on a constant c. There may be many problems with the same value of and we can order them however we want (and the question will be: if there is a paradox for at least one order). Let's call such a set of tied problems a block.

For each problem you can calculate its minimum and maximum possible number of granted points — one case is at the end of his block and the other case is to solve this problem as early as possible so at the beginning of his block. So, for fixed c for each problem we can find in linear time the best and worst possible scores (given points).

When do we get a paradox? Where we have two problems i and j that pi < pj (pi was worth less points) we solved problem i much earlier and later we got less points for problem pj. We can now use some segment tree or sort problems by pi and check whether there is a pair of problems with inequalities we are looking for — pi < pj and maxi > minj where maxi and minj we found in the previous paragraph.

We can do the binary search over the answer to get complexity or faster. Can you solve the problem in linear time?

639F - Медведь и химия — Task is about checking if after adding some edges to graph, some given subset of vertices will be in one biconnected component. Firstly, let's calculate biconnected components in the initial graph. For every vertex in each query we will replace it with index of its bicon-component (for vertices from subset and for edges endpoints). Now we have a forest. When we have a list of interesting vertices in a new graph (bicon-components of vertices from subset or edges) we can compress an entire forest, so it will containg at most 2 times more vertices than the list (from query) and will have simillar structure to forest. To do it, we sort vertices by left-right travelsal order and take LCA of every adjacent pair on the sorted list. If you have compressed forest, then you just have to add edges and calculate biconnected components normally, in linear time.

Tutorial of VK Cup 2016 - Round 1

•
• +104
•

By Errichto, 10 months ago, ,

Problems ABCG will be described better soon.

problem A — watch out for test like "1 1 1 2 2 2 2 3 3 3". It shows that it's not enough to sort number and check three neighbouring elements. You must remove repetitions. The easier solution is to write 3 for-loops, without any sorting. Do you see how?

problem B — you should generate all 6n possible starting strings and for each of them check whether you will get "a" at the end. Remember that you should check two first letters, not last ones (there were many questions about it).

653C - Медвежонок, взлёты и падения — Let's call an index i bad if the given condition about ti and ti + 1 doesn't hold true. We are given a sequence that has at least one bad place and we should count ways to swap two elements to fix all bad places (and not create new bad places). The shortest (so, maybe easiest) solution doesn't use this fact but one can notice that for more than 4 bad places the answer is 0 because swapping ti and tj can affect only indices i - 1, i, j - 1, j.

With one iteration over the given sequence we can find and count all bad places. Let x denote index of the first bad place (or index of some other bad place, it's not important). We must swap tx or tx - 1 with something because otherwise x would still be bad. Thus, it's enough to consider O(n) swaps ~-- for tx and for tx - 1 iterate over index of the second element to swap (note that "the second element" doesn't have to be bad and samples show it). For each of O(n) swaps we can do the following (let i and j denote chosen two indices):

1. Count bad places among four indices: i - 1, i, j - 1, j. If it turns out that these all not all initial bad places then we don't have to consider this swap — because some bad place will still exist anyway.
2. Swap ti and tj.
3. Check if there is some bad place among four indices: i - 1, i, j - 1, j. If not then we found a correct way.
4. Swap ti and tj again, to get an initial sequence.

Be careful not to count the same pair of indices twice. In the solution above it's possible to count twice a pair of indices (x - 1, x) (where x was defined in the paragraph above). So, add some `if` or do it more brutally — create a set of pairs and store sorted pairs of indices there.

TODO — add codes.

CHALLENGE — can you solve this problem if the initial sequence is already nice (if it doesn't have bad places)?

653D - Медвежья доставка — invented and prepared by lewin, also the editorial.

Java code: 16825205
C++ code solving also the harder version: 16825257

Let's transform this into a flow problem. Here, we transform "weight" into "flow", and each "bear" becomes a "path".

Suppose we just want to find the answer for a single x. We can do this binary search on the flow for each path. To check if a particular flow of F is possible, reduce the capacity of each edge from ci to . Then, check if the max flow in this graph is at least x. The final answer is then x multiplied by the flow value that we found.

MUCH HARDER VERSION — you are also given an integer k (1 ≤ k ≤ 104) and your task is to find the answer for x paths, for x + 1 paths, ..., and for x + k - 1 paths. There should be k real values on the output.

The solution of the harder version.

653E - Медвежонок и забытое дерево 2

C++ code: 16826422

You are given a big graph with some edges forbidden, and the required degree of vertex 1. We should check whether there exists a spanning tree. Let's first forget about the condition about the degree of vertex 1. The known fact: a spanning tree exists if and only if the graph is connected (spend some time on this fact if it's not obvious for you). So, let's check if the given graph is connected. We will do it with DFS.

We can't run standard DFS because there are maybe O(n2) edges (note that the input contains forbidden edges, and there may be many more allowed edges then). We should modify it by adding a set or list of unvisited vertices s. When we are at vertex a we can't check all edges adjacent to a and instead let's iterate over possible candidates for adjacent unvisited vertices (iterate over s). For each b in s we should check whether a and b are connected by a forbidden edge (you can store input edges in a set of pairs or in a similar structure). If they are connected by a forbidden edge then nothing happens (but for each input edge it can happen only twice, for each end of edge, thus O(m) in total), and otherwise we get a new vertex. The complexity is where is from using set of forbidden edges.

Now we will check for what degree of vertex 1 we can build a tree. We again consider a graph with n vertices and m forbidden edges. We will first find out what is the minimum possible degree of vertex 1 in some spanning tree. After removing vertex 1 we would get some connected components and in the initial graph they could be connected to each other only with edges to vertex 1. With the described DFS we can find c (1 ≤ c ≤ n - 1) — the number of created connected components. Vertex 1 must be adjacent to at least one vertex in each of c components. And it would be enough to get some tree because in each component there is some spanning tree — together with edges to vertex 1 they give us one big spanning tree with n vertices (we assume that the initial graph is connected).

And the maximum degree of vertex 1 is equal to the number of allowed edges adjacent to this vertex. It's because more and more edges from vertex 1 can only help us (think why). It will be still possible to add some edges in c components to get one big spanning tree.

So, what is the algorithm? Run the described DFS to check if the graph is connected (if not then print "NO"). Remove vertex 1 and count connected components (e.g. starting DFS's from former neighbours of vertex 1). Also, simply count d — the number of allowed edges adjacent to vertex 1. If the required degree k is between c and d inclusive then print "YES", and otherwise print "NO".

653F - Бумажная работа — invented and prepared by k790alex, also the editorial.

Java code (modify-SA-solution): 16821422
C++ code (compressing-solution): 16826803

There are two solutions. The first and more common solution required understanding how do SA (suffix array) and LCP (longest common prefix) work. The second processed the input string first and then run SA+LCP like a blackbox, without modifying or caring about those algorithms.

Modify-SA-solution — The main idea is to modify the algorithm for computing the number of distinct substrings using SA + LCP.

Let query(L, R) denote the number of well formed prefixes of substring(L, R). For example, for substring(L, R) = "(())()(" we would have query(L, R) = 2 because we count (()) oraz (())().

How to be able to get query(L, R) fast? You can treat the opening bracket as  + 1 and the ending bracket as  - 1. Then you are interested in the number of intervals starting in L, ending not after R, with sum on the interval equal to zero. Additionally, the sum from L to any earlier right end can't be less than zero. Maybe you will need some preprocessing here, maybe binary search, maybe segment trees. It's an exercise for you.

We can iterate over suffix array values and for each suffix we add query(suffix, N) - query(suffix, suffix + LCP[suffix] - 1) to the answer. In other words we count the number of well formed substrings in the current suffix and subtract the ones we counted in the previous step.

The complexity is but you could get AC with very fast solution with extra .

Compressing-solution — I will slowly compress the input string, changing small well-formed substrings to some new characters (in my code they are represented by integer numbers, not by letters). Let's take a look at the example:

or equivalently:

Whenever I have a maximum (not possible to expand) substring with single letters only, without any brackets, then I add this substring to some global list of strings. At the end I will count distinct substrings in the found list of strings (using SA+LCP). In the example above I would first add a string "a" and later I would add "baa". Note that each letter represents some well formed substring, e.g. 'b' represents (()) here.

I must make sure that the same substrings will be compressed to the same letters. To do it, I always move from left to right, and I use trie with map (two know what to get from some two letters).

problem G — you can consider each prime number separately. Can you find the answer if there are only 1's and 2's in the input? It may be hard to try to iterate over possible placements of the median. Maybe it's better to think how many numbers we will change from 2^p to 2^{p+1}.

•
• +66
•

By Errichto, 10 months ago, ,

Hi everybody.

The IndiaHacks finals will take place tomorrow (on Saturday). The contest is being organized by HackerEarth. Just after the official finals, the CF round will start (check-your-time) with almost the same problems. You can treat it as a standard CF round — there will be 5 problems in each of 2 divisions, and 2 hours to solve them. Two divisions will compete together on the problem set with 7 problems, with 2 hours to solve them.

I want to especially thank I_love_Tanya_Romanova for testing the problems, GlebsHP for help with making the CF round possible, and MikeMirzayanov for his awesome attitude and for the Polygon system. Setters: lewin, k790alex, Sokolov, Errichto. Testers: I_love_Tanya_Romanova, Errichto. Small help: belowthebelt, raviojha2105, johnasselta, Stonefeang. And my big thanks to HackerEarth for inviting me to Bangalore, it's truly a vibrant city.

Some info only for 40 official finalists — Remember not to discuss anything until the CF round ends (so, at least 2 hours after the official contest ends). You will find all important information at link-to-the-contest. You can ask me questions by PM on CF or on HE, and I will put answers in the "Challenge Details" at the link provided. Do not use comments here because it can only confuse others. You can use some old blog about the IndiaHacks semifinals if you want to discuss something.

I wish you great fun and no frustrating bugs. Enjoy the contest.

Scoring: 500-1000-1500-2000-2500-3500-3500.

WINNERS

1. TooDifficuIt, the only one to solve all 7 problems!
2. izrak
3. jcvb
4. andrew.volchek
5. ikatanic

In the official finals there were technical issues with the stack size (it was again only 8MB) and constraints in E weren't correct at the beginning. We want to fix it as much as possible, without any guessing though — we can't say how much time did you waste because of something. If you were affected then write to me PM with the description of the situation. Your time penalties will be canceled (and maybe some earlier submission will be accepted, if only the stack size didn't allow you to get AC).

Editorial is being created here.

•
• +197
•

By Errichto, 11 months ago, ,

If you don't know what the dynamic scoring is, you can read about it here. In my opinion it's a useful alternative. With smoother steps (250 instead of 500) it doesn't work so bad. Or does it? The main advantage is that organizers don't have to correctly estimate the difficulty. What are drawbacks? And should it be changed and improved in some way?

•
• +87
•

By Errichto, 11 months ago, ,

Hi. I want to invite you to HourRank 6. The contest will take place tomorrow (exact time) on the HackerRank platform. The duration is exactly one hour. I think that both beginners and experienced participants will find problems interesting for them.

There are problems from me and from forthright48. I want to thank stonefeang for helping me with preparing problems, and for testing. I also thank malcolm, wanbo and Shafaet for testing and the technical help.

Limak needs you! I wish you great fun and no frustrating bugs. Looking forward to seeing you!

Besides fun, top 10 will get HR t-shirts. Good luck.

WINNERS

•
• +67
•

By Errichto, 11 months ago, ,

It happened to me twice to skip a CF round because of the registration. Once I was too late, and once I even implemented A and tried to submit — but it turned out I haven't registered. It also happened to some of my friends.

For standard CF rounds the registration ends 5 minutes before the contest. The reason is that participants must be divided into rooms, to be able to hack. But hacking isn't so important, right? It's some extra possibility and many would enjoy a round even without hacks.

Let's allow participating without having a room. All people registered at least 5 minutes before should be assigned to rooms as usually. And after that, one should be able to register "out of room" — to participate without hacking and being hacked. A round should be rated for everybody. So, one could register after reading problems, and maybe even after implementing something.

Note that hacks are only a privilege. It's good to be hacked instead of getting WA on systests, and it's good to be able to hack others. So, it will be optimal to register before a round, if possible.

Does anybody see any drawbacks? If not, then make this change please. @CF_TEAM

•
• +382
•

By Errichto, 12 months ago, ,

Hi again.

Tomorrow (exact time) the Semifinals of IndiaHacks-Algorithms will start — link. You can participate only if you got any points in at least one of qualifiers. You will get 24 hours and 10 problems, including an approximation one to break ties. The submitting time doesn't matter unless you have a tie in an approximation problem (very unlikely).

In my opinion problems are unusually interesting. They were prepared by kostya_by, k790alex, and by me. Thanks for johnasselta and belowthebelt for helping me with testing and checking everything.

Top20 Indians advance to onsite finals. Top20 non-Indians advance to finals but will participate remotely, still fighting for prizes. Finals will happen somewhen in March.

I wish you great fun and no frustrating bugs. Looking forward to seeing you! Below, you can see prizes for top contestants in the final round.

WINNERS OF THE SEMIFINALS

And congratulations for all advancing to the final round. The unofficial list of advancers is in the comments below.

•
• +55
•

By Errichto, 12 months ago, ,

Good morning everybody.

January Clash '16 will start tomorrow (check your time zone). Duration is 24 hours and submitting time doesn't matter so you can join whenever you want.

Note the unusual starting time (compared to previous Clashes). We moved it a bit because of colliding with Facebook Hacker Cup.

You will be given 5 algorithmic problems and one approximate (optimization) one. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves. Getting full points on all 5 problems should be hard for everyone. Remember to solve as many subtasks as possible if you want to get to the top.

Problems were prepared by lewin. He is an author of numerous contests, including many SRM's on TopCoder (link) so you don't have to worry about the quality of the problem set. I am a tester and an editorialist.

Problems are interesting and so do smaller subtasks. Don't expect them to be very easy though — some of them are far from being straightforward. Anyway, solve them first if you don't see a 100-points-solution.

There are prizes — t-shirts and Amazon gift cards. And the eternal glory of course.

Enjoy a contest.

WINNERS

Congratulations:

I want to congratulate anta for solving the hardest problem and Egor for almost solving it — but well, he won anyway. Kostroma had the best score in an approximate problem and HellKitsune was very close to that.

What was your approach to an approximate problem?

•
• +66
•

By Errichto, 13 months ago, ,

Hello Codeforces!

HackerEarth invites you to a unique Artificial Intelligence type contest — Bot Challenge. The contest will start on January 8, 3:30 PM MSK and will last for almost a week.

You have to build a bot that plays a two-player game (like Tic-tac-toe or Chess) with a bot built by another user. Your bot has to read what happens and play (print) its moves against the opponent. At the end of challenge, your bot will be played in a tournament against all other bots, and the bot that wins the tournament will be declared the winner.

Also, while the contest is running, you can challenge other people who have submitted their bots to play against you.

Register at https://www.hackerearth.com/bot-challenge-india-hacks-2016/ and fight for prizes:

You can practice in previous Bot contests(#1 and #2), to understand more about the problem statement and the format of the contest. Gullesnuffs won last two Bot challenges. Will you allow him to take the first place again?

You can check out this gameplay between Gullesnuffs and uwi in one of previous Bot challenges. Hit the replay button there and just watch it.

This challenge is a part of IndiaHacks 2016 tracks. Don't miss qualifications for the other track — algorithms. Check out date of the next qualification round at the link provided. I'm responsible for the final round (problems will be prepared by many setters though) — 24 hours, 10 problems, including an approximate one. And the same set of prizes!

Participate and have fun!

•
• +62
•

By Errichto, 13 months ago, ,

611A - New Year and Days

There are two ways to solve this problem.

The first is to hard-code numbers of days in months, check the first day of the year and then iterate over days/months — http://ideone.com/4TYPCc

The second way is to check all possible cases by hand. The 2016 consists of 52 weeks and two extra days. The answer for "x of week" will be either 52 or 53. You must also count the number of months with all 31 days and care about February. http://ideone.com/Bf9QLz

611B - New Year and Old Property

Each number with exactly one zero can be obtained by taking the number without any zeros (e.g. 6310 = 1111112) and subtracting some power of two, e.g. 6310 - 1610 = 1111112 - 100002 = 1011112. Subtracting a power of two changes one digit from '1' to '0' and this is what we want. But how can we iterate over numbers without any zeros? It turns out that each of them is of form 2x - 1 for some x (you can check that it's true for 6310).

What should we do to solve this problem? Iterate over possible values of x to get all possible 2x - 1 — numbers without any zeros. There are at most values to consider because we don't care about numbers much larger than 1018. For each 2x - 1 you should iterate over powers of two and try subtracting each of them. Now you have candidates for numbers with exactly one zero. For each of them check if it is in the given interval. You can additionally change such a number into binary system and count zeros to be sure. Watch out for overflows! Use '1LL << x' instead of '1 << x' to get big powers of two. http://ideone.com/Kfu8sF

611C - New Year and Domino

How would we solve this problem in O(wh + q) if a domino would occupy only one cell? Before reading queries we would precalculate dp[r][c] — the number of empty cells in a "prefix" rectangle with bottom right corner in a cell r, c. Then the answer for rectangle r1, c1, r2, c2 is equal to dp[r2][c2] - dp[r2][c1 - 1] - dp[r1 - 1][c2] + dp[r1 - 1][c1 - 1]. We will want to use the same technique in this problem.

Let's separately consider horizontal and vertical placements of a domino. Now, we will focus on horizontal case.

Let's say that a cell is good if it's empty and the cell on the right is empty too. Then we can a place a domino horizontally in these two cells. The crucial observation is that the number of ways to horizontally place a domino is equal to the number of good cells in a rectangle r1, c1, r1, c2 - 1.

You should precalculate a two-dimensional array hor[r][c] to later find the number of good cells quickly. The same for vertical dominoes. http://ideone.com/wHsZej

611D - New Year and Ancient Prophecy

By {x... y} I will mean the number defined by digits with indices x, x + 1, ..., y.

Let dp[b][c] define the number of ways to split some prefix (into increasing numbers) so that the last number is {b... c} We will try to calculate it in O(n2) or . The answer will be equal to the sum of values of dp[i][n] for all i.

Of course, dp[b][c] = 0 if digit[b] = 0 — because we don't allow leading zeros.

We want to add to dp[b][c] all values dp[a][b - 1] where the number {a... b - 1} is smaller than {b... c}. One crucial observation is that longer numbers are greater than shorter ones. So, we don't care about dp[a][b - 1] with very low a because those long numbers are too big (we want {a... b - 1} to be smaller than our current number {b... c}). On the other hand, all a that (b - 1) - a < c - b will produce numbers shorter than our current {b... c}. Let's add at once all dp[a][b - 1] for those a. We need . Creating an additional array with prefix sums will allow us to calculate such a sum in O(1).

There is one other case. Maybe numbers {a... b - 1} and {b... c} have the same length. There is (at most) one a that (b - 1) - a = c - b. Let's find it and then let's compare numbers {a... b - 1} and {b... c}. There are few ways to do it.

One of them is to store hashes of each of n·(n + 1) / 2 intervals. Then for fixed a, b we can binary search the first index where numbers {a...} and {b... } differ. http://ideone.com/Rrgk8T. It isn't an intended solution though. Other way is to precalculate the same information for all pairs a, b with dynamic programming. I defined nxt[a][b] as the lowest x that digit[a + x] ≠ digit[b + x]. Now, either nxt[a][b] = nxt[a + 1][b + 1] + 1 or nxt[a][b] = 0. http://ideone.com/zczsc3

611E - New Year and Three Musketeers

The answer is  - 1 only if there is some criminal stronger than a + b + c. Let's deal with this case and then let's assume that a ≤ b ≤ c.

Let's store all criminal- s in a set (well, in a multiset). Maybe some criminals can be defeated only by all musketeers together. Let's count and remove them. Then, maybe some criminals can be defeated only by b + c or a + b + c (no other subsets of musketeers can defeat them). We won't use a + b + c now because it's not worse to use b + c because then we have the other musketeer free and maybe he can fight some other criminal. Greedily, let's remove all criminals which can be defeated only by b + c and at the same time let a defeat as strong criminals as possible. Because why would he rest?

Now, maybe some criminals can be defeated only by a + c or b + c or a + b + c. It's not worse to use a + c and to let the other musketeer b defeat as strong criminals as possible (when two musketeers a + c fight together).

We used a + b + c, b + c, a + c. We don't know what is the next strongest subset of musketeers. Maybe it's a + b and maybe it's c. Previous greedy steps were correct because we are sure that .

Now in each hour we can either use a, b, c separately or use a + b and c. Let's say we will use only pair a + b and c. And let's say that there are x criminals weaker than a + b and y criminals weaker than c. Then the answer is equal to . The explanation isn't complicated. We can't be faster than because we fight at most two criminals in each hour. And maybe e.g. y (because c is weak) so c will quickly defeat all y criminals he can defeat — and musketeers a + b must defeat x - y criminals.

Ok, we know the answer in O(1) if we're going to use only a + b and c. So let's assume it (using only these two subsets) and find the possible answer. Then, let's use a, b, c once. Now we again assume that we use only a + b and c. Then we use a, b, c once. And so on.

What we did is iterating over the number of times we want to use a, b, c. http://ideone.com/R3Oy3F

611F - New Year and Cleaning

Let's not care where we start. We will iterate over robot's moves.

Let's say the first moves are LDR. The very first move 'L' hits a wall only if we started in the first column. Let's maintain some subrectangle of the grid — starting cells for which we would still continue cleaning. After the first move our subrectangle lost the first column. The second move 'D' affects the last row. Also, all cells from the last row of our remaining subrectangle have the same score so it's enough to multiply the number of cells there and an index of the current move. The third move 'R' does nothing.

Let's simulate all moves till our subrectangle becomes empty. To do it, we should keep the current x, y — where we are with respect to some starting point. We should also keep maxx, maxy, minx, miny — exceeding value of one of these four variables means that something happens and our subrectangle losts one row or one column.

But how to do it fast? You can notice (and prove) that the second and and each next execution of the pattern looks exactly the same. If we have pattern RRUDLDU and the first letter 'U' affects out subrectangle in the second execution of the pattern, then it will also affect it in the third execution and so on. If and only if.

So, we should simalate the first n moves (everything can happen there). Then, we should simulate the next n moves and remember all places where something happened. Then we should in loop iterate over these places. Each event will decrease width or height of our subrectangle so the complexity of this part is O(w + h). In total O(w + h + n). http://ideone.com/xrU9u2

CHALLENGE FOR PROBLEM F (CLEANING ROBOT) — I was considering an alternative version of this problem, harder one. The same constraint for n but this time h, w ≤ 109. Describe a solution in comments and optionally implement it (it should get AC on this problem, right?). I will mention here the first person to solve this challenge.

611G - New Year and Cake

We are given a polygon with vertices P1, P2, ..., Pn. Let Poly(i, j) denote the doubled area of a polygon with vertices Pi, Pi + 1, Pi + 2, ..., Pj - 1, Pj. While implementing you must remember that indices are in a circle (there is 1 after n) but I won't care about it in this editorial.

We will use the cross product of two points, defined as A × B = A.x·B.y - A.y·B.x. It's well known (and you should remember it) that the doubled area of a polygon with points Q1, Q2, ..., Qk is equal to Q1 × Q2 + Q2 × Q3 + ... + Qk - 1 × Qk + Qk × Q1.

Let smaller denote the area of a smaller piece, bigger for a bigger piece, and total for a whole polygon (cake).
smaller + bigger = total
smaller + (smaller + diff) = total
diff = total - 2·smaller (the same applies to doubled areas)
And the same equation with sums:
where every sum denotes the sum over possible divisions.

In O(n) we can calculate total (the area of the given polygon). So, the remaining thing is to find and then we will get (this is what we're looking for).

For each index a let's find the biggest index b that a diagonal from a to b produces a smaller piece on the left. So, .

To do it, we can use two pointers because for bigger a we need bigger b. We must keep (as a variable) the sum S = Pa × Pa + 1 + ... + Pb - 1 × Pb. Note that S isn't equal to Poly(a, b) because there is no Pb × Pa term. But S + Pb × Pa = Poly(a, b).

To check if we should increase b, we must calculate Poly(a, b + 1) = S + Pb × Pb + 1 + Pb + 1 × Pa. If it's not lower that then we should increase b by 1 (we should also increase S by Pb × Pb + 1). When moving a we should decrease S by Pa × Pa + 1.

For each a we have found the biggest (last) b that we have a smaller piece on the left. Now, we will try to sum up areas of all polygons starting with a and ending not later than b. So, we are looking for Z = Poly(a, a + 1) + Poly(a, a + 2) + ... + Poly(a, b). The first term is equal to zero but well, it doesn't change anything.

Let's talk about some intuition (way of thinking) for a moment. Each area is equal so the sum of cross products of pairs of adjacent (neighboring) points. We can say that each cross product means one side of a polygon. You can take a look at the sum Z and think — how many of those polygons have a side PaPa + 1? All b - a of them. And b - a - 1 polygons have a side Pa + 1Pa + 2. And so on. And now let's do it formally:

Poly(a, a + 1) = Pa × Pa + 1 + Pa + 1 × Pa
Poly(a, a + 2) = Pa × Pa + 1 + Pa + 1 × Pa + 2 + Pa + 2 × Pa
Poly(a, a + 3) = Pa × Pa + 1 + Pa + 1 × Pa + 2 + Pa + 2 × Pa + 3 + Pa + 3 × Pa
...
Poly(a, b) = Pa × Pa + 1 + Pa + 1 × Pa + 2 + Pa + 2 × Pa + 3 + ... + Pb - 1 × Pb + Pb × Pa

Z = Poly(a, a + 1) + Poly(a, a + 2) + ... + Poly(a, b) =
= (b - a)·(Pa × Pa + 1) + (b - a - 1)·(Pa + 1 × Pa + 2) + (b - a - 2)·(Pa + 2 × Pa + 3) + ... + 1·(Pb - 1 × Pb) +
+ Pa + 1 × Pa + Pa + 2 × Pa + ... + Pb × Pa

The last equation is intentionally broken into several lines. We have two sums to calculate.

1. The first sum is (b - a)·(Pa × Pa + 1) + (b - a - 1)·(Pa + 1 × Pa + 2) + ... + 1·(Pb - 1 × Pb). We can calculate it in O(1) if we two more variables `sum_product` and `sum_product2`. The first one must be equal to the sum of Pi × Pi + 1 for indices in an interval [a, b - 1] and the second one must be equal to the sum of (Pi × Pi + 1)·(i + 1). Then, the sum is equal to `sum_product * (b + 1) - sum_product2`.

2. The second sum is Pa + 1 × Pa + Pa + 2 × Pa + ... + Pb × Pa = SUM_POINTS × Pa where SUM_POINTS is some fake point we must keep and SUM_POINTS = Pa + 1 + Pa + 2 + ... + Pb. So, this fake point's x-coordinate is equal to the sum of x-coordinates of Pa + 1, Pa + 2, ..., Pb and the same for y-coordinate. In my code you can see variables `sum_x` and `sum_y`.

Implementation. http://ideone.com/RUY5lF

611H - New Year and Forgotten Tree

There are at most k = 6 groups of vertices. Each grouped is defined by the number of digits of its vertices.

It can be probed that you can choose one vertex (I call it "boss") in each group and then each edge will be incident with at least one boss. We can iterate over all kk - 2 possible labeled trees — we must connect bosses with k - 1 edges. Then we should add edges to other vertices. An edge between groups x and y will "kill" one vertex either from a group x or from a group y. You can solve it with flow or in O(2k) with Hall's theorem. http://ideone.com/7KuS1l

Tutorial of Good Bye 2015

•
• +184
•

By Errichto, 13 months ago, ,

Hi everybody.

The last round of the 2015 will take place on the 30-th of December (starting time). The contest will last 3 hours.

It won't be a usual round. Both divisions will compete together. You will get 8 problems to solve in 3 hours. Points will decrease slower than usually — otherwise you would get eps for solving a problem at the end. Scoring will be announced just before a contest. So will the speed of the points/minute loss.

My goal was to provide you a diverse problemset with interesting problems for all contestants. During a contest you should consider reading not only the next problem but the few next ones.

You will get this round thanks to work of many people. I am a problem setter. GlebsHP helps me with everything (a lot). AlexFetisov, johnasselta and Zlobober are testers (thanks guys!). Delinur translates everything into Russian. Last but not least, MikeMirzayanov provides two awesome platforms — CF and Polygon. And there are so many people involved in Codeforces. Thank you all.

Let me give you more motivation to compete. The New Year is coming for Limak and he needs your help! Limak is a little polar bear by the way. You will help him, won't you?

I wish you great fun and no frustrating bugs. Looking forward to seeing you!

SCORING

Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hours rounds. Points for problems are 500-750-1250-1750-2500-2500-3000-3500. Enjoy the last contest in this year!

EDITORIAL

Instead of refreshing standings you can read an editorial. I will keep polishing it.

WINNERS

I'm amazed by the number of high-rated participants today. Fight was really tough and winners truly deserve respect.

It was the last Codeforces round in the 2015. Thanks for participating. And kudos for Mike for creating CF.

I wish you all an awesome year. Let the 2016 be (even) better than the passing year. Cheers.

Announcement of Good Bye 2015

•
• +1387
•

By Errichto, 13 months ago, ,

Hello Codeforces Community!

I invite you to December Clash 2015. It will take place on Dec, 19-th at 9:30 MSK. Duration is 24 hours and submitting time doesn't matter so you can start whenever you want.

You will be given 5 algorithmic problems and one approximate (optimization) one. Some problems should be hard even for very strong competitors. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves.

EDIT — Problems are not necessarily sorted by the difficulty! Each problem is worth 100 points but scoring is partial so try to pass as many tests as possible! There is no penalty for incorrect submissions.

In my opinion problems are interesting and I hope you will have nice time solving them. It shouldn't be a typing competition for anybody. I'm very curious about the number of people with all 5 problems solved and about your scores in an approximate problem. We'll see.

I want to thank Akul Sareen (akulsareen) for his amazing help as a tester. He will also provide you editorials after a contest. And big thanks to HackerEarth admins — Arjit Srivastava (belowthebelt) and Ravi Ojha (raviojha2105).

Enjoy problems!

Oh, and there prizes. 5 T-shirts and 3 Amazon gift cards for the best participants. I guess it will make a fight for top spots a bit more interesting.

The contest is over! I hope you enjoyed it. Congratulations for top5, good job.

1. mugurelionut
2. marcin_smu
3. LayCurse
4. zeliboba
5. Carsten Eilks (HE account)

Is it a coincidence that top6 has nicely distributed scores? Roughly, the i-th place has score 510 - 10i.

•
• +53
•

By Errichto, 14 months ago, ,

Div2

Codes for all Div2 problems

BearSong (250p.)

There are two ways to solve this problem. The first way is to create an array T of size 1000 to count occurrences of each note. For each number x in the given sequence we should do `T[x]++`. After that, we should iterate over T and count the number of indices with value 1.

There is an alternative O(N2) solution. For each element of the given sequence we can iterate over other elements to check whether some of them is equal to the current one.

BearSlowlySorts (500p.)

Again, there are two ways to solve a problem. The first one is quite boring. One could notice that the answer must be small and we can simulate first few moves in any possible way. Some extra observation is that after sorting the first N-1 we shouldn't sort them again in the next move. So we should either do moves in the order {first, last, first, last, ...} or {last, first, last, first, ...} — there are only two possibilities.

With some cases analysis you can find solve this problem even without sorting. The crucial observation is that we care mostly about the smallest number and the largest one.
- The answer is 0 only if the sequence is already sorted.
- If the first number is the smallest one (thus, we don't have to move it), then the answer is 1.
- If the last number is the largest one, the answer is 1.
- If the first number is unfortunately the largest and the last number is the smallest one, the answer is 3.
- Otherwise, we can sort a sequence in 2 moves.

BearPermutations2 (1000p.)

O(N4) solutions should get AC but I will describe a O(N2) solution. We want to find an answer for all n up to given N.

For fixed n let's iterate over all n possible places to put the smallest number. Let where denote an index of the smallest number. The smallest number divides n numbers into two almost independent groups A and B and the equation |A| + |B| + 1 = n holds (moreover, |A| = where - 1, |B| = n - where). There are ways to divide numbers into two groups. For fixed division of numbers and for fixed position of the smallest number in A there are (|A| - 1)!·|B|! ways to arrange numbers. Note that it doesn't matter what "position of the smallest number in A" we chose.

For nonempty A and B for any arrangement the difference between indices of the smallest numbers in A and in B could be written as a sum of two terms:
- the difference between an index of the smallest number in B and a value where defined before. Note that such a distance is in interval [1, |B|].
- the difference between where and an index of the smallest number in A

Calculating the two terms above separately allows us to calculate everything for A and for B separately. Now, we can sum up for all so it's enough to add to the result. There is |A| - 1 because the smallest elements is chosen and placed already. More details in my code.

Div1

Codes for all Div1 problems

BearCavalry (300p.)

For each horse let's assume that it is assigned to Bravebeart and let's calculate the number of ways to assign other horses to other warriors.

For each case let's sort all other warriors and all other horses. With two pointers we can find for each warrior what horses he can get (it's limited by the strength of the Bravebeart's unit). We now know the number of ways (let a denote it) to assign a horse to the strongest warrior. He takes one horse and it was one of the horses the next (second strongest) warrior could get. We calculated that the second strongest warrior can take one of b horses but one was taken so he can b - 1 possibilities. The third warrior could take c horses but two are taken so we multiply some variable (result for this case) by c - 2. And so on. For each case we should add a·(b - 1)·(c - 2)·... to the result.

BearPermutations (600p.)

Read the Div2-Hard editorial first. The task there was to sum up scores for the given N.

In O(N4·S2) we could do the following dynamic programming. dp[n][where][S] is the number of n-permutations with the smallest number in position (index) where and the score equal to S. The main line of our program would be:

``````dp[n1+n2+1][n1+1][S1+S2 + n1+1+where2 - where1] +=  binom[n1+n2][n1] * dp[n1][where1][S1] * dp[n2][where2][S2]
``````

We can notice that terms S2 and where2 appear only in one dimension of the resulting dp[][][]. The same for S1 and where1. Thus, we can create an array dpLeft[n][sw] to store the sum of dp[n][where][s] that where - s = sw. Similarly, we should create an array dpRight[n][sw]. You can additionally notice that these two arrays are similar and we need only one of them.

BearGirls (1000p.)

Backwards dynamic programming. What is hard to calculate is f(k, r) denoting the expected value of the r-th biggest number among k randomly chosen ones. It turns out to be simple to calculate because f(k, r) = p·f(k + 1, r + 1) + (1 - pf(k + 1, r) for . Don't be misled by words "simple to calculate". It took me literally weeks to solve this problem and I don't say that it is easy to find the formula above.

Looks like binomial coefficient, right? And this is how we can prove its correctness. When we have k numbers and the r-th biggest one is marked, we can still add other numbers one by one. The new number will be greater with probability . You can find my code above.

You may wonder why there was some cost given. The problem would be fine without it but well written O(N3) solution could be squeezed to pass then.

•
• +139
•

By Errichto, 15 months ago, ,

Good morning, Codeforces.

On Sunday, Nov 8-th at 11:30 MSK the ACM ICPC training (link) will be hosted on HackerEarth. Gather your team up to 3 members and try to solve as many problems as you can (and solve them fast).

You will be provided 10-12 problems to solve in 5 hours. Problems are of decent difficulty, hard enough for any contestants. My more precise estimation is that there is not more than one team in the world able to solve all problems in 2-3 hours. Of course, beginners will find something interesting too.

Poland has an acm-preparing camp right now so you will compete with all Polish teams going to CERC. Rumors say that all(?) Croatians will be present too. Some more countries for which one warm-up is not enough? (Don't miss the official CERC warm-up, starting one hour from now — link.)

All people, teams and countries are invited to participate. Though there are some small-ish prizes for top European teams! (that's why you can see a word "Europe" in the contest's name)

ACM rules apply. Binary scoring, 20 minutes, one computer per team, teams up to 3 members. To be more precise: a team can't use two computers at any moment of time. You can code in some different places though — you must communicate then e.g. using some chat (yes, you can use chat at the same time).

Finally, I want to mention all people involved in the preparation. For setting problems thanks and maybe praise go to: akulsareen, allllekssssa, dalex, desert97, k790alex, Mex-Mans, raghumdani, Shaikhitdin, Sokolov, Xellos. For their patience: belowthebelt, raviojha2105. For writing the longest announcement in the world, for talking, and for testing things: Errichto. Finally, you will be provided editorials by pkacprzak — he is the next reason to participate because (as far as I know and read) he provides awesome editorials.

Btw. at least some of problems are nice in my humble opinion.

EDIT: We know about collisions but it's impossible to avoid them all. This date was the best possible choice.

•
• +86
•

By Errichto, 15 months ago, ,

HackerEarth will host the ACM ICPC Practice contest in the first half of November. You can remember the recent easier contest focused on Indian teams. This one will be focused on European teams and those can win small prizes. I am a coordinator and tester.

As you can guess by title, we are looking for problems, especially the hard ones. Write me PM and we will discuss your ideas (likely by gchat). Write problems in brief, no need to invent story now. You can propose one problem, you can propose 5 of them. No need to be experienced ;)

Cheers!

UPD: Thanks guys! No more proposals needed.