Анонсирован VK Cup 2018! Регистрация уже идет! Приглашаем ознакомиться с информацией о Чемпионате на его странице. ×

### Блог пользователя lewin

Автор lewin, 2 месяца назад, ,

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
Разбор задач Good Bye 2017

•
• +336
•

 » 2 месяца назад, # |   +60 kudos to a lightening fast editorial!
 » 2 месяца назад, # |   +11 Is there any way to interpret E as a vector space or group or something like that?
•  » » 2 месяца назад, # ^ | ← 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)
•  » » » 2 месяца назад, # ^ |   +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).
•  » » » » 2 месяца назад, # ^ |   +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).
•  » » » 2 месяца назад, # ^ |   +16 I think the term you are looking for is "Sigma Algebra".
•  » » » » 2 месяца назад, # ^ |   +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
•  » » » » » 2 месяца назад, # ^ | ← 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".
•  » » » » 2 месяца назад, # ^ |   +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.
•  » » » » » 2 месяца назад, # ^ | ← 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
 » 2 месяца назад, # |   +53 maths too hard~~
 » 2 месяца назад, # |   +2 Codeforces is becoming awesome day by day :D
 » 2 месяца назад, # |   +2 Editorial even before system testing finished, amazing punctuality grandmaster.
 » 2 месяца назад, # |   +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
•  » » 2 месяца назад, # ^ |   +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 :)
•  » » » 2 месяца назад, # ^ |   +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!
•  » » 2 месяца назад, # ^ |   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 :(
•  » » » 2 месяца назад, # ^ |   +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); } ``````
•  » » » » 2 месяца назад, # ^ |   +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?
•  » » » » » 2 месяца назад, # ^ | ← 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 :)
•  » » » » » » 2 месяца назад, # ^ |   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?
•  » » » » » » » 2 месяца назад, # ^ | ← 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.
•  » » » » » » » » 2 месяца назад, # ^ |   0 Doesn't it always handle complete tripartite graphs correctly?
•  » » » » » » » 2 месяца назад, # ^ |   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?
•  » » » » » 2 месяца назад, # ^ |   +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...
•  » » » » » » 2 месяца назад, # ^ |   +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!
•  » » 2 месяца назад, # ^ |   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?
•  » » » 2 месяца назад, # ^ |   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.
•  » » » » 2 месяца назад, # ^ |   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.
 » 2 месяца назад, # |   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
 » 2 месяца назад, # |   0 WOW! Thank you so much for super fast Editorial and also for the awesome problems !
 » 2 месяца назад, # |   0 Whoohh such a fast editorial!!!!!!!!
 » 2 месяца назад, # |   +11 F was a Div2C question. I wonder why the authors kept it at F :(
 » 2 месяца назад, # | ← 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
•  » » 2 месяца назад, # ^ |   +3 Use the spoiler tag to share code or put your submission link, please.
•  » » » 2 месяца назад, # ^ |   -18
•  » » 2 месяца назад, # ^ |   +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.
•  » » » 2 месяца назад, # ^ |   -21
 » 2 месяца назад, # |   0 can anyone please help in understanding the dp transition in D.
 » 2 месяца назад, # |   +21 goodbye rating
•  » » 2 месяца назад, # ^ | ← Rev. 2 →   0 dude you solved 4 question on one go. you shouldn't be saying this :P
•  » » » 2 месяца назад, # ^ |   0 but the problem D had cost most of my time during the contest. :( Anyway the problems are good, yet I'm foolish.
 » 2 месяца назад, # |   0 Problems blew my mind, great contest-great problems.
 » 2 месяца назад, # |   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?
