Geekly Articles each Day
📜 ⬆️ ⬇️

Russian Code Cup 2012: detailed analysis of tasks from the qualifying round (semi-final)



Last Saturday, June 16, the qualifying round of the Russian Code Cup 2012 was completed. The tasks of the qualifying round are more complicated than they were in qualifying - well, that’s the semi-final. I have already talked about what was offered to the participants on previous online tours, analyzed in detail solutions ( Q1 , Q2 , Q3 ).

600 people were invited to the qualifying round. 434 people were able to solve at least one problem. All tasks were solved only by two. Top 50 went to the final. In just 3 hours of the tour, 3190 solutions were sent to the verification system.
')
So, let's go to the tasks themselves. I tried to explain them in such a way that the solutions were understandable even taking the first steps in sports programming (and in programming in general).

Transposition

The essence of the task was to determine whether, by applying two types of permutations in arbitrary order, to move an element from the specified position to the one indicated in the list of values. By the condition of the problem, it was possible to apply the so-called interposition, changing the first two elements in places, and a complex permutation defined by the rule-set of values ​​(a1, a2, ..., aN), where each of the values ​​determines the ordinal position to which you can move number from this position. For example, the last two in the permutation rule (1,4,3,2) means that it is possible to rearrange from the last position to the second one, and from it to the last one. Actually, as a result, it is required to give a response of the form “Yes / No” to the input data containing this list (from N values) and a query in the form (position1, position2) - “can the element be moved from position 1 to position 2”.

This task was the simplest at the contest, 411 people coped with it, the first test that passed the tests was proposed by Dmitry Zhukov at 3 minutes 31 seconds after the start of the round.

It is obvious that all permutations ultimately boil down to a set of cycles. In the example above, cycle three is 4-> 2-> 4-> 2 ... 1-> 1-> 1 ... 3-> 3-> 3 ... That is, if we only had the operation “apply permutation p”, then for two elements ai and bi the answer would be “Yes” if and only if these elements lay on the same cycle in the permutation p.

Let us think about what happens when applying the “transposition” z. If initially the first and second elements lay in different cycles, then the use of the “transposition” gives us the opportunity to rearrange some element from one of these two cycles to the other.

Now we can formulate a general solution.


The division into cycles is as follows:

//    col,   −1. vector<int> col(n, −1); //    ,    ,       for (int i = 0; i < n; i++) { if (col[i] != −1) continue; //     int x = i; do { col[x] = i; //    x = a[x]; } while (col[x] == −1); }


We combine the first two cycles into one:

 for (int i = 0; i < n; i++) if (col[i] == 0) col[i] = 1;


As a result, we have an array of col, the i-th element of which denotes the cycle, which includes the i-th position.

 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; //  ,          . cout << ((col[a — 1] == col[b — 1])? «Yes» : «No») << «\n»; }


Coronation

Under the terms of the problem, there are two capitals and a certain multitude of cities connected by roads in such a way that from any to any one can be reached in the only way. But they are of such quality that after the passage of a certain number of cars specified for each road, they become unsuitable for passage. It was decided to add another (possibly duplicating) road with unlimited bandwidth between any two cities, none of which is the capital. It is necessary to find the maximum number of cars that can travel between the two capitals, taking into account this new road.

A detailed statement of the problem can be found on the round page on the official site of the Russian Code Cup.

This task turned out to be the second in complexity “from the end” - 313 people solved it. The first correct decision was sent by Dmitry Zhukov at 12:50.

In the problem we have a weighted undirected tree. That is, a graph that does not have loops and multiple edges, the edges of which (“roads”) are assigned “weights” - the capacity of the roads.

It has two peaks - the "capital" - s and t. It is necessary to add an edge that does not affect either s or t, such that the flow from s to t is maximal.

Let us add an edge from vertex a to vertex b. Let us prove that between s and t there will be at most two simple paths (a path is called simple if the edges in it do not repeat). Prove by contradiction. Suppose we managed to find three paths.

Consider two cases:



As a result, we found out that adding an edge ab leads to the appearance of no more than two simple paths and only one of them has an edge ab, and the other, obviously, runs along the edges of the tree and is the only one between the vertices-cities.

