### Lewin's blog

By Lewin, 3 years ago,

Here's the editorial. Hope you have a happy new year!

Code can be found here: https://www.dropbox.com/sh/i9cxj44tvv5pqvn/AACQs7LLNyTZT-Gt_AMf7UQFa?dl=0

New Year and Counting Cards
New Year and Buggy Bot
New Year and Curling
New Year and Arbitrary Arrangement
New Year and Entity Enumeration
New Year and Original Order
New Year and Boolean Bridges
Tutorial of Good Bye 2017

• +336

 » 3 years ago, # |   +60 kudos to a lightening fast editorial!
 » 3 years ago, # |   +11 Is there any way to interpret E as a vector space or group or something like that?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 If I'm not mistaken, E should be related to counting the number of topologies on {1, 2, ..., m} in which the given family of n sets is open.(Not topologies but sigma algebras — lapsus calami)
•  » » » 3 years ago, # ^ |   +24 It is not a requirement in topological spaces that the complement of an open set is also open (In fact, in spaces like R^n, the complement of an open set is a closed set, and only R^n and the empty set are both open and closed sets). So in this problem, what is asked is exactly to count the number of topological spaces on , such that the complement of any open set is also an open set.Such spaces happen to also be linear subspaces of , since it is easy to write xor using only and, or and not. This observation might or might not help in arriving at the key observation on partitions (it is equivalent to observing than, when performing a careful Gaussian elimination, one can achieve a triangular matrix that has exactly one "1" per column).
•  » » » » 3 years ago, # ^ |   +8 Continuing with this completely unnecessary abstract translation, the key observation regarding partitions is equivalent to the fact that the Kolmogorov quotient of our space has the discrete topology (Kolmogorov quotient "glues" indistinguishable elements into one new single element).
•  » » » 3 years ago, # ^ |   +16 I think the term you are looking for is "Sigma Algebra".
•  » » » » 3 years ago, # ^ |   +3 Indeed! Nice catch. So the key observation can also be stated as "finite sigma algebras are essentially equivalent to partitions". Googling that right now shows a related question here: https://math.stackexchange.com/questions/143796/number-of-sigma-algebra-on-the-finite-set
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Which is how I solved it :DWell, I would have probably figured it out on my own if I had thought about it for a minute or two, but it was too tempting to just google "Number of sigma algebras on a finite set".
•  » » » » 3 years ago, # ^ |   +21 In fact (to be even more pedantic :D) you don't need the "sigma" part, which refers to countable unions. Since everything is finite it is just an algebra of sets.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 For anyone delighted with the present display of pedantry, a friend of mine just made me notice that finite topologies are equivalent to preorders (a point x is less than another y, if any open set containing y also contains x), which are also essentially just "transitive" directed graphs.So in the finite case:Sigma algebra --> partitionsTopology --> preorder
 » 3 years ago, # |   +53 maths too hard~~
 » 3 years ago, # |   +2 Codeforces is becoming awesome day by day :D
 » 3 years ago, # |   +2 Editorial even before system testing finished, amazing punctuality grandmaster.
 » 3 years ago, # |   +64 My solution to H is probably equivalent to yours, but it's explained in much simpler terms than Walsh-Hadamard transform :)See "4.2 Inclusion-exclusion" in http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf
•  » » 3 years ago, # ^ |   +14 Nice solution. I noticed my solution looked like inclusion/exclusion but didn't know how to explain it. I found it easier to explain through walsh hadamard transform since that's how I originally thought of the problem/solution. Glad to know there is a simpler explanation :)
•  » » » 3 years ago, # ^ |   +44 I actually admire that your knowledge enables you to use Walsh-Hadamard transform in a solution so easily :) I had to Google the paper to make progress.Thanks a lot for the contest!
•  » » 3 years ago, # ^ |   0 The O(nk·2.45n) algorithm (dynamic programming, only iterating over maximal independent subsets) also passes in less than 1 second.Unfortunately, too many bugs :(
•  » » » 3 years ago, # ^ |   +19 We can also all borrow a trick from dotorya:  while (clock() - st <= CLOCKS_PER_SEC * 4.5) { random_shuffle(u, u + X); int mx = 0; for (i = 0; i < X; i++) col[i] = 0; for (i = 0; i < X; i++) { int t = u[i]; for (j = 1; j <= X; j++) tchk[j] = false; for (j = 0; j < X; j++) if (conn2[t][j]) tchk[col[j]] = true; for (j = 1;; j++) if (!tchk[j]) break; col[t] = j; mx = max(mx, j); } mn = min(mn, mx); } 
•  » » » » 3 years ago, # ^ |   +3 That should probably fail on a chain of length 23, though?... Or does it have so many attempts that it passes that one as well?
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   +18 For a chain of length 23, I think the expected round is at most .I have no time left and implemented a similar solution.And I passed all the system testcases with only 100 iterations and 15ms :)
•  » » » » » » 3 years ago, # ^ |   0 At least for a bipartite graph, this solution should work in O(2n).Take one valid coloring, and suppose that there are B black vertices and W white vertices. If dotorya chooses a permutation such that all black vertices come before all white vertices (and vice versa), it works correctly. This happens with probability .Is this O(2n) for general graphs or not?
•  » » » » » » » 3 years ago, # ^ | ← Rev. 6 →   0 What about complement of complete tripartite graph (so? Growth rate of is around O(33n).UPD: I misunderstood algorithm, sorry for many updates.However, it seems like it might be more difficult to bound this runtime.
•  » » » » » » » » 3 years ago, # ^ |   0 Doesn't it always handle complete tripartite graphs correctly?
•  » » » » » » » 3 years ago, # ^ |   0 What do you think about the graph on n vertices where vertex i is connected to vertices in interval [i - k, i + k] with chromatic number k + 1?
•  » » » » » 3 years ago, # ^ |   +31 Actually I didn't compute probability at all. I just wrote general time-cutting method and prayed this would pass. Sorry :( After the conteat, I thought that the worst case is a chain with 23 vertices, which makes 10^-6 probability, which can pass this within time limit. But I was not sure whether this is the worst case...
•  » » » » » » 3 years ago, # ^ |   +31 There's nothing to be sorry about, I meant it when I said we should borrow a trick from you — you got the problem accepted quicker, and that is good!
•  » » 3 years ago, # ^ |   0 I imagine that the number of k-colourings can get quite big though (n! for a complete graph, and I'm not sure if that's the worst case). I see you used a randomly selected prime modulus to get a solution that is right with high probability (and which is hack-resistant), but would a solution that's guaranteed correct (presumably using bignums) run fast enough?
•  » » » 3 years ago, # ^ |   0 Well, the probability of error is at most 23*1e-9, so I would say that there's not much difference — i.e., in my mind it's like quicksort working in O(nlogn).But I don't know a deterministic fast enough version of my solution.
•  » » » » 3 years ago, # ^ |   0 I managed to add an extra O(logk) factor, and I had to use modulo 232 hash to fit into TL. Luckily it passes.
 » 3 years ago, # |   0 Really nice problems! I kept thinking about how to handle the infinitely large case in D, but couldn't figure it out at last :( And also, F is a really cool problem I think :D
 » 3 years ago, # |   0 WOW! Thank you so much for super fast Editorial and also for the awesome problems !
 » 3 years ago, # |   0 Whoohh such a fast editorial!!!!!!!!
 » 3 years ago, # |   +11 F was a Div2C question. I wonder why the authors kept it at F :(
 » 3 years ago, # | ← Rev. 2 →   -90 What's wrong with my code for problem B? #include #include #include using namespace std; int main() { string s="lrud"; int n,m; cin>>n>>m; char a[n][m]; int x,y,p,q; for(int i=0;i>c; sort(s.begin(),s.end()); for(int i=0;i0 && a[x-1][y]!='#') { x--; k=1; } if(ch=='r' && x0 && a[x][y-1]!='#') { y--; k=1; } if(ch=='d' && y
•  » » 3 years ago, # ^ |   +3 Use the spoiler tag to share code or put your submission link, please.
•  » » » 3 years ago, # ^ |   -18
•  » » 3 years ago, # ^ |   +5 next_permutation STL function only permutes according to the lexicographically greater comparator...hence in our case, it does consider all the 24 cases needed.
•  » » » 3 years ago, # ^ |   -21
 » 3 years ago, # |   0 can anyone please help in understanding the dp transition in D.
 » 3 years ago, # |   +21 goodbye rating
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 dude you solved 4 question on one go. you shouldn't be saying this :P
•  » » » 3 years ago, # ^ |   0 but the problem D had cost most of my time during the contest. :( Anyway the problems are good, yet I'm foolish.
 » 3 years ago, # |   0 Problems blew my mind, great contest-great problems.
 » 3 years ago, # |   0 For C, do we need to compute dy for all discs that can possibly touch (i.e. all discs in the ≤ 2r range), or can we just compute it for the disc with the highest y coordinate of these?
•  » » 3 years ago, # ^ |   +1 You want to find the highest y+dy overall, not the highest y (and then + the dy of that).
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 My question is:Suppose a disc X is within the +/- 2r range. That means, if the disc currently being processed keeps dropping, it will eventually touch this disc X, unless it first touches some disc Z.The question is whether we can conclude such disc Z must have a higher Y coordinate than disc X.I.E. for N discs in the range, the dropping disc must touch the one with the highest Y coordinate.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +1 No, that's not true in general. You can try this case for example: 5 1 2 1 4 4 2 For the last disk, the highest y-coordinate disk wihtin range is the fourth one, but it will touch the second disk first.
•  » » » » 3 years ago, # ^ |   +6 No, that's false. if the highest-y disc is far away, and an almost-as-high-y disc is very close, it can touch the almost-as-high disc before the highest disc.For concreteness, consider R=2, discs at (0, 2), (2, 1), and a new disc dropping at x=2. Then it will touch the (2,1) disc first.
•  » » » 3 years ago, # ^ |   0 That is where I fell :( I found the highest y colliding with a circle and then found the dy of that. :/Great question btw!
 » 3 years ago, # |   +6 Light-speed Tutorial,Light-speed System Test! I like it!
 » 3 years ago, # |   +6 Editorial before Final testing. So fast. (y)
 » 3 years ago, # |   +1 Editorials before system testing. That's a perfect goodbye to 2017 (*-*)
 » 3 years ago, # |   +4 Great problems and a fast, nice, and concise editorial. Great Job!
 » 3 years ago, # |   0 There is a slight formatting error with the bell number link. (Extra right bracket at the end)
 » 3 years ago, # |   0 Thanks for good contest!
 » 3 years ago, # |   0 In Problem D Can somebody please explain why infinite length sequence is not necessary for "exact answer" ?
