### Kniaz's blog

By Kniaz, 5 years ago, translation,

Problem author: MikeMirzayanov.

Problem author: MikeMirzayanov, Kniaz.

Problem author: Kniaz.

Problem author: MikeMirzayanov, Kniaz.

Problem author: Kniaz.

Problem author: Kniaz.

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

• +80

 » 5 years ago, # |   +17 Very nice contest. Thank you <3
 » 5 years ago, # |   0 Nice problem set !!
 » 5 years ago, # |   0 I think a typo in F: It should be (l — 1) / (y ^ (n — 1)) instead of l / (y ^ (n — 1)).
•  » » 5 years ago, # ^ |   0 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
 » 5 years ago, # |   0 Can someone explain O(1) solution of problem C?
•  » » 5 years ago, # ^ |   0 I just found this accepted solution 23972771 of problem C implementing a O(1) algorithm. It might help you.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
 » 5 years ago, # |   0 Also I want to thank authors of B for creating test 17.
•  » » 5 years ago, # ^ |   0 Why so?, I actually passed all cases, and can't found anything peculiar about that case.
 » 5 years ago, # |   0 in problem D, how to check the following string (base 16)101because if we take greedily from the suffix, we will end up with 01, but we cant add 1 to make it 101 (>n)
•  » » 5 years ago, # ^ |   +4 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).
 » 5 years ago, # |   +6 Dynamic programming is usually associated with overlapping subproblems. The way solution for E is described may cause confusion...
•  » » 5 years ago, # ^ |   +3 That made think this solution was totally different from my solution, when it's actually pretty much the same. Anyway, really cool problem.
 » 5 years ago, # |   0 Can somebody explain editorial for Problem E . How dpmin is used for calculating the answer ?
 » 5 years ago, # | ← Rev. 2 →   0 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
 » 5 years ago, # | ← Rev. 4 →   +14 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)
 » 5 years ago, # |   +1 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!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » 15 months ago, # ^ |   0 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
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +3 Can someone explain how to find the feasible solution for problem E? I just do not get the answer from the Editorial. Please.
 » 5 years ago, # | ← Rev. 4 →   +11 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).
•  » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 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 reducedsee my code UPDATEA: My time complexity is O(nlogn) because of the merging node approach.
•  » » 5 years ago, # ^ |   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 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.
 » 5 years ago, # |   0 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 .
•  » » 5 years ago, # ^ |   0 It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'.
•  » » » 5 years ago, # ^ |   0 Ow thanks , i understand .
 » 5 years ago, # |   0 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?
 » 5 years ago, # | ← Rev. 2 →   0 As many people here asked for more details on the solution to problem E, here you go.
 » 5 years ago, # |   0 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?
 » 5 years ago, # |   0 Can I get the data sets of any problem???
 » 19 months ago, # |   0 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$.
•  » » 19 months ago, # ^ |   0 thanks for such a fast reply
 » 15 months ago, # |   0 There are many codes getting ac of type like this but fail for test case R!!!