RussianCodeCup's blog

By RussianCodeCup, history, 14 hours ago, translation, In English,

Hi, everyone!

There are already more than 400 participants who are preparing for the Elimination Round of Russian Code Cup 2017. If you are still among those who has not qualified yet, we invite you to take part in the Third Qualification Round that will take part this Saturday, April 29, at 14-00 Moscow Time. Top 200 participants will also qualify to the Elimination Round and will be able to compete to get to the Final Round of Russian Code Cup 2017.

Good luck and see you at russiancodecup.ru!

Read more »

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

By RussianCodeCup, history, 13 days ago, translation, In English,

A. Very Important Persons

There are two main ways to solve the problem.

The first way is to assign guests to seats by diagonals, starting from the seat (1, 1). You should be careful with considering cases n < m and m < n when implementing traversal.

The second way is a more common solution which however requires more advanced algorithm. Let us run BFS from (1, 1) and assign seats to guests in order they are popped from the queue, starting from the most important one.

B. Least Common Multiple

Let p / q be divisible by both a / b and c / d, all fractions are irreducible. So the numbers (p / q): (a / b) = (p·b) / (q·a) and (p / q): (c / d) = (p·d) / (q·c) are integers.

Since p·b is divisible by q·a, b and a are relatively prime, then p is divisible by a. p and q are also relatively prime, so b is divisible by q. Similar argument allows to conclude that p is divisible by с, and d is divisible by q.

Therefore p is divisible by lcm(a, c), q is a divisor of gcd(b, d). The fraction lcm(a, c) / gcd(b, d) is divisible by both a / b and c / d, and is therefore the smallest such fraction. So the answer is lcm(a, c) / gcd(b, d).

C. Bad Order

You have to add numbers to the given array to convert it to a permutation that requires maximal number of swaps when being sorted by selection sort.

First suppose that the permutation is fixed. Let us find the number of swaps that selection sort makes. Consider permutation as a set of cycles. Let us consider a cycle that contains the minimal number that occupies wrong position. Length of this cycle is greater than 1. After we make a swap, it is split to two cycles: of length 1, and 1 shorter than its initial length. Therefore the cycle of length L will be split L - 1 times, so the number of swaps required is n - c, where c is the number of cycles.

Therefore we must add numbers to the given array in such way that the number of cycles in the resulting permutation was minimal possible. To do it consider the given array as a directed graph, if a[i] = j, add an edge from i to j. The graph is a union of cycles and paths. All cycles in the graph will remain there after we convert the array to a permutation. All paths can be concatenated to a single long cycle (vertices without both incoming and outgoing edges are considered paths of length 0). To do so, order paths arbitrarily, and add an edge from the end of each path to the beginning of the next path. Finally make them a single cycle by adding an edge from the end of the last path to the beginning of the first one.

D. Red-Black Tree

First you must notice a subtle hint in the first sentence of the statement. It is easy to prove (or find in any data structures textbook) that red-black tree with n vertices has O(log(n)) black vertices on any path from the root to a leaf. Let us use this fact in our solution.

Let us call a tree almost red-black if its coloring satisfies all constraints of the red-black tree, except that its root is red.

We can now use dynamic programming to calculate for each subtree the number of ways to color it to become red-black or almost red-black, and to have the number of black vertices on any path from its root to a leaf equal to h.

Let us denote the described number of ways as d[v][h][t], here v is the vertex, h is the number of black vertices on any path from v to a leaf in its subtree, t is the type of coloring, t equal to 0 would, for example, mean that the subtree is red-black, and t equal 1 would mean that the subtree is almost red-black.

Now d[v][h][0] is the product for all u children of v of values (d[u][h - 1][0] + d[u][h - 1][1]). Similarly, d[v][h][1] is the product for all u children of v of values d[u][h][0].

The answer to the problem is the sum for all h of values d[1][h][0].

Since h for all valid colorings is limited by C = O(log(n)), we can consider the number of colorings be zero if h > C.

So we only need O(nlog(n)) states, and O(1) to calculate the result for each state. The time complexity is O(nlog(n)).

E. Array Study

Since there are the same constrains to n and q, let us use n instead of max(n, q). Let us make some observations.

Observation one: the answer to the query is the maximal length of [L, R], such that prefL - 1 = prefR, where prefi = a1 + a2 + ... + ai is the prefix sum of the given array. Let us move from the initial array to the array of prefix sums and for a query [l, r] look for the longest subarray of [l - 1, r] such that prefL = prefR.

Observation two: prefi are quite small ( - n ≤ prefi ≤ n).

Let us make use of queries given offline. Our method will be similar to Mo's algorithm. Split all queries to groups, the i-th group will contain queries [li, ri] such that i·K ≤ li < (i + 1)·K (here K is approximately sqrt(n)). In each group sort queries by their right end. Let us solve the problem separately for each group.

Consider the i-th group, where li is in [Li, Ri]. Let us consider queries by non-decreasing of ri, and maintain two arrays: mostLeft[p] and mostRight[p] — the first after Ri and the last before r occurrence of the prefix sum p. Using these two values, we can find the answer that is subarray of [Ri + 1, r]. To get the complete answer to [l, r] query, let us calculate the answer with the beginning of the required subarray at [l, min(r, Ri)] using mostRight array, and take maximum of that value and the optimal subarray for [R + 1, r].

So it takes O(K·ci + n) to answer all queries of one group, here ci is the number of queries in that group. Adding up all O(n / K) groups, we get the total time complexity O(sum(i = 1... n / K: K·ci + n)) = O(K·sum(ci) + n2 / K). Setting K = sqrt(n) we get O(n·sqrt(n)) complexity.

Read more »

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

By RussianCodeCup, 2 weeks ago, translation, In English,

Hello everyone!

Top 200 from the First Qualification Round have already advanced to the Elimination Round, but the other paricipants still strive to get there. If you haven't qualified yet, we invite you to take part in the Second Qualification Round that will take place this Sunday, April 16, at 12-00 Moscow Time. Best 200 participants will advance to the Elimination Round, other participants can try again in the Third Qualification Round.

Good luck to everyone, see you at http://russiancodecup.ru!

Read more »

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

By RussianCodeCup, history, 4 weeks ago, translation, In English,

A. Martian Volleyball

First note that in order to end the game as soon as possible only the currently leading team must get points.

Consider the condition that one of the teams wins. It must score at least k points and have at least 2 points advantage.

So the answer is max(k, min(x, y) + 2) - max(x, y).

B. Painting the Wall

First note that if the maximal length of the continuous segment is L, at least L colors are needed to paint the wall. On the other side L colors is always enough.

Consider a square L × L, fill the first line with integers from 1 to L, fill the following lines with all its possible circular shifts. Use these squares to cover the given wall rectangle like this (L = 4):

1 2 3 4 1 2 3 4 1 2

2 3 4 1 2 3 4 1 2 3

3 4 1 2 3 4 1 2 3 4

...

Now each vertical and horizontal segment of length L or less has all tiles of different colors. All that is left is to bring back the lamps.

C. Magic Artifact

Let us denote advantage that Maxim gets if he finds artifact as ci, so ci = ai - bi.

Let Maxim first complete levels in order 1, 2, ..., n. If he finds the artifact at the i-th level, the time he needs to complete the game is equal to bj plus c1 + ... + ci. So the expected time of completing the game is:

b1 + ... + bn + p1·c1 + p2·(c1 + c2) + ... + pn·(c1 + ... + cn).

b1 + ... + bn doesn't depend on level order, so let us try to make the rest as small as possible. Expanding the sums, we get sum of all ci·pk for such i, k that i ≤ k.

Let us now swap levels i and i + 1 in our order. For the given i among ci·pk terms only the one equal to ci·pi + 1 changes — it is replaced with ci + 1·pi. If the order was optimal, it must be ci·pi + 1 ≤ ci + 1·pi, in the other case it was optimal to swap them and get a better answer. Transform this to:

ci / pi ≤ ci + 1 / pi + 1.

In the optimal answer for all i from 1 to n - 1 this inequality must be satisfied. Therefore it is optimal to sort levels according to the key ci / pi. Note that if pi = 0, you may consider ci / pi = ∞.

Sorting according to the key ci / pi should be done carefully. If the fractions are compared using floating-point division, the case ci = pi = 0 will lead to error because 0 / 0 = NaN. If the fractions are compared using the comparator ci·pk < ck·pi, the case ci = pi = 0 will also lead to error because the result of that comparison will always be false. That means that levels with ci = pi = 0 should be handled separately. Such levels can be completed at any time because they do not affect the result besides fixed terms bi. For example, they can be placed at the end.

After sorting the desired expected value can be found using the formula above, use prefix sums for ci to get it fast.

D. Memory Manager

First for each query qi let us find goi — the minimal j, such that among qj, qj + 1, ..., qi there are at most k different blocks — that would mean that it is possible to place pointers before the j-th query in such way that queries j, j + 1, ..., i are performed immediately. This can be made in O(sum(|qi|)), using, for example, two pointers.

Now let us use dynamic programming, denote as dpi the minimal time needed to perform the first i queries. If goi = 0 then dpi = 0. If the equation is not satisfied, dpi = minj = goi..i(dpj - 1 + sj) — we choose the query j to perform the pointer movement before. Since values goi do not descend, this value can be maintained using either std::set of dpj - 1 + sj, or queue with minimum query support.

E. LISA

First let us consider the problem for given two strings: to solve it calculate the number of occurrences of each letter in the first string, the number of occurrences of each letter in the second string, not including the first letter of the first string and the last letter of the second string, that must be used any way. Now the answer is the product of string lengths, decreased by the sum of values cnt1[letter] * cnt2[letter] for each letter. Let us leave proof as an exercise, such problem was at Northern Subregional Contest of NEERC 2015 http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, Problem C. Unlimited participants could solve this problem at Three Quaterfinals Cup.

For n strings similar ideas can be used. Put all strings to a prefix trie, all strings to a suffix trie, the total number of ways to get a string is the product of the number of vertices in these tries. What we need to subtract is similar product of number of occurrences of letters in tries, first/last letters of each word must not be considered.

Now we need to answer segment queries. Let us make sqrt-decomposition, divide all strings to groups based on sum of their lengths. Let us greedily add strings to a group until their sum of lengths is more than sqrt(total sum of lengths). Note that the last string can have a big length.

Now use Mo's algorithm, sort queries using the block of the left end as a key, move right end only forward between left end block changes. To add/remove a string to a trie one must maintain the number of active vertices in a trie subtree for each vertex, and the number of entries of letters to a trie.

Read more »

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

By RussianCodeCup, 4 weeks ago, translation, In English,