•  » » 3 years ago, # ^ |   +3 Didn't solve it, but I'm guessing it's because you can find the expected value of the amount of trials until first success with a closed form formula: https://www.cut-the-knot.org/Probability/LengthToFirstSuccess.shtmlJust 1/p.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 At some point adding only one 'b' will satisfy the condition k. The probability of adding n 'a's then one 'b' at this point is: (1 - p)n × p where p is the probability of putting a 'b' (e.g: ).Hence the expected value of the sequence's length is: which is finite.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   +3 I know i am wrong,but i don't know whywhy cant i say thatE = (1 — p)(E + 1) + pbecause it has probability p of ending here,taking one step,or it has 1 — p of continuing,which takes one extra stepthenE = E(1 — p) + 1 — p + pE * p = 1E = 1 / p LE:this would give me the average number of steps untill i stop,but i should subtract 1 from it because i am interested in the average numbers of ab,not the avreage length. So 1/p — 1 = (1-p) / p
•  » » » » 3 years ago, # ^ |   0 This is correct!!
•  » » » » » 3 years ago, # ^ |   -7 yeah but i didn't realise for a long time that i need to subtract 1 :))).But yeah,now it's corect :))
•  » » » » 3 years ago, # ^ |   0 can you please help me in understanding the solution. I didn't understand : "because it has probability p of ending here,taking one step,or it has 1 — p of continuing,which takes one extra step" please elaborate it a little and if possible please explain it with an example.
•  » » » » » 3 years ago, # ^ |   +3 So lets say 2 events could happen:-a succes with probability of p-a failure with probabilty of 1 — p we are at the first step,and we ant to see the expected number of steps untill the first succeswell if you have a succes(with probability p),then you only take one step. so E = p * 1 + the other caseif you have a failure(with probability 1 — p),then imagine that the next step is exactly like step 1,so the expected from that point would be the same. But,because you already had a failure,you must add one to it.so E = p * 1 + (1 — p) * (E + 1)if you do a bit of math this meansE = 1 / pNow,back to our original problem,this is the expected length of a string untill we put a b.this would give us length — 1 more ab's.So the real expected value is E — 1 = (1 / p) — 1 = (1 — p) / p
•  » » » » » » 3 years ago, # ^ |   0 here p is probability to get 'ab' ?
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 no,p is probability to put bso pb/(pa + pb)
•  » » » 3 years ago, # ^ |   0 I wonder how to prove this formula..
•  » » » » 3 years ago, # ^ |   +3
•  » » » » » 3 years ago, # ^ |   0 Thanks
•  » » » 3 years ago, # ^ |   0 Why we need to use DP if the answer to the problem is (1-p)/p? I can not understand it at all.
•  » » » » 3 years ago, # ^ |   0 The condition for applying the formula is when adding only one ‘b’ is enough to satisfy the condition ‘k’. This means that we have constructed a prefix of ‘a’s and ‘b’s, and that appending one ‘b’ to our prefix is enough to satisfy our condition.To construct that prefix we use DP. The formula is applied when we hit a base case.
 » 3 years ago, # | ← Rev. 2 →   +5 For problem D, I managed to get the formula but then I did not know how to make sure P and Q to be coprime. It turned out that I did not have to do anything and it would still pass. Can someone explain to me please why. (I used the same formula in the editorial)
•  » » 3 years ago, # ^ |   +11 Say you have integers p = p'g and q = q'g where g = gcd(p, q).Then pq - 1 = p'g(q'g) - 1 = p'gg - 1q' - 1 = p'q' - 1.
•  » » » 3 years ago, # ^ |   0 Makes sense, thanks.
 » 3 years ago, # |   0 What is wrong with my approach to problem C ? Approach — for any circle- check all the points in the range c-r to c+r (c is center). find which previous circle(if any) in that range has the largest height. so it will touch that circle. then find the height as per the formula in the editorial. and update the range with the new circle.My solution link http://codeforces.com/contest/908/submission/33786083
•  » » 3 years ago, # ^ |   0 I haven't seen ur code but you have to check from c-r-r to c+r+r
•  » » » 3 years ago, # ^ |   0 why is it? range of the outermost points of the circle colliding should be [c-r,c+r] right?
•  » » » » 3 years ago, # ^ |   0 The center of the circle it collides with is another r distance away
•  » » » » » 3 years ago, # ^ |   0 I mark the range of each circle, so it will encounter the circle whose center is r distance away from its circumference. The reason I got wa was the thing that bmerry explained below.
•  » » 3 years ago, # ^ |   +16 I think you made a mistake that I hacked a few other solutions on too: you've assumed that the disk you hit first will be the one that stopped with greatest y, but that's not necessarily true if there is one with a slightly lower y but much closer x.
•  » » » 3 years ago, # ^ |   0 yes, that might be the case. I should have taken the max over all. :( Thanks.
 » 3 years ago, # |   0 Will there be an editorial in Russian?
