### robinyu's blog

By robinyu, 4 years ago,

• +236

 » 4 years ago, # |   +8 In div1 B, preprocessing all relevant factorials and also their modular multiplicative inverses modulo 109 + 7 can be in O(n) even if we don't consider the a constant :)
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 How can we calculate modular multiplicative inverses of factorials in O(n) for inverse we will need logNLike this? first calculate ifact[MAXN] , then ifact[x-1]=ifact[x]*x ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 oops, sorry I can't read.
•  » » » 4 years ago, # ^ |   +17 Yes, this is an efficient method in , and I prefer it to the following O(n) method: rev[i] = -(MOD / i) * rev[MOD % i] (where MOD  = 109 + 7), and then ifact[i] = ifact[i - 1] * rev[i].Anyway, is very close to O(n) and much smaller than .
 » 4 years ago, # |   +11 In "Karen and Test": We will repeatedly perform the operation until the number of elements n is even, and the first operation is addition, ... this will happen somewhere within the first 4 rows.Even better, it will happen within the first 2 rows. If n is even, it has already happened. If n is odd, we only need to do one iteration. The second line will have an even number of elements, and the first operation will always be "+". That's because the first line has (n-1) operations, which is an even number, so the first operation in the second line is guaranteed to be "+".
 » 4 years ago, # |   +8 Really awesome editorials along with pictorial representations <3
 » 4 years ago, # |   0 Div 2 B with binary search Complexity O(nlogn + n + q)Code
 » 4 years ago, # |   0 Div.2 B was really nice, there is more than a dozen of approaches to solve this task :D
 » 4 years ago, # |   +10 In div1 E, I used binary search. Fix k and divide the segments to three sets(left, right, middle). The remaining part is easy. Time complexity is O(log^2 n).http://codeforces.com/contest/815/submission/27895623
•  » » 4 years ago, # ^ |   0 Thank you. Your solution is much easier to understand and implement for me compared to other solutions of Div.1 E .
•  » » 4 years ago, # ^ |   0 Can you please elaborate what your solution does ?
 » 4 years ago, # |   +55 Nice contest and editorial, too. However, the following makes me a bit sad:
•  » » 4 years ago, # ^ |   +14 Actually, there is no upcoming contest in AtCoder too. It's so sad...
•  » » » 4 years ago, # ^ |   0 There is a contest in csacademy, and hackerrank. I believe that there are a lot of other contests in other websites.
•  » » 4 years ago, # ^ |   +32 I do not know if it is a notorious coincidence :P When I have my holidays,CF rounds are so rare but during my semester exam time ,They are quite frequent :(
•  » » 10 months ago, # ^ |   -10 how old are you/
 » 4 years ago, # |   0 Can inclusion exclusion be used for Karen and cards?
 » 4 years ago, # |   +1 I used event sorting for my DIV2 B solution but i think i like the solution of the problem setter. Simple and interesting.
 » 4 years ago, # |   -188 Please hide this anime bullshit. Codeforces is not an anime site. I don't want to see these pictures when I read an editorial.
•  » » 4 years ago, # ^ |   +171 Please hide this hate bullshit. Codeforces is not a hate site. I don't want to see these comments when I read an editorial.
•  » » 4 years ago, # ^ |   +39 Understandable. The editorial is already quite long, and adding the pictures just makes it a bit longer and less readable. They should be removed in a while.Have a great day!
•  » » » 4 years ago, # ^ |   +17 Nooo, don't. I like the pictures
•  » » 2 years ago, # ^ |   0 But I see no picture on the editorial......
 » 4 years ago, # |   0 Nice explanations! I liked the reduction presented in 2D's editorial.
 » 4 years ago, # | ← Rev. 3 →   0 In Div2D/Div1B[editorial] what does the K represent?