Hi, everyone!

This Sunday, April, 2 at 19-00 Moscow time the First Qualification Round of Russian Code Cup 2017 will take place. 200 top participants will qualify for the Elimination Round, those who wouldn't qualify can still take part in two following qualification rounds.

We have a news for you: we have added Kotlin, Haskell and Free Pascal to our list of programming languages, also you can now submit your Python programs to run in PyPy. Exact versions of compilers and compilation commands are published at the official web site. We are working on adding more programming languages.

Good luck to everyone and see you at http://russiancodecup.ru!

UPD Editorial is published

Read more »

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

By RussianCodeCup, 6 weeks ago, translation, In English,

Hello, everyone and thank you for participation!

First of all we would like to say sorry for the length of the testing queue during the first hour. We have selected IOIP problems for the Warmup Round — there are many common problemsetters for IOIP and RCC — the round was prepared by Victoria Erokhina (viktoria), Dmitry Filippov (DimaPhil), Stanislav Naumov (josdas), Mikhail Putilin (SpyCheese), Grigory Shovkoplyas (GShark), Andrew Stankevich (andrewzta), Ilya Zban (izban). We wanted to let everyone solve our interesting problems.

But one small glitch lead to a big failure. You might have noticed that we usually make multiple tests in one input data for RCC. That is because the most expensive operation is to run user solution. But IOIP has fewer participants, so the easiest problem had 32 tests. It is not too many for a problem, but during 15 minutes 400 participants submitted the correct solution and our testing machines capacity was not enough.

We decreased the number of tests in the problem, and the situation got better. We will take this into account when preparing problems for future contests.

Now let us proceed to problem analysis.

A. Spaceship

Note that if the last enemy to destroy has power equal to x, the sum of powers of all enemies is 2x. Therefore to find the power of the enemy to destroy last, let us find the sum of all powers and divide it by two. After that just pick any enemy with such power and swap it with the last one.

B. Rangers in the Bus

Let us process passengers one by one. Since Pink Ranger could take any seat, any passenger can be Pink Ranger.

For each seat we want to be able to quickly answer if it is free. Let us use std::set that stores the set of occupied seats. To check whether the current passenger can be Red Ranger let us find the seat that Red Ranger would choose. Iterate row from 1 to n, and if there is a free seat in the current row, take the left seat if it is free, or the right seat in the other case. If the current passenger chose that seat, he could be Red Ranger. Similarly we can check whether the current passenger could be Blue, Black or Yellow Ranger. After processing the passenger, add the seat he chose to the set of occupied seats.

The solution described uses O(nk) time and O(k) memory.

To get rid of time limit, let us note that all we need is to store the minimal and the maximal row that have free seats. Use two indices first and last to store them. Initially first = 1, last = n. After each passenger update these values. Increase first by 1, until the row pointed by first is completely occupied, then similarly decreaser last. There are at most k / 2 occupied rows, so both indices will be changed O(k) times.

C. Magic Weapon

Precalculate arrays: R[a][b] — the number of red details that have the first digit of the model number equal to a and the last digit equal to b; G[a] — the number of green details that have the last digit equal to a; и B[b] — the number of blue details that have the first digit equal to b.

