RAD's blog

By RAD, 12 years ago, translation, In English

278B - New Problem

The total number of different strings of 2 letters is 262 = 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 = x2 + 107), and set up the rest n - m points on a concave function (for example, y =  - x2 - 107). 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 ai is the size of the i-th pile. Then the result of the game without i-th pile is . We want to replace ai 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.

(timeLargei + timeLargej)(1 - probFailj) + timeLargei(1 - probFaili)probFailj < (timeLargei + timeLargej)(1 - probFaili) + timeLargej(1 - probFailj)probFaili

 - probFailj·timeLargej - timeLargei·probFailj·probFaili <  - probFaili·timeLargei - timeLargej·probFaili·probFailj

timeLargei·probFaili(1 - probFailj) < timeLargej·probFailj(1 - probFaili)

timeLargei·probFaili / (1 - probFaili) < timeLargej·probFailj / (1 - probFailj)

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 + timeSmalli], the expected total score increases by scoreSmalli, and the expected penalty time increases by timeSmalli (we assume that this input is solved in the very beggining of the contest)

  3. solve both inputs: update z[i + 1][j + timeSmalli + timeLargei], the expected total score increases by scoreSmalli + (1 - probFaili)scoreLargei, and the expected penalty time becomes timeSmalli + (1 - probFaili)(j + timeLargei) + probFaili·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 1012 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 106 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 pi as a parent, so that ypi > yi and distance between i and pi is minimal possible. Renumerate all the nodes in order of non-increasing of y. Now it's clear that pi < 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.

Full text and comments »

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

By RAD, 12 years ago, In English

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

Full text and comments »

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

By RAD, 12 years ago, translation, In English

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 105. 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 aij (element of the given matrix) we can easily calculate addij — how many do we have to add in order to make aij 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 (ai - 1) must be divisible by d, i. e. d is a divisor of gcd(a1 - 1, ..., an - 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 - 2ld), where d is any odd divisor of gcd(a1 - 1, ..., an - 1), and l is such, that 2ld ≤ m.

Full text and comments »

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