•  » » 3 years ago, # ^ |   +2 You can use Chrome and then translate automaticaly all the page
 » 3 years ago, # |   0 It should be noted for problem F that, if there are no green points, you do not have to connect the red points and the blue points. In every other case, the optimal solution must involve connecting all points to each other, but, in this case, none of the red points have to be connected to the blue points. The problem may be a little misleading in this regard, as it says that Roy and Biv want all the points to be connected; however, later on, it does specify that they only want all the points they can see to be connected.
 » 3 years ago, # | ← Rev. 2 →   +10 In H, I've picked random number and calculated result modulo this number, hopeing, that when number of colorings will be greater than zero, then it will also after moduling be greater than zero. Can you prove, that we don't have to use any modulo (so use 2^64), and it'll still be ok?
 » 3 years ago, # |   +10 Thanks for the contest :) was really fun ^^ and thank you for the fast editorial! srsly.
•  » » 3 years ago, # ^ |   0 And wow kudos for the solution in multiple language!!
 » 3 years ago, # |   0 what is wrong in my solution for problem C the link is here.
•  » » 3 years ago, # ^ |   0 Figured out :D Thanx for the comment bmerry
 » 3 years ago, # |   0 Editorial has appear faster than ratings. Hm....
 » 3 years ago, # |   +14 I can't get D solution. Could somebody explain the solution with more detail?
•  » » 3 years ago, # ^ |   0 Finally I've got it! solution coded directly from formula 33810491
 » 3 years ago, # |   0 What is wrong with this solution for Problem C http://codeforces.com/contest/908/submission/33779874 . It is giving WA for Test Case 7.
•  » » 3 years ago, # ^ |   0 Got it.
 » 3 years ago, # | ← Rev. 4 →   +4 Why is the formula for D not dp[i][j] = (pa * dp[i  minus  1][j] + pb * dp[i][i  minus j]) / (pa + pb) ?As in to reach current state with i a's we can only arrive here from having i-1 a'sand to reach current state having j ab subsequences we can add b to prefix with i-j a's and get a prefix with j ab's Thanks :)EDIT(for those who clicked pluses): Okay, so it seems we are working backwards, because our base cases are when j >= k, it means that at (i,j) we are ending our algorithm, so expected value of 'ab' subsequences is j. Because of that our answer should be dp[0][0]we also have the i + j >= k condition, to ensure that a's in our prefix doesn't exceed b's so that out count of a's are bounded by k.Therefore our answer is dp[1][0], because there has to be atleast one 'a' to form some amount of 'ab' subsequences
•  » » 3 years ago, # ^ |   0 Thank you your comment helped to understand the way the editorial thinks.The key is that you start the algorithm from a fixed state and it only matters the amount of a's and ab's sub-sequences to compute the expected ab's when the algorithm finishes
 » 3 years ago, # |   +20 dotorya solved G at 00:49:58 before bmerry
•  » » 3 years ago, # ^ |   +20 Oops, thanks for catching this.
 » 3 years ago, # | ← Rev. 2 →   0 Didn't understand some moments in explanation of problem F. Firstly, outer points = the leftmost and the rightmost points on the line ? Assuming that let's consider the first case: the outer green points are not directly connected, in which case, we must connect all the red/blue points in the line. Okay, look at the test: 1 G 3 B 5 G 7 B 9 G Firstly, doing the second observation I should connect 3 — 5 and 5 — 7. Okay, what's next? I guess I should connect 7 — 9 and 1 — 3 ? Just can't see something like that in editorial. Secondly, let's consider the second case: the outer green points are directly connected, in which case, we can omit the heaviest red and blue segment. Word "directly" seems very strange to me there. I really can't imagine that case not counting variant when we have only two adjacent green points. For example: 1 G 3 G 5 G Are x = 1 and x = 5 points directly connected if they linked through the point with x = 3 ? Need more detailed explanation, please.
•  » » 3 years ago, # ^ |   +3 I think you may be misinterpreting what the observations give you. The main point is that there can be no edge that "skips" a green point, thus, we can split the problem into sections which are each independent so that we only need to solve the case where the only green points could be first and last points.For the second case, I should have clarified that a "red" edge is an edge that connects (red/green) to (red/green), and a "blue" edge is an edge that connects (blue/green) to (blue/green).
 » 3 years ago, # |   +1 In D why "The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored. To fix this, we can adjust our answer to be dp[1][0]."Why just ignore it? Why doesn't it change the answer?
•  » » 3 years ago, # ^ |   +3 Those b's can't be part of any subsequence that forms 'ab', since there's no 'a' before them, and we're only interested in expected amount of times 'ab' occurs.
•  » » » 3 years ago, # ^ |   0 So what happens with sequences like "bab.." or "bbbaab.."? Don't we count them in the answer?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 The reasoning is this way. With no loss of generality every case we run the algorithm start with a finite amount of b's and then an a. In all the cases so we finish with 1 a and 0 ab's, thus, by definition the answer is dp[1][0].
 » 3 years ago, # |   0 In problem D, I didn't understand the meaning of this statement.You stop once there are at least k subsequences that form 'ab'.We can have infinite bs then an ab, can this be the case?Please help me understand the problem.
 » 3 years ago, # |   +6 The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored.Shouldn't we multiply by 1 + p + p2 + .. where p = pb / (pa + pb) instead of ignoring?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 dp[i][j] = (pa * dp[i + 1][j] + pb * dp[i][i + j]) / (pa + pb)When i = j = 0, dp[0][0] = (pa * dp[1][0] + pb * dp[0][ 0]) / (pa + pb)bring pb/(pa+pb) to the left and it becomes (1-pb)/(pa+pb) = pa/(pa+pb) which cancels on both sides, so we getdp[0][0] = dp[1][0]