It model numbers of different colors were distinct, the answer would be equal to the sum for all a and b of values G[aR[a][bB[b].

To resolve the situation when some pair of details have the same model number, calculate the number of red-blue pairs with the same model number, red-green pairs and green-blue pairs. Note that only model numbers with the same first and last digit need to be considered. You can use std::map to calculate the number of such model numbers. Now use inclusion-exclusion principle to find the answer: subtract the number of pairs of each type and add back twice the number of triples that all three rangers use detail with the same model number.

D. Knights and Knaves

Let us use dynamic programming with mask of the last two columns as a state. Consider for example subtask of calculating the maximal number of knights.

Let dp[i][mask_prev][mask_cur] be the maximal number of knights that can be positined among the first i columns, where mask_cur is the mask of the i-th column, mask_prev is the mask of the (i - 1)-th. Use bit equal to 1 to denote a knight and 0 to denote a knave.

Try all possible masks for the (i + 1)-th column, check whether constraints for the soldiers in the i-th column are satisfied, because now we know all of their neighbors.

The first and the last columns must be considered separately, because soldiers there don't have one of the neighbors.

Initial values: dp[2][mask_prev][mask_cur] the number of ones in mask_prev and mask_cur, if mask_prev can be before mask_cur.

Updating values: relax dp[i + 1][mask_cur][mask_next] with dp[i][mask_prev][mask_cur] + ones(mask_next), where ones(x) is the number of ones in x.

The answer is the maximum among dp[k][mask_prev][mask_cur], such that mask_cur can be after mask_prev.

Finally, we probably need to consider k = 1 separately, because there is no previsous column for any column in this case.

E. Parallelepiped

Let us give a sketch of the main solution idea. First, separately consider all parallelepipeds that have two or three equal sides. This can be done in O(n).

Now let us consider the case where all three sides are different. Let us build the following undirected graph: vertices are side length, connect a and b if there are at least two sheets of size a × b. Now the problem is reduced to considering all triangles in this graph which can be done in O(n2 / w) or O(nsqrt(n)) time (here w is the word size, 32 or 64 which comes up from bit compression).

Read more »

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

By RussianCodeCup, 6 weeks ago, translation, In English,

Hi, everyone!

We are pleased to announce Russian Code Cup 2017! Qualification rounds will start in April, the Final round will be held online in September. Each of the three Qualification rounds will allow 200 participants to qualify for Elimination round, top 50 from Elimination round will proceed to Final round. The problems will be both in Russian and in English.

The full schedule of the tournament can be found at http://russiancodecup.ru, you can also register there. Note that you must register for the new season even if you took part in the previous tournaments.

We still have more than two weeks before the first Qualification, so we would like to invite everyone to the warm up round that will take plance on Sunday, March 19, 14-00 Moscow time. Visit http://russiancodecup.ru to take part in the round, it will be 2 hours long.

Good luck to everyone and see you at Russian Code Cup 2017!

UPD: We remind you that the Warmup Round will start at 14-00 Moscow time. Problems of the Warmup Round are based on IOIP problems (Russian contest for high school students, run today at several cities) that are prepared by the same team of authors. We kindly ask students that take part in IOIP to play fairly and not to try to take part in RCC Warmup. Good luck to everyone!

UPD2: Thanks to all participants that made a real stress testing for our judging machines. Unfortunately we had long queues during the first hour, they were fixed, and from the middle of the contest the waiting time in most cases was limited to 2-3 minutes. We will make sure there would be no queues during further rounds.

Read more »

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

By RussianCodeCup, history, 7 months ago, translation, In English,

Hi, everyone!

Russian Code Cup 2016 is over, the problems for the Final Round were more difficult than usually, but the participants didn't give up. The champion is Gennady Korotkevich tourist, the second place winner is Vladislav Epifanov vepifanov, the third place winner is Nikolay Kalinin KAN. Congratulations to the winners, the complete results are at the RCC web site http://russiancodecup.ru

Before proceeding to the tutorial, we would like to thank Mail.Ru Group for organizing the tournament and providing the prizes, and the judges from ITMO University for problems. Chief judge Andrew Stankevich andrewzta, judges Vitaly Aksenov Aksenov239, Nikolay Budin Budalnik, Dmitry Filippov DimaPhil, Borys Minaiev qwerty787788, Ilya Peresadin pva701, Grigory Shovkoplyas GShark, Artem Vasiliev vartem, Nikolay Vedernikov Niko, Ilya Zban izban.

And now the short tutorial. To get more details, you can read the programs of the judges solutions, published at the official site http://russiancodecup.ru together with the official tests.

A. Closing ceremony

Probably the easiest way to solve the problem is greedy. Sort people from the first line by increasing of their stamina. Give them tickets in this order, each time using the place which is furthest away from the other line. After that try to assign people from the second line to the remaining seats by sorting people by stamina and seats by the distance.

The time complexity of your solution must not exceed O((nm)2), however using std::set one can get a solution with complexity of O(nmlog(nm)).

B. Cactusophobia

Let us divide the graph to biconnected blocks. Each block is either a bridge, or a cycle. Our goal is to remove one edge from each cycle, so that the number of remaining colors were maximum possible.

Let us build a bipartite graph, one part would be blocks, another one would be colors. For each block put an edge of capacity 1 for each color of an edge in this block (make multiple edges, or bigger capacity if there are several edges of some color). Add two vertices: source and sink, add edges from source to blocks, if the block is a cycle of length l, set its capacity to l - 1, if it is a bridge, set its capacity to 1. Add edges from color vertices to the sink of capacity 1.

It is quite clear that size of the maximum flow in this graph is indeed the answer to the problem.

As a final note, the judges know the solution that runs in O(n) and requires no maximum flow algorithms, challenge yourself to come up with it!

C. Homework

The solution is constructive.

  • First let us use backtracking to find solutions for all n, m < 5, it is also better to precalculate all answers, in order not to mess with non-asymptotic optimizations.
  • Now m ≥ 5.
  • Let us put asterisks from left to right, one row after another. When adding the new asterisk, we add 4 new L-trominoes, except the first asterisk in a row that adds 1 new L-tromino, and the last asterisk in a row adds 3 new L-trominoes. Let us stop when the number of remaining L-trominoes k is less than 4, or there are less than 5 free squares in the table.
  • Now there are two cases
    • there is a free row
    • thee is no free row
  • If there is a free row, we stopped because k is now less then 4. So:
    • k = 0: the solution is found
    • k = 1: if there are already at least 2 asterisks in the current row, put the asterisk in the beginning of the next row, if there is only 1, put it in the end of the current row
    • k = 2, k = 3 — similar, left as an exercise.
  • If there are now free rows left, one can see that you can only add k from the set {0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 15} L-trominoes.
  • And finally there is also the special case where the size of the board is 3 × m, m ≥ 5 and k = 2 * (m - 1) - 8 — in this case the first column should be left empty, and the rest of the board must be completely filled with asterisks.
D. Slalom

First let us consider all paths from the starting square to the finish one. Let us say that two paths are equivalent, if each obstacle is at the same side for both paths. For each class of equivalence let us choose the representative path — the one that tries to go as low as possible, lexicographically minimum.

Let us use dynamic programming. For each square let us count the number of representative paths that go from the starting square to this one. When the obstacle starts, some paths can now separate. The new representatives will pass this obstacle from above (it will be to the right of them). So we add the sum of values for squares below it, but above any other lower obstacle, to the value for the square right above the obstacle.

To overcome the time and memory limits that the naive solution with O(nm) memory and O(nm2) time complexity, we use segment tree for range sum queries with mass update, running scanline and events "start of an obstacle", "end of an obstacle". This leads to the solution with O(m) memory and O(nlogm) time complexity.

E. Cipher

First let us consider a slow solution. Let us find a condition for each number k after what number of seconds Borya can distinguish it from the given number. Let us look at their initial encoding. Increase both numbers by 1 until the encodings are different (or one of the numbers needs more than n digits to represent in which case the beep allows Borya to distinguish the numbers as well).

Now there are two main ideas that allow us to get a better solution. First, we don't have to check all numbers. We only need to check numbers that differ from the given number in exactly one digit.

Second: to get the time when the numbers can be distinguished we don't need to iterate over all possible values. We just need to try all digit positions and all values for that position, and check only moments when the digit at the position will first have this value in one of the numbers.

So the complexity is now polynomial in n and since n ≤ 18, it easily fits into the time limit.

F. Array Covering

We give the outline of the solution, leaving technical details as an excercise.

First note that the answer will always use min(k - n, 0) subarrays with maximal sums. Sof let us find the sum of min(k - n, 0) maximal subarrays, elements that are used in them, and the following min(k, n) subarrays. We can do it using binary search for the border sum, and a data structure similar to Fenwick tree. For the given value of the sum this tree must provide the number of subarrays with greater or equal sum, sum of their sums, and the set of the elements of these subarrays. It should also allow to list all these subarrays in linear time complexity. This part has time complexity O(nlog2n).

Let us now describe how to solve the problem in O(n2logn). Let us try all values of x — the number of subarrays with maximum sums that we will use in our solution (there are O(n) variants, because top min(k - n, 0) subarrays will definitely be used). Let elements with indices i1, ..., im be the ones that are not used in these subarrays. Now we must add k - x segments that would contain all of these elements. Note that each of these k - x segments must contain at least one of these elements, and no two segments can have a common element among them (in the other case the solution is not optimal). These observations let us greedily choose these k - x segments in O(nlogn) and the final solution complexity is O(n2logn)

To optimize this solution, we keep segments [ij + 1; ij + 1 - 1] in the ordered set. When we iterate over x and increase its value, we remove some of the ij-s, and recalculate the required values for the affected segments. After that we must take k - x maximal values from the set, so since there are O(n) changes in total, this part now works in O(nlogn).

Read more »

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

By RussianCodeCup, history, 7 months ago, translation, In English,

Hi, everyone!

Tomorrow, on September 18, 2016, at 12-00 the Final Round of Russian Code Cup 2016 will take place. Top 50 participants of the Elimination Round will take part in the contest and have a chance to win great prizes. The length of the Final Round this year is 2 hours, the Final Round participants will compete online. You can watch the Final Round at http://russiancodecup.ru

Meanwile we are pleased to announce that the Russian Code Cup team together with Codeforces project have prepared a small surprise to all those who didn't manage to get to the Final Round of RCC-2016. After the Final Round ends, at 14-05 Codeforces will host online-contest with RCC-2016 Final Round problems.

The contest will use ACM ICPC rules and will not be rated. Problems will be in English and in Russian. Problems were prepared for Russian Code Cup Final Round, so they are quite difficult, the contest is mostly suitable for Div1 participants. Of course, we would like to ask the Final Round participants do not use the contest for testing their upsolved solutions, please wait until the end of the online contest and use the problem archive.

So, everyone is welcome to watch the Final Round and then to take part in the online-contest! Good luck to everybody!

Read more »

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

By RussianCodeCup, history, 10 months ago, translation, In English,
A. Important Test

For each variant consider all prefixes of tasks. It is optimal to copy the task that takes most time, so we keep track of maximal time and calculate the sum S of tij of the prefix. If the maximal time is greater than t0 it is better to copy this task, getting the total time needed be S - max(0, M - t0). Now compare this value to t to check whether it is possible to write down that many tasks for this variant.

B. Centipede

First sort all notes based on the number of left legs. Then iterate over this array. If the centipede has li left legs, then first i notes can be correct, and other notes are definitely incorrect (we can ignore the fact that some notes have the same li, we will find the answer considering them).

Now we want to find out how many of the first i notes can be correct. Note with number j ≤ i can be correct if rj ≤ n - li. This problem is quite standard, we can solve it using, for example, Internal Tree.

C. Binary Tree

To minimize the number of days Basil needs, we need to minimize the height of the resulting tree. If the depth of the leaf in the resulting tree is h, Basil needs 2h - 1 - n days to create the required number of vertices.

Note that if the tree has a vertex of degree greater than 3, it is impossible to fulfill the task, because in a complete binary tree every vertex has at most 3 neighbors. Also note that the root vertex must have two sons.

So let us try all vertices with degree not greater than 2 and try it as a root. Choose vertex which results in the smallest tree height.

Finding the most distant vertex for each vertex in a tree is a well known trick. Choose vertex 0 as a root and run dfs(0). First find h[v] for each vertex — the length of the longest path down starting from v. Then run dfs2(0) passing the longest path up[v] to a vertex v through its parent. To find it when running dfs2(x) from y we choose maximum among up[y] + 1, and maximal value of h[z] + 2 for all children z of y except x.

D. Containers and Reagents

The solution proceeds in several rounds.

  • If sum(mini) > sum(vi) — the answer is «NO»;
  • If sum(maxi) < sum(vi) — the answer is «NO»;
  • Pour mini·pi / 100 of ci to each container;
  • For each reagent i sort containers that have cj = i by increasing pj and pour the rest of reagent i to them;
  • Pour (maxj - minjpj / 100 of reagent cj to the container j;
  • The rest of reagents can be put to containers arbitrarily;
  • If after doing so there is still extra liquid the answer is «NO»;
  • Some containers may still have not enough liquid.
  • Consider such container i, first pour from other container reagents other than this container is marked by, not making it contain less then minj of liquid
  • If it is still not enough, we can now move liquid cj from container j, it will not ruin percentage condition any more.

Now the resulting distribution of reagents satisfies all required conditions.

Final note: there could be precision troubles in this problem. Although there were no such tests, they are possible, Petr Mitrichev (congratulations on winning the round!) found such test after the contest. We understand that this is not good, and will try to avoid such problems in future.

E. Money Exchange

Let us first solve the following problem: find the minimal amount of money that cannot be paid by a set of coins. Let us first consider that we have no coins and the maximal amount we can pay is 0.

Let us describe the step when we have considered all coins with the value not exceeding X and we can pay any sum up to Y, inclusive. Let the total cost of coins with value greater than X, but not exceeding Y + 1, be sum. Then if sum = 0, we cannot represent Y + 1 with this set. In the other case we can move to the state where we have considered coins with the value not exceeding Y + 1, and we can pay any sum up to Y + sum, inclusive.

Now we see, that the value of the greatest considered coin grows as Fibonacci numbers, so the process terminates in at most O(log Answer) iterations.

So what we need to do now is to find the sum of numbers not exceeding X at a segment. This can be done using Interval Tree, the final complexity is O(m log n log Answer).

F. Elimination Round, Problem F

The answer is «NO» only if d is not divisible by the greatest common divisor of all ai. In any other case the answer exists. First let us create any array that satisfies a1·x1 + a2·x2 + ... + an·xn = d, but not necessarily other conditions. To do this divide all ai and d to gcd(a1, ..., an). If n = 1, then x1 = d / a1. In other cases find the corresponding values for any prefix [1, p] such values xi, p that a1x1, p + ... + apxp, p = gcd(a1, ..., ap). Use induction. Set x1, 1 = 1. If we have xi, p and want to find xi, p + 1. Use extended Euclid algorithm to find s and t: s·gcd(a1, ..., ap) + t·ap + 1 = gcd(gcd(a1, ..., ap), ap + 1) = gcd(a1, ..., ap + 1). Then for i ≤ p xi, p + 1 = s·xi, p and xp + 1, p + 1 = t. Getting xi, n, find xi = d / gcd(a1, ..., anxi, n = d·xi, n. This solution takes O(n2), and doesn't finish in time limit. To decrease the time complexity, first find subset of ai that has gcd equal to 1. Iterate over ai and add the current ai to the set if it decreases the number of different divisors. Such subset would contain at most 7 elements. Use the algorithm described above for this set, for other elements set xi = 0.

Now the algorithm is fast, but the conditions for xi are not satisfied: they can exceed 106 by their absolute value and there can be zeroes. Now let us normalize the values. First let us decrease xi to not exceed 106. To do this make xi non-negative, and less then a1 for all i > 1. This can be done by the following operation: subtract kai from x1 and add ka1 to xi where k = (xi mod a1 - xi) / a1. Note that the results of this operation can be stored in 64-bit integers, because x1 cannot exceed |d - a2x2 - ... - anxn| < 106·106·105. Now consider xi starting from the second one, and for each one do the following: subtract a1 from xi and add ai to x1. Note that there exists i, such that after applying the operation to x1, ..., xi we have 0 ≥ x1 ≥  - 106. Now we have |xi| ≤ 106, so everything that is left is to get rid of zeroes. Let us pair all zeroes to each other, except probably one if the number of zeroes is odd. For each such pair (i, j) set xi = aj and xj =  - ai. We probably have one index p left such that xp = 0. Consider several cases:

  • If there exists xj such that it is not equal to ap by its absolute value, then apply the following operation: subtract sign(xj)ap from xj and add sign(xj)aj to xp.
  • If there is no such xj, but ap ≤ 5·105, for any xj we can apply the following operation: add sign(xj)ap to xj and subtract sign(xj)ap from xp.
  • Finally if none of the above is true there must be aq, such that aq ≠ ap. Now do the following: subtract sign(xj)ap from xq and add sign(xj)aq to xp. Now xq is zero. But if n > 2, it is the first case for q, if n = 2 it is the second case for q.

Finally note that we must make this normalization must be performed for each prefix in the algorithm described in the first paragraph, so that the intermediate results fit 64-bit type. See judges solution for more details.

Read more »

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

By RussianCodeCup, history, 10 months ago, translation, In English,

Hello!

Let us remind you that Russian Code Cup 2016 Elimination Round will take place on June 19, 2016 at 14-00 Moscow time. Top 200 from each qualification round can take part in Elimination round, 200 best coders in Elimination round will get branded championship t-shirt, and top 50 will advance to the Final Round that will take place in September. There are money prizes to grab in the Final Round.

Good luck everyone and see you at http://russiancodecup.ru !

Read more »

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

By RussianCodeCup, history, 11 months ago, translation, In English,
A. Rectangle and Squares

To solve this problem, notice that the sides of the Elijah's rectangle don't matter, only the area is considered. So he can use any number of squares to create a rectangle of size C × nC for any positive integer n.

The optimal n is the result of the division AB / C2 rounded either up or down. So we just check two variants and choose the better one. Additionally, it is important to remember that n > 0, so sometimes it is impossible to round down.

B. Zeroes and Ones

First notice, that we can make inversions only in one string. Also notice that the order of inversions doesn't matter.

So the solution is greedy: consider characters of the first string from left to right. If the corresponding character s1[i] ≠ s2[i], we inverse characters i, i + 1 of the first string. In the end check that s1[n] = s2[n], if it's not, there is no solution, in the other case we have found the only, and therefore optimal, solution.

C. New Track

The solution is using special construction.

First, let us show how to create the track with maximal possible k. Starting with the horizontal segment, each vertical segment would cross all previous horizontal segments except the adjacent one. The example with 14 segments is shown in the picture.

To get exactly k segments first draw 2l segments such that l(l - 1) / 2 ≥ k > (l - 1)(l - 2) / 2, make a small track with k intersections. To do so, start creating the maximal example, but terminate the last segment after required number of intersections. The remaining n - 2l segments can be added in the beginning of the track to form the spiral around the smaller track. See picture below for example, where n = 17 and k = 9.

The constraint on k is really the maximal bound on the number of intersections of n segments. We omit the proof, but the hint is: look at the number of intersections of the pair of segments n and n - 1 with pairs n - 3 and n - 4, n - 5 and n - 6, ..., 2 and 1 (or only the segment 1, if n is even).

D. Tree

Let us add weights to tree edges, and set edge weight equal to 1 initially for all edges. Now instead of removing the vertex we would change the weight of the edge from it to its parent to 0. The distance between any pair of vertices would be equal to the distance that would be should we had actually removed the vertex.

We can solve the new problem as follows. For each vertex in the initial vertex find the distance from the root to the vertex, and put the distances to the array in DFS order. After changing some edge weight, we must change the distances in the continuous segment of the array. This can be implemented using, for example, range tree.

Now the distance between vertices can be found, using : dab = da + db - 2·dlca, where lca — is the least common ancestor of a and b, dv — is the distance from the root to v.

E. Barbarians

Notice that the angriness of all people in one connected component is equal to their initial angriness multiplied by some value, the same for all islands in this component.

Let us process edge removal in time proportional to the size of the smaller components that appears after its removal. In this case the time complexity of the algorithm would be . To prove the complexity notice that for each vertex when it is in the smaller component, the size of the component at least halves. So it can only happen times.

If removing the edge we could know which component is smaller, we could traverse it and move its vertices to a new component, leaving the vertices from the larger one in the old one. But we don't know which component is smaller. So let us run two BFS-s simultaneously in both components, and when one of them terminates, terminate the other one as well. This way the time for such BFS would be proportional to the size of the smaller component.

Read more »

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

By RussianCodeCup, history, 11 months ago, translation, In English,

Hi, all!

The last possibility to get to the Elimination Round of Russian Code Cup this year is the Third Qualification Round, that will take place on Sunday, June 5, 16:00. Everyone who has not yet qualified is welcome to participate. Good luck, and see you at Russian Code Cup 2016!

Read more »

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

By RussianCodeCup, history, 11 months ago, translation, In English,

Hi all!

The second qualification round of Russian Code Cup 2016 will take place on Sunday, May 29, 2016, at 12-00! We invite everyone who has not qualified yet to take part. Those who would not qualify in the second round are invited to take part in the third round on June 5. Good luck to everyone and see you at the round, don't forget to register for the championship at http://russiancodecup.ru if you haven't done so already.

Read more »

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

By RussianCodeCup, 12 months ago, translation, In English,

A. Binary String

First notice that there is no solution in one of the following two cases:

  • Either |b - c| > 1
  • Or b = 0, c = 0, and both a ≠ 0 and d ≠ 0

For other cases there are two steps in the solution. First, construct the minimal string that satisfies conditions for 01 and 10 pairs. After that add a - 1 zeroes after the first zero, and d - 1 ones after the first one.

B. Train in a Tunnel

The solution is greedy.

First let's turn the light on in the first and in the last car. Then divide the train to one or more segments of continuous cars with light off. Сonsider one such segment. Iterate over cars and when you the sum of lengths of such cars would exceed h if we didn't turn the light on in the current car. Then turn the light in that car on, and continue from the next car.

C. Beautiful Partition

Consider a[1], it is either in M1, or in M2. Since it doesn't matter, let it be in M1. Then a[1] divides gcd(M1), therefore gcd(M1) — is the divisor of a[1].

Consider all divisors of a[1] (there are at most 1344 for numbers not exceeding 109). For each each divisor d all elements of the array that are divisible by dcan be put to M1 (in this case gcd(M1) would not be less then d, and the fewer elements are there in M2 — the greater gcd(M2) is), all the other elements can be put to M2. The answer can be relaxed with the value min(gcd(M1), gcd(M2)). For the purpose of relaxation we can ignore that M2 is empty and consider gcd for an empty set be equal to infinity. If we put any element to M2 the value of gcd(M2) will not be less then d in this case since all elements are divisible by d.

The time estimation is O(sqrt(a[1] + d(a[1])·n) where d(a[1]) ≤ 1344.

D. Problem Preparation

First let us solve the problem if there are no changes in ti. Let us generate new array cnt[j] equal to the count of i such that ti = j. Also calculate the array of prefix sums for cnt. Then for each k we can find the time for each friend in O(MAX / k) where MAX is the maximal time needed for one problem. We just iterate over all j and find the number of problems that require exactly j minutes for each friend using prefix sums array. The sum for all valid k of O(MAX / k) is O(MAXlogMAX).

Now let us see what happens if we change the time needed for the problem from t to t + 1. Note that only values for k which are divisors of t change. Since the number of divisors is small, we can just iterate over all divisors and change the answer just for them.

Similar idea works when t changes to t - 1, the answer changes only for such k that are divisors of t - 1.

E. Similar Subways

You have to find isomorphic connected subtrees of the two given trees with maximal number of vertices. Let us use dynamic programming to solve the problem.

Consider two directed edges (u1, v1) in the first tree and (u2, v2) in the second tree. Let the value dp[u1][v1][u2][v2] be equal to the maximal size of isomorphic subtrees, such that u1 is corresponding to u2 and vertices v1 and v2 are not included into the corresponding subtrees. Additionally, let us also calculate such value for v1 =  - 1 or v2 =  - 1, which means that any vertex from the first/second tree can be in a subtree. Then the answer to the problem is maximum over all u1, u2 of the values dp[u1][-1][u2][-1].

To calculate dp[u1][v1][u2][v2] we have to make correspondence between subtrees of u1 in the first tree and u2 in the second tree. Let us note that if e1 is the child of u1 not equal to v1, subtree of e1 contains fewer vertices then subtree of u1. So if we find the values in increasing order of sizes of subtrees, we can use values for all child subtrees. The value dp[e1][u1][e2][u2] gives us the maximal number we can get if we put correspondence between e1 and e2. So we can get the matrix a[e1][e2] which contains maximal values for each pair of adjacent vertices to u1 and u2, correspondingly. Now we have to find the maximal weight matching in this matrix which can be done by mincost flow, or Hungarian algorithm.

The complexity is O(n5).

Read more »

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

By RussianCodeCup, history, 12 months ago, translation, In English,

Hello, all!

We are glad to announce the final version of Russian Code Cup 2016 rules! The most important news of this year is that Russian Code Cup goes international, now the problems are available in both Russian and English. Anybody can participate, to enter the competition, please register at http://russiancodecup.ru, participants of previous championships need to confirm their participation in their profile.

This year the prize pool is again 750 000 rub. We have changed the structure of the prizes to give more money prizes away, so top 25 now get cash. The winner gets 150 000 rub, the second place gets 100 000 rub, the third place gets 65 000 rub. Those who take places from 4 to 10 get 30 000 rub, and places from 11 to 25 can account for 15 000 rub. Top 200 in elimination round get branded Russian Code Cup t-shirts.

There are three levels of the championship. First you must qualify in one of the three Qualification Rounds (May 8, May 29 and June 5). Top 200 from each round proceed to Elimination Round (June 19), top 50 from it proceed to Final Round (September 18). If you fail to qualify in a Qualification Round you can still try in the following Qualification Rounds.

We invite you to the Qualification Round 1 on Sunday, May 8, 19-00 Moscow Time, and wish everyone good luck!

Read more »

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

By RussianCodeCup, 12 months ago, translation, In English,

A. Secret Code

All you have to do is just implement the required counting. Identifying correct characters at correct positions is absolutely straightforward. Identifying correct characters at incorrect positions can be, for example, implemented using used[c] array with true values for characters in the secret code and false for other characters.

B. Chaos

Consider two maximal numbers of the initial array. The maximal possible value that can be obtained is their average value.

To prove this, you can see Doc's moves as removing one number from the board and replacing two other numbers with two copies of their average value. So the average value of two maximal numbers never increases.

The following strategy allows to get such value in the end: each move remove the minimal number and replace two maximal numbers with two copies of their average values. Starting from the second move the two maximal numbers will be the same and equal to the answer.

C. New Adventure of Marty and Doc

You have to minimize the sum Sum(i = 1..n, j = 1..m, 2·ai, j·(|i - x| + |j - y| + 1)). First notice that no term depends on both coordinates, so the sum can be divided to three sums: Sum(2·ai, j), Sum(2·ai, j·|i - x|) and Sum(2·ai, j·|j - y|).

The first sum is constant for the given input, so we need to minimize the second and the third sum which can be done independently by choosing the row and the column. Consider the second sum, it can be proved that the optimal value is achieved if we take r equal to the median of Sum(j = 1..m, a1, j) times 1, Sum(j = 1..m, a2, j) times 2, ..., Sum(j = 1..m, an, j) times n.

Column can be found using the same idea.

D. Teams Creation

Let's use dynamic programming.

Sort all skill levels, and for each value find the number of students with such skill level. Note that if the team contains students with skill levels l and r, all students with skill levels m such that l < m < r will also be in the same team. So let us calculate the value dp[i][j][f] — the number of ways to create j teams of students with skill levels up to i, the last team can (f = true) or cannot (f = false) have more students. To make a transition we need additional value f[k][g] counts the number of ways to create g teams of k students that have the same skill level. Let there be k students with skill level i + 1, we iterate over g from 1 to k and relax dp[i + 1][j'][f'] using f[k][g]. Note that this takes O(nk) because the total number of g attempted for each j is equal to n.

To find f[k][g] we consider the k-th student. He is either in the team on his own (f[k - 1][g - 1]) or in one of the other teams (f[k - 1][gg).

Both arrays are calculated in time O(nk), so the time complexity is O(nk).

E. Maximal Sum

Let us sort bj in decreasing order. Add values to array a in decreasing order as well until all numbers greater or equal to the current bj is added. Now the array contains only numbers ai ≥ bj. After adding the new ai use interval tree to find the maximal sum subsegment at the segment (see discussion here, for example, to learn how to do this using interval tree: http://codeforces.com/blog/entry/17780).

Read more »

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

By RussianCodeCup, history, 12 months ago, translation, In English,

Hi!

We are pleased to announce that in 2016 Russian Code Cup goes international! Problems will be available in two languages: Russian and English, everyone is welcome to participate!

Championship rules and time table will be announced next week, meanwhile we would like to invite you to take part in Warm Up round on Saturday, April 23, 18-00 Moscow Time (UTC+3). Register at http://russiancodecup.ru and participate!

Good luck and see you at Russian Code Cup 2016!

Read more »

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

By RussianCodeCup, history, 19 months ago, In Russian,

Задача А. Сгибание ленточки.

Идея: Владимир Смыкалов.
Реализация: Дмитрий Филиппов.
Разбор: Дмитрий Филиппов.

В задаче дана полоска 1×2n, которую сначала n раз сложили ровно пополам, а потом развернули обратно. Складывания возможны двух способов: левую половину наложить на правую или правую половину наложить на левую. Требуется отвечать на запросы — по номеру сгиба узнать, ориентирован он вверх или вниз.

Научимся отвечать на запрос за O(log 2n), то есть за O(n). Суммарное количество запросов не превосходит 105, поэтому этого вполне достаточно. Будем эмулировать процесс сгибания для каждого запроса. Зная текущие длину ленточки и номер сгиба, легко понять, в какой половине этот номер находится, а затем, зная, в какую сторону произойдет сгиб пополам, можно найти и новое положение сгиба в укороченной в два раза ленточке. Для ответа на запрос одновременно с положением поддерживаем, в какую сторону сейчас ориентирован сгиб. Итого, получаем решение за O(qn), где q — суммарное количество запросов.

Задача B. Сбор монет.

Идея: Виталий Аксенов.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

В задаче дана лента, разбитая на клетки, по которой ходит игрок. Каждую секунду в каждой клетке дополнительно появляется некоторое число монет, фиксированное для каждой клетки. Игрок за секунду может перейти в соседнюю клетку или остаться в текущей. Каждый раз когда игрок находится в некоторой клетке, он собирает все монеты, которые в ней находятся. Необходимо посчитать, какое максимальное число монет может собрать игрок за t секунд.

Заметим, что для каждой клетки важно знать только последний момент, когда игрок в ней находился. Рассмотрим путь игрока с конца. В каждый момент времени про некоторый непрерывный отрезок клеток уже известен последний момент их посещения, а для остальных клеток нет. Поэтому можно воспользоваться методом динамического программирования, состоянием которого будет отрезок посещенных клеток и текущее время. Кроме того необходимо хранить текущую позицию игрока. Заметим, что можно хранить только те позиции, когда игрок стоит на одном из концов отрезка посещенных клеток. Из каждого состояния существует не более чем два перехода — игрок может посетить клетку слева или справа от уже посещенных. Таким образом, время работы алгоритма составляет O(n2t).

Задача C. Топологическая сортировка и дети.

Идея: Артем Васильев.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

В задаче дан граф и его топологическая сортировка, некоторые элементы которой были стёрты. Нужно корректно её восстановить топологическую сортировку.

Рассмотрим сначала алгоритм, а потом докажем его корректность. Вершины, для которых дан порядок, будем называть помеченными, остальные — непомеченными. Мы знаем какие числа не использовались в топологической сортировке, будем выставлять их по одному от больших к меньшим в соответствие вершинам. У нас есть очередное нерасставленное число. Первым делом удалим все уже помеченные стоки. Далее для каждого непомеченного стока узнаем максимальное значение в помеченной вершине, достижимой по обратным рёбрам. Для каждой вершины это число можно предподсчитать заранее: находим какую-либо топологическую сортировку графа и решаем задачу динамического программирования. В качестве соответствующей вершины нерасставленному числу выбираем любой сток, у которого предподсчитанное число наибольшее, и удаляем его из графа.

Предподсчёт чисел выполняется за O(V+E). Каждую итерацию нужно выполнять как можно быстрее, поэтому в каждой вершине мы храним количество оставшихся из неё исходящих рёбер. Когда мы удаляем сток, у всех вершин, из которых есть в него ребро, уменьшается исходящая степень, и если эта степень становится нулём, помещаем эту вершину в сет по предподсчитанному значению. Тем самым в нашем сете хранятся все стоки, и для выбора нужного нам достаточно взять самую последнюю вершину из сета. Каждая вершина кладётся в сет и вытаскивается ровно один раз. Итого время работы алгоритма: O(V·log(V) + E).

Теперь докажем корректность нашего алгоритма. Заметим, что нам достаточно доказать правильность первого шага алгоритма, далее используем метод математической индукции. Рассмотрим корректно заполненную топологическую сортировку p, предварительно выкинув все помеченные стоки. Далее рассмотрим сток s, который мы выбрали нашим алгоритмом для максимального числа, и сток, которому оно соответствует в топологической сортировке p. Если мы все числа в перестановке большие p(s) уменьшим на единицу, а выбранному нами стоку s выдадим максимальное число, перестановка останется корректной. Операция произошла корректно: мы сохранили свойство топологической сортировки для непомеченных вершин, а для помеченных вершин значение топологической сортировки не поменялось, так как по свойству выбора вершины s p(s) больше, чем значение топологической сортировки любой помеченной вершины.

Задача D. Правильный сад.

Идея: Артем Васильев.
Реализация: Артем Васильев.
Разбор: Артем Васильев.

В этой з[адаче дано множество точек на плоскости, и введено понятие хорошего множества точек. Хорошим множеством точек называется такое множество точек, что любой невырожденный прямоугольник со сторонами, параллельными осям координат и с противоположными углами в заданных точках содержит хотя бы одну другую точку из этого множества внутри или на границе. Требуется проверить, обладает ли заданный набор точек таким свойством.

Для начала докажем эквивалентное свойство: множество точек хорошее тогда и только тогда, когда для каждого угла такого прямоугольника существует точка на смежной с этим углом стороне. Очевидно, если выполняется это свойство, то выполняется и свойство, описанное в условии задачи. Однако, верно и следствие в противоположную сторону: рассмотрим произвольный прямоугольник с углами в точках A и B. По предположению, внутри или на границе этого прямоугольника существует другая точка из множества, назовем ее C. Если эта точка уже лежит на стороне, смежной с A, то наше утверждение верно. Иначе рассмотрим прямоугольник, построенный на точках A и C. Его площадь строго меньше, чем площадь исходного прямоугольника, а точек в множестве конечное число, значит когда-нибудь мы выберем точку, лежащую на стороне, смежной с A.

Сформулированное свойство помогает дойти до решения: для точки (xi, yi) обозначим за lefti такой максимальный x < xi, что в заданном наборе существует точка (x, yi). В случае, когда это значение не определено, считаем его равным равным минус бесконечности. Аналогичным образом введем величины righti, downi и upi. Рассмотрим область (lefti, righti) × (downi, upi). Если в этой области есть другая точка из заданного набора, то можно найти две точки, для которых построенный прямоугольник нарушает свойство. Стоит заметить, что подходит не любая точка из этой области. В качестве второй точки всегда подходит, к примеру, ближайшая по евклидовому или манхэттенскому расстоянию. Когда в этой области находится только точка (xi, yi), все прямоугольники содержат другую точку на стороне, смежной с ней. Таким образом, решение свелось к проверке n прямоугольников на наличие более одной точки внутри.

Реализовать такую проверку можно с помощью любой структуры данных, которая позволяет считать количество точек в прямоугольнике на плоскости: двумерное дерево отрезков (онлайн решение) или оффлайн решение со сканирующей прямой и одномерным деревом отрезков. Такое решение можно реализовать за O(n log(n)).

Задача E. Междуречье.

Идея: Виталий Аксёнв.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче даны n непересекающихся монотонных ломаных и выпуклый многоугольник. Нужно узнать, какое минимальное число раз нужно приложить многоугольник, чтобы каждая ломаная имела хотя бы одну общую точку с одним из приложенных многоугольников (на границе или внутри многоугольника).

Заметим, что поскольку многоугольник выпуклый, а ломаные монотонны и не пересекаются, верен следующий факт: если многоугольник пересекает ломаные i, k, то для любого j, что i ≤ j ≤ k, этот многоугольник пересечет и j-ю ломаную. Используя этот факт, будем решать задачу жадно: найдем максимальное i1, такое, что существует многоугольник, пересекающий все ломаные с 1-й по i1-ю, добавим его к ответу, и продолжим: найдем максимальное i2 такое, что существует многоугольник, покрывающий ломаные с i1+1-й по i2-ю, и так далее. Число многоугольников, которые пришлось использовать, и будет ответом.

Научимся для ломаной ik находить значение ik+1. Это максимальный индекс, такой, что существует многоугольник, покрывающий ik+1-ю и ik+1-ю ломаную. Решим сначала более простую задачу: есть точка A и отрезок BC, нужно проверить, существует ли многоугольник, содержащий внутри себя и данную точку, и какие-то точки отрезка. Для этого построим сумму Минковского этого многоугольника и его самого же, инвертированного относительно (0, 0) (то есть, с противоположными по знаку координатами всех точек). Это какой-то новый многоугольник, назовем его P, с O(n) вершин, содержащий внутри себя точку (0, 0). Сдвинем его так, чтобы точка (0, 0) перешла в точку A, и проверим, что отрезок BC пересекается со сдвинутым многоугольником P — несложно убедиться, что это необходимое и достаточное условие.

Научившись проверять, существует ли многоугольник, пересекающий точку и отрезок, проверить то же самое для двух ломаных совсем несложно: перебираем отрезок на одной ломаной, строим его сумму Минковского с многоугольником P, и проверяем, пересекается ли новый выпуклый многоугольник с каким-нибудь отрезком второй ломаной.

Пусть k — суммарное число вершин на всех ломаных. Найдём асимптотику используемых нами операций — O(n) на построение многоугольника P, O(n) на построение суммы Минковского P и отрезка ломаной и O(log n) на проверку пересечения выпуклого многоугольника и отрезка. Так как многоугольников нужно построить максимум k, а пересечь в худшем случае нужно каждый многоугольник с каждым отрезком, итоговая асимптотика времени работы равна O(nk + k2log n).

Задача F. Робот на дереве.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

В задаче дано неориентированное дерево из n ≤ 10 вершин. Про каждое ребро известна его прочность wi, которая не превышает 15. По дереву перемещается робот, который изначально находится в случайной вершине. Каждый раз робот равновероятно выбирает ребро из тех, по которым он может пройти, и перемещается по нему. Каждый раз когда робот проходит по ребру, его прочность уменьшается на единицу. Если прочность становится равна нулю, то ребро удаляется. Если у робота нет ребер, по которым он может пойти, он останавливается. Необходимо посчитать математическое ожидание длины пути робота.

Для начала решим более простую задачу. Предположим, что необходимо посчитать не математическое ожидание длины пути, а количество различных путей, по которым мог пройти робот. Представим, что мы зафиксировали вершины, в которых робот начал и закончил свой путь, а также количество раз, которые робот прошел по каждому ребру. Рассмотрим, какие существуют ограничения на эти количества. Во-первых, ребра, по которым робот прошел положительное число раз, должны образовывать связный подграф исходного дерева. Во-вторых, рассмотрим некоторую вершину и количество раз, которые робот прошел по всем ребрам, которые являются смежными с этой вершиной. Если эта вершина является концом пути, то каждое смежное с ней ребро должно использоваться ровно wi раз. Максимум два ребра смежных с вершиной должны быть использованы нечетное число раз. Причем, если эта вершина лежит на пути из стартовой в конечную, то ровно два ребра должны быть использованы нечетное число раз. Для стартовой и конечной вершины (если они не совпадают) должно быть ровно одно ребро, которое используется нечетное количество раз, либо ноль, если вершины совпадают. Для всех остальных вершин все смежные ребра должны быть использованы четное число раз.

Если все эти условия выполнены, научимся считать количество путей, которые удовлетворяют условию задачи и используют ребра фиксированное количество раз. Для каждой вершины рассмотрим все смежные с ней ребра. Мы знаем количество раз, которое робот прошел по каждому из них. Мы можем легко посчитать, сколько раз робот прошел по ребру в направлении от заданной вершины. В каком порядке робот мог проходить по этим ребрам? Во-первых, по ребру, которое лежит на пути к вершине, в которой робот закончил путешествие, робот должен пройти в последнюю очередь. По всем остальным ребрам он может идти в любом порядке. Подсчет количества таких способов является стандартной задачей. Чтобы посчитать общее количество путей, по которым может пройти робот, необходимо перемножить посчитанные значения для каждой вершины.

Заметим, что для подсчета общего количества путей можно воспользоваться методом динамического программирования. Посчитаем количество путей, которые проходят по некоторому ребру заданное число раз и каким-либо образом проходят по поддереву, которое ограничено этим ребром. При этом считается, что каждый раз, когда путь идет вверх по ребру, он сразу же возвращается назад по нему. Чтобы посчитать значение динамического программирования необходимо зафиксировать количество раз, которые робот прошел по каждому из ребер, которые идут в поддеревья, умножить на уже посчитанные значения для поддеревьев, а также на количество способов расположить переходы в поддеревья. Будем рассматривать поддеревья вершины по очереди и фиксировать количество раз, которые суммарно робот пойдет во все рассмотренные поддеревья. Рассматривая очередное поддерево переберем количество раз, которые робот перейдет в это поддерево. Домножим ответ на значение динамического программирования от поддерева, а также на количество способов расставить переходы в поддерево среди других переходов.

Вернемся к первоначальной задаче. Теперь вместо количества способов будем хранить вероятность выбрать такой путь, а также математическое ожидание его длины. Подсчет вероятности отличается от подсчета количества способов только тем, что при каждом переходе по ребру необходимо поделить значение на количество ребер, которые инцидентны данной вершине. Единственная проблема, которая возникает при этом заключается в том, что степень вершины не является константой, так как ребра удаляются во время путешествия робота. Чтобы посчитать значения динамического программирования для ребра воспользуемся следующей идеей. Зафиксируем все поддеревья, ребра в которые будут удалены, а также общее количество раз, которое робот будет идти из вершины по некоторому ребру. Будем восстанавливать путь с конца. Существует два возможных варианта, которые необходимо различать. Либо робот идет по ребру, которое не будет удалено, тогда нужно уменьшить количество ребер, по которым еще необходимо пойти роботу и перейти к меньшей задаче. Либо робот идет по ребру, которое будет удалено, тогда к общему количеству ребер, по которым роботу необходимо пройти, нужно добавить количество раз, которые он пройдет по данному ребру, а также увеличить количество существующих инцидентных ребер на единицу.

Всего существует O(2childrenwi) состояний в динамическом программировании для заданного ребра, и переход между ними осуществляется за O(1). Так как необходимо посчитать значение динамического программирования для каждого количества раз, в которых было использовано ребро, общее время работы алгоритма получается равным O(2n(∑wi)2).

Read more »

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

By RussianCodeCup, history, 19 months ago, In Russian,

Всем привет!

Финал Russian Code Cup в этом году пройдет онлайн, но финалисты могут по желанию приехать лично на одну из двух площадок на выбор: офис Mail.Ru Group в Москве или в Университет ИТМО в Санкт-Петербурге.

В то время как участники будут решать выданные задания, с 11:30 по московскому времени на сайте https://it.mail.ru/rcc в прямом эфире будет транслироваться ток-шоу, посвящённое прошлому, настоящему и будущему программирования и высоких технологий.

Среди гостей такие известные люди как Николай Никифоров — министр связи и массовых коммуникаций РФ, Наталья Касперская — генеральный директор InfoWatch, Сергей Андреев — президент ABBYY, Болтунов Олег — член PostgreSQL Foundation, Алексей Пажитнов — изобретатель игры «Тетрис» и многие другие.

Гости будут обмениваться мнениями по самым разным вопросам, связанным с развитием IT и программирования. В качестве ведущих выступят Антон Комолов и Михаил Мирзаянов, руководитель Центра олимпиадной подготовки программистов Саратовского Государственного Университета.

Трансляция пройдёт 19 сентября с 11.30 до 16.00 московского времени на https://it.mail.ru/rcc

Среди зрителей будут разыгываться призы, так что приглашаем всех присоединиться к трансляции Russian Code Cup, а финалистам желаем удачи!

Read more »

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

By RussianCodeCup, 22 months ago, In Russian,

Благодарности

Прежде чем перейти к разбору задач, мы хотели бы поблагодарить всех, кто помогал делать отборочные раунды Russian Code Cup.

Руководитель подготовки задач Андрей Станкевич andrewzta

Члены жюри, авторы и разработчики задач:

  • Виталий Аксенов Aksenov239
  • Артем Васильев VArtem
  • Николай Ведерников Niko
  • Илья Збань izban
  • Георгий Корнеев
  • Анна Малова
  • Борис Минаев qwerty787788
  • Дмитрий Филиппов DimaPhil
  • Григорий Шовкопляс GShark

Координатор разборов Виталий Аксенов Aksenov239

Прорешивали раунды:

Разумеется, те, кто участвовал в чемпионате, прорешивали только раунды, в которых они не могли участвовать.

Перейдем теперь к разбору задач.

Задача A. Игра со строками

Идея: Григорий Шовкопляс.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

В задаче дана строка, с которой можно делать следующие операции:

  • удалить три подряд идущих единицы;
  • удалить два подряд идущих нуля;
  • заменить подстроку «01» на подстроку «10»;
  • заменить подстроку «10» на подстроку «01».
Нужно посчитать, сколько существует способов получить строку определенной длины из данной, применяя эти операции.

Для начала посмотрим на операции замен и поймем, что это ни что иное как swap. Таким образом, мы можем получить из данной строки любую, в которой содержится такое же количество нулей и единиц.


Теперь с помощью этих операций получим из исходной строку, где все нули стоят в начале, а единицы в конце. Из получившейся строки мы можем получить строку новой длины, ничего не переставляя, так как все единицы и нули уже сгруппированы. Строку длины k, можно получить из строки длины n, удалив 3x единиц и 2y нулей, где k = n — (3x + 2y). Значения x и y можно перебрать.


И наконец, для каждой полученной строки нужной нам длины, нужно учесть все перестановки. Их можно посчитать, например, как количество сочетаний из длины строки по количеству единиц в ней. Ответ будет равен сумме этих сочетаний для всех строк нужной длины, которые можно получить из данной.

Задача B. Разбиение на команды

Идея: Григорий Шовкопляс.
Реализация: Дмитрий Филиппов.
Разбор: Дмитрий Филиппов.

В задаче дан граф, на каждом ребре которого написаны числа 0 или 1, означающие, что концы ребра одного цвета или разного соответственно. Также некоторые вершины графа покрашены в белый или черный цвет. Спрашивается, можно ли как-нибудь покрасить в черный и белый цвета остальные вершины, чтобы информация, написаная на ребрах, была верна, и количество вершин черного и белого цвета было одинаковым?

Разобьем наш граф на компоненты связности. Заметим, что, зная цвет одной вершины в компоненте, мы можем восстановить цвет всех остальных. Из этого следует, что если в компоненте хотя бы одна вершина уже покрашена, раскраска всей компоненты единственна (кроме случая, когда в полученной раскраске нарушится какое-то из требуемых условий, тогда ответ на задачу — «NO»). Если же ни одна вершина еще не покрашена, вариантов раскраски два — можно покрасить любую вершину компоненты в белый цвет, восстановить цвета остальных вершин, а после этого, если их инвертировать — получим вторую раскраску.


Несложно заметить, что мы свели нашу исходную задачу к задаче о рюкзаке — из каждой компоненты мы можем взять некоторое количество белых вершин, и всего их надо набрать n ⁄ 2 (если n нечетное, ответ на задачу — «NO»). А это уже можно решить с помощью динамического программирования за O(n2).

Задача C. Карта.

Идея: Георгий Корнеев, Виталий Аксёнов.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

В задаче дан клетчатый выпуклый многоугольник на клетчатой плоскости. Нужно сложить его один раз по вертикальной линии сетки, чтобы площадь, занимаемая многоугольником после сложения, была минимальной.

Рассмотрим сначала самую простую версию задачи. Дан прямоугольник, и нужно его сложить, получив минимальную площадь. Очевидно, что его нужно складывать по линии сетки, ближайшей к середине. (Если таких две, то можно сложить по любой.) Рассмотрим функцию площади от позиции сгиба. Для прямоугольника с углами (x1, y1) и (x2, y2) эта функция имеет следующий вид:

  • На отрезках (-∞; x1] и [x2; +∞) функция равна площади прямоугольника;
  • На отрезке [x1; (x1 + x2) / 2] функция линейно убывает с коэффициентом y2y1;
  • На отрезке [(x1 + x2) / 2; x2] функция линейно возрастает с коэффициентом y2y1.
Итого: функция меняет своё состояние только в трёх точках. Между двумя подряд идущими точками функция является линейной.

Заметим, что так как наша задача дискретная, в случае, когда (x1 + x2) не делится на два, лучше бить функцию на пять участков между точками x1, ⌊(x1 + x2) / 2⌋, ⌈(x1 + x2) / 2⌉ и x2.

Пусть наш многоугольник задан n вершинами. Тогда несложно заметить, что выпуклый клетчатый многоугольник можно нарезать на не более n прямоугольников горизонтальными прямыми. Тогда функция зависимости площади от места сложения будет являться суммой функций для прямоугольников. Опять же несложно убедиться, что если мы возьмём все точки изменения для каждой функции и отсортируем их, то между двумя соседними точками глобальная функция будет линейной. Тогда в качестве ответа нужно взять минимум из значений в этих точках.

Чтобы это реализовать, нужно воспользоваться идеей событий. Каждое событие будет соответствовать точке изменения функции для какого-то прямоугольника. Тогда обрабатывая события слева направо и пересчитывая коэффициент линейной функции, несложно посчитать функцию в выделенных точках.

Задача D. Декартовы деревья.

Идея: Артем Васильев.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче дано n чисел yi, нужно было посчитать, сколько декартовых деревьев можно построить на множестве (i, yi).

Для начала заметим, что если все n чисел yi равны одному и тому же числу, то ответ — Cn, n -е число Каталана. Понять это можно, например, исходя из рекуррентной формулы: если в левое поддерево определить k вершин, то в правом окажется n-k-1 вершин, то есть Cnk=0n Ck·Cn-k-1.

Рассмотрим все вхождения максимального числа в массиве. Любая вершина с таким приоритетом может быть либо корнем, либо быть ребенком другой вершины с таким же приоритетом. Пусть вхождения максимума имеют индексы a1, a2, ..., ak. Тогда мы должны построить какое-то декартово дерево на вершинах a1, a2, ..., ak, и подвесить к нему какие-то декартовы деревья, построенные на вершинах (1, ..., a1-1), (a1+1, ..., a2-1), ..., (ak+1, ..., n). Заметим, что для соседних ai и ai+1 в любом декартовом дереве, построенном лишь на максимальных вершинах, одна из этих вершин будем предком другой, поэтому поддерево, построенное на вершинах (ai+1, ..., ai+1-1), мы сможем однозначно подвесить за одну из этих двух вершин.

Таким образом, число способов построить декартово дерево на вершинах с l по r равно cnt(l, r)=C k · cnt(l, a1-1) · ... · cnt(ak+1, r). Ответом будет являться cnt(1, n).

Задача E. Аллея.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

С математической точки зрения в задаче даны отрезки целочисленной длины. Необходимо разбить некоторые из них на более мелкие так, чтобы длина наибольшего отрезка была как можно меньше, а количество разбиений не превосходило заданного числа. Задача несколько усложняется тем, что суммарная длина всех отрезков может достигать 109, а количество запросов, на которые необходимо дать ответ, может достигать 106.

Рассмотрим, сколько необходимо сделать разбиений, чтобы ответ получился не более Ans. Для каждого отрезка длины Len необходимо сделать (Len — 1)/Ans разбиений (результат деления округляется вниз). Построим функцию количества необходимых разбиений от ответа для каждого отрезка. Сложим эти функции для всех отрезков. Для того чтобы найти минимальное значение Ans, которое можно достичь, сделав не более чем K разбиений, воспользуемся двоичным поиском.

Будем хранить функции в сжатом виде, а именно, сохраним значение функции для Ans только, если f(Ans) ≠ f(Ans-1). Можно доказать, что для отрезка длины Len потребуется O(sqrt(Len)) памяти, чтобы сохранить его функцию. Позиции, в которых меняется значение функции, можно определить за время пропорциональное их количеству. Максимальное суммарное число позиций изменения будет достигаться на тесте, в котором все отрезки имеют одинаковую длину. В случае ограничений, которые даны в условии задачи, их количество не может превышать 106·sqrt(103)=107.5.

Чтобы объединить несколько функций, которые сохранены в сжатом формате, необходимо отсортировать все моменты изменения функций. Для этого разобьем все позиции, в которых функции изменяются, на два класса. В первый класс отнесем все позиции, которые меньше 106. Их можно отсортировать подсчетом за время пропорциональное их количеству. Остальных же позиций будет немного, и для их сортировки можно использовать встроенные функции языка. Чтобы убедиться, что количество позиций, которые больше 106 невелико, сделаем следующее. Для того, чтобы отрезок максимальной длины не превосходил 106, достаточно сделать не более Len/106 разбиений отрезков. Поскольку, в условии задачи суммарная длина отрезков не превосходит 109, то количество изменений функции, позиции которых превосходят 106, будет меньше 1000.

Задача F. Освещение сцены.

Идея: Артем Васильев.
Реализация: Артем Васильев.
Разбор: Артем Васильев.

В этой задаче с довольно запутанным условием дан массив пар (мощность, множество выходов), и для каждой левой границы в массиве нужно найти минимальную правую границу, чтобы на этом подмассиве существовало подмножество пар со следующими условиями:

  1. Сумма мощностей должна быть не меньше Z;
  2. Множества выходов выбранных прожекторов попарно не пересекаются.
Подмассив с такими свойствами будем называть хорошим.

Для начала решим задачу для одной фиксированной левой границы. Такую задачу можно решить при помощи динамического программирования по двоичным маскам: dpmask — это максимальная стоимость прожекторов, для которых объединение множеств выходов является подмножеством mask. Формула пересчета для добавления одного элемента (p, m) выглядит так: dp'mask = max(dpmask, dpmask — m + p), если m является подмаской mask, и dpmask, иначе. Добавление одного элемента можно реализовать за O(2k). Когда dp2k — 1 становится больше или равно Z, надо выдать ответ.

Легко доказать, что при возрастании левой границы, соответствующая правая граница неубывает. Это позволяет использовать технику двух указателей для нахождения ответа. Для реализации техники двух указателей необходимо реализовать структуру данных, которая поддерживает следующие операции:

  1. Добавить элемент в конец;
  2. Удалить элемент из начала;
  3. Ответить на запрос: "Является ли текущее множество прожекторов хорошим?".

Решение данной задачи использует реализацию очереди на двух стеках с идеями из метода реализации очереди с минимумом. Аналогично очереди с минимумом, будем хранить в стеках не просто элементы, а пары (элемент; массив dpi, в котором содержатся значения ДП для элементов с текущего и ниже). Добавление одного элемента в такой стек можно выполнить за O(2k), удаление за O(1). Окончательно, используя такую модификацию стека в очереди, можно отвечать на запрос типа 3 за O(2k): ответ на него положителен тогда и только тогда, когда maxi = 0..2k-1 dp1i+dp22k-1-i ≥ Z, где dp1, dp2 — массивы значений ДП на вершине первого и второго стека, соответственно.

В заключение, вспоминая, что каждый элемент в результаты работы очереди, реализованной на двух стеках, перемещается O(1) раз, получаем, что решение работает за O(n2k) времени и использует O(n2k) памяти.

Read more »

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

By RussianCodeCup, history, 23 months ago, In Russian,

Всем привет!

Чемпионат Russian Code Cup 2015 приближается к финишной прямой. В ближайшее воскресенье 14 июня в 13:00 состоится отборочный тур RCC-2015. В отборочном туре примут участие 604 лучших по итогам трех квалификационных раундов — борьба была такой напряженной, что в первой и третьей квалификациях 200-е место оказалось поделено, и в отборочный раунд прошло по 202 участника.

Обратите внимание, что отборочный тур длиннее квалификационных и продлится 3 часа.

По итогам отборочного раунда 200 лучших раунда получат фирменную футболку наших соревнований, а топ 50 участников пройдут в финальный раунд и получат возможность сразится за ценные призы. Финал состоится 19 сентября и, как и в прошлом году, пройдет онлайн. В соответствии с правилами соревнований в финал могут пройти только те, кому на момент проведения финала исполнится 18 лет.

Приглашаем квалифицировавшихся принять участие в отборочном раунде, а всех остальных поболеть за своих друзей на сайте http://russiancodecup.ru!

Read more »

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

By RussianCodeCup, 23 months ago, In Russian,

Задача A. Покупка велосипеда.

Идея: Виталий Аксёнов.
Реализация: Дмитрий Филиппов.
Разбор: Дмитрий Филиппов.

По условию задачи нужно сказать, можно ли по данным числам a, b, c найти такие числа a1, b1, что a1  ≤  a, b1  ≤  b и a1 + 2 · b1 = c.

Решение у этой задачи простое: почти всегда достаточно проверить, что суммарный номинал наших монет не меньше c: a + 2 · b  ≥  c. Исключение — когда c нечётное. Тогда ещё нужно проверить, что a  ≥  1.

Задача B. Цифровые корни.

Идея: Григорий Шовкопляс.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

В этой задаче нужно по числам a и b определить, какие из значений цифрового корня встретятся на этом отрезке наибольшее количество раз.

Заметим, что у цифрового всего девять значений, а также они циклически повторяются. Таким образом, нужно вычислить только цифровые корни от a и b, а чаще всего встречаются цифры между значениями этих цифровых корней. Единственное, что нужно было дополнительно учесть — это случай, когда цифровой корень a больше чем цифровой корень b. Также нужно было не забыть, что ответ нужно выводить по возрастанию.

Задача C. Две улитки.

Идея: Дмитрий Филиппов.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

В этой задаче две улитки днём поднимаются на ai, а ночью опускаются на bi. Требуется определить, сколько по времени первая улитка обгоняла вторую.

Задача решается моделированием. Рассматриваем часы последовательно. Для начала узнаем сейчас день или ночь. Посмотрим положение улиток до начала этого часа и после. Если до начала часа одна была выше другой, а после окончания часа, также была выше, то обгона не было. Тогда, если выше была первая, то к ответу добавим один час. Если же в начале часа была выше, а потом ниже, следовательно одна обогнала другую. Для того, чтобы узнать время, когда одна обгонит другую, надо посчитать расстояния между ними и поделить на разницу скоростей. После этого добавить к ответу время, в когда первая улитка была выше второй в этот час.

Задача D. Игровые автоматы.

Идея: Анна Малова.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

Нам даны кнопки, которые умеют выключать какой-то набор из лампочек, и кнопки, которые умеют включать какой-то набор лампочек. Задача: с помощью кнопок перевести лампочки из выключенного состояния в заданнное, или сообщить, что такое сделать нельзя.

Сначала, поймём, что дважды нажимать одну и ту же кнопку не имеет смысла, так как мы всегда можем оставить только последнее её нажатие, и конечное состояние не изменится. Далее, рассмотрим задачу с конца. У каждой лампочки будет три состояния: включена, выключена и неизвестно. Когда мы обращаем нажатие кнопки, помечаем все лампочки, за которые она отвечала, что их состояние неизвестно.

Мы могли нажимать кнопку, если:

  • кнопка выключает лампочки, то состояния изменённых лампочек должны быть или выключены, или неизвестны;
  • кнопка включает лампочки, то состояния изменённых лампочек должны быть или включены, или неизвестны.

Смотрим на последнее состояние, и нажимаем кнопки, каждую по одному разу, если это возможно. Пусть ни одну кнопку нажать нельзя, то нужно проверить, правда ли лампочки или выключены, или неизвестны, что соответствует стартовому состоянию. Если правда, мы можем последовательностью нажатий перейти в заданное состояние, иначе — нельзя.

Задача E. Интернетопровод.

Идея: Виталий Аксёнов.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче дано n точек, и нужно найти некоторую прямую l и расстояние d такие, что количество точек, расположенных ровно на расстоянии d от прямой l было максимально.

Любая прямая задается тройкой коэффициентов a, b и c таких, что ax+by+c=0. Две прямые (a1, b1, c1) и (a2, b2, c2) параллельны, если коллинеарны векторы (a1, b1) и (a2, b2).

Проведем прямые через все пары точек, и приведем их к нормальному виду: GCD(a, b)=1, и a>0 или a=0 и b>0. Такое представление единственно для любой прямой. Перебрав все прямые, проходящие через пару точек, мы получим все углы, под которыми есть смысл проводить прямую-ответ (в случае, когда ответ больше двух, какие-то две точки из ответа будут лежать на одной прямой). Зная угол, под которым проходит прямая-ответ, несложно указать оптимальное d: для фиксированных a, b, задающих угол наклона прямой, нужно выбрать два самых часто встречаемых с этими значениями a, b значения c, и мы получим две прямые, параллельные искомой, находящиеся от нее на расстоянии d. В случае, если такое значение c всего одно, то, если не все точки лежат на одной прямой, можно добавить к ответу еще одну точку.

Read more »

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

By RussianCodeCup, 23 months ago, In Russian,

Всем привет!

В это воскресенье 31 мая в 13:00 по Москве состоится третий квалификационный раунд Russian Code Cup. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Третий раунд — последний шанс для тех, кто еще не успел пройти квалификацию, так что не пропустите! Отборочный раунд состоится в 13:00 14 июня, в него проходят 200 лучших участников из каждого квалификационного раунда.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Приглашаем всех принять участие в квалификационном раунде Russian Code Cup и желаем всем удачи!

Read more »

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

By RussianCodeCup, 2 years ago, In Russian,

Analysis QR2 RCC 2015

Задача A. Турникеты в метро.

Идея: Дмитрий Филиппов.
Реализация: Дмитрий Филиппов.
Разбор: Виталий Аксёнов.

По условию задачи нужно найти момент времени, когда числа, отображаемые на турникете у двух мальчиков, будут отличаться в k раз. В первую очередь разберём случай k=1, в этом случае ответ — YES, если на обоих турникетах показывается 99 или если a = b. Иначе, несложно заметить, что правильный момент времени наступит не раньше, чем у какого-то мальчика количество поездок станет меньше 99. Перейдём сразу к первому такого моменту. У нас осталось всего не более 99 вариантов подходящих дней. Переберём и проверим каждый из них на то, что он удовлетворяет условию задачи.

Задача В. Игра.

Идея: Николай Ведерников.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

По условию задачи нужно найти математическое ожидание длины пути с первого уровня до последнего. Для этого воспользуемся методом динамическим программированием.

В dp[i][j] будет хранить математическое ожидание длины пути, если мы начнем на i-м этаже в j-ой комнате и пойдём до последнего уровня. Тогда ответ на нашу задачу будет хранится в dp[1][1].

Будет решать задачу с последнего уровня до первого. Понятно, что dp[n &plus; 1][x] = 0, где x от 1 до n &plus; 1. Теперь зная ответ для (k &plus; 1)-го уровня, посчитаем значение динамики для k.

  • Если a[k][j][0] < a[k][j][1], тогда dp[k][j] = dp[k &plus; 1][j] + a[k][j][0]. Где a[k][j][0] —  длина коридора с k-го уровня j-ой комнаты в j-ую комната на (k &plus; 1)-ом уровне. А a[k][j][1] —  длина коридора с k-го уровня j-ой комнаты в (j &plus; 1)-ую комната на (k &plus; 1)-ом уровне.
  • Если a[k][j][0] > a[k][j][1], тогда dp[k][j] = dp[k &plus; 1][j &plus; 1] + a[k][j][1].
  • Если a[k][j][0] = a[k][j][1], тогда dp[k][j] = (dp[k &plus; 1][j] + dp[k &plus; 1][j &plus; 1]) / 2 + a[k][j][0]. Так как мы могли равно вероятно пойти как по первому коридору, так и по второму с равной вероятностью.


После подсчёта ответ на задачу будет храниться в dp[1][1].

Задача С. Палочки и Шарниры.

Идея: Георгий Корнеев.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

В этой задаче нам дана последовательность палочек, соединенных шарнирами, которая может принимать форму любой ломаной, с ребрами равными длинам соответствующих палочек. В условии эта фигура была названа цепочкой. Нужно найти минимальный радиус такой окружности, что в нее можно поместить цепочку, при этом центр окружности должен совпадать с началом первой палочки.

Рассмотрим решение с помощью двоичного поиска по ответу. Очевидно, что если цепочка помещается в окружность, то она поместится и в окружность большего радиуса.

Теперь надо научиться проверять, что окружность может вместить в себя цепочку. Идея проста: наберем максимальное количество палочек, такое что их суммарная длина меньше либо равна радиусу окружности. Если больше палочек нет, то задача решена. Иначе, смотрим, можем ли поместить следующую: если ее длина минус сумма предыдущих больше радиуса (развернули ее в шарнире на 180 градусов, и она вышла за пределы окружности), значит, уместить цепочку в эту окружность нельзя, иначе — на окружности найдется точка, на которую можно положить следующий шарнир, а значит, эта палочка поместится. Теперь проверяем, что длина оставшихся палочек меньше диаметра окружности, что равносильно тому, что мы можем разложить все оставшиеся шарниры на окружность, и цепочка поместится в окружность.

Задача D. Числа Фибоначчи.

Идея: Илья Збань.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

По условию задачи нужно найти сумму k-ых степеней первых n чисел Фибоначчи по модулю 109+23. Самое первое действие заключалось в разложении модуля на множители: 109+23 = 3·112·61·45161. Давайте посчитаем нужную сумму по каждому из этих модулей и восстановим по Китайской Теореме об Остатках ответ на задачу.

Для каждого модуля по отдельности задача решается следующим образом. Найдём период чисел Фибоначчи. Для наших модулей они получаются небольшими, и предпериод всегда равен 0. Посчитаем сумму k-ых степеней чисел Фибоначчи на данном периоде и ещё небольшом кусочке. Тогда ответ на задачу при фиксированном n будет равен сумме нескольких периодов и сумма на маленьком кусочке.

Получив ответ для каждой из меньших задач, восстанавливаем ответ для начальной задачи.

К сожалению, на данном этапе задача не заканчивалась. Нужно придумать любую оптимизацию для того, чтобы программа прошла по времени. Можно было применить следующие: избавиться от двойного взятия по модулю при быстром возведении в степень, предварительно предподсчитав числа в степенях степени двойки, либо возводить не в степень k, а воспользоваться теоремой Эйлера и возводить в степень по модулю φ.

Задача E. Телепорты.

Идея: Илья Збань.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче дано n точек-телепортов, от которых можно отразиться, и требуется проверить, можно ли добраться из стартовой точки до конечной.

Заметим, что два отражения подряд относительно точек i, j прибавят к координате текущей точки вектор f(i, j) = (2(xjxi), 2(yjyi)). Если мы знаем, что в ответе четное число отражений, то задачу можно свести к следующей: можно ли представить вектор (xfxs, yfys) суммой векторов f(i, j). Случай с нечетным числом векторов в ответе сводится к задаче с четным числом, если первым действием отразить стартовую точку относительно любого телепорта (может показаться, что нужно перебрать все n вариантов первого хода, но на самом деле это не обязательно) и попытаться решить задачу с четным числом векторов в ответе.

Заметим, что не нужно использовать все n2 векторов f(i, j): f(i, j) = f(1, j) — f(1, i). Итак, у нас в рассмотрении остался всего n-1 вектор. Утверждается, что целочисленную линейную оболочку целочисленных векторов можно представить как целочисленную линейную оболочку всего двух некоторых векторов, т.е. эта оболочка — некоторая сетка на плоскости.

Будем добавлять в рассмотренное множество векторы по одному и поддерживать два вектора, задающие линейную комбинацию всех уже добавленных. Один вектор будет иметь вид v1 = (x1, 0), где x1 — минимально возможное положительное, а второй — v2 = (x2, y2), где y2 — минимально возможное положительное, и 0 ≤ x2 < x1.

Пока все добавленные векторы коллинеарны, используя алгоритм Евклида легко находить, какой единственный вектор может представить своей линейной комбинацией все остальные. Как только в рассмотренном множестве появляется хотя бы одна пара неколлинеарных векторов, векторы пересчитываются иначе. Пусть добавлен был вектор v3.

Чтобы найти новый вектор v1, надо посмотреть на GCD двух векторов: старого v1, и вектора с минимальным x вида (x, 0), представимого линейной комбинацией векторов v2 и v3. Для этого нужно найти минимальное решение уравнения k2 · y2 + k3 · y3 = 0.

Чтобы найти новый вектор v2, надо рассмотреть вектор вида k2 · v2 + k3 · v3. Нужно найти любое решение уравнения k2 · y2 + k3 · y3 = GCD(y2, y3), и прибавить несколько раз новый v1, чтобы гарантировать минимальность по х-координате.

Зная два вектора, задающие сетку, легко проверить, что данный вектор представим в виде их целочисленной линейной комбинации: нужно всего лишь проверить, что его коэффициенты разложения по этим двум векторам являются целыми числами.

Read more »

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