278B - New Problem

The total number of different strings of 2 letters is 26² = 676, but the total length of the input strings is no more than 600. It means that the length of answer is no more than 2. So just check all the strings of length 1 and 2.

277A - Learning Languages

Build bipartite graph with n nodes for employees and m nodes for languages. If an employee initially knows a language, than there will be an edge between corresponding nodes. Now the problem is simple: add the minimal number of edges in such a way, that all the n employees will be in the same connected component. Obviously, this number equals to the number of initially connected components, containing at least one employee, minus one. But there is one exception (pretest #4): if initially everyone knows no languages, we'll have to add n edges, because we can't add the edges between employees (remember that the graph is bipartite).

277B - Set of Points

For m = 3, n = 5 and m = 3, n = 6 there is no solution.

Let's learn how to construct the solution for n = 2m, where m ≥ 5 and is odd. Set up m points on a circle of sufficiently large radius. This will be the inner polygon. The outer polygon will be the inner polygon multiplied by 2. More precisely (1 ≤ i ≤ m):

If m is even, construct the solution for m + 1 and then delete one point from each polygon. If n < 2m, delete 2m - n points from the inner polygon.

Unfortunately, this solution doesn't work for m = 4, n = 7 and m = 4, n = 8.

Another approach is to set up m points on a convex function (for example, y = x² + 10⁷), and set up the rest n - m points on a concave function (for example, y =  - x² - 10⁷). Take a look at rng_58's solution — 3210150.

277C - Game

At first, notice that horizontal and vertical cuts are independent. Consider a single horizontal line. It contains m unit segments. And in any game state it's always possible to decrease the number of uncut units as the player wants. Imagine, that she starts growing a segment from a border, increasing it's length by 1 at a time. Each time the total uncut length decreases by either 0 or 1. In the end it obviously reaches 0.

The same holds for vertical lines as well. So if there are no initial cuts, the game is a nim with n - 1 piles of m stones and m - 1 piles of n stones. Could be solved with simple formula.

Initial k cuts should be just a technical difficulty. For any vertical/horizontal line, which contains at least one of the cuts, it's pile size should be decreased by the total length of all segments on this line.

How to make a first move in nim: let res is the result of state (grundy function), and a_i is the size of the i-th pile. Then the result of the game without i-th pile is . We want to replace a_i with some x, so that . Obviously, the only possible . The resulting solution: find a pile for which , and decrease it downto .

277D - Google Code Jam

Suppose we have fixed set of inputs that we have to solve. Let's learn how to determine the optimal order. Obviously, Small inputs (and Large inputs with probFail = 0) won't fail in any case. It means that our penalty time is no less than submission time of last such ``safe'' inputs. So we will solve such inputs before all the others. Inputs with probFail = 1 are just a waste of time, we won't solve such inputs. Now we have only inputs with 0 < probFail < 1. Let i and j be two problems that we are going to solve consecutively at some moment. Let's check, if it is optimal to solve them in order i, j, or in reversed order. We can discard all the other inputs, because they don't affect on the relative order of these two.

(timeLarge_i + timeLarge_j)(1 - probFail_j) + timeLarge_i(1 - probFail_i)probFail_j < (timeLarge_i + timeLarge_j)(1 - probFail_i) + timeLarge_j(1 - probFail_j)probFail_i

 - probFail_j·timeLarge_j - timeLarge_i·probFail_j·probFail_i <  - probFail_i·timeLarge_i - timeLarge_j·probFail_i·probFail_j

timeLarge_i·probFail_i(1 - probFail_j) < timeLarge_j·probFail_j(1 - probFail_i)

timeLarge_i·probFail_i / (1 - probFail_i) < timeLarge_j·probFail_j / (1 - probFail_j)

Now we've got a comparator for sort, which will give us the optimal order. Note, that inputs with probFail = 0, 1 will be sorted by the comparator correctly as well, so it's not a corner case.

Let's return to the initial problem. First of all, sort problems with the optimal comparator (it's clear that any other order won't be optimal by time, and the score doesn't depend on the order). Calculate the DP: z[i][j] = pair of maximal expected total score and minimal expected penalty time with this score, if we've already decided what to do with the first i problems, and we've spent j real minutes from the contest's start. There are 3 options for the i-the problem:

1. skip: update z[i + 1][j] with the same expected values

2. solve the Small input: update z[i + 1][j + timeSmall_i], the expected total score increases by scoreSmall_i, and the expected penalty time increases by timeSmall_i (we assume that this input is solved in the very beggining of the contest)

