Hi, Codeforces!

Educational Codeforces Round 4 will take place on 25 December 2015 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here. This time a little time has passed since the previous round. Although we planned this round at Monday, we forgot to include it to schedule, so it was appeared only now. So it is the fourth and the last educational round this year.

<Maybe this paragraph will not be changed ever>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

</Maybe this paragraph will not be changed ever>

This time the round was prepared only by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov for helping to invent the problems. Also thanks in advance to Maria Belova Delinur who will check English statements, when they will be ready :-)

I think this time the problems is simpler than usually, because at first we have too hard problemset and removed the hardest problem and added very simple problem. I hope you will enjoy the problems and solve all of them!

Also I want to wish you Happy New Year!!!

Good luck and have fun!

UPD 1: The first phase is ended, hack the solutions of your opponents!

UPD 2: The editorial is ready.

This round was unusual: some of problems was prepared by students and employees of Saratov State U for some of past olympiads and one of problems was prepared by dalex for Codeforces regular round but was not used there.

609A - USB Flash Drives

Let's sort the array in nonincreasing order. Now the answer is some of the first flash-drives. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: O(nlogn).

609B - The Best Gift

Let's denote cnt_i — the number of books of i th genre. The answer to problem is equals to . In first sum we are calculating the number of good pairs, while in second we are subtracting the number of bad pairs from the number of all pairs.

Complexity: O(n + m²) or O(n + m).

609C - Load Balancing

Denote s — the sum of elements in array. If s is divisible by n then the balanced array consists of n elements . In this case the difference between maximal and minimal elements is 0. Easy to see that in any other case the answer is greater than 0. On the other hand the array consists of numbers and numbers is balanced with the difference equals to 1. Let's denote this balanced array b. To get array b let's sort array a in nonincreasing order and match element a_i to element b_i. Now we should increase some elements and decrease others. In one operation we can increase some element and decrease another, so the answer is .

Complexity: O(nlogn).

609D - Gadgets for dollars and pounds

If Nura can buy k gadgets in x days then she can do that in x + 1 days. So the function of answer is monotonic. So we can find the minimal day with binary search. Denote lf = 0 — the left bound of binary search and rg = n + 1 — the right one. We will maintain the invariant that in left bound we can't buy k gadgets and in right bound we can do that. Denote function f(d) equals to 1 if we can buy k gadgets in d days and 0 otherwise. As usual in binary search we will choose . If f(d) = 1 then we should move the right bound rg = d and the left bound lf = d in other case. If binary search found the value lf = n + 1 then the answer is  - 1, otherwise the answer is lf. Before binary search we can create two arrays of gadgets which are selling for dollars and pounds, and sort them. Easy to see that we should buy gadgets for dollars on day i ≤ d when dollar costs as small as possible and j ≤ d when pounds costs as small as possible. Let now we want to buy x gadgets for dollars and k - x gadgets for pounds. Of course we will buy the least cheap of them (we already sort the arrays for that). Let's iterate over x from 0 to k and maintain the sum of gadgets for dollars

Unable to parse markup [type=CF_TEX]

Complexity: O(klogn).

609E - Minimum spanning tree for each edge

This problem was prepared by dalex.

Let's build any MST with any fast algorithm (for example with Kruskal's algorithm). For all edges in MST the answer is the weight of the MST. Let's consider any other edge (x, y). There is exactly one path between x and y in the MST. Let's remove mostly heavy edge on this path and add edge (x, y). Resulting tree is the MST contaning edge (x, y) (this can be proven by Tarjan criterion).

Let's fix some root in the MST (for example the vertex 1). To find the most heavy edge on the path from x to y we can firstly find the heaviest edge on the path from x to l = lca(x, y) and then on the path from y to l, where l is the lowest common ancestor of vertices x and y. To find l we can use binary lifting method. During calculation of l we also can maintain the weight of the heaviest edge.

Of course this problem also can be solved with difficult data structures, for example with Heavy-light decomposition method or with Linkcut trees.