•  » » 2 месяца назад, # ^ |   +1 You want to find the highest y+dy overall, not the highest y (and then + the dy of that).
•  » » » 2 месяца назад, # ^ | ← 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.
•  » » » » 2 месяца назад, # ^ | ← 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.
•  » » » » 2 месяца назад, # ^ |   +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.
•  » » » 2 месяца назад, # ^ |   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!
 » 2 месяца назад, # |   +6 Light-speed Tutorial,Light-speed System Test! I like it!
 » 2 месяца назад, # |   +6 Editorial before Final testing. So fast. (y)
 » 2 месяца назад, # |   +1 Editorials before system testing. That's a perfect goodbye to 2017 (*-*)
 » 2 месяца назад, # |   +4 Great problems and a fast, nice, and concise editorial. Great Job!
 » 2 месяца назад, # |   0 There is a slight formatting error with the bell number link. (Extra right bracket at the end)
 » 2 месяца назад, # |   0 Thanks for good contest!
 » 2 месяца назад, # |   0 In Problem D Can somebody please explain why infinite length sequence is not necessary for "exact answer" ?
•  » » 2 месяца назад, # ^ |   +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.
•  » » 2 месяца назад, # ^ | ← 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.
•  » » » 2 месяца назад, # ^ | ← 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
•  » » » » 2 месяца назад, # ^ |   0 This is correct!!
•  » » » » » 2 месяца назад, # ^ |   -7 yeah but i didn't realise for a long time that i need to subtract 1 :))).But yeah,now it's corect :))
•  » » » » 2 месяца назад, # ^ |   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.
•  » » » » » 2 месяца назад, # ^ |   +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
•  » » » » » » 2 месяца назад, # ^ |   0 here p is probability to get 'ab' ?
•  » » » » » » » 2 месяца назад, # ^ | ← Rev. 2 →   0 no,p is probability to put bso pb/(pa + pb)
•  » » » 2 месяца назад, # ^ |   0 I wonder how to prove this formula..
•  » » » » 2 месяца назад, # ^ |   +3
•  » » » » » 2 месяца назад, # ^ |   0 Thanks
•  » » » 7 недель назад, # ^ |   0 Why we need to use DP if the answer to the problem is `(1-p)/p`? I can not understand it at all.
•  » » » » 7 недель назад, # ^ |   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.
 » 2 месяца назад, # | ← 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)
•  » » 2 месяца назад, # ^ |   +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.
•  » » » 2 месяца назад, # ^ |   0 Makes sense, thanks.
 » 2 месяца назад, # |   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
•  » » 2 месяца назад, # ^ |   0 I haven't seen ur code but you have to check from c-r-r to c+r+r
•  » » » 2 месяца назад, # ^ |   0 why is it? range of the outermost points of the circle colliding should be [c-r,c+r] right?
•  » » » » 7 недель назад, # ^ |   0 The center of the circle it collides with is another r distance away
•  » » » » » 7 недель назад, # ^ |   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.
•  » » 2 месяца назад, # ^ |   +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.
•  » » » 2 месяца назад, # ^ |   0 yes, that might be the case. I should have taken the max over all. :( Thanks.
 » 2 месяца назад, # |   0 Will there be an editorial in Russian?
•  » » 2 месяца назад, # ^ |   +2 You can use Chrome and then translate automaticaly all the page
 » 2 месяца назад, # |   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.
 » 2 месяца назад, # | ← 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?
 » 2 месяца назад, # |   +10 Thanks for the contest :) was really fun ^^ and thank you for the fast editorial! srsly.
•  » » 2 месяца назад, # ^ |   0 And wow kudos for the solution in multiple language!!
 » 2 месяца назад, # |   0 what is wrong in my solution for problem C the link is here.
•  » » 2 месяца назад, # ^ |   0 Figured out :D Thanx for the comment bmerry
 » 2 месяца назад, # |   0 Editorial has appear faster than ratings. Hm....
 » 2 месяца назад, # |   +14 I can't get D solution. Could somebody explain the solution with more detail?
•  » » 2 месяца назад, # ^ |   0 Finally I've got it! solution coded directly from formula 33810491
 » 2 месяца назад, # |   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.
