Kniaz's blog

By Kniaz, 2 months 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 (PikMike) for translation of tutorial!

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

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Very nice contest. Thank you <3

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem set !!

»
2 months 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)).

  • »
    »
    2 months 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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why so?, I actually passed all cases, and can't found anything peculiar about that case.

»
2 months 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)

  • »
    »
    2 months 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).

»
2 months 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...

  • »
    »
    2 months 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.

»
2 months 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 ?

»
2 months 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

»
2 months 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)

»
2 months 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!

  • »
    »
    2 months 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).

»
2 months 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?

  • »
    »
    2 months 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.

»
2 months 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.

»
2 months 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).

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How this submission got accepted for problem B : http://codeforces.com/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 .

  • »
    »
    2 months 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'.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the maximum weight for all subtrees for Problem E? What is maximum weight, if we can't increase strength or weight for the edges? Isn't that the same as total weight for a subtree?

»
7 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

On problem E, when we compute dpmin, why do we substract 1 in the formula? Could somebody explain in a little bit more detail, please?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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