netman's blog

By netman, history, 7 years ago, translation, In English
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
C++ code
Java code

Full text and comments »

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

By netman, history, 7 years ago, translation, In English

THi Codeforces!

I'm glad to announce that today at 17:35 MSK will take place first round in the new year — Codeforces Round #390 for the second division. Traditionally, first division participants will be able to take part out of competition.

Round was prepared by me, Alex netman Vistyazh.

Many thanks to Nikolay KAN Kalinin for his help in contest preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon platforms.

You will be offered five problems and two hours to solve them.

Scoring will be announced closer to beginning of the round.

UPD: Scoring is 500 — 1000 — 1500 — 2000 — 2500

UPD2:

There were some troubles during contest — in problem C first pretest wasn't equal to first sample, and unfortunately this problem was solved much worse than we expected. I made conclusions and next time I will estimate difficulties of problems more responsibly.

Congratulations to the winners!

Div 2:

  1. i_wanna_no_exams_fluever
  2. markysha
  3. Yamada
  4. LLI_E_P_JI_O_K
  5. I_love_livlivi
  6. wolf29
  7. sunjam
  8. AkaneSasu
  9. GemaSamuca
  10. EliteWantsYou

Div 1:

  1. kraskevich
  2. vintage_Vlad_Makeev
  3. uwi
  4. halyavin
  5. sugim48

UPD3:

Editorial posted!

Full text and comments »

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

By netman, 10 years ago, translation, In English

Warning: my English is very bad.

456A - Laptops

Solution: 7407613;

In this task you need to check the existense of such pair i and j, such that i ≠ j, a[i] < a[j], b[i] > b[j]. If such i and j exist, Alex is happy.

There is very simple solution. Let's check that for all i a[i] = b[i]. If this condition is true we should print "Poor Alex". We can easy prove it. Let's sort arrays a and b like pair of numbers in increasing order. We can see that Alex is happy if we have at least one inversion in array b, i.e there is such pair i and j that b[i] > b[j] и i < j (). i.e it means that array b is not sorted and it's means that a ≠ b.

456B - Fedya and Maths

Solutions: 7407625, 7407631;

In this task you need to calculate formula that given in the statement, but it's hard to calculate it with the naive way.

But we can transform our formula to this:

This formula is right because 5 is prime number and it's coprime with 1, 2, 3, 4.

φ(5) = 4

To solve this task we should be able to calculate remainder of division n by 4 and calculate formula for small n.

Asymptotics — .

There is also another solution. It uses a fast exponentiation, but not binary exponentiation. The idea of this exponentiation is the same as that of the binary exponentiation. Let we want to fast calculate xnmodP. Algorithm is very simple. Let process digits of n moving from end to begin. Let Result — current result and Kx(10i), i — number of the currently processed digit (digits are numbered from the end. Used 0-indexation). During processing of digits, we must update result: , c[i]i-th digit of the number n (digits are numbered from the end).

Asymptotics — .

456C - Boredom / 455A - Boredom

Solutions: 7407649, 7407655;

In this task we need to maximize the sum of numbers that we took. Let precalc array cnt. cnt[x] — number of integers x in array a. Now we can easily calculate the DP:

f(i) = max(f(i - 1), f(i - 2) + cnt[ii), 2 ≤ i ≤ n;

f(1) = cnt[1];

f(0) = 0;

The answer is f(n).

Asymptotics — O(n).

456D - A Lot of Games / 455B - A Lot of Games

Solutions: 7407663, 7407670;

To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: win[v] — Can player win if he makes a move now (players have word equal to prefix v in the prefix tree(trie)). lose[v] — Can player lose if he makes a move now (players have word equal to prefix v in the prefix tree(trie)).

if v is leaf of trie, then win[v] = false; lose[v] = true;

Else win[v] = (win[vor (not win[i])); lose[v] = (lose[vor (not lose[i])), such i — children of vertex v.

Let's look at a few cases:

If win[v] = false, then second player win (first player lose all games).

If win[v] = true и lose[v] = true, then first player win (he can change the state of the game in his favor).

If win[v] = true and lose[v] = false, then if , then first player win, else second player win.

Asymptotics — .

456E - Civilization / 455C - Civilization

Solutions: 7407681, 7407683;

You can see that the road system is a forest. For efficient storage component we need to use DSU. First, we need to build the initial system of roads. For each component of the initial road system, we must find the diameter of component. This can be done using a DFS or BFS. Let a — any vertex of component. Let b — furthest vertex from vertex a. Let c — furthest vertex from vertex b. Diameter equal to distance from b to c. This algorithm for finding the diameter is correct only for tree. For each component in the DSU, we know its diameter.

Now it is very easy to answer the query of the $1$st type: To know the component which contains the vertex x and output diameter of this component. Query of the $2$nd type also very easy to process: Let u — of component in which lie the vertex x, v — of component in which lie the vertex y. If u ≠ v, then we can merge components: The diameter of the new component is computed as follows:

Asymptotics — O(n·A - 1(n)), где A - 1(n) — inverse Ackermann function.

455D - Serega and Fun

Solutions: 7407693, 7407699, 7407703;

Let's change the query type 1 to two more simple requests:

Erase a number from r-th position. Insert this number after (l - 1)-th position.

Now let's keep our array as blocks. In each block will store the numbers themselves in such a manner as in the array a and will store an array cnt. cnt[x] — number of integers x in block. This requires O(n sqrtn) space.

Now we can fast process the queries of the 1st type. We can erase number from r-th position in operations. And we can insert this number after (l - 1)-th position in operations. Also we can fast recalc cnt after transformations.

Also we can fast process the queries of the

Unable to parse markup [type=CF_TEX]

O (\ sqrt n) $ numbers are in blocks, which are partly lie within the boundaries of the query.

To keep the size of the blocks close to , we need rebuild our structure after each -th query of the 1st type. We can rebuild structure in O(n) operations.

Asymptotics — .

455E - Function

Solutions: 7407711, 7452418;

In this problem you should quickly be able to compute the function described in the statement.

You may notice that this task is equivalent to next task:

Go through the array a, starting from the position of y, making (x - 1) step. Step might be: step to the left or to stay in place.

Function is calculated as follows: , ki — how many times we visited the i th element of the array a.

For a fixed l is clear, it is most optimally that a minimum on the interval [l, y] has been visited by (x - (y - l)) times, and all the other numbers once.

You may notice that optimally to a[l] was a minimum.

From all this we can conclude that for a fixed l answer is — sum[y] - sum[l] + a[l]·(x - (y - l)), where sum — an array of prefix sums of array a.

Above formula can be written as follows:

sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[ll + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[ll - sum[l])

You may notice that in brackets something like the equation of the line — K·X + B. That's very similar to the equation of the line: a[l]·(x - y) + a[ll - sum[l], where K = a[l], X = (x - y), B = a[ll - sum[l].

Now we must find minimum for all l and fixed X = (x - y).

We have n lines, i. e. for every element in array a one line (Ki, Bi).

Answer for query equal to:

, where (Ki, Bi)i-th line. Ki = a[i], Bi = a[ii - sum[i].

For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires space, because each line lies in vertices. And we can answer query in operations. Because we visit vertices and each vertex need in operations. You can learn the theory about Convex Hull Trick here.

Full text and comments »

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