•  » » 4 years ago, # ^ |   0 The index of the element in the sequence.
 » 4 years ago, # |   0 I can't understand how and why exactly greedy solution works in div2 C.
 » 4 years ago, # |   +25 For Div1B, I'm very curious why we can always reduce it to the "addition" version of the problem. In contest I failed to find a proof for it, and the editorial only mentions some pattern finding, which is way far from proving it. Is there any Div1B level proof for it?
•  » » 4 years ago, # ^ |   +15 I'm not quite sure what you mean by reducing it to "addition" version of the problem. If you start with addition then after applying the operation four times, you'll do n - 1 + n - 2 + n - 3 + n - 4 = 2(2n - 5) additions/subtractions in total, so if you start with addition, after four rows the first operation will also be addition.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +11 Well sadly, I also can't understand what you are saying, too..Whatever, Let me rephrase what I meant. Author claims : The problem with only plus operation is easily solvable with fast algos. After 4k-th iteration, The problem with only minus operation actually become an instance of "The problem with only plus operation", with input as odd / even array element. So we can perform 4[n/4] operation very fast. I agree on first paragraph, and pattern shows second is true, but I'm not sure why.UPD : Ok now I got it. I didn't read the part that we always reduce it to + / even n case. Now we can prove it. I'm sorry, and thank you for the help!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 What I was trying to say is the pattern always repeats itself every four rows so the pattern will continue.
 » 4 years ago, # |   -13 Yeah! After a long time waiting
 » 4 years ago, # |   +20 In div 1 C. How does the sum converge to O(n)?
•  » » 7 weeks ago, # ^ |   0 I have the same question bro Why no one answered you q.q
 » 4 years ago, # | ← Rev. 2 →   0 Isn't Div1E effectively this: https://code.google.com/codejam/contest/3264486/dashboard#s=p2 ?
•  » » 4 years ago, # ^ |   0 It's not exactly the same. However, both are similar to problem I proposed at Croatian Olympiad in Informatics 2 years ago (http://hsin.hr/2015/olympiad/tasks.pdf; OGLEDALA).Also, the story of GCJ one is similar, but it's understandeable, as the inspiration obviously comes from real life — urinals. I don't remember why we changed it to washbasins in my problem, though.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +20 Ha, speaking of urinals: http://www.spoj.com/problems/URI/And if I'm not mistaken, this is actually exactly the same as Div1E. (I'm problemsetter for the SPOJ problem). Too bad I did not participate in the round :D
 » 4 years ago, # |   +31 In div1 C, the naive dp actually works in N^2 if you don't take j and k all the way up to n every time but only the amount which is actually possible in those subtrees.
