Sammarize's blog

By Sammarize, 9 years ago, translation, In English,

1. Clothes (A Div-2)

In this problem constraints are allow to look throw all triples of clothes. For every triple one can check if all elements of tripe areturn out to match with others, and anong those triples find one whith minimal cost.

2. Sum of digits (B Div-2)

Initial number consist of no more then 100000 digits. Therefore after first transform resulting number will be no more then 900000, and then it will constist of no more then 6 digits. Thus after next transform number will be no more then 54 and so it will be two-digit or one-digit. Sum of digits of a two-digit number no more, then 18, and sum of digit of such number no more, then 9.
Thus Gerald can't do nore, then 4 transforms. First transform one can implement one simple pass throw symbols of given string. Following operations take very little time.

3. Homework (C Div-2, A Div-1)

Lets count up the number of entries to string of every letter. Let Gerald choose x letter and lose them. Obvious thet if he lose x rarest letters then overall number of losed letter do not increase, and then if he can lose some x lettes, he can lose x rarest ones. Thus it's easy to determine if Gerald can loses x letters. And now to calculate the answer one only need to find the minimal such x, so Gerald can lose x letters.

4. Buses (D Div-2, B Div-1)

For every slop from 0 to n lets calculate k x - number of ways come to them. Consider the i-th bus. Number of ways come to stop t i applied i-th bus is uqual to number of way to embus to i-th bus.
One can embus to i-th bus on the stops s i, s i + 1, ..., t i - 1. Thus number of ways come to stop t i in the i bus is equal to sum  k s i + k s i + 1 + ... + k t i - 1. Finally, lets note that overall number of way to come to stop t i is the sum of numbers of ways to come to stop t i on every bus.
It's remained two problems. First problem: 0 ≤ n ≤ 109. Therefore all k x not climb in memory limit. But we need to know only non-zero k x. For instance, one can gripe coordinates: create list of all occured stops (and also stops 0 and n), sort this list, delete the repeated stops and replace all numbers of stops they indexes in this list. After this operations all number of stops not exceed 200001, and all k x are climb to the memory.
Second problem: if we will use loop "for" for counting sum  k s i + k s i + 1 + ... + k t i - 1, asymptotic of time of working will be O(m^2). There is an easy way to solve this problem: one can create and update array sum[], such that sum[i] = k[0] + k[1] + ... + k[i - 1], by another words, sum[0] = 0, sum[i + 1] = sum[i] + k[i].
Then munber of ways to come to stop t i using bus i is equal to sum[t i] - sum[s i].
So time complexity is O(m \cdot log(m)), memory complexity is O(m).

5. Vectors (E Div-2, C Div-1)

Lets formulate the problem in complex number.
Consider complex numbers  a = x A + iy A b = x B + iy B and c = x C + iy C. One can do operation  A → A + C and A → iA.
If we apply this transform some times in some order to A, we will get number  A· i k + aC + biC - cC - idC for some non-negative integers k, a, b, c, d or, in another words, A· i k + aC + biC for k = 0, 1, 2, 3 and some integers a, b. Since k can be equal only 0, 1, 2 or 3, sufficiently to get to know is one can to represent B - A, B - iA, B + A or B + iA in the form of aC + biC.
Then, how to determine, is one can to represent some complex number D in the such form? One can represent equation D = aC + biC in the form of linear real equation system:
a· x C - b· y C = x D
a· y C + b· x C = y D
To solve this system - is standart tehnical problem.

6. Castle (D Div-1)

Remunerate vertexes in such a way, that start Gerald vertex have got number 0.
Consider that vertex 0 is the root of tree, and lets consider its children. Let Gerald first go to vertex x. Then he must to travel throw hole subtree, otherwise he will not visit all vertex in subtree. Then he come back to 0 and go to some next its child.
Lets try to calculate looked for value for hole tree when we know all subtree values. If we can to do it, we can solve problem using dynamyc programming on the tree.
Lets vertex 0 have n children. Lets i-th subtree have k i offspring (inclusive i-th child of 0). 
Let the hole tree consist of N vertexes.
Lets T i is the doubled sum of lenght all edges in i-th subtree, inclusive edge between 0 and its i-th child. It is the time to travel throw hole i-th subtree, starting in 0 and returning to 0.
Finally, lets t i is answer to problem on i-th subtree. At once we add to this time length of edge between 0 and its i-th child.
Lets Gerald travel throw all subtrees in order 1, 2, ..., n. What is average time of finding the treasure?
Treasure can be in first subtree with probability . Then average time of finding the treasure will be  t 1.
Treasure can be in second subtree with probability . Then average time of finding the treasure will be  T 1 + t 2.
And so on. Thus, average time of finding the treasure will be

Can we decrease this time? Lets swap i and i + 1 subtrees. Then item k i + 1 T i disappear from sum and appear item k iT i + 1. Sum will chenge to k iT i + 1 - k i + 1 T i. Sum will decrease, if k iT i + 1 - k i + 1 T i < 0, in ather words .
Therefore, one can't decrease average time, if subtrees are sorted by increasing value .
So, we must to sorted trees in this order and traveling from them in this order.

7. Candies and Stones. (E Div-1)

Essence of problem is that there is a board  n × m in cell of wich placed numbers. And one must go from cell (0, 0) to cell (n - 1, m - 1), doing moves to one cell up and right (that is, increasing by 1 on of coordinates), maximizing sum o number on the cell in the path.
Gerald's problems is determine m + n - 1 cells of optimal path. Lets start with search one, middle cell. Lets . What cell of board can be k-th in path? It is cell, sum of coordinate of wich is equal to k, thus, it is diagonal of doard. And then we can calculate, what maximum sum Gerald can collect, came to every cell in the diagonal, by dynamic programming in lower triangle. And the same way, we can calculate, what maximum sum Gerald can collect, came to cell (n-1,m-1), starting from every cell in the diagonal. Sumed up this to values, we calculate, what maximum sum Gerald can collect, came to from cell (0, 0) to cell (n - 1, m - 1), travel throw every cell in the diagonal. And now we will find cell (x, y), in wich maximum is reached. It is k-th cell of the path. We used time  O((n + m)2) and memory O(n + m).
Then we make recursive call on subproblems. In other word, will find optimal path from cell (0, 0) to cell (x, y) and from cell (x, y) to cell (n, m).
It is evident, this solution take memory O(n+m). Why it tkae time O((n+m)^2)?
Lets n + m is r.
Once we are find middle cell of path of length k. Twice we are find middle cell of path of length . Four times we are find middle cell of path of length . And so on. Therefore, time of program working will be . Thus, this solution take time O((n + m)2).

Read more »

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

By Sammarize, 9 years ago, translation, In English,


I'm, Valeriy Samojlov, graduating student of SPbSU,  present you codeforces beta round 79. Today you will meet with boy Gerald and will help him to solve some living problems. 

Today we have usually cost of problems in both divisions: 500 - 1000 - 1500 - 2000 - 2500.

It my first codeforces round, I hope, problems will be interesting.

I want to thank Artem Rakhov ( RAD ) for big help with preparation of problems, Makar Krasnoperov ( Connector) for some useful remarks and Maria Belova for translation.

Good luck for participants of both dovisions!

Contest is over! Congratulation to winners!

Division 1:

1.  RAVEman

2.  ilyakor

3.  ACRush

Division 2:

1.  SuperLight

2.  xiaowuc1

3.  Timur_Sitdikov

Editoral a appeared.

Read more »

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