•  » » » 3 years ago, # ^ |   +6 Ah, or continuing from what I said, the answer is (1 + p + p2 + ...) * pa / (pa + pb) * dp[1][0] = dp[1][0]. In either your derivation or what I wrote above, the initial 'b's cannot be "ignored", they simply cancel out with the leading a. Is there any intuitive explanation of this fact, or is lewin's editorial misleading in using the word "ignored"?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 The number of 'ab' subsequences in a string s is the same as if there was an extra 'b' in the beginning of s (or two b's, three, etc).Maybe it gets intuitive if you think that the distribution is constant for every "pattern" (I mean, s, s and an extra 'b', two extra b's, etc), and the expected value of a constant distribution is the value of the constant. It's like you could just get the value for s rather than the "average" of all these cases, since all their values are equal.
•  » » » 3 years ago, # ^ |   +13 Logically, (pa+pb)/pa * dp[0][0] is the answer. Which is also equivalent to dp[1][0] by calculation. But how are they equivalent intuitively?
 » 3 years ago, # |   +5 When will the ratings be updated ?
 » 3 years ago, # | ← Rev. 3 →   0 In solution code of D- why have you kept if (ab >= k) ? if we already have this check - if (a + ab >= k) ? First one will never be encountered.
•  » » 3 years ago, # ^ |   0 Keep this if (ab >= k) condition above second one so that it is checked earlier
•  » » » 3 years ago, # ^ |   0 But its useless. if you have ab>=k then a+ab>=k is already satisfied. so it never executes.
•  » » » » 3 years ago, # ^ |   0 Yes we can avoid that
 » 3 years ago, # | ← Rev. 2 →   +19 Problem G can be solved in O(102n).
•  » » 3 years ago, # ^ |   0 Well what do one and cnt mean in your code? Would you please explain it a little bit? Thanks a lot.
•  » » » 3 years ago, # ^ |   +18 For fixed d, we would like to add o(x) = 111...1 (x's ones) to the answer if the number contains x digits not less than d.To maintain when we find a new digits not less than d, .
•  » » » » 3 years ago, # ^ |   0 Got it. Thanks. But what does means? Is it a typo?
 » 3 years ago, # | ← Rev. 4 →   0 My approach to F(New Year and Rainbow Roads) is to connect all green points where the cost = (last green - first green). And then considering all green points a single one, connect it with the red ones using mst and do the same with blue ones. If there is no green point then ans should be (last red - first red + last blue - first blue). Can someone tell me where I am wrong...please
•  » » 3 years ago, # ^ |   +3 The issue is that green points don't need to be directly connected: it is also valid to connect two green points using two different paths, one going over all the red points in between and one going over all blue points in between. It is easy to verify that this satisfies the constraints of the problem.The following should be a breaking case that tests this case: 7 1 G 2 R 3 B 4 R 5 B 6 R 7 G The correct answer for this case is 12, but it seems like your solution would output 14.
•  » » » 3 years ago, # ^ |   0 Understood..Thanks a lot!!
 » 3 years ago, # | ← Rev. 4 →   0 Can someone help where I am going wrong in finding closed-form condition for Problem DImageUPD : The derivation is actually correct we can put (1-a)=b then cancel out b and the ans will finally be x+b/a = done+f+(b/a)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 https://imagebin.ca/v/3mS1m1CZVCff You mean this?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes, it is similar but i is varying from 0 to inf but I wonder what about that constant factor x(=done + f) Why it is not added later?
•  » » » » 3 years ago, # ^ | ← Rev. 7 →   0 I think you are having trouble with the base case.The formula you wrote there in the image is wrong. You are not considering all the cases. (a+ab >= k) is just the marker. here we know one b has to come to satisfy the min k ab's constraint.In base case we have to consider three things - expectation(of already present ab) it will simply 1*ab = ab expectation(ab's formed with already present a's and coming one b) it will be equal to 1*a = a expectation(of ab's formed with, one coming b and number of a's it brings with it). For the calculation of 3. we consider say it brings 0 a or 1 a with it or 2 a or n a, upto inf a's. we consider all these cases by the summation formula in my image. As 1 and 2 will always be the same irrespective of the number of a's the coming one b brings with it.summation formula = Here if the coming number of extra ab's formed will be equal to number of a's it brings with it.So, P(ab) = Pa*Pb and E(ab) = P(ab)*1 ,as 1 ab is formedP(aab) = Pa2*Pb and E(ab) = P(aab)*2 ,as 2 ab's are formed.similary you can compute upto inf and get the summation formula to generalize. Here, Pa = a/(a+b) , Pb = b/(a+b) , Pa = 1 — Pb
•  » » » » » 3 years ago, # ^ |   0 Thanks :) Got it!
 » 3 years ago, # |   +5 Can someone please provide a good explanation of problem E?
 » 3 years ago, # |   0 In problem D, in second base case, i  +  j  ≥  k, can some one explain the closed form of expectation?
