Sammarize's blog

Codeforces Beta Round 79, editoral
By Sammarize, 13 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 kx - number of ways come to them. Consider the i-th bus. Number of ways come to stop ti 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 si, si + 1, ..., ti - 1. Thus number of ways come to stop ti in the i bus is equal to sum ksi + ksi + 1 + ... + kti - 1. Finally, lets note that overall number of way to come to stop ti is the sum of numbers of ways to come to stop ti on every bus.
It's remained two problems. First problem: 0 ≤ n ≤ 109. Therefore all kx not climb in memory limit. But we need to know only non-zero kx. 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 kx are climb to the memory.
Second problem: if we will use loop "for" for counting sum ksi + ksi + 1 + ... + kti - 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 ti using bus i is equal to sum[ti] - sum[si].
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 = xA + iyA, b = xB + iyB and c = xC + iyC. 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· ik + aC + biC - cC - idC for some non-negative integers k, a, b, c, d or, in another words, A· ik + 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· xC - b· yC = xD
a· yC + b· xC = yD
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 ki offspring (inclusive i-th child of 0). 
Let the hole tree consist of N vertexes.
Lets Ti 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 ti 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 t1.
Treasure can be in second subtree with probability . Then average time of finding the treasure will be T1 + t2.
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 ki + 1Ti disappear from sum and appear item kiTi + 1. Sum will chenge to kiTi + 1 - ki + 1Ti. Sum will decrease, if kiTi + 1 - ki + 1Ti < 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).
  • Vote: I like it
  • +31
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice questions :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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 n1 depend only on the values of n1 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.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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...
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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.
      → Reply
      • 9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you are right.^_^

        → Reply
      • 11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • 7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tkae should be take.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is the Smallest Solution for the B problem

#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;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not getting problem D.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Im also finding the solution very difficult to understand

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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:)

→ Reply