3. solve both inputs: update z[i + 1][j + timeSmall_i + timeLarge_i], the expected total score increases by scoreSmall_i + (1 - probFail_i)scoreLarge_i, and the expected penalty time becomes timeSmall_i + (1 - probFail_i)(j + timeLarge_i) + probFail_i·penaltyTime(z[i][j]), where penaltyTime(z[i][j]) is the expected penalty time from DP

The resulting answer is the best of z[n][i], (0 ≤ i ≤ t).

The expected total score could be a number around 10¹² with 6 digits after decimal point. So it can't be precisely stored in double. And any (even small) error in calculating score may lead to completely wrong expected time (pretest #7). For example, you can multiply all the probabilities by 10⁶ and store the expected score as integer number to avoid this error.

277E - Binary Tree on Plane

If there is no "binary" restriction, the solution is simple greedy. Each node of the tree (except the root) must have exactly 1 parent, and each node could be parent for any number of nodes.

Let's assign for each node i (except the root) such a node p_i as a parent, so that y_pi > y_i and distance between i and p_i is minimal possible. Renumerate all the nodes in order of non-increasing of y. Now it's clear that p_i < i (2 ≤ i ≤ n). So we've just built a directed tree with all the arcs going downwards. And it has minimal possible length.

Let's recall the "binary" restriction. And realize that it doesn't really change anything: greedy transforms to min-cost-max-flow on the same distance matrix as edge's costs, but each node must have no more than 2 incoming flow units.

Hi everyone!

Codeforces Round #170 begins soon, and I'll be the problem setter. I hope many people will be happy to solve all the problems.

UPD: The scoring is dynamic. The problems are sorted by increasing of estimated difficulty.

And the standard part: thanks to Gerald for his help with the problems, Seyaua and sdya for testing the contest, Delinur for translations, MikeMirzayanov for building the Codeforces platform.

Good luck!

UPD: Tutorial

271A - Beautiful Year

This is a very straight forward problem. Just add 1 to a year number while it still has equal digits.

271B - Prime Matrix

Precalculate the next prime for every integer from 1 to 10⁵. You can do that in any way. The main thing is to test all the divisors up to square root when you are checking if a number is prime.

Now for each a_ij (element of the given matrix) we can easily calculate add_ij — how many do we have to add in order to make a_ij prime. After that all we need to do is to find row or column with minimal sum in this new matrix.

271C - Secret

If 3k > n there is no solution (because each of the k sets must have at least 3 elements). Otherwise we can divide first 3k words in the following way:

1 1 2 2 3 3 ... k k 1 2 3 ... k

For each of the k sets, the difference between the first and the second elements will be 1. And the difference between the second and the third elements is definitely not 1 (more precisely, it is 2k - i - 1 for the i-th set). So each set doesn't form an arithmetic progression for sure.

For this solution it doesn't matter how we divide the rest n - 3k words.

271D - Good Substrings

At first, build a trie containing all suffixes of given string (this structure is also called explicit suffix tree). Let's iterate over all substrings in order of indexes' increasing, i. e. first [1...1],  then [1...2], [1...3], ..., [1...n], [2...2], [2...3], ..., [2...n], ... Note, that moving from a substring to the next one is just adding a single character to the end. So we can easily maintain the number of bad characters, and also the "current" node in the trie. If the number of bad characters doesn't exceed k, then the substring is good. And we need to mark the corresponding node of trie, if we never did this before. The answer will be the number of marked nodes in the trie.

There is also an easier solution, where instead of trie we use Rabin-Karp rolling hash to count substrings that differ by content. Just sort the hashes of all good substrings and find the number of unique hashes (equal hashes will be on adjacent positions after sort). But these hashes are unreliable in general, so it's always better to use precise algorithm.

271E - Three Horses

It could be proved, that a card (x, y) (x < y) can be transformed to any card (1, 1 + k·d), where d is the maximal odd divisor of y - x, and k is just any positive integer. So every (a_i - 1) must be divisible by d, i. e. d is a divisor of gcd(a₁ - 1, ..., a_n - 1), and we can just iterate over all possible divisors. Let's take a look at all the initial cards (x, y), which have have d as their maximal odd divisor: these are cards with y - x equal to d, or 2d, or 4d, 8d, 16d, ... Don't forget that the numbers x and y must not exceed m. It means that the total number of cards with some fixed difference t = y - x is exactly m - t.