•  » » 3 years ago, # ^ |   0 Check http://codeforces.com/blog/entry/56713?#comment-404349 and the image I posted in that thread above.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Nevermind, got it!
•  » » » » 3 years ago, # ^ |   0 Look at my comment and think carefully. Its in the same form.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 I will try to explain it:i => number of a's in the prefix,j => number of ab's in the prefix.and i+j >= K,so we can do like this:1) put 1 b in the end => number of ab is now (i+j) which is >= K so we stop and probability is (Pb/(Pa+Pb)) so we add (i+j)*(Pb/(Pa+Pb)) .2) put 1 a and then 1 b in the end => number of ab is now (i+j+1) which is >= K , so we stop and probability is (Pa/(Pa+Pb))*(Pb/(Pa+Pb)) so we add (i+j+1)*(Pa/(Pa+Pb))*(Pb/(Pa+Pb)).3)put 2 a and then 1 b in the end => number of ab is now (i+j+2) which is >= K , so we stop and probability is ((Pa/(Pa+Pb))^2)*(Pb/(Pa+Pb)) so we add (i+j+2)*((Pa/(Pa+Pb))^2)*(Pb/(Pa+Pb)).and so on..Now if we add these it becomes =>(i+j)*(Pb/(Pa+Pb)) + (i+j+1)*(Pa/(Pa+Pb))*Pb/(Pa+Pb)) + (i+j+2)*((Pa/(Pa+Pb))^2)*(Pb/(Pa+Pb)) + ...Let's leave as an exercise for you to solve this. Spoiler: answer is => i+j+Pa/Pb Hope this helps :)
•  » » » 3 years ago, # ^ |   0 Thanks, I got it from the picture and comment described in http://codeforces.com/blog/entry/56713?#comment-404349
•  » » » 3 years ago, # ^ |   0 Hi faceless_man =))) Can you explain me more about the line : "1) put 1 b in the end => number of ab is now (i+j) which is >= K so we stop and probability is (Pb/(Pa+Pb)) so we add (i+j)*(Pb/(Pa+Pb)) " Why when put 1b in the end => we add (i+j) * (Pb / (Pa+Pb)) instead of adding Pb / (Pa + Pb) . I can't find the reason for why (i+j) * ... ?? =))) Sory for my bad English =))
•  » » » 3 years ago, # ^ |   0 i have a question for i+j>=k if i=k and j=0 is this like aaaaaa(k times) and 0 'ab' if we put 1 'b' at the end it become aaaaa(k times)b why we can stop this if we only get one 'ab' but not at least k 'ab'?
 » 3 years ago, # |   0 Can anyone explain paragraph 5th of D'solution? I couldn't get it's idea
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   0 This is how i understand: we consider all satisfied subsequence, for each of them, calculate p = probality and x = number of 'ab' sequence, then our excepted number equal sum of product of all pair (p, x). So why can we ignore subsequences which is large or have 'b' continuously at the beginning?
•  » » » » 3 years ago, # ^ |   0 we are not ignoring the large subsequences. we are including that in the summation formula. also if you have b's in the beginning then number of ab's formed is zero since no a's are prior to those b's. so expectation = (probab of those b)*0 = 0, so we ignore that case.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I was wrong when asking ignore subsequences which have 'b' continuously at the beginning. i mean why can we ignore all continuously 'b' at the beginning of every sequence, as the editorial said that we can ignore them, or did i misunderstood the editorial?For example, probality of adding 'a' is 0.3, adding 'b' is 0.7, then for subsequence 'bab', p = 0.147 and x = 1. But if we ignore first 'b', we get p = 0,21, which change the anwser.
•  » » » » » » 3 years ago, # ^ |   +7 Oh you are confused over the word "ignored"our answer has to be Pbn * Pa * dp[1][0] for lets say n b's occurred before the first a.so generalizing this case for we can get 0 to inf number of b's before first a.we get ans = (Pb0 + Pb1 + Pb2 + ..) * Pa * dp[1][0]= = dp[1][0]
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't know why they didn't explain in the editorial like what you did. Ignore few explanations could make the editorial harder, when they can add them easily.
•  » » » » » » » » 3 years ago, # ^ |   0 Maybe because It was div1+div2 combined that's why.
•  » » » » » » » » » 3 years ago, # ^ |   0 Yeah, but at least D is still for div 2
•  » » » » » » » 3 years ago, # ^ |   0 Also, intuitively you can think that if you start the algorithm from beginning in all cases you will expect to have n b's and one a in some moment, thus the expected answer in all cases is dp[1][0], thus ans=dp[1][0] no matter how we weigh the cases.
 » 3 years ago, # |   0 Looking at number of solutions passed each task we could notice that A,B,C and too far from D,E,F. I think difficulty should reduce more.. gradually.
 » 3 years ago, # |   0 Can't Understand G. Anyone?
 » 3 years ago, # |   0 In Problem E, can someone explain me — by taking f(i) as a partitioning factor how can we get a partition of the bit positions?
•  » » 3 years ago, # ^ |   0 Elements with the same f value will belong in the same set in a particular partition.
 » 3 years ago, # |   0 Problem D.-Let dp[i][j] be the expected answer given that there are i subsequences of the form 'a' in the prefix and j subsequences of the form 'ab' in the prefix.-The answer should be dp[0][0].These two statements seem contradicting to me.