•  » » 2 месяца назад, # ^ |   0 Got it.
 » 2 месяца назад, # | ← 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
•  » » 2 месяца назад, # ^ |   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
 » 2 месяца назад, # |   +20 dotorya solved G at 00:49:58 before bmerry
•  » » 2 месяца назад, # ^ |   +20 Oops, thanks for catching this.
 » 2 месяца назад, # | ← 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.
•  » » 2 месяца назад, # ^ |   +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).
 » 2 месяца назад, # |   +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?
•  » » 2 месяца назад, # ^ |   +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.
•  » » » 2 месяца назад, # ^ |   0 So what happens with sequences like "bab.." or "bbbaab.."? Don't we count them in the answer?
•  » » » » 2 месяца назад, # ^ | ← 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].
 » 2 месяца назад, # |   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 `b`s then an `ab`, can this be the case?Please help me understand the problem.
 » 2 месяца назад, # |   +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?
•  » » 2 месяца назад, # ^ | ← 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 get`dp[0][0] = dp[1][0]`
•  » » » 2 месяца назад, # ^ |   +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"?
•  » » » » 2 месяца назад, # ^ | ← 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.
•  » » » 2 месяца назад, # ^ |   +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?
 » 2 месяца назад, # |   +5 When will the ratings be updated ?
 » 2 месяца назад, # | ← 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.
•  » » 2 месяца назад, # ^ |   0 Keep this if (ab >= k) condition above second one so that it is checked earlier
•  » » » 2 месяца назад, # ^ |   0 But its useless. if you have ab>=k then a+ab>=k is already satisfied. so it never executes.
•  » » » » 2 месяца назад, # ^ |   0 Yes we can avoid that
 » 2 месяца назад, # | ← Rev. 2 →   +19 Problem G can be solved in O(102n).
•  » » 2 месяца назад, # ^ |   0 Well what do `one` and `cnt` mean in your code? Would you please explain it a little bit? Thanks a lot.
•  » » » 2 месяца назад, # ^ |   +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, .
•  » » » » 2 месяца назад, # ^ |   0 Got it. Thanks. But what does means? Is it a typo?
 » 2 месяца назад, # | ← 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
•  » » 2 месяца назад, # ^ |   +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.
•  » » » 7 недель назад, # ^ |   0 Understood..Thanks a lot!!
 » 2 месяца назад, # | ← 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)
•  » » 2 месяца назад, # ^ | ← Rev. 2 →   0 https://imagebin.ca/v/3mS1m1CZVCff You mean this?
•  » » » 2 месяца назад, # ^ | ← 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?
•  » » » » 2 месяца назад, # ^ | ← 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
•  » » » » » 2 месяца назад, # ^ |   0 Thanks :) Got it!
 » 2 месяца назад, # |   +5 Can someone please provide a good explanation of problem E?
 » 2 месяца назад, # |   0 In problem D, in second base case, i  +  j  ≥  k, can some one explain the closed form of expectation?
•  » » 2 месяца назад, # ^ |   0 Check http://codeforces.com/blog/entry/56713?#comment-404349 and the image I posted in that thread above.
•  » » » 2 месяца назад, # ^ | ← Rev. 2 →   0 Nevermind, got it!
•  » » » » 2 месяца назад, # ^ |   0 Look at my comment and think carefully. Its in the same form.
•  » » 2 месяца назад, # ^ | ← 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 :)
•  » » » 2 месяца назад, # ^ |   0 Thanks, I got it from the picture and comment described in http://codeforces.com/blog/entry/56713?#comment-404349
•  » » » 7 недель назад, # ^ |   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 =))
•  » » » 6 недель назад, # ^ |   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'?
 » 2 месяца назад, # |   0 Can anyone explain paragraph 5th of D'solution? I couldn't get it's idea