Consider the second path passing through the edge ab. One end of this edge is connected to the path to the vertex s, and the other to the path to the vertex t. Now, if we move the junction ab with <s; a> to the node closer to s, then the bandwidth will not degrade. Similarly, arguing with the road to t, and, remembering the constraint in the problem, we arrive at the fact that the new path passing through the capital nodes s, t and edge ab in its most efficient form consists of three edges - edges from s, edge ab and edges from t.

As a result, we obtain that our answer consists of two paths, one of which existed before adding the edge ab, and the second — an edge from s, an edge ab, and an edge in t.

We get the solution:
  1. Find a path from s to t along the edges of the tree,
  2. Skip it to the maximum number of machines and, accordingly, reduce the throughput of all edges along the way. In this case, the path will definitely collapse - after all, the maximum number of machines corresponds to the lowest throughput capacity of the edges in the path.
  3. Probably, there will still be roads (or one road) from s and from t. Choose those with maximum throughput.
  4. Combining them with the edge ab, we calculate the number of cars - the minimum value of the carrying capacity of the two edges leaving the capitals.


Social phobia

The condition of the problem is worth it to bring it here with minimal abbreviations.

“Not all people are pleased to be constantly in the crowd. Many love privacy and are even willing to pay for it. That is why Joyful Railways OJSC has introduced a new service on its ticket sale site, called Sociophobe. The service is necessary in order to enable each passenger to ride in a compartment with the smallest possible number of neighbors. Its essence is as follows.

Let the tickets be sold to a car in which part of the compartment is already full. If at some point another passenger buys a ticket for this car, he sells a seat in the empty compartment, that is, in a compartment in which the number of people is no more than in all others. If there are several such compartments, then the compartment with the lowest number is selected. If a passenger from some compartment gives up his ticket, after which the difference between the number of people in this compartment and in the most filled compartment becomes equal to at least two, then from the most filled compartment the passenger who earlier bought the ticket before the others changes, there is a passenger with the lowest number. If there are several most filled coupes, then the coupe closest to the one in which the ticket was handed over is selected. And if there are several such, then the coupe with the smallest number is selected.

According to the data on how passengers bought and handed over the tickets, it is required to derive the final distribution of passengers in the compartment. It is guaranteed that every time a passenger buys a ticket, there is at least one free seat in the car. ”


It seems that the train in question is truly a huge one, since the number of sales and return tickets is up to 200,000, the number of compartments is up to 50,000.

In total, this task was solved by 167 people, of whom the first was Kunyavsky Pavel (23:19).

One solution to this problem is as follows. Prepare the following data structures:

 // ,     . Pas[i] = , -1  «  ». vector<int> pas(200000+1, -1); //   –    . Cars[i]     vector< set<int> > cars(50000 + 1);


We will also support two sets (in C ++, for example, you can use set for this, in Java - the TreeSet): zero and one. At zero, we will store the compartment numbers in which we have the smallest number of passengers, and in one - where the most.

 set<int> zero; set<int> one;


Initially, all coupes are empty, so put them in the list of candidates for filling - zero.

 for (int i = 1; i <= n; i++) zero.insert(i);


We do not need others, since the difference between the number of passengers in different compartments will never exceed one.

Ticket sale operation ("+"). According to the condition of the problem, we must choose the car with the lowest number, in which the least number of people. To do this, take the smallest element of the set zero. Update the information in pas and cars. Then we will delete the found element from zero and add it to one, since now there are as many people in this car as in all cars lying in one. If zero becomes empty, then it is necessary to swap one and zero, since the same number of people became in all compartments.

 int car = *zero.upper_bound(0); //    pas[++id] = car; //      cars[car].insert(id); //       zero.erase(car); //        one.insert(car); // …     if (zero.empty()) //   ,      … { zero = one; //        zero.erase(-n); zero.erase(2 * n); one.clear(); //     one.insert(-n); one.insert(2 * n); }


Ticket operation ("-"). With the help of the array pas we find out in which compartment the passenger was sitting. Remove the passenger from the corresponding compartment.

 int car = pas[x]; cars[car].erase(x); pas[x] = −1;


