Codeforces Beta Round 79, editoral

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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 ≤ 10⁹. 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 $\text{[math]}$ . Then average time of finding the treasure will be t₁.

Treasure can be in second subtree with probability $\text{[math]}$ . Then average time of finding the treasure will be T₁ + t₂.

And so on. Thus, average time of finding the treasure will be

$\text{[math]}$

Can we decrease this time? Lets swap i and i + 1 subtrees. Then item k_i + 1T_i disappear from sum and appear item k_iT_i + 1. Sum will chenge to k_iT_i + 1 - k_i + 1T_i. Sum will decrease, if k_iT_i + 1 - k_i + 1T_i < 0, in ather words $\text{[math]}$ .

Therefore, one can't decrease average time, if subtrees are sorted by increasing value $\text{[math]}$ .

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 $\text{[math]}$ . 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)²) 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 $\text{[math]}$ . Four times we are find middle cell of path of length $\text{[math]}$ . And so on. Therefore, time of program working will be $\text{[math]}$ . Thus, this solution take time O((n + m)²).

#include<bits/stdc++.h> using namespace std; string s ; int main(){ cin >> s;int ans = 0; while(s.size()!=1){ int n =0;for(int i=0;i<s.length();++i) n+=s[i]-'0'; s = to_string(n); ans++; } cout << ans << endl; return 0; }

Comments (19)

Show archived | Write comment?

phantom11

13 years ago, # |

Nice questions :)

→ Reply

Borisp

I have somewhat different approach to the last problem. In fact one can say I have implemented the most straight forward solution.

If it weren't for the reconstruction of the path it is easy to write dynamic solution of the problem. We iterate all values of n 1...n and calculate the best gain we can get for every possible value of m. The values for some n₁ depend only on the values of n₁ and thus we consume only O(n) memory and it took O(n * m) calculations for this part of the problem.

The thing is that the memory is not enough to store all the actions we took to get to this result. This is why when I do this calculations I store the actions taken only for the upper quarter of all ns. Then I can resotre the last quarter of the sought string. But when I restore it I can also formulate smaller problem to be solved (with smaller values of n and m). In it I do the same and again consider the actions taken only for the last portion of ns corresponding to the quarter of the original n. When I repeat this 4 times I have all the whole answer.

This solution fits in both memory and time.

Sammarize

13 years ago, # ^ |

Asymptotically your solution is take up time O(nm), but really, I think, it will work too slow, becouse you are repeat dynamic four times...

The thing is that with this time restirctions you can afford recalculating several times. Memory limits impose that, but as soon as the dynamic can be done in O(n * m) it is not a problem.

The greatest slow down is that you still have to optimise your memory quite a lot and this is why I store every action I take in only single bit. This adds on some more actions you have to take for every read and every write operation.

And something I forgot to mention: as with every other time in which I post my solution, I have passed the problem in codeforces, beforehand.

li924579

9 years ago, # ^ |

I think you are right.^_^

streidi

10 months ago, # ^ |

so the space is still O(nm), but you split it in half (or a quarter), so that it takes 25MB, and then compute the rest? Feels like the recursive solution, but you split it only once or so and the dp is simpler (its not a diagonal row). I'm not sure if i get your idea.

pabloskimg

7 years ago, # ^ |

← Rev. 2 →

I came up with a very similar solution. First I find all the cells of the middle diagonal and then use DP to find the cell inside the diagonal that also belongs to the optimal path. Then using DP and a bitset<200000000> I find the optimal path from the upper left corner to the cell in the diagonal (this is the first half). I do the same thing to find the optimal path from the cell in the diagonal to the lower right corner (this is the second half). I join both halves and the full path is totally recovered. Here is my submission: http://codeforces.net/contest/101/submission/31324561

newbeginBKB

9 years ago, # |

tkae should be take.

shikhar2817

5 years ago, # |

I think this is the Smallest Solution for the B problem

devartstar_85

4 years ago, # ^ |

Nice solution... a little way to make it faster is by adding ths line before for loop :-

s.erase(remove(s.begin(),s.end(),'0'), s.end());

This helps in removing the unwanted '0' from the string which dosent add to change the sum

dracarys23

what is the use of subtracting v from the lower_bound iterato vector<pair<int,int> v ; int l = lower_bound(v, v + i, pii(v[i].second, 0)) — v;

jello3899

4 years ago, # |

I keep running into problems where I hit a wall because the input is too big for what I know how to handle in Java.

Question B is one of those problems. I am using longs and they still aren't long enough for the digits in the input.

Is this a sign that the answer has to be found with another language or is there a technique I don't know about?

Dan4Life

Try using strings instead :)

kunal_rai

I am not getting problem D.

Petersburg

3 years ago, # ^ |

Im also finding the solution very difficult to understand

pedroangeli

Here is how I solved:

Let dp[x] be the number of ways to get to stop x. dp[0] = 1. So, for every bus i, you can do: $$$dp[t_i] = \sum_{s_i \leq j < t_i} dp[j]$$$. But we have a problem here, since $$$1 \leq t_i \leq 10^9$$$. You can use coordinate compression to handle this. You also can't compute this sum naively. I did it with a segment tree. Here is my submission for details.

yatoyaboku123

9 months ago, # |

-8

242922518 my approach to the problem was to create a string consisting of integer characters, and adding the integer value of them to the variable called sum and after the summation is finished, converting the sum to the string and go on while the string.size() is bigger than 1 since the number we want is one digit.

sorry for my bad english, I hope this solution helps someone someday. Gl to all on their journeys.

AdamElmadani

5 months ago, # |

I like the B problem easy implementation but i strugled to find the solution

Ayu_041

3 months ago, # |

can anyone provide the solution for Homework (C Div-2, A Div-1) i am a beginner to CP but this question looked interesting for greedy algorithm. i am having some difficulty in implementing it. Answer to this will help me a lot, Thanx:)