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:

1. Egor
2. Kostroma
3. HellKitsune
4. anta
5. akashdeep
6. ishraq

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?

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!

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. 63₁₀ = 111111₂) and subtracting some power of two, e.g. 63₁₀ - 16₁₀ = 111111₂ - 10000₂ = 101111₂. 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 2^x - 1 for some x (you can check that it's true for 63₁₀).

What should we do to solve this problem? Iterate over possible values of x to get all possible 2^x - 1 — numbers without any zeros. There are at most values to consider because we don't care about numbers much larger than 10¹⁸. For each 2^x - 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(n²) 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 max_x, max_y, min_x, min_y — 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 ≤ 10⁹. 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 P₁, P₂, ..., P_n. Let Poly(i, j) denote the doubled area of a polygon with vertices P_i, P_i + 1, P_i + 2, ..., P_j - 1, P_j. 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 Q₁, Q₂, ..., Q_k is equal to Q₁ × Q₂ + Q₂ × Q₃ + ... + Q_k - 1 × Q_k + Q_k × Q₁.

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 = P_a × P_a + 1 + ... + P_b - 1 × P_b. Note that S isn't equal to Poly(a, b) because there is no P_b × P_a term. But S + P_b × P_a = Poly(a, b).

To check if we should increase b, we must calculate Poly(a, b + 1) = S + P_b × P_b + 1 + P_b + 1 × P_a. If it's not lower that then we should increase b by 1 (we should also increase S by P_b × P_b + 1). When moving a we should decrease S by P_a × P_a + 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 P_aP_a + 1? All b - a of them. And b - a - 1 polygons have a side P_a + 1P_a + 2. And so on. And now let's do it formally:

Poly(a, a + 1) = P_a × P_a + 1 + P_a + 1 × P_a
Poly(a, a + 2) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a
Poly(a, a + 3) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a + 3 + P_a + 3 × P_a
...
Poly(a, b) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a + 3 + ... + P_b - 1 × P_b + P_b × P_a

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

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

1. The first sum is (b - a)·(P_a × P_a + 1) + (b - a - 1)·(P_a + 1 × P_a + 2) + ... + 1·(P_b - 1 × P_b). 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 P_i × P_i + 1 for indices in an interval [a, b - 1] and the second one must be equal to the sum of (P_i × P_i + 1)·(i + 1). Then, the sum is equal to sum_product * (b + 1) - sum_product2.

2. The second sum is P_a + 1 × P_a + P_a + 2 × P_a + ... + P_b × P_a = SUM_POINTS × P_a where SUM_POINTS is some fake point we must keep and SUM_POINTS = P_a + 1 + P_a + 2 + ... + P_b. So, this fake point's x-coordinate is equal to the sum of x-coordinates of P_a + 1, P_a + 2, ..., P_b 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 k^k - 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(2^k) with Hall's theorem. http://ideone.com/7KuS1l

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.

1. tourist
2. Petr
3. Egor
4. rng_58
5. black_horse2014
6. step5
7. I_love_Tanya_Romanova
8. bmerry
9. W4yneb0t
10. V--o_o--V

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.

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.

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(N²) 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(N⁴) solutions should get AC but I will describe a O(N²) 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(N⁴·S²) 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 - p)·f(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(N³) solution could be squeezed to pass then.

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, mexmans, asteri, nezametdinov, 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.

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.

Sorry for long testing queues and timeouts. I hope it won't repeat.

Congratulations for the winners — tourist, Petr, Egor, and snuke. They managed to solve all three problems!

Thanks for helping Limak again. What do you think about problems? Feedback will be appreciated.

Div2

250, BearPaints — Iterate over one side of desired blue rectangle and in constant time calculate maximum possible second side. code

500, BearDartsDiv2 — Iterate over three numbers. For found value of a*b*c we must know how many times it occurs in some suffix of a sequence. We need an array or a map. code

1000, BearDestroysDiv2 — Dynamic programming with bitmasks, O(2^W·H·W). Iterate over cells in the given order (first row, then second row and so on) and consider all possible state of the next W + 1 cells. code

Div1

300, BearCries — Dynamic programming in O(N³). dp[i][A][B] where A is number of started emoticons already with at least one underscore (ready for being closed by second semicolon) and B is number of started emoticons with single semicolon only (without underscores). code

500, BearDarts — Rewrite given condition as t[a] / t[b] = t[d] / t[c]. Use map of pairs — irreducible fractions. code

900, BearDestroys — Problem would be easier with small W and big H. But it can be proved that we can consider Limak's walk in some other order, diagonal by diagonal:

1247..
358..
69..

Now we can use the same technique as in div2hard to get complexity O(2^H·H·W). code

Hello Codeforces Community!

I invite you to October Easy '15 on first day of October at 19:00 MSK. Contest will be of difficulty similar to div2 CF round. Will you manage to solve all 6 problems in 3 hours? Will anybody do it in 1 hour?

Problems will be given in random order. Each problem is worth 100 points but scoring is partial so try to pass as many tests as possible!

I want to thank Arjit Srivastava (belowthebelt) for his great help with HackerEarth's system and website. And big thanks go to Akul Sareen (akulsareen) — it was so nice to work with him. He is a tester and editorials' writer. I hope I will work again with these two guys.

Enjoy problems!

Easy — BearCharges

Did you help Limak, a little bear? Each base is a vertex and all vertices (except 0) should have a parent — base from which this one was captured. So we are looking for a tree but not exactly MST because for a vertex order of his children matters.

Let dp[mask][x] denote time needed to capture all bases in set defined by mask if we start with base x. We will calculate dp[S][a] by iterating over possible first son of a and over bitmask denoting set of vertices in subtree of a — so consider to which base b we shoot first and what bases will be captured directly or indirectly by b. dp[S][a] = min(dp[S][a], dist(a, b) + max(dp[A][a], dp[S - A][b]))

It is O(3ⁿ·n²) but you can get easier implementation with O(4ⁿ + 3ⁿ·n²) — check out my code.

Med — LuckyGrid

Let's assume n > 1. Note: by line I mean row or column.

The only possible lucky sums of lines are 44, 47, 74, 77, 444, 447. For n ≠ 11 there are exactly 0 or 2 lucky sums possible to get (e.g. only 74 and 77). Then for fixed n we have condition e.g. "sums should be 74 or 77" and it is equivalent to "in a line there should be x or x + 1 fours" — and we want to maximize number of fours.

We should solve this new problem with a flow. It's possible to solve it with "bounded flow" (I haven't heard of it before) but I will describe solution with MinCost. For all lines there could be some fours already in the grid so we count them and we know how many more fours should this line have. From S to each vertex denoting row we add two edges:
1. minimum capacity we want, cost 0
2. capacity 1, cost C where C is some big constant (I had 10⁵).
Similarly for edges from vertices denoting columns to T. And ofc. we add unit edges from each vertex to each column if there is empty cell. Now we run MinCostFlow and thanks to C we know number of used edges of each kind, ie. cost / C is number of used edges with cost C.