The resulting solution: sum up (m - 2^ld), where d is any odd divisor of gcd(a₁ - 1, ..., a_n - 1), and l is such, that 2^ld ≤ m.

263A - Beautiful Matrix

If the single 1 is located on the intersection of the r-th row and the c-th column (1-based numeration), then the answer is |3 - r| + |3 - c|.

263B - Squares

If k > n, then the answer doesn't exist. Otherwise let's sort the squares by descending of their sizes. Now you can print any point that belongs to the k-th square and doesn't belong to the k + 1-th square. One of the possible answers is (a_k, 0).

263C - Circle of Numbers

First of all, we have to check that each number occurs in the input exactly 4 times. If it's not true, then the answer definitely doesn't exist.

Otherwise, let's try to restore the circle. As cyclic shift of circle doesn't matter, let 1 to be the first number. As the second and the third number must be connected to each other and to 1, there are only few possibilities. So let's try them all. And when we know first three numbers, the rest of the circle could be easily and unambiguously restored in O(n). Just find a number, which is not included in the circle yet, and is connected to the last two numbers of the circle. Add this number to the resulting circle (as new last number), and repeat the procedure while possible. If we succeeded to add all the numbers to the circle, than the resulting circle is the answer.

263D - Cycle in Graph

Consider any simple path v₁, v₂, ..., v_r which cannot be increased immediately (by adding a node to it's end, v_r). In other words, all the neighbours of v_r are already included in the path. Let's find the first node of the path (say, v_l), which is connected to v_r. It is clear that v_l, v_l + 1, ..., v_r is a cycle and it contains all the neighbours of v_r. But according to the problem's statement, each node has at least k neighbours. So length of the cycle is at least k + 1 ( + 1 is for node v_r itself).

263E - Rhombus

Divide the rhombus of size k into 4 right-angled triangles as shown on a picture below. One of them has size k, two — size k - 1, and another one — size k - 2.

Let's solve the problem separately for each triangle. The most convenient way to do that is to rotate the input 4 times and run the same solving function 4 times. The result of this function will be a 2D array. Cell (x, y) indicates the answer we get if the right-angled vertex of triangle is located at cell (x, y). So it will be easy to combine 4 such arrays (just rotating and shifting properly) to get the actual answer for rhombus.

The main idea of the solution for triangle is the following. If we know the answer for a cell, we can easily move our triangle by one cell in any direction (right, down, left, or up) and recalculate the answer for that new cell in constant time. In fact, we need only 2 directions: right and down. And the values for top left corner should be calculated with straightforward cycles in O(k²) time.

More precisely, let's define 5 functions:

1. The sum on diagonal segment of k elements:

2. The sum on vertical segment of k elements:

3. The weighted sum on vertical segment of k elements:

4. The sum on a triangle:

5. The weighted sum on a triangle:

Calculating the first 3 functions in O(nm) in total is quite obvious. Formulas for the others are following:

triangle(x, y + 1) = triangle(x, y) - diagonal(x, y - k + 1) + vertical(x, y + 1)

triangleWeighted(x, y + 1) = triangleWeighted(x, y) - triangle(x, y) + verticalWeighted(x, y + 1)

Formulas for moving in other directions are similar.

Initially the order of problems was A-C-E-D-B. But we were not sure about last two.

166A - Rank List

This is simple straight-forward problem — you were asked to sort the teams with the following comparator: (p₁ > p₂) or (p₁ = p₂ and t₁ < t₂). After that you can split the teams into groups with equal results and find the group which shares the k-th place. Many coders for some reason used wrong comparator: they sorted teams with equal number of problems by descending of time. Such submits accidentally passed pretests but get WA #13.

166B - Polygons

Polygon A is convex, so it is sufficient to check only that every vertex of polygon B is strictly inside polygon A. In theory the simplest solution is building common convex hull of both polygons. You need to check that no vertex of polygon B belongs to this hull. But there is a tricky detail: if there are many points lying on the same side of convex hull than your convex hull must contain all these points as vertices. So this solution is harder to implement and has some corner case.

Another solution: cut polygon A into triangles (by vertex numbers): (1, 2, 3), (1, 3, 4), (1, 4, 5), ..., (1, n - 1, n). The sequences of angles 2 - 1 - 3, 2 - 1 - 4, 2 - 1 - 5, ..., 2 - 1 - n is increasing. It means that you can find for each vertex of B to which triangle of A it can belong using binsearch by angle.

Similarly you can cut polygon A into trapezoids (with vertical cuts). In this case you'll need a binsearch by x-coordinate.

166C - Median

If the initial array doesn't contain number x, than you definitely need to add it (that's +1 to answer). Than do the following. While median is strictly less than x you need to increase it. Obviously the surest way to increase the median is to add a maximal possible number (10⁵). Similarly while the median is strictly more than x, add a number 1 to the array. Constraints are small, so you can add the numbers one by one and recalculate the median after every addition.