•  » » 4 years ago, # ^ |   +13 Will you please explain how it runs in O(n^2) .
•  » » » 4 years ago, # ^ |   +13 Initially you have the size of 1. When you get a subtree of size S you'll make a S * size transition and then you'll make size += S. On the first step, you'll pair the current vertex with all the vertices from the subtree. From the second step onwards, you'll pair the current vertex AND the already counted vertices with the vertices of the next subtree (the number of such pair is S * size). This means that you'll never count any pair twice and the complexity will be exactly the number of such pairs, or O(n^2)
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +5 To be pricise,you can calculate the complexity is this way: just a sketch:  int now=1; for (k=0;k=0;j--) for (int l=s[t];l>=1;l--) { f[1][i][j+l]=min(f[1][i][j+l],f[1][i][j]+f[1][t][l]); f[0][i][j+l]=min(f[0][i][j+l],f[0][i][j]+min(f[0][t][l],f[1][t][l])); } now+=s[t]; } s[1]*1+s[2]*(1+s[1])+s[3]*(1+s[1]+s[2])+...=sigma(s[i]*s[j])=[(sigma(s[i]))^2-sigma(s[i]^2)]/2adding each iteration together,you will find all terms except n^2 will cancel each other So in total,complexity=O(n^2)
•  » » » » 4 years ago, # ^ |   0 Here, you have calculated the time complexity of finding f values for a single node and it turns out to be O(n^2). It may still become O(n^3) when you sum it over all the nodes.
•  » » » » » 4 years ago, # ^ |   +8 No.As I explained above, for each iteration(say node v), the complexity is O((number of sons of v+1)^2-sigma(size of each subtree of v)^2) =O((size of tree rooted at v)^2-sigma(size of tree rooted at a son of v)^2)When adding these complexity together, we get O(n^2),where n is the size of tree rooted at 1, as all other terms will cancel each other. (according to the problem statement ,each node has only one father;and of course each node is the root of a unique subree)
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   -13 How come my this solution is not passing then, which is IMO exactly as per the algorithm which you have shown to be O(N^2). It's TLE(ing) on 27th test case.
•  » » » » 4 years ago, # ^ |   0 Thanks a lot .
•  » » » » 3 years ago, # ^ |   +5 I tried the question DIV1 C using the approach you have suggested but I'm getting TLE and to me, it seems like the complexity of my code is O(n^2 * logn) and for the given constraints it should be enough but still its giving TLE. Please, can you have a look at my code?Here is the code: https://code.hackerearth.com/fc4042j?key=3bf86a65804663409e836178af8310a6Here is the link to my latest submission for this problemhttp://codeforces.com/contest/816/submission/30966480
 » 4 years ago, # |   0 In 815B/816D the pattern found for the n mod 4 = 2 on the fourth constant should it be (((n-2)/2) 1)?
 » 4 years ago, # |   +72 I have some complaints.B: 'Well, we can do something and find magic formulas but wait, we can do something different with triangles and find other magic formulas, now it is much more beautiful!' I will leave aside question about why give this problem to the round. But how can 'watch closely' be an editorial?C: 'Rather straightforward O(n3) DP' is actually O(n2).D: Sorry, I stop reading after words 'segment tree'. 27860187 — easy O(n + p + q + r) solution without any data structures.E: WTF is this?! 'Now, draw the trees with root segments 40, 41, 42, ..., 47' Really? You expect me to draw all these trees to find some really strange pattern which you don't even bother to prove? Who needs proofs anyway. If you don't have any other solutions then 1. How you prove for yourself that all these patterns lead to a correct solution? 2. Why to give this problem on round? You really expect that someone will make all these great observations during two hours?And yes, there are much simpler solutions 27862681. And (look in comments) there were problems similar to given and even this exact problem.To sum it up: we have three problems (out of five) for which there exists a solution simpler than it was expected. And expected solution for E looks like it is really unlikely to come up with.I think that coordinator should have done much more serious work here.