•  » » 3 years ago, # ^ |   +7 We are working backwards. We start our dp from known values which are dp[i][j] where i + j >= k, and the answer is in dp[1][0]. In state dp[i][j] we can add a letter 'a' with probability p and have expected value which is in dp[i + 1][j] or 'b' with probability (1 — p) and have expected value from dp[i][i + j].
•  » » 3 years ago, # ^ | ← Rev. 3 →   +7 You start with an empty string (that does not have any 'a' nor 'ab' occurrence)I think what may be troubling you is that the "base case" of this dynamic programming approach is not in the beginning, but in the end. (Sometimes the base case is i == 0 or j == 0, but here we have i+j >= k)
•  » » » 3 years ago, # ^ |   +1 Ok, I got it now.But still I think the definition of dp in the editorial is quite confusing. I suppose it would be more clear if explained as "answer we get if we start with a sequence containing i subsequences of the form 'a' and j of the form 'ab'". But maybe that's just my dullness.
 » 3 years ago, # |   0 Didn't know cards can have same indentity, which pay me 1 hack!
 » 3 years ago, # |   0 I have a solution to G with higher time complexity and I don't know how to make it better.Supposed X have len digit, we enumerate the first different digit i with X (notice the case that the first element is 0) , then we can use any number in the last len-i digit. It can be solved with f[a][b],g[a][b] which means we have filled the first b digit using 0~a,the sum and the count of it(Remember to consider the number we filled in fist i-1 digit).I have to pay len*10 in the part of enumerate , and used len^2*10 in dp , so the general time complexity is len^3*100 that can't pass the test cases :(Can anyone help me?My English isn't good and I may have many mistakes in my expreesion , sorry for it.
 » 3 years ago, # |   0 Problem H was nice and hard!
 » 3 years ago, # |   +3 in problem E, can someone explain to me what is the relation between: 1- when f(x) != f(y) therefore f(x) & f(y) will be 0. and 2- the good sets S correspond to the partitions of {1,2,...,m} ??
•  » » 3 years ago, # ^ |   0 Elements with the same f value belong in the same set in a particular partition
 » 3 years ago, # |   +1 I think I'm missing some concepts in order to fully understand problem D. Can anyone point me out where to look?In the first example, if we stop when we get the first 'ab' sub-sequence, how is it possible for expected value of the number of such sub-sequences be greater than 1 in the end?Thank you.