Complexity: O(mlogn).

It's very strange but I can't find any articles with Tarjan criterion on English (although there are articles on Russian), so here it is:

Some spanning tree is minimal if and only if the weight of any other edge (x, y) (not from spanning tree) is not less than the weight of the heaviest edge on the path from x to y in spanning tree.

609F - Frogs and mosquitoes

Let's maintain the set of not eaten mosquitoes (for example with set in C++ or with TreeSet in Java) and process mosquitoes in order of their landing. Also we will maintain the set of segments (a_i, b_i), where a_i is the position of the i-th frog and b_i = a_i + l_i, where l_i is the current length of the tongue of the i-th frog. Let the current mosquito landed in the position x. Let's choose segment (a_i, b_i) with minimal a_i such that b_i ≥ x. If the value a_i ≤ x we found the frog that will eat mosquito. Otherwise the current mosquito will not be eaten and we should add it to our set. If the i-th frog will eat mosquito then it's tongue length will be increased by the size of mosquito and we should update segment (a_i, b_i). After that we should choose the nearest mosquito to the right the from frog and if it's possible eat that mosquito by the i-th frog (this can be done with lower_bound in C++). Possibly we should eat several mosquitoes, so we should repeat this process several times.

Segments (a_i, b_i) we can store in segment tree by position a_i and value b_i. Now to find segment we need we can do binary search by the value of a_i and check the maximum b_i value on the prefix to be at least x. This will work in O(nlog²n) time. We can improve this solution. Let's go down in segment tree in the following manner: if the maximum value b_i in the left subtree of segment tree is at least x then we will go to the left, otherwise we will go to the right.

Complexity: O((n + m)log(n + m)).

Hi, Codeforces!

Educational Codeforces Round 3 will take place on 19 December 2015 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here. A lot of time have passed since the previous round. I hope that the next rounds will be more regular.

<This paragraph wasn't changed>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

</This paragraph wasn't changed>

This time the round was prepared not only by me, Edvard Davtyan. Firstly, thanks a lot to Alexey Dergunov dalex who shared one of his problems with well-known idea. Also thanks a lot to Alexandr Frolov fcspartakm, Vitaliy Kudasov kuviman and Arthur Svechnikov ikar for their help in preparing problems. MikeMirzayanov helped us to invent the problems. Also thanks a lot to Maria Belova Delinur for translating the problems from my RussianEnglish to English :-)

I hope you will enjoy the problems.

Good luck and have fun!

UPD1: The first part of competition is over. I hope that you enjoyed the problems. Now you let's hack other solutions :-)

UPD2: The editorial is ready.

UPD3: The round is over. All solutions are rejudged on full testset. The results are final.

UPD4: 6725 rows affected :-)

600A - Extract Numbers

This is a technical problem. You should do exactly what is written in problem statement.

600B - Queries about less or equal elements

Let's sort all numbers in a. Now let's iterate over elements of b and for element b_j find the index of lowest number that is greater than b_j. We can do that using binary search. That index will be the answer for value b_j.

Complexity: O(nlogn).

600C - Make Palindrome

Let's denote cnt_c — the number of occurences of symbol c. Let's consider odd values cnt_c. Palindrome can not contain more than one symbol c with odd cnt_c. Let's denote symbols with odd cnt_c as a₁, a₂...a_k (in alphabetical order). Let's replace any one of symbols a_k with symbol a₁, a_k - 1 with a₂ and so on until the middle of a. Now we have no more than one odd symbol. If we have some let's place it in the middle of the answer. First half of answer will contain occurences of symbol c in alphabetical order. The second half will contain the same symbols in reverse order. For example for string s = aabcd at first we will replace d by

Unable to parse markup [type=CF_TEX]

Compexity: O(n).

600D - Area of Two Circles' Intersection

If the circles don't intersect than the answer is 0. We can check that case with only integer calculations (simply by comparing the square of distance between centers with square of the sum of radiuses). If one of the circles is fully in other then the answer is the square of the smaller one. We can check this case also with only integer calculations (simply by comparing the square of distance between centers with square of the difference of radiuses).