•  » » 4 years ago, # ^ |   +30 I completely don't get your point in B. I am satisfied by described solution.For D I think there are few ways to solve this problem instantly using really standard ideas like some segment trees or I thought about some set of pairs that also does work. You came up with some tricky solution, fine, you're clever, but that doesn't mean that problem is shit. However I didn't really like it anyway because "compute volume of sum of boxes" doesn't sound like an innovative problem.
•  » » » 4 years ago, # ^ |   0 Reread editorial for B. Phrases that are closest to formal proof are 'Observe the following picture' and 'Am I the only one whose mind is on the verge of exploding?'. We observe and notice, we don't prove.
•  » » » » 4 years ago, # ^ |   +16 Did you notice the picture with yellow and blue numbers :|? Isn't that sufficient for you as a proof? Would you feel better if instead of that there will be some hard to follow formulas that will prove what is obvious from that picture? Observing, noticing and proving for statement of such type are typically the same thing. By no means I want to say that noticing pattern is always sufficient for a proof but here once we note pattern from picture then converting it to formal proof is a task for 10years old child, I thought you are capable of such feat.
•  » » » » » 4 years ago, # ^ |   0 I get your point. You can deduce the proof from that picture so you think that everybode can.Yes, triangle on the picture is quite convincing and I can make from it a proof. But that's not what author says. He says 'It is beautiful that is why it's true'.
•  » » » 4 years ago, # ^ |   +15 Maybe you are right about D. Maybe I just tried to find more examples of strange things in this round and went too far.
•  » » 4 years ago, # ^ |   +16 Can you explain your O(n + p + q + r) solution for problem D?
•  » » » » 2 years ago, # ^ |   0 So we use prefix sum instead of segment tree here, is that correct?
•  » » » » » 2 years ago, # ^ |   0 So you have already Accepted the problem right before you have solved this......You didn't get the segment tree approach? 44903594
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hi, Please could you explain why your solution for problem C is O(n^2)? You have this loop in your code for (int v = n - 1; v > 0; v--) { int u = par[v]; for (int i = 0; i <= sz[v]; i++) dp[v][1][i] = min(dp[v][1][i], dp[v][0][i]); for (int i = sz[u]; i >= 0; i--) for (int j = sz[v]; j >= 0; j--) { for (int k = 0; k < 2; k++) { dp[u][k][i + j] = min(dp[u][k][i + j], add(dp[u][k][i], dp[v][k][j])); } } sz[u] += sz[v]; } First you iterate over each node, inside that you have two loops that iterate over the size of the node and the size of the father, in a line-graph (i.e. 1 — 2 — 3 — 4 — ... — n), this won't be O(n^3)?Thanks
•  » » » 4 years ago, # ^ |   +5 Let's suppose each vertex v has its own 1v and for some set of vertices V. Now calculate the number of iterations of inner cycle in my algo like this: whenever you want to add szv·szu, replace each sz with corresponding sum of 1 and then open brackets. It is easy to see that 1v·1u appears exactly once for all different v, u, so the sum is exactly n(n - 1) / 2.
•  » » » » 3 years ago, # ^ |   +5 I tried the question DIV1 C using the same approach which you have suggested but I'm getting TLE and to me, it seems like the complexity of my code is O(n^2 * logn) and for the given constraints it should be enough but still its giving TLE. Please, can you have a look at my code? I am not able to figure out why my solution is still O(n^3).Here is the link to my latest submission for this problemhttp://codeforces.com/contest/816/submission/30966480
•  » » » » » 3 years ago, # ^ |   +3 I think that this piece of code may be problematic: dp1[0][0] = 0; int NOW = 0; for(int i=1;i<=child.size();i++){ NOW += sz[child[i-1]]; for(int j=0;j<=NOW;j++){ for(int k=0;k<=j;k++){ I would say that k should go to sz[child[i-1]]. You should modify your algo, so that one loop goes to NOW and the other iterates just over the size of the child's subtree.
•  » » » » » » 3 years ago, # ^ |   0 Hey, Thank you for your reply. I made the changes which you suggested but still its giving TLE on the same test case. Here is the link to my latest submission. Please have further look if you think we can further improve the complexity.http://codeforces.com/contest/816/submission/31972625Thank you, once again for helping me !!!
•  » » » » » » » 3 years ago, # ^ | ← Rev. 5 →   +3 Another tle possibility is the fact that you increment NOW before the loop. The idea is that you should iterate over each possible number of vertices from your subtree and everything which was already processed. I don't understand your code exactly — for some reason you update dp for children first. In order to update dp for next child you are using values for the previous child. The idea is to calculate dp for curr using the values from children. This way the loop which iterates over child subtree would go from 1 to sz[child[i-1]] and the loop for curr would go from 0 to NOW. After you process child[i-1] you add appropriate size to NOW.In current version vertices from subtree are paired with each other, which could bump the complexity to O(n^3) as they can be paired with each other multiple times.EDIT. To make sure that you understand the idea. Each value from the subtree can be assigned to different vertex from the subtree. You calculate values for 1,2,3,..,sz[subtree] vertices, so every time you add one new vertex. Now you want to get every vertex from the subtree and try to match it with values which are already calculated — each such value represents one of the vertices already processed, using the same logic. When you do comparison dp[curr][j+k] = min(dp[curr][j+k], dp[curr][j] + dp[child][k]) you do the matching (j-th processed vertex and k-th vertex from child's subtree). Now, you have to make sure that on every stage you match vertex k, with vertex j, such that you have never matched them before -> this way you visit O(n^2) pairs in total. Otherwise you will be matching vertices multiple times and you have n possibilities to do that. Hence your total number of matches could be O(n^3).
•  » » » » » » » » 3 years ago, # ^ |   +5 Thank you for your help. I got an AC finally. Because of your comment, I finally got the idea why the code was giving TLE. I made the changes you suggested and got an AC.
•  » » » » » » » » » 3 years ago, # ^ |   0 You're welcome!
 » 4 years ago, # | ← Rev. 2 →   0 Does anyone have a rigorous proof of Div2 D/Div1 B?I am simply unable to understand why the last two terms come out as the answers to the "simpler" versions a1,a3,a5,... and a2,a4,a6,...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 Claim: So long as the number of terms is even, in 2 lines, the each term will be dependent only on the similarly colored term.Proof: Basically what is shown, because arbitrary numbers are being used the result will not depend on input. The addition pattern is going to be the same since the number of terms is even.This proof shows that after 2 lines it will still be true. We can again use it to show that after 4 lines it will still be true. And so on to the last line.
 » 4 years ago, # |   +2 "woosh"? Does this word exist? XD