•  » » 3 years ago, # ^ |   0 For the first example, we could make a sequence like "aaab", which has 3 occurences of the subsequence "ab".
•  » » » 3 years ago, # ^ |   0 Ah, that's what message was about. Are these three exactly: "a**b", "*a*b" and "**ab"?Anyway, I think I've got it now. Thanks :)
 » 3 years ago, # |   0 Can someone give a brief description on solution of D. I read the editorial, but couldn't understand it....
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 Define dp[i][j] as they expected answer of se start problem algoritm with Amy position that has i a's and j ab's subsequences. Imagine you start the algorithm from one of these positions. In one case worth pa a's are incremented and in the other case worth pb ab's are incremented by i. So we know in both cases the new state thus the expected answer in them (asumming we have already computed dp with higher i,j) We just make a weigthed average of expected answer in both cases to reach dp[i][j] formula (case a worths pa, expected answer dp[i+1][j], case b worths pb, expected answer dp[i][i+j]. (See Wikipedia for weigthed average, it is an easy formula ) Base case and final case are very hard. Try to think them and ask if you are lost
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 thanks a lot..... i understood it a bit now. One query, why the final answer is dp[1][0] and not dp[0][0]??
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 dp[0][0] is defines as any starting position with only b's. dp[1][0] is any starting positions with a finite amount of b's and then an a. It can be proved mathematically dp[0][0]=dp[1][0] but I used intuitive aproach. When you start algorithm you have 0 b's thus expected answer must be dp[0][0]. However no matter your luck when you the algorithm in all scenarios you end in a moment with a finite amount of b's and an a (could be 0 b's). Thus in all cases expected answer should be dp[1][0]
•  » » » » » 3 years ago, # ^ |   0 okay... understood it now.. thanks
 » 3 years ago, # | ← Rev. 2 →   0 Hi! and Happy new Year to all. In problem E, I think to understand the editorial (most of it) but I don't get how all hypothesis claimed there implies a solution for the given problem. If someone would give me an example where this hypothesis are used. thanks
 » 3 years ago, # |   0 Can anyone please explain Problem G in details ? Codeforces editorial was a bit difficult to understand. Something about dynamic programming on digits...... I watched Endagorion's screencast of the same, but I couldn't understand properly.
 » 3 years ago, # |   0 for those who are having problem in understanding D : https://discuss.codechef.com/questions/120548/help-in-understanding-expectationAll the credits to John_smith :)
•  » » 3 years ago, # ^ |   0 Thanks, E(aaa)=E(aaaa)/2+E(aaab)/2 nice example explanation for understanding dp
•  » » » 3 years ago, # ^ |   0 yaah it's awesome ! ALl thanks to JOHN :)
•  » » » 3 years ago, # ^ |   0 btw did you have any good tutorial for centroid decomposition? If you have then please share!Happy coding :)
•  » » » » 3 years ago, # ^ |   0 currently don't have enough EXP to unlock that skill :(
 » 3 years ago, # |   0 Need some help for problem E. I understood it as letting fi=fj or fi*fj=0 for all i,j, thus counting the number of ways of partitioning {1,2...m}. But how are we take into account set T?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +17 so, basically, T is describing whether 2 elements can stay in the same set in the partition or not.for example, you are given T as (the same format as problem input): 01234567 -------- 11100000 10100111 10011111 01101111 And for example, you are now checking whether element 0 and 2 can be in the same set, then you retrieve their bits (just take the corresponding columns of the input matrix): 02 -- 11 11 10 01 now the third row is 1 and 0, meaning if 0 is taken, don't take 2 in the final partition.you will see that 2 elements can be in the same set iff their bits (columns) are the same.So you can group the elements with same bits together and calculate how many ways you can partition them.
 » 3 years ago, # |   0 Thank you for the great problems and quality editorials!Since I still have difficulty in understanding editorial of problem D, can I add one more question? Can you explain how i+j >= k can contribute to make sequence space closed ? For example, with k = 3, there are infinite i, j pairs. (3,0), (4, 0), (5, 0), and so on.
•  » » 3 years ago, # ^ |   +3 So for i + j >= k, if you get another 'b', you will stop. Now ignore the i and j.Suppose you get a 'b' with probability p each time, which corresponds to pb/(pa+pb) in the problem. Then the expected number of experiments you have to do to get a 'b' is 1/p.So i + j >= k the case where you can calculate the exact expected number.
•  » » » 3 years ago, # ^ |   0 To be honest, I am not clear with your statement "i + j >= k the case where you can calculate the exact expected number." Could you elaborate a little further on that point?
•  » » 3 years ago, # ^ |   +3 Let me answer my previous question as I understood. If i + j >= k, E(i, j) = i + j + Pa/Pb <== faceless_man showed how it is calculated. Though infinite i/j pairs satisfies i+j>=k, we want to have smaller number of base cases for the efficiency (which means smaller DP states to be calculated.) So, with k=3, (3,0), (2,1), (1, 2) are considered as the base cases, but (4,0), (2,2), (3,1), (1,3) are not.
 » 3 years ago, # |   +1 That D has to be one of the coolest DP problems I've seen. Seriously, compressing an infinitely long memoization matrix into finite size is sweet.
 » 3 years ago, # |   -8 I can't get G solution.Can somebody explain me the solution with more details?
•  » » 3 years ago, # ^ | ← Rev. 4 →   +3 You need to calculate this subproblem: solve n[i][j], which means the number of integers that is <= X and when sorted, has i-th digit >= j. (say, i starting from 0 and counting from the least significant digit)For example, let X = 22, and let's sort the numbers: 1 2 3 4 5 6 7 8 9 01 11 12 13 14 15 16 17 18 19 02 12 22 You will see that, n[1][1] = 10 {11,12,...,19, 12} and n[1][2] = 1 {22}.Suppose you have this subproblem solved, you can get the final answer by doing sum for i to be the length of the sequence and for j to be 1 to 9: (n[i][j] - n[i][j + 1]) * 10^(i) * j i.e. you reformulate the sum of the original problem, by doing it digit by digit.However, to calculate n[i][j] is not easy (I'm not sure). (this is similar to calculating bell numbers directly is not easy, you need a O(n^2) dp).So, you now turn to calculate dp[a][b][c] for a fixed digit j. The state represents that you have considered a digits, how many intergers <= X, when not sorted, have equal to or more than b occurrence of j, given that integer is still equal to X or not (c). (the same defined in the official solution)After solving that dp, n[i][j] = dp[0][i + 1][0]. (Since you have a number >= j on i-th index, then you must have at least i+1 digits that are >= j for that number)And to calculate dp[a][b][c], you will need: dp[a+1][b/b-1][0/1]. The boundary cases are when b = 0/ a = |len(X)|.Also, you must be careful about the multiplication and modulo.So you see this problem is not so direct. If this is your first-ish digit dp problem, don't worry. It is not easy to understand and you may want to first do some easier digit dp first. Also, you may notice that there is a common strategy for solving dp[a][b][c] (like, assuming whether you are getting a number < or == the given upperbound or so...).
 » 3 years ago, # |   0 Can someone read my solution of problem H and tell me the complexity? http://codeforces.com/contest/908/submission/33975786
 » 3 years ago, # |   +3 Can somebody explain me, how in problem D do we get 370000006 from 341/100 and 1e9+7? ... как взять дробь по модулю целого числа?
•  » » 3 years ago, # ^ |   +5 a / b = a * b^-1 ≡(mod m) a * b^-1 * b^φ(m) = a * b^(φ(m) - 1)For prime m latter is equal to a * b^(m - 2). It can be calculated using binary exponentiation.φ is called Euler function, b^-1 ≡(mod m) b^(φ(m) - 1) is called modular (multiplicative) inverse.
•  » » » 3 years ago, # ^ |   0 Thank you very much
 » 3 years ago, # |   0 What is the meaning of "the expected number of times 'ab' is a subsequence in the resulting sequence" in D?