•  » » 2 месяца назад, # ^ |   0
•  » » » 2 месяца назад, # ^ |   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?
•  » » » » 2 месяца назад, # ^ |   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.
•  » » » » » 2 месяца назад, # ^ | ← 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.
•  » » » » » » 2 месяца назад, # ^ |   +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]
•  » » » » » » » 2 месяца назад, # ^ | ← 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.
•  » » » » » » » » 2 месяца назад, # ^ |   0 Maybe because It was div1+div2 combined that's why.
•  » » » » » » » » » 2 месяца назад, # ^ |   0 Yeah, but at least D is still for div 2
•  » » » » » » » 2 месяца назад, # ^ |   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.
 » 2 месяца назад, # |   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.
 » 2 месяца назад, # |   0 Can't Understand G. Anyone?
 » 2 месяца назад, # |   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?
•  » » 2 месяца назад, # ^ |   0 Elements with the same f value will belong in the same set in a particular partition.
 » 2 месяца назад, # |   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.
•  » » 2 месяца назад, # ^ |   +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].
•  » » 2 месяца назад, # ^ | ← 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)
•  » » » 2 месяца назад, # ^ |   +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.
 » 2 месяца назад, # |   0 Didn't know cards can have same indentity, which pay me 1 hack!
 » 2 месяца назад, # |   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.
 » 2 месяца назад, # |   0 Problem H was nice and hard!
 » 2 месяца назад, # |   +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} ??
•  » » 2 месяца назад, # ^ |   0 Elements with the same f value belong in the same set in a particular partition
 » 2 месяца назад, # |   +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.
•  » » 2 месяца назад, # ^ |   0 For the first example, we could make a sequence like "aaab", which has 3 occurences of the subsequence "ab".
•  » » » 2 месяца назад, # ^ |   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 :)
 » 2 месяца назад, # |   0 Can someone give a brief description on solution of D. I read the editorial, but couldn't understand it....
•  » » 2 месяца назад, # ^ | ← 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
•  » » » 7 недель назад, # ^ | ← 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]??
•  » » » » 7 недель назад, # ^ | ← 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]
•  » » » » » 7 недель назад, # ^ |   0 okay... understood it now.. thanks
 » 2 месяца назад, # | ← 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
 » 2 месяца назад, # |   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.
 » 7 недель назад, # |   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 :)
•  » » 7 недель назад, # ^ |   0 Thanks, E(aaa)=E(aaaa)/2+E(aaab)/2 nice example explanation for understanding dp
•  » » » 7 недель назад, # ^ |   0 yaah it's awesome ! ALl thanks to JOHN :)
•  » » » 7 недель назад, # ^ |   0 btw did you have any good tutorial for centroid decomposition? If you have then please share!Happy coding :)
•  » » » » 7 недель назад, # ^ |   0 currently don't have enough EXP to unlock that skill :(
 » 7 недель назад, # |   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?
•  » » 7 недель назад, # ^ | ← 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.
 » 7 недель назад, # |   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.
•  » » 7 недель назад, # ^ |   +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.
•  » » » 7 недель назад, # ^ |   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?
•  » » 7 недель назад, # ^ |   +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.
 » 7 недель назад, # |   +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.
 » 7 недель назад, # |   -8 I can't get G solution.Can somebody explain me the solution with more details?
•  » » 7 недель назад, # ^ | ← 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...).
 » 7 недель назад, # |   0 Can someone read my solution of problem H and tell me the complexity? http://codeforces.com/contest/908/submission/33975786
 » 7 недель назад, # |   +3 Can somebody explain me, how in problem D do we get 370000006 from 341/100 and 1e9+7? ... как взять дробь по модулю целого числа?
•  » » 6 недель назад, # ^ |   +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.
•  » » » 6 недель назад, # ^ |   0 Thank you very much
 » 3 недели назад, # |   0 What is the meaning of "the expected number of times 'ab' is a subsequence in the resulting sequence" in D?