By RAD, 12 years ago, In English

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 (ak, 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 v1, v2, ..., vr which cannot be increased immediately (by adding a node to it's end, vr). In other words, all the neighbours of vr are already included in the path. Let's find the first node of the path (say, vl), which is connected to vr. It is clear that vl, vl + 1, ..., vr is a cycle and it contains all the neighbours of vr. 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 vr 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(k2) 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.

Full text and comments »

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

By RAD, 13 years ago, translation, In English

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: (p1 > p2) or (p1 = p2 and t1 < t2). 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 (105). 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 li and li + 1. It allows solving with dynamics. The state will be (the number of first unconsidered man i, is pair of shoes with size li available, is pair of shoes with size li + 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.

Full text and comments »

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

By RAD, 13 years ago, translation, In English
Hi

Unfortunately, Codeforces Beta Round #93 is rescheduled for tomorrow because of circumstances beyond our control. The new time is November, 9, 21:00 Moscow time (exactly 24 hours ahead).

We apologize for any inconvenience.
 
See you tomorrow,

Full text and comments »

  • Vote: I like it
  • -59
  • Vote: I do not like it

By RAD, 14 years ago, translation, In English

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 

Full text and comments »

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

By RAD, 14 years ago, translation, In English
Good evening! 

I am glad to invite you to participate in Codeforces Beta Round #52 (Div. 2). Today's round was prepared Michael Mirzayanov, Max Ivanov and Maria Belov. 

It's possible that "out of the competition"-participants will not be able to use the tab "hacks". Do not panic, on the next Div. 2 Round we will necessarily fix it. 

Good luck!
Artem Rakhov and Codeforces team

Full text and comments »

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

By RAD, 14 years ago, translation, In English

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

Full text and comments »

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

By RAD, 14 years ago, translation, In English

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:

Ratings will be updated later

Full text and comments »

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

By RAD, 14 years ago, translation, In English
Good evening

Yesterday evening the Saratov university delegation returned from St. Petersburg, from the ACM-ICPC NEERC 2010/11 World Programming Championship semi-finals. If you haven't seen the final standings: 4 Saratov teams received diplomas, and we (Saratov SU 2) advanced to the finals. Saratov SU 1 was also among those, who advanced, that's pretty cool for their first time, but didn't advance because of the limitation "only one team from one university".

Also we have prepared a Div. 2 round. Thanks for prompt assistance to Edvard Davtyan, Gerald Agapov and Maria Belova.

Good luck!
Artem Rakhov and Codeforces team


Unfortunately, the discrepancy between author’s solution and statement of problem E was detected. We bring our apologies to all the participants. All solutions that have not been Accepted previously were rejudged. Thanks to member xcr for detection of the issue.

Full text and comments »

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

By RAD, 14 years ago, translation, In English

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

UPD:

Full text and comments »

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

By RAD, 14 years ago, translation, In English
Hello everyone on Codeforces Beta Round 31 (Div. 2, Codeforces format)

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

Good luck!
Artem Rakhov and Codeforces team

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By RAD, 14 years ago, translation, In English
Today in Russia it's not just the 20th of september, it's Recruiter's Day. In Azerbaijan – Oil Industry Worker's Day, and in Belarus – Customs Officer's Day. But for us it's another good day to arrange the round. Welcome to Codeforces Beta Round #29 (Div. 2, Codeforces format)!

Helped with preparation of the round: Mike MirzayanovDmitry MatovGerald Agapov and Nickolay Kuznetsov, thank them for that.

Happy Recruiter's Day,
Artem Rakhov

Full text and comments »

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

By RAD, 14 years ago, translation, In English

Let's divide all trucks into the classes by l + r + c. It can be seen, that all the trucks that can be included in the answer are in the same class.

Let's solve the problem separately for each class. Consider all trucks from same class in the order they appear, and keep the following value: z[k] = the maximum sum that you can get, if the last taken truck has ri = k. Consider the truck number i - there are 2 options to update z:

It can update z[ri] with z[ri + ci] + vi, i. e. continue the motorcade, which has last truck with r = ri + ci. (For neighboring trucks should be true the following: rprev  =  ri  +  ci)

If li = 0, it can update z[ri] with vi, i. e. became the first truck in the new motorcade. (For the first truck should be true the following: li = 0)

The answer will be in z[0].

To restore the trucks included in the answer, we can keep with the maximal sum in z the index of last truck that updated this sum. Also we store the ancestor p for each truck that updated something in z. This ancestor is calculated when we consider i-th truck and doesn't change further: p[i] = -1 if truck i became beginning of the motorcade, otherwise p[i] = last truck that updated z[ri  +  ci].

We start restore of the answer from last truck updated z[0]. After that we restore everything using only p.

Full text and comments »

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

By RAD, 14 years ago, translation, In English
We want to congratulate you with a happy new school year with this contest. We wish you excellent marks, easy exams and many Accepted in the contests. Let this year bring you many new and interesting knowledge!

Artem Rakhov and Codeforces team 

P. S. Note that the round will be held on the Codeforces Format Rules. Read the rules before the competition. Good luck!

Full text and comments »

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

By RAD, 14 years ago, translation, In English

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!


UPD: The contest is over, thank you to everyone for participating.

Full text and comments »

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

By RAD, 14 years ago, translation, In English
Hi everybody

Today the author of the majority of problems is Dmitry Zhukov, many thanks to him for this. 
Also I want to thank Mike Mirzayanov for choosing problems for the contest and organizing it and Julia Satushina for the translation of the statements.

Good luck!

UPD:

Full text and comments »

Announcement of Codeforces Beta Round 23
  • Vote: I like it
  • +25
  • Vote: I do not like it

By RAD, 14 years ago, translation, In English

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!

Full text and comments »

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

By RAD, 14 years ago, translation, In English

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!

Full text and comments »

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

By RAD, 14 years ago, translation, In English

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!

Full text and comments »

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