Find out which set belonged to the coupe car. Here are the following options:



 set<int>::iterator ll = (one.upper_bound(car)); ll--; //  ,    set<int>::iterator rr = (one.upper_bound(car)); //  ,    if (abs(*ll - car) > abs(*rr - car)) //        ll = rr; int l = *ll; one.erase(l); zero.insert(l); //   one  zero int p = *cars[l].upper_bound(0); cars[l].erase(p); cars[car].insert(p); //      pas[p] = car;


To output the answer to the task, we will use the cars array. To display information about passengers in the i-th compartment, it is enough to display the size of the set of cars [i],

 cout << cars[i].size() << ((cars[i].size() == 0) ? "\n" : " ");


and then all passengers belonging to multiple cars [i].

 set<int>::iterator en = cars[i].end(); en--; for (set<int>::iterator it = cars[i].begin(); it != cars[i].end(); it++) cout << *it << ((it == en) ? "\n" : " ");


Coins

According to the condition of the problem, a certain wizard Rinsvid confuses the coins, and instead of paying for, say, doubloons, he counts sterling (and he does not pay by real sterling). It is necessary to calculate how many pairs of coins exist, such that by accepting the first coin for the second, he could pay exactly T dollars instead of S, as he considered.

An example is provided for illustration. If there are coins in denominations of 1, 2 or 3 dollars, and Risvind paid 10 dollars instead of 9, then he could do this by accepting 2 coins with a nominal value of 1, and paid, for example, four coins with a nominal 2 and one coin with a nominal 2 which he took as nominal "1".

He could also accept coins of face value 3 for coins of face value 2 and pay seven coins of face value 1 and one face value of 3, which he accepted as a coin of face value 2.

How much is actually paid in nominal 1How much is actually paid in nominal 2How much is actually paid in nominal 3Total paid
-really
4 coins
(8 dollars, 4 × 2)

1 coin
(2 dollars, 2 × 1)
in the view of Risvind -

1 dollar (1 × 1)
-really
5 coins

(10 dollars, 4 × 2 + 2 × 1)

in the view of Risvind -

9 dollars (4 × 2 + 1 × 1)
really
7 coins
(7 dollars, 7 × 1)		-really
1 coin
(3 dollars, 3 × 1)
in the view of Risvind -
2 dollars (2 × 1)		really
8 coins
(10 dollars, 4 × 2 + 1 × 1)
in the view of Risvind -
9 dollars (4 × 2 + 2 × 1)


Suppose that Rincewind took the coin t for s. In the last example, the coin 3 (t) for 2 (s). This means that he dialed a certain amount of V (in the example - $ 10), without using the coin s (in the example - $ 7), then put another k coin number t, thinking that this is the coin number s (in the example - 1 coin 3, thinking it is 2).

In other words, the whole variety of options fits into two groups of cases:


The first condition can be checked for O (1). notice, that

k = (s - t) / (as - at);
V = S - k · as

It remains to verify that the numbers obtained are integers, V ≥ 0, and k> 0.

In order to check the second condition, we use the dynamic programming method. Let D [i] [j] - is it possible to get the sum j using the first i coins? Base: D [0] [0] = true. Transition: D [i] [j] = D [i - 1] [j] or D [i] [j - ai]. For implementation, a single array of size S is sufficient. The running time of this algorithm is O (S · n). For details on the approach using dynamic programming, see Parsing tasks from the last tour , as well as good material with examples and illustrations .

Using the described method, we calculate for each sum V from 1 to S, whether Rincewind could collect this sum without using the coin s. After that, let's sort out the coin, which Rincewind took for s. Now the check of both conditions is carried out for O (1). The final asymptotic solution is O (S · n2).

The task of "Coins" was solved first by Peter Mitrichev at 17:06. In total, we received the correct decisions of 234, which puts this task in third place from the end in terms of complexity.

Parse string

The task describes the algorithm for finding dictionary words from a given text — the so-called greedy algorithm, when every time a found word is removed from this text. An example is given that in some cases such an approach leads to incorrect results. For example, for workingrass, working can be removed and some rass would remain, while the correct solution would be to break up the work / in / grass into three words, each of which would be in the dictionary. It is necessary to check whether the greedy algorithm will work correctly with the specified dictionary, and, if it does not, give an example of a string for which the word break from the dictionary exists, but cannot be found by the described algorithm. If there are several such examples, it is necessary to find the shortest one, that is, one whose length is no more than the rest. If there are several, you need to withdraw any.