So now let's consider the general case. The answer will be equal to the sum of two circular segments. Let's consider the triangle with apexes in centers if circles and in some intersecting point of the circles. In that triangle we know all three sides so we can compute the angle of the circular segment. So we can compute the square of circular sector. And the only thing that we should do now is to subtract the square of triangle with apexes in the center of circle and in the intersecting points of circles. We can do that by computing the half of absolute value of cross product. So we have the following formulas:

,

where d is the distance between centers of the circles. And also we should do the same thing with second circle by replacing of indices 1 ≤ ftrightarrow2.

Complexity: O(1).

600E - Lomsat gelral

The name of this problem is anagram for ''Small to large''. There is a reason for that :-) The author solution for this problem uses the classic technique for computing sets in tree. The simple solution is the following: let's find for each vertex v the ''map<int, int>'' — the number of occurences for each colour, ''set<pair<int, int>>'' — pairs the number of occurences and the colour, and the number sum — the sum of most frequent colours in subtree of v. To find that firstly we should find the same thing for all childs of v and then merge them to one. These solution is correct but too slow (it works in O(n²logn) time). Let's improve that solution: every time when we want to merge two map-s a and b let's merge the smaller one to larger simply by iterating over all elements of the smaller one (this is the ``Small to large''). Let's consider some vertex v: every time when vertex v will be moved from one map to another the size of the new map will be at least two times larger. So each vertex can be moved not over than logn times. Each moving can be done in O(logn) time. If we accumulate that values by all vertices then we get the complexity O(nlog²n).

I saw the solutions that differs from author's but this technique can be used in a lot of other problems.

600F - Edge coloring of bipartite graph

Let's denote d is the maximum degree of vertex in graph. Let's prove that the answer is d. We will build the constructive algorithm for that (it will be the solution to problem). Let's colour the edges one by one in some order. Let (x, y) be the current edge. If there exist colour c that is free in vertex x and in vertex y then we can simply colour (x, y) with c. If there is no such colour then there are a couple of colours c₁, c₂ so that c₁ is in x and not in y and c₂ is in y but not in x. Let's make vertex y free from colour c₂. Denote z the other end of edge from y with colour c₂. If z is free from colour c₁ then we can colour x, y with c₂ and recolour y, z with c₁. So me make alternation. If z is not free from colour c₁ let's denote w the other end of the edge from z with colour c₁. If w is free from colour c₂ then again we can do alternation. And so on. We will find an alternating chain because the graph is bipartite. To find the chain we can use depth first search. Each chain contains no more than O(n) vertices. So we have:

Сложность решения: O(nm).

Hi, Codeforces!

Educational Codeforces Round 2 will take place on November 27th, 2015, at 15:00 UTC for the first and second divisions. You can read about educational rounds here.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

Round was prepared by me, Edvard Davtyan. Problems was invented by me and MikeMirzayanov.

I hope you will enjoy the problems.

Good luck and have fun!

UPD: Thanks a lot to PrinceOfPersia for testing the problems and Delinur for checking my bad English (in problem statements).

UPD2: The first part of competition is over. I hope that you enjoyed the problems. Now you let's hack other solutions :-)

UPD3: At the stage of hacking we found that a lot of correct solutions are numerically unstable, so they print the right answer with error in ninth digit. So we decided to increase the requirement for precision from 10^- 9 to 10^- 6. All submissions and hacks will be rejudged soon. It will not affect correct solutions. They will got Accepted as earlier.

UPD4: The editorial is ready.

UPD5: The round is over. All solutions are rejudged on full testset. The results are final.

Hi, Codeforces!

Educational Codeforces Round #1 will take place on 13 ноября 2015 года в 18:00 MSK for the first and second divisions. You can read about educational rounds here.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve five problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