What about n = 11? I did some cases analysis and solved it with bipartite matching only but one can run algo described mincost multiple times — for each line we set desired number of fours as either 44 - 47 or 74 - 77.

my implementation

Hard — SubRectangles

Let's say H2 = W2 = 4. You can see that t[1][1] - t[5][1] = t[1][5] - t[5][5]. Then we can deduce that for each pair (a, b) where 0 ≤ a, b < 4 one of two holds:
1. t[x][y] = t[x + 4][y] if x%4 = a and y%4 = a
2. t[x][y] = t[x][y + 4] if x%4 = a and y%4 = a
For all possible ways to assign types to 16 cells we will calculate result and sum them up. So we consider 2¹⁶ bitmasks.

For first type of cells (with condition t[x][y] = t[x + 4][y]) we should set all cells of this type in first four columns — columns on the right will be the same. We should do it in such a manner that numbers of tokens in 1-st, 5-th, 9-th, ... rows are equal. The same for 2-nd, 6-th, ... and so on. Let's look at first set of rows (1-st, 5-th, ...). We should iterate over number of tokens we want to put in this "type" of rows. For each value we sum/multiply up some binomial coefficient powered up to number of rows of this type. E.g. for H = 14 there are 4 rows in this group, so if we have 2 possible cells here (number of lighten bits in bitmask) and we want to put 1 token in each row, then we have bin(2, 1)⁴. The same for the second direction but with some inclusion-exclusion formula. You can read my implementation.

Div2B — Bear and Three Musketeers