Also there is a solution without any cases: while the median isn't equal to x, just add one more number x to array.

166D - Shoe Store

Let's sort the people by decreasing of shoes size. Observe that when considering the i-th man we are interested in no more than 2 pairs of shoes: with size l_i and l_i + 1. It allows solving with dynamics. The state will be (the number of first unconsidered man i, is pair of shoes with size l_i available, is pair of shoes with size l_i + 1 available). You have 3 options: leave the i-th man without shoes or sell him a pair of shoes of one of suitable size (if available).

166E - Tetrahedron

Obvious solution with dynamics: you need to know only how many moves are left and where is the ant. This is 4n states, each with 3 options – most of such solution passes. Observe that the vertices A, B, C are equivalent. This allows writing such solution:

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
	int nzD = zABC * 3LL % MOD;
	int nzABC = (zABC * 2LL + zD) % MOD;
	zD = nzD;
	zABC = nzABC;
}
cout << zD;

Also this problem could be solved by log(n) with binary exponentiation of some 2 × 2 matrix into power n.

While the world community of participants of programming contests is waiting with bated breath for the news about new date and place of the Final, we decided not to delay the next round and prepared some problems on the train from Petrozavodsk to Saratov. In preparation were involved Mike Mirzayanov, Artem Rakhov and Max Ivanov. Tasks were translated into English by Maria Belova.

Good luck!

Artem Rakhov and Codeforces team 

Hi everyone!

The recent testing round went well. It is expected that everything will run faster. Today's round was prepared by: Mike Mirzayanov, Nickolay Kuznetsov, Ivan Fefer and Maria Belova.

Good luck!

Artem Rakhov and Codeforces team

• Problems
• Standings
• Winner: JKeeJ1e30

Good evening!

Soon many of you will have your examinations, and someone even have it now. I wish you excellent marks and many easy exams!

Thanks to Nickolay Kuznetsov, Gerald Agapov and Ivan Fefer for their help in preparation of the round.

Good luck!

Artem Rakhov and Codeforces team

UPD:

• Standings
• Problems
• Winner: ghostof2007

Attention, participants from the Division 1! As a test feature, you can participate in Codeforces Beta Round #32 "out of competition".

Everybody knows, that the 2nd of October - birthday of Mohandas Gandhi. We dedicate today's round to him, and many other great people who were born on October 2 :)

Round was prepared by Mike Mirzayanov, Matov Dmitry and Max Ivanov.

Special thanks to Julia Satushina for translation of statements.

Good luck!

Artem Rakhov and Codeforces team

Welcome to Codeforces Beta Round #25 (Div. 2)

Authors of today's round problems are Mike Mirzayanov and me. I want to thank to Dmitry Levshunov for technical assistance in organizing the contest, as well as Gerald Agapov and Nikolay Kuznetsov for writing alternative solutions.

I wish you all good luck!

• Problems
• Final standings
  
• Winner: saeedreza.seddighin

Welcome all to Codeforces Beta Round #22

Note that at this time registration is possible during the round. The contest will begin at 19:00 MSK.

Today I am an author of the problems. I would like to thank Mike Mirzayanov for help in contest preparations, Edvard Davtyan and Nickolay Kuznetsov for writing the verification solutions, and Julia Satushina for translating statements into English.

Good luck on the contest!

UPD: The contest is over. Thank you all for participating!
Problems
Results
Winner Kasparyanm_Mihail gains +203 to rating after the contest!

Welcome to Codeforces Beta Round #18

Authors of today's contest are Mike Mirzayanov, Edvard Davtyan and me. Thanks to Dmitry Matov for his help in statements preparation and Julia Satushina for translation of problems in English.

Good luck everyone!

• Problems
• Final standings
  
• Contest winner: I_am_Feeling_Lucky

Good afternoon.

Today I am the author of problems. I want to thank the creator of Codeforces Mike Mirzayanov and Edvard Davtyan for assistance in the problems preparation and Julia Satushina for great translations into English.

I wish everyone advance to the first division!
Artem Rakhov

UPD: The contest is over, thank you all for participating!

• Problems
• Final standings
  
• Contest winner: krijgertje