Educational rounds are (and would) be prepared by me, Edvard Davtyan from Saratov SU Daemons team. Problems was invented by me and MikeMirzayanov. Thanks to my teammate danilka.pro for testing problems and MikeMirzayanov for Codeforces, Polygon and idea of the educational rounds.

I hope you will enjoy the problems. If they will be too simple for you, you are welcome to the second educational round, problems there should be harder.

Good luck and have fun!

UPD: The first phase of round is over. I remind that the results is not final and you can hack any solution during the day.

UPD2: Please use only deterministic generators. For example you should not use srand(time(NULL)) with calling rand() function in C++. Your generator should always generate the same test.

586A - Alena's Schedule

The problem has been prepared by adedalic.

To solve this problem one should remove all leading and trailing zeroes from array and then calculate the number of ones and number of zeroes neighboured by ones. The sum of this values is the answer for the problem.

Complexity: O(n).

586B - Laurenty and Shop

The problem has been prepared by Oleg_Smirnov.

Let's call some path ith if we start it by going i times left, then we cross the prospect and go left n - 1 - i times again. Let d_i be equal to the time we should wait on traffic lights while following i-th path. If we consider any way from the shop to home, it is equal (but reversed) to only path from home to the shop, meaning that we need to find two distinct paths from home to the shop. So the answer to the problem is the sum of the smallest and the second smallest values among d_i. One could easily calculate d_i using calculated d_i - 1, so d_i could be found in one for cycle.

If we will consider only two minimum values among d_i, solution complexity will be O(n).

Complexity: O(n).

585A - Gennady the Dentist

The problem has been prepared by Neon.

Let's store for each child his current confidence value and a boolean indicating whether child had left the queue (or visited the dentist office) or not. Then one could easily process children one by one, considering only children who still are in the queue (using boolean array), and changing stored values.

Such solution has complexity O(n²) and requires author's attention much, especially the case with possible confidence value overflowing. Of course there are much faster solutions not required in our case.

585B - Phillip and Trains

The problem has been prepared by IlyaLos.

One could consider a graph with vertices corresponding to every (x, y) position. I should notice that train positions for each Phillip position are fully restorable from his y coordinate. Edge between vertices u and v means that we could get from position corresponding to u to position corresponding by v in one turn without moving onto a train cell or moving in a cell which will be occupied by some train before the next turn. All we need next is to find whether any finishing position is reachable from the only starting position (using BFS or DFS, or, as soon as graph is a DAG, dynamic programming).

As soon as graph has O(n) vertices and O(n) edges, solution complexity equals to O(n).

585C - Alice, Bob, Oranges and Apples

The problem has been prepared by Edvard.

Firstly, let's understand the process described in problem statement. If one would write a tree of a sum-pairs (x, y) with letters and , he would get the Stern–Brocot tree. Let the number of oranges be enumerator and the number of apples be denumerator of fraction. At every step we have two fractions (at first step they are ) and should replace exactly one of them with their mediant. In such way first fraction is first parent to the left from mediant while second fraction is parent to the right. The process described in statement is, this way, a process of finding a fraction in the Stern-Brocot tree, finishing when the current mediant is equal to current node in the tree and (x, y) pair is the fraction we are searching.

This means that if , (x, y) does not correspond to any correct fraction and the answer is "Impossible". Other way, we could find it in the tree. If x > y, we should firstly go in the right subtree. Moreover, we could then consider we are searching from the root. If x < y, we should go left and next consider from the root. This gives us Euclidian algorithm, which could be realized to work in complexity.

Complexity: O(logn).

585D - Lizard Era: Beginning

The problem has been prepared by danilka.pro.

To solve the problem we will use meet-in-the-middle approach. For we should consider all variants. Let in some variant approval values of three companions are a, b, c respectively. If we will consider some variant from other half (there are of them) and a', b', c' approval values, then to ``merge'' such two parts correctly, two conditions a - b = b' - a' и b - c = c' - b' must be true (a + a' = b + b' = c + c' is true), and the value we are maximizing is a + a'.

