Kniaz's blog

Разбор Codeforces Round #392 (Div. 2)
By Kniaz, 8 years ago, translation, In English
Tutorial is loading...

Problem author: MikeMirzayanov.

Tutorial is loading...

Problem author: MikeMirzayanov, Kniaz.

Tutorial is loading...

Problem author: Kniaz.

Tutorial is loading...

Problem author: MikeMirzayanov, Kniaz.

Tutorial is loading...

Problem author: Kniaz.

Tutorial is loading...

Problem author: Kniaz.

I want to thank Mikhail Piklyaev (awoo) for translation of tutorial!

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

Comments Comments (33)
| Write comment?
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Very nice contest. Thank you <3

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

I think a typo in F: It should be (l — 1) / (y ^ (n — 1)) instead of l / (y ^ (n — 1)).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • Let the first element of sequence be q0 = k*(y^(n-1)).
    • q0 >= l
    • k*(y^(n — 1)) >= l
    • k >= (l/(y^(n — 1)))
    • k = cell(l/(y^(n — 1)))
    • the best way to implement cell-function : k = (l + (y^(n-1)) — 1)/(y^(n — 1))
    • sorry for my english :3
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain O(1) solution of problem C?

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

    I just found this accepted solution 23972771 of problem C implementing a O(1) algorithm. It might help you.

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

    After one T=n*m(time period) you can consider all other time period as T'=(n-1)*m which will add 1 to the answer of middle rows and add 1 to corner rows alternatively.One can derive a closed from expression for the middle bottom and top rows after n periods.The botom row will be the minimum and middle rows the maximum after Total time=k*T'.Now all that is left is the remainder<T' which may influence the answer by 1.

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

Also I want to thank authors of B for creating test 17.

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

in problem D, how to check the following string (base 16)

101

because if we take greedily from the suffix, we will end up with 01, but we cant add 1 to make it 101 (>n)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Seems you have just answered your own question.

    Whenever you can't take anymore numbers, you need to check whether your created number contains any leading zeroes, if yes delete them (and be careful not to consider a number consisting a single zero as leading zero).

    → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Dynamic programming is usually associated with overlapping subproblems. The way solution for E is described may cause confusion...

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

    That made think this solution was totally different from my solution, when it's actually pretty much the same. Anyway, really cool problem.

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

Can somebody explain editorial for Problem E . How dpmin is used for calculating the answer ?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain the last part of editorial of E, how are we finding optimal values of dpF_x(the final weight of subtree of x) which should be between dpmin_x and dpmax_x by dpW, dpmin, dpmax

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +14 Vote: I do not like it

In general, problem E is a linear programming problem.

variables are the weight w of each edge. equations are p = old_p — old_w + w >= 0, w >= 1, p >= w of subtree, w <= old w.

we can use DP to split the equations to small groups by keeping the max w (dpmax) and min w (dpmin) of each subtree.

finding the maximum w is easy. but i run out of time to find the feasible solution (the dpW to reconstruct the tree).

very nice problem.

(1 WA for positive weight)

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey guys I m not able to understand greedy approach behind DIV 2 D and also how it can be done with DP ? .please help me out!

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

    The number formed in a given base will never exceed base.Proof using contradiction:Consider you have done maximal matching as given in editorial.Now if you try to increase the length of right component by 1 (reducing left by 1) the netchange will always be positive as left component will be multiplied by base^(exp+1) and right component by base^(exp).

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

    I did it by an easy to prove brute-force DP: Store the given number $$$k$$$ as a string $$$s$$$. Consider $$$dp[i]$$$ as the minimum decimal number, which when converted to base-$$$n$$$, is equal to $$$s[i]s[i+1]s[i+2]...s[n]$$$.

    Now to get recursive relation, you have to use the greedy fact that there is a monotonic relation between power of $$$n$$$ and $$$dp[i]$$$. It's proof is very easy. For the exact recurrence, you can view my submission.

    87005109

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

Could anyone please tell me why the difference between the max and min number of questions in C would be more than 1? If k>n*m then the entire matrix can be filled and whatever is left, that is, k%(n*m) would be filled in order, so at max the difference between max and min should be 1?

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

    The order of asking the rows looks as follows: the 1-st row, the 2-nd row, ..., the n - 1-st row, the n-th row, the n - 1-st row, ..., the 2-nd row, the 1-st row, the 2-nd row, ...

    Notice that the 1st and the last row gets asked way less time.

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain how to find the feasible solution for problem E? I just do not get the answer from the Editorial. Please.

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

E can be solved by a simple greedy algorithm too. Observe the fact that it is always beneficial to reduce the edges that are at a lower depth before the ones above them. You will reduce the weight (and strength) of an edge only when all the edges in its subtree are at their minimum possible values. You can use DSU on tree technique to implement this and BIT/segment tree to keep track of current sum of weights in any subtree.

This is my code for the same. Complexity is O(n*logn).

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

    Good day to you,

    I've solved this int very similar manner — but with slight differences.

    I made dfs, while pushing all nodes to "priority_queue" [priority on time of visit === lower first]. I sometime had to merge those queues, for which I pushed the bigger into the lower [this shall be O(Nlog(N)) amortized, if I'm right].

    For updates, I — instead of fenwick — propagated this information ONLY to parent [who could do it to its parent when processed ... and so on], making a "STOP" at node/edge, which is being "helped".

    Anyway I think the overall idea is very similar

    Have nice day

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Seems my solution is similar to yours, but I just use deque instead of priority_queue and have O(n) complexity. just need to merge those nodes whose weight can be reduced
      see my code

      UPDATEA: My time complexity is O(nlogn) because of the merging node approach.

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

    I tried a similar approach to yours, using DSU on tree. However, I don't understand why a fenwick tree is needed, though without it I get WA. Could you shed some light on that?

    This is my implementation (from my understanding of the solution): 24814935

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

      The weights of the edges do not stay constant. They keep changing. So I used a Fenwick tree to get the current sum of edges in any subtree.

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

        Thanks for the reply. It's still a little unclear to me why I can't use simple tree DP (I'm getting WA with it). I have already considered that the weights of the edges don't stay constant and I thought tree DP can handle that. My approach was to take the edge with largest visit time and reduce the weight and strength of that edge accordingly. Then, I take away the difference between original weight and new weight from the sum of weights in the current subtree. I'm not sure how a fenwick tree is different from simple tree DP for this purpose. What's wrong with my approach? Can you provide a counterexample? If you're confused with the explanation of my approach you can look at the code above (hopefully it's not too messy XD) Thanks in advance.

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

Even though I couldn't solve it during the contest, I really liked C which in hindsight is elegant when you properly see it's periodicity.

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

How this submission got accepted for problem B : http://codeforces.me/contest/758/submission/23954612 .

The answer for this input RB!YRB!! is 0 0 1 2 , But that submission is give 0 0 1 0 output for that input . How this got accepted ? Am i wrong ? Or dataset was weak . RB!YRB!! solution is RBGYRBGY so R=0 B=0 Y=1 G=2 .

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

    It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As many people here asked for more details on the solution to problem E, here you go.

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

Can I get the data sets of any problem???

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

Here's a much simpler solution for F: For each number $$$x \in [l, r]$$$, compute its signature, by factoring it as $$$p_1^{a_1} p_2^{a_2} \ldots p_m^{a_m}$$$ and reducing $$$a_i$$$ modulo $$$n-1$$$. The solution is just the number of ordered pairs of different integers with identical signatures. This works for all $$$n \geq 2$$$.

→ Reply