We first consider the key idea leading us to the solution of the problem. Let there be a string t - the required counter-example of the shortest length, and some of its splitting into words from the dictionary w 1 , w 2 , ..., w k . Let the greedy parser that we are trying to break, when exploring this line, first bite off the string w from it.

Let us prove the following statement: if the length of the string w is not greater than the sum of the lengths of the rows w 1 , w 2 , ..., w k-1 , then there is a counterexample shorter than the string t.

Let, to begin with, the length of the string t is equal to this sum. Then it is obvious that the greedy parser will correctly work on string t, since the string w will be “bitten off” first, and then the string w k , since it will be the longest string prefix contained in the dictionary.

In this case, let the length of the string w be less than the sum of the lengths of the rows w 1 , w 2 , ..., w k-1 . Then there is a number j such that w j is divided into the prefix w j1 and the suffix w j2 , and w j1 is the suffix of the string w (possibly, of zero length). Consider the string w j2 . If for it there is a correct splitting into words from the dictionary, then it suffices to leave as a counterexample the concatenation of the strings w j2 , w j + 1 , w j + 2 , ..., w k , which will be a shorter counter example. If for the string w j2 the division into words from the dictionary does not exist in principle, then a shorter counterexample is the concatenation of the strings w 1 , w 2 , ..., w j .



So now we can imagine what the desired counterexample looks like.



We develop an effective algorithm for its construction. Suppose that for each line from the dictionary we know which of its suffixes and prefixes there is a division into words from the dictionary (later we will explain how to calculate this data). Let's look through all the lines from the dictionary to find out if they are the same string w that will be “bitten off” first. It is clear that the penultimate line from the correct partition can end only in the same place where some prefix of the string w ends, for which there is a partition. Let's sort through all such prefixes. Now it only remains to understand which lines may be the last in the correct partitioning of the counterexample. First, it must be strings whose length is longer than the length of the uncovered suffix of the string w being checked. Secondly, the uncovered suffix of the string w must exactly match the prefix of the candidate string to the last place in the partition of the appropriate length. And finally, the candidate string suffix, uncovered by the string w, should not have a correct vocabulary splitting.

Here it is appropriate to make one important remark. Even if the uncovered candidate string suffix has a word splitting from the dictionary, what we are checking at the moment may still be a counterexample. However, then the counterexample will be the suffix in itself, and then what we are testing is not the shortest counter-example of interest, and we are not interested.



With this approach to solving the problem, you need to ask another question. And what will happen if, instead of the string w, which we check, another string will be “bitten off”, with w being the prefix? In this case, the greedy parser will behave unpredictably, and may find some kind of partition. However, in order to avoid this fate, you simply need to check the strings for whether they are not the string w in the order of non-increasing their lengths, and remember the strings that we have already checked. Then every line with which such a problem is possible at all will be checked at the time of the problem, and we can just ignore this line.

Now, when there is a general algorithm for solving the problem, it remains to solve the problem of checking prefixes and breakable suffixes, and also learn how to quickly compare the necessary substrings of the necessary strings for equality. The second problem is solved quite simply with the help of hashing algorithms, which themselves are the subject of a separate article or lecture. The first problem is solved using dynamic programming. Let for all prefixes of the string t, the length of which is strictly less than l, we know whether there is their division into lines from the dictionary. To check whether there is a partition of the prefix of length l, it is enough to go through all the lines from the dictionary and check for the existence of such that two statements are true:



, O(sumL × n), sumL — , n — , , . , .

« » ( ) « », , – 115:47.

, , . , / , . , , , . , , , — Impossible.

, , x , x — . : (0, 0) (x, y) y, ( ), ( ) (). .



, , , . , , .

, . , , «» , . , . . , - . . , .

, . , . , . , , , , - . , . , , . x, . , , .

, , . O(n2 log n) , O(n) O(n) O(n) . O(n log n) , O(n) .

, .



and



.



– 23 , – 100:18. , , – , 2 . , .



50 . 10 Swissotel, . , , , .



Mail.Ru Group

Source: https://habr.com/ru/post/146458/

More articles:


All Articles