•  » » 4 years ago, # ^ |   +21 It surely exists, and it's pretty rad.https://xkcd.com/1627/
•  » » 4 years ago, # ^ |   +69 Humans :How to solve div 2/1 A B C D E ?How to prove div 2/1 A B C D E ?I know simpler solution than editorial.round winner:Is 'woosh' a real word?Yo mama is a presentation error.
 » 4 years ago, # |   0 In f(i, j) = min(f(i, j), f(i, j - k) + f(i, k)), how are we making sure that we don't repeat elements?
 » 4 years ago, # |   0 Waiting for another contest !!
 » 4 years ago, # |   0 What does it mean?
•  » » 4 years ago, # ^ |   +5 You might know it as C(n - 1, k - 1). It's number of ways to choose k - 1 elements from n - 1 elements.
 » 4 years ago, # |   +3 can someone explain why can we skip the largest subtree, i didn't got that point. thanks in advance
 » 4 years ago, # |   0 Can someone explain me why the contribution of the K-th element when there are n elements is precisely
 » 4 years ago, # |   0 can someone explain the editorial for problem div2 E karen and supermarket, its not striking after reading the editorial. please help
 » 4 years ago, # |   0 "First, simplify the problem so that only addition ever happens. In fact, this version is much easier: the contribution of the element when there are n elements is precisely (n-1) (k-1)."Can anyone explain this line in Div1 B editorial?
 » 4 years ago, # |   0 A great editorial and thank u sooo much for such detailed approaches...A newbie like me will learn a lot.
 » 4 years ago, # | ← Rev. 2 →   0 For Div 2 Problem E/Div 1 Problem C:Note that we can't do this at the start, because otherwise it could cause conflicts.What conflict could it possibly cause? I can't seem to think of any in this case.
 » 4 years ago, # | ← Rev. 2 →   0 In Div2 C, what if we gave decrementing a row by 1 the weight of X and decrementing a column by 1 a weight of Y, would the problem change? will the greedy approach still be guaranteed to work? and how to optimally approach it in this case.
 » 4 years ago, # | ← Rev. 3 →   0 When n mod 4  =  2, the 4th pattern seems wrong, should be C((n - 2) / 2, 1)?
 » 4 years ago, # |   0 Suppose our tree was binary. Now, we can compute fi, j = min0 ≤ k < j(fa, j - k - 1 + fb, k + ci - di), where a and b are the subtrees of i, with s(a) ≥ s(b). This skips iterating through the larger subtree a. How ? Please explain.
 » 9 months ago, # |   0 one of my favourite editorial:3
 » 6 months ago, # |   0 problem 816 B (link : https://codeforces.com/contest/816/problem/B) we do  a[l]++ , a[r + 1]--  then we do prefix sum. my question is in which cases we can use this  a[l]++ , a[r + 1]--  technique ? please help :)