This way, to solve the task one could consider every variant from the first half and store for every possible pair (a - b, b - c) the maximum a value achievable (using, for example, the structure or any fast sorting algorithm). If one would then consider every variant from the second half, he just need to find (b' - a', c' - b') pair in the structure to get the maximum a value if possible and update answer with a + a' value. Answer restoring is pretty same to the algorithm above.

Such solution has complexity.

585E - Present for Vitalik the Philatelist

The problem has been prepared by gridnevvvit.

Let's calculate the number of subsets with gcd equal to 1 — value A. Let's do that using principle of inclusions-exclusions: firstly we say that all subsets is good. The total number of subsets is equal to 2ⁿ. Now let's subtract subsets with gcd divisible by 2. The number of that subsets is equal to 2^cnt₂ - 1 (cnt_i is the number of numbers that is divisable by i). Next we should subtract 2^cnt₃ - 1. Subsets with gcd divisible by 4 we already counted with number two. Next we should subtract 2^cnt₅ - 1. Now we should notice that subsets with gcd divisible by 6 we already processed twice: firstly with number 2, then with — 3, so let's add the number of these subsets 2^cnt₆ - 1. If we continue this process we will get, that for all numbers d we should add the value μ(d)(2^cnt_d - 1), where μ(d) is equals to 0, if d is divisible by square of some prime, 1, if the number of primes in factorization of d is even and  - 1 in other case. So the numbers that is divisible by square of some prime we can ignore, because they have coefficient 0. To calculate values cnt_i we should factorize all numbers and iterate over 2^k divisors with value μ(d) ≠ 0. Now it's easy to see, that the number of subsets with gcd greater than 1 equals to B = 2ⁿ - A. To solve the problem let's fix the stamp that Vitaliy will buy a_i. Let's recalculate the number B for array a without element a_i. To do that we should only subtract those terms that was affected by number a_i. We can do that in 2^k, where k is the number of primes in factorization of the number a_i. It's easy to see that only the subsets with gcd greater than 1, but not divisible by any divisor of a_i, should we counted in answer. To calculate number of those subsets let's again use the principle of inclusions-exclusions. For every divisor d of a_i let's subtract the value μ (2^cnt_d - 1) from B. So now we got B_i — the number of subsets with gcd greater than 1, but coprime with a_i. The answer to problem is the sum over all B_i. The maximum number of primes in factorization of number not greater than 10⁷ is equal to 8. We can factorize all numbers from 1 to n in linear time by algorithm for finding the smallest divisors for all intergers from 1 to n, or by sieve of Eratosthenes in O(nloglogn) time.

Complexity: O(C + n2^K), where , K — is the largest number of primes in factorization of a_i.

585F - Digits of Number Pi

The problem has been prepared by Edvard.

Consider all substrings of string s with length . Let's add them all to trie data structure, calculate failure links and build automata by digits. We can do that in linear time using Aho-Korasik algorithm. Now to solve the problem we should calculate dp z_{i, v, b1, b2, b}. State of dp is described by five numbers: i — number of digits, that we already put to our number, v — in which vertex of trie we are, b₁ — equals to one if the prefix that we built is equals to prefix of x, b₂ — equals to one if the prefix that we built is equals to prefix of y, b — equals to one if we already have some substring with length on the prexif that we built. The value of dp is the number of ways to built prefix with the given set of properties. To update dp we should iterate over the digit that we want to add to prefix, check that we still is in segment [x, y], go from vertex v to the next vertex in automata. So the answer is the sum by all v, b₁, b₂ z_{b, v, v1, v2, 1}.

Complexity: O(nd²).

Hi, Codeforces!

Codeforces Round #325 will take place on October 12, 2015 at 09:00 UTC for the first and second divisions. Please note that the round will start at unusual time!

The problems of this round are taken from the Regional stage of the All-Russian school team programming olympiad that will be at the same time in Saratov, Russia. Lets wish school teams good luck on competition!