Warriors are vertices and "knowing each other" is an edge. We want to find connected triple of vertices with the lowest sum of degrees (and print sum - 6 because we don't want to count edges from one chosen vertex to another).

Brute force is O(n³). We iterate over all triples a, b, c and consider them as musketeers. They must be connected by edges (they must know each other). If they are, then we consider sum of their degrees.

We must notice that there is low limit for number of edges. So instead of iterating over triples of vertices we can iterate over edges and then iterate over third vertex. It gives us O(n² + nm) and it's intended solution. To check if third vertex is connected with other two, you should additionally store edges in 2D adjacency matrix.

It's also possible to write it by adding "if" in right place in brute forces to get O(n² + nm). Check it out in code.

Div1A — Bear and Poker

Any positive integer number can be factorized and written as 2^a·3^b·5^c·7^d·....

We can multiply given numbers by 2 and 3 so we can increase a and b for them. So we can make all a and b equal by increasing them to the same big value (e.g. 100). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal. Code

Alternative solution is to calculate GCD of given numbers. Answer is "YES" iff we can get each number by multiplying GCD by 2 and 3. Otherwise, some number had different power of prime number other than 2 and 3. Code

Div1B — Bear and Blocks

In one operation the highest block in each tower disappears. So do all blocks above heights of neighbour towers. And all other blocks remain. It means that in one operation all heights change according to formula h_i = min(h_i - 1, h_i - 1, h_i + 1) where h₀ = h_n + 1 = 0. By using this formula two times we get height after two operations: h_i = max(0, min(h_i - 2, h_i - 1 - 1, h_i - 2, h_i + 1 - 1, h_i + 2)) and so on. From now I will omit max(0, ...) part to make it easier to read.

After k operations we get h_i = min(Left, Right) where Left = min(h_i - j - (k - j)) = min(h_i - j + j - k) for and Right is defined similarly. h_i becomes zero when Left or Right becomes zero. And Left becomes zero when k = min(h_i - j + j) — we will find this value for all i. If you are now lost in this editorial, try to draw some test and analyze my formulas with it.

For each i we are looking for min(h_i - j + j). We can iterate over i from left to right keeping some variable best:

best = min(best, h[i]);
best is answer for i;
best++;

We should to the same for Right and take min(Left, Right) for each i. Then final answer is maximum over answers for i. Code

Div1C — Bear and Drawing

Let's consider a tree already drawn on a strip of paper. Let's take first vertex on the left and last vertex on the right (in case of two vertices with the same x, we choose any of them). There is a path between them. Let's forget about vertices not on this path. A path divides a strip into 1D regions.

What can be added to the main path? Only simple paths attached to it with one edge. So it can be one of the following structures — Y-letter or Line:

Note that Y-letter can have long legs but its central part can have only one edge.

How to check if given tree is a path + Y-letters + Lines? First, let's move from each leaf till we have vertex with degree at least 3, marking vertices as deleted. We don't mark last vertex (that with degree at least 3) as deleted but we increase his number of legs. Finally, for each not-deleted vertex we count his not-deleted neighbours for which degree - min(legs, 2) > 1 — otherwise this neighbour is start of Line or Y-letter. Each vertex on the main path can have at most two neighbours that also belong to the main path. There can be more neighbours but they must be in Lines or Y-letters — that's why we didn't count them. So answer is "No" iff for some vertex we counted more than two neighbours. Code

Div1D — Bear and Cavalry

Let's sort warriors and horses separately (by strength). For a moment we forget about forbidden assignments. Inversion is a pair of warriors that stronger one is assigned to weaker horse. We don't like inversions because it's not worse to assign strong warriors to strong horses: A·B + a·b ≥ A·b + B·a for A ≥ a and B ≥ b. Note that repairing an inversion (by swapping assigned horses) decreases number of inversions — prove it by yourself (drawing a matching with intersections could be helpful). Without any restrictions the optimal matching is when we assign i-th warrior to i-th horse (indexed after sorting) — to get no inversions.

Let's go back to version with forbidden connections. We have n disjoint pairs which we can't use. We will prove that there exists an optimal assignment where (for all i) i-th warrior is assigned to j-th horse where |i - j| ≤ 2.

Let's take an optimal assignment. In case of ties we take the one with the lowest number of inversions. Let's assume that i is assigned to i + 3. There are at least 3 warriors j > i assigned to horses with indices lower than i + 3. So we have at least 3 inversions with edge from i to i + 3 (warriors on the left, horses on the right):

Above, connection warrior-horse is an edge. Then inversions are intersections. Swapping horses for warriors i and j (where j belongs so some red edge) would decrease number of inversions and it wouldn't decrease a score. We took an optimal assignment so it means that it's impossible to swap horses for them. Hence, for each red edge we can't change pair (black, read) into the following blue edges:

So one of these blue edges is forbidden. Three red edges generate three pairs of blue edges and in each pair at least one blue edge must be forbidden. Note that all six blue edges are different. All blue edges are incident to warrior i or to horse i + 3 but only one forbidden edge can be incident to warrior i and only one forbidden edge can be incident to horse i + 3. We have at most two forbidden edges incident to them so it can't be true that three blue edges are forbidden.

By cases analysis we can prove something more — that there can be only three possible types of connecting in an optimal assignment. First type: i can be connected to i. Second: warrior i with horse i + 1 and warrior i + 1 with horse i. Third: warriors i, i + 1 and i + 2 are connected with horses i, i + 1, i + 2.

It gives us O(nq) solution with calculating queries independently with dp[i] defined as "what result can we get for assigning everything with indices lower than i?". To calculate dp[i] we must know dp[i - 3], dp[i - 2] and dp[i - 1]. It wasn't intended solution because we can get better complexity.

We can create a segment tree and for intervals we should keep info "result we can get for this interval with 0/1/2 first and 0/1/2 last elements removed". For an interval we keep matrix 3x3 and actualizing forbidden edge for single i consists of: 1. calculating values of 3x3 matrix for a small interval with i 2. actualizing a tree with times multiplying matrices

Complexity is .

Div1E — Bear and Bowling

FIRST PART — greedy works

We will add (take) elements to a subsequence one by one. Adding number x, when we have k - 1 taken numbers on the left, increases result by k·x + suf where suf is sum of taken numbers on the right. Let's call this added value as the Quality of element x.

We will prove correctness of the following greedy algorithm. We take element with the biggest Quality till there are no elements left. For every size of a subsequence (number of taken elements) we will get optimal score.

(lemma) If a_i > a_j and i < j, we won't take a_j first.

Proof. Let's consider a moment when we don't fulfill the lemma for the first time. If there are no taken numbers between a_i and a_j, we have Q_i = k·a_i + suf > k·a_j + suf = Q_j so a_i is a better choice. For taken numbers between a_i and a_j — each number x changes Q_i by x and Q_j by a_j. We'll see that x > a_j so Q_i will remain greater than Q_j. If a_i > x, the lemma (fulfilled till now) says that x wasn't taken before a_i — it can't be true because x is taken and a_i is not. So indeed x ≥ a_i > a_j.

Let's assume that our greedy strategy is not correct. Let's consider first moment when we take some element a_j and for some s we can't get optimal subsequence with size s by taking more elements (using any strategy). Let A denote a set of elements taken before. So there is no way to add some more elements to set A + a_j and achieve optimal score with size s. But it was possible just before taking a_j so there is a subset of remaining elements B that |A + B| = s and set A + B is the best among sets with size s. Note that B can't be empty.

(case 1 — B contains at least one element on the left from a_j) Let a_i denote last element from B that i < j (here "last" means "with the biggest i"). Our strategy wanted a_j before elements from B so we know from lemma that a_i ≤ a_j. It will turn out that replacing a_i with a_j (in set A + B) doesn't decrease the score so taking a_j is acceptable. Note that replacing an element with another one doesn't change size of a set/subsequence.

In moment of choosing a_j it had the biggest quality so then Q_j ≥ Q_i. Now in A + B there are new elements, those in B. Let's imagine adding them to A (without a_i and a_j). Each new element x on the right change both Q_i and Q_j by x. Elements on the left change Q_i by a_i and Q_j by a_j (note that a_i ≤ a_j). And there are no elements between a_i and a_j. Now, taking a_i would give us set A + B but Q_j remains not less than Q_i so we can take a_j instead.

(case 2 — B contains only elements on the right from a_j) Similarly, we can replace a_i with closest a_j from set B. As before, elements on the right change Q_i and Q_j by the same value.

SECOND PART — how to implement it

First, let's understand solution. We divide a sequence into Parts. When choosing the best candidate in a Part, we want to forget about other Parts. It's enough to remember only x and suf — number of taken elements on the left (in previous Parts) and sum of elements on the right (in next Parts). x affects choosing the best element in a Part, suf doesn't (but we need this constant to add it to result for best candidate). For a Part we want to have hull with linear functions of form a_i·x + b. With binary search we can find the best element in and then construct new hull for this Part in .

We can remove from complexity. First, binary search can be replaced with pointers — for each Part initially we set a pointer at the beginning of Part. To find best candidate in Part, we slowly move pointer to the right (by one). Complexity is amortized . And we can sort linear functions a_i·x + b by angle only once because value a_i doesn't change — then constructing a hull is only . Note that when rebuilding a hull, we must set pointer to the beginning of Part.

So we have . Code.

There are other two correct lemmas to speed your solution up. We can take all positive numbers first (it's not so easy to prove). And we can stop when taken number doesn't increase score — next taken numbers won't increase score neither.

Hello Codeforces community!

Codeforces Round #318 (for both divisions) will take place on August, 29 at 19:30 MSK. It is the Thanks-Round devoted to Russian Code Cup. You will be given 5 problems and 2 hours to solve them. Scoring will be announced close to the round. I strongly recommend you to read all problems.

RussianCodeCup is the largest open programming competiton for Russian-speaking participants by Mail.Ru Group. Its history started in 2011. And since the first championship RCC offers great problems and generous prizes. This year finals will be held on September, 19th. Wish good luck to all the finalists! Thank you, RussianCodeCup, for your gift on the 5th anniversary of Codeforces!

I am honoured to be a problem setter for this round. I wouldn't do it alone. I want to thank Zlobober for his great help with problems preparation and MikeMirzayanov (and all people working on Codeforces and Polygon) for this awesome site. It's an amazing place to learn and compete. My big thanks to winger and AlexFetisov for their help with testing a round. And to Delinur for translating statements. As you see, not only a setter creates a round.

It's my first Codeforces round but not my first problems here. You can check out A, C and D from VK Cup 2015 — Round 2. Also you might remember some of my problems in TC rounds. I'm very happy with finally preparing a full round for Codeforces and I hope you will enjoy it. I tried my best to prepare nice and diverse problemset, you will judge it. In all problems you will have to help Limak who is quite unusual bear.

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

UPD: Scoring is 500-1000- 1750 -2000-2500 in div1 and 500-1000-1500-2000- 2750 in div2. Enjoy a round!

UPD: Editorial

UPD: Contest is over. The winners:

Div1:

1. Marcin_smu
2. mnbvmar
3. subscriber
4. LoneFox
5. Shef

Div2:

1. cescmentation_folch (5 problems solved!)
2. fhxb520630 (5 problems solved!)
3. bugCollector
4. Sehnsucht
5. okaduki1

And note from an author. There were some wrong solutions passing. Sorry for that. I tried my best to create strong tests but I failed a bit. Did you like this round? What do you think about problems?

Thanks for participating!

You can find editorial here. Sorry for technical troubles with challenging. What do you think about problems? Which did you enjoy, which do you hate?

--UPDATE--

broadcast: The match will be rated, and challenge results will stand. However, if you feel you were personally affected negatively/unfairly, please message tkirchner@appirio.com, and I will consider individual requests. (I have some limited ability to confirm that individuals had issues)

Today will be CF #313. I will take part in it and I will do at least 20*sqrt(max(0,myRatingLoss)) push-ups in 24h. Wish me good luck.

Usually A,B,C from Div1 are C,D,E from Div2. I solved such a shared problem during a contest and later I wanted to read my code again. So I went to "PROBLEMSET" and chose that task (it was green!). But page with statement didn't show my submission. It seems my submission is attached to div1-version of problem and "PROBLEMSET" page shows shared tasks as div2 ones. It is a bit uncomfortable.

Later I found my code (I chose right d1-contest from list of all contests) and from curiosity I tried to submit my solution by page with d2-version. As I've expected it gave me +1 to problemset standings (number of solved tasks).

I think it is something to be fixed.

Btw. thanks Mike (and other people working on CF) for such an amazing platform! :)