The problemset for school olympiad differs from problems that will be on round. In addition in problemset for school olympiad there will be some problems, which are not included in the round and vice versa. So don't be frightened by the difficulty of problems given for school teams :-)

The process of problems preapring was very interesting: we were reworking problem statements many times, adding tests, changing limits, even managed to change fully prepared problem with another (we had to stop the conveyor already printing problem statements :-)) Let's thank all who were preparing, helping in preparing, reading the problem statements, writing solutions: Adilbek adedalic Dalabaev, Roman Roms Glazov, Vladimir vovuh Petrov, Oleg Oleg_Smirnov Smirnov, Alexey Perforator Ripinen, Maxim Neon Mescheryakov, Ilya IlyaLos Los, Vitaliy gridnevvvit Gridnev, Danil danilka.pro Sagunov, Alexander fcspartakm Frolov, Pavel HolkinPV Kholkin, Igor Igor_Kudryashov Kudryashov, Elena elena Rogacheva, Dmitriy Nerevar Matov, Vitaliy kuviman Kudasov. Chairman of the jury of the Olympiad is Mikhail MikeMirzayanov Mirzayanov (also he is the author of some of tasks). I (Edvard Edvard Davtyan) prepared some tasks and coordinated the work of the authors. So we are a large team of writers (I hope I did not forget anyone)!

Also let's thank Max Akhmedov (Zlobober), The-One-Who-Must-Not-Be-Named (if I am not wrong, he or she is right now solving the round problems) for their help in problems preparing, Maria Belova (Delinur) for translating problems in English and again Mikhail Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems.

You will have only two hours to solve six problems. The scoring distribution will be anounced a little before the round. I wish high rating to all participants! Good luck and have fun!

P.S.: Also I want to wish good luck to the participants of the ACM ICPC Southern Subregional Programming Contest that will be held on Wednesday.

UPD Due to technical reasons round is delayed by 10 minutes.

UPD: In problem Subway roller there were tests with trains of length one. At this moment authors are discussing how much it troubled the round results. We are apologize to participants who had problems with that. We will announce our decision about this problem soon.

UPD2: There were trains with length equal to one in tests for problem Subway Roller. Jury decided to accept the first right solution of each user that passed all tests except the wrong, also other submissions were ignored. In addition we accept all successed hacks, although the hack is not correct and the hacked solution passed all other tests. Contest will be rated, but any user who think that this situation is cardinally affected to his/her result can send me in 24 hours a message and jury will discuss the question to make round unrated only for that participant. We are apologize to participants one more time for this situation.

UPD3: Editorial

Hi Codeforces!

Today while solving problem F from Zepto-cup I need an array of linked lists of size about 6·10⁵ and I decided to use std::stack. But I got ML cause that array has a size of about 350MB. Then I replaced std::stack by std::list and got AC. Anyone know why std::stack use so lot of memory?

#include <stack>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 600 * 1000 + 3;

stack<int> z[N];

int main()
{
	z[rand()].push(rand());
	cout << z[rand()].size() << endl;
	return 0;
}
=====
Used: 420 ms, 352524 KB

#include <list>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 600 * 1000 + 3;

list<int> z[N];

int main()
{
	z[rand()].push_back(rand());
	cout << z[rand()].size() << endl;
	return 0;
}
=====
Used: 0 ms, 4704 KB

Happy new 2015 year!!! Hope that everyone celebrates it very cheerfully and wish you to achieve every target that you have for this year!

Tomorrow will be next SRM #644 at 07:00 EST.

Good luck and have fun to participants!!!

Hi everyone!

Today I've got to know that there is a nice algorithm for online MST problem.

The problem looks like this: we have an undirected weighted graph and queries to change the weight of edge, after each query need to find the weight of MST.

I've heard that exist an O(n logn) algorithm for this problem. Can anyone give me some link to the article? Or any book in which I can read about it. Thanks in advance.

Hi!

Anyone know where I can download samples for this problem?

Link from problem is not available