### I_love_tigersugar's blog

By I_love_tigersugar, 5 years ago, ,

Tomorrow, the next SRM will be held at 07:00 EDT. Don't miss!

Have a nice SRM. Good luck :D

• +54

 » 5 years ago, # |   +19 7 AM SRM Makes me regret Choosing STEM
 » 5 years ago, # | ← Rev. 3 →   +1 Can anyone tell me how to solve div1 500? Looks rather tricky for me.I've seen several solutions, but still haven't got the whole idea. UPD: OMG, second problem in last few weeks in which there's such "shortest-distance" graph is constructed and I don't manage to understand that the cycles can be only of length 2. Hopefully, I won't forget it next time.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The number of connected components depends on the number of cycles. It can be proved that there exist only cycles between 2 vertices. Hence, we can reduce the problem into calculating the expected number of cycles between 2 vertices.
•  » » » 5 years ago, # ^ |   0 calculating the expected number of cycles between 2 vertices. I got this far, but how to solve this kind of problem?
•  » » » » 5 years ago, # ^ |   +11 For each vertex you can sort other vertices by priority (first distance, then y coordinate, then x).Then for each pair of vertices you want rabbits to NOT be in the cells that have higher priority compared to the picked vertices in at least one of the list.If there are n places for rabbits, r rabbits and e cells must be empty, the chance for that is C(n - e - 2, r - 2) / C(n, r) (two picked cells are already occupied by rabbits, which leads to minus 2). Add this chance to ans for each pair.That's O(n^6), not sure if it's quick enough, as I didn't implement it during the contest :c
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 but the problem said the graph is undirected, so the cycles are edges between two points or not?
•  » » 5 years ago, # ^ |   +24 A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees. Therefore number of components is equal to the number of cycles of size two.Expectation of this value is equal to sum of probabilities for every two empty cells of grid to form a 2-cycle. Two points form a 2-cycle iff no point is closer to the first point than the second, and vice versa; so, all points must lie outside some set. The probability for this is Csr - 2 / Cpr, where s is size of the set, p is number of empty cells.
•  » » » 5 years ago, # ^ |   +34 Congratulations for the victory!
•  » » » » 5 years ago, # ^ |   +52 Thanks.
•  » » » 5 years ago, # ^ |   -14 There exist people who denote Newton's symbol using that weird notation with Cij :OO!
•  » » » » 5 years ago, # ^ |   +27 This notation is widespread in Russia.
•  » » » 5 years ago, # ^ |   0 "A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees.". What if the connected component is a cycle of size 3, like 1 -> 2 and 2 -> 3 and 3 -> 1? It does not contain cycle of size 2.
 » 5 years ago, # |   +21 Hmm, 1000 didn't seem tricky or really hard to me this time (meet in the middle), I wonder if the fails were due to TLE on constant/log factor...
•  » » 5 years ago, # ^ | ← Rev. 2 →   +16 I think so too. If you had implemented it, you'd see that the time limit was very tight.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +16 I did implement it actually, but didn't manage to debug it in time :D(and now, I'm getting Uncaught exception in the practice room on something that should totally pass: an assignment in an existing map memlimit exceeded — speaking of which, didn't TC use to report memlimit exceeded specifically?)
•  » » 5 years ago, # ^ |   0 Yes, there were not enough time for me to make one simple optimization. And that's why my solution failed during contest
 » 5 years ago, # | ← Rev. 2 →   +17 I was never able to solve the task 250 in regular DIV 1 (I solved some in TCO) during contest, but today I solved the task 500 :D
•  » » 5 years ago, # ^ |   0 But in SRM 635 you was able to earn 0 points but increase your rating, that looks strange :o
•  » » » 5 years ago, # ^ |   0 Yeah, and not only my rating increased. It's pretty funny. Do nothing and earn points. :D Nowise it does not give much satisfaction, at least not me. I prefer well-deserved successes.
•  » » » » 5 years ago, # ^ |   0 Well, rating systems can act weird in unexpected situations (in this case, tricky 250). How much did you gain exactly?In a sense, you did well by not losing points :D
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I gained 4. xDAnd several contests ago in TCO 2A I gained 81 (also doing nothing), but then I was grey.
•  » » » » » » 5 years ago, # ^ |   0 Well yes, a grey user isn't really expected to get to round 2, so it's normal to gain rating just by being there.Getting +4 is like nothing at all... so it's not really a fail, I guess.
•  » » » » » » » 5 years ago, # ^ |   +7 And in rounds 3A and 3B even some yellow users increased their ratings with 0 — take a look at olpetOdessaONU:)
•  » » » » 5 years ago, # ^ |   0 It's always better try, than do nothing :)
 » 5 years ago, # |   0 can somebody explain, how to solve div2 1000?
•  » » 5 years ago, # ^ |   +3 Binary search the lower bound of the minimum sum of the 16 sub-rectangles brute force the 3 vertical cuts greedily pick the horizontal cuts in order to exceed the lower bound total complexity O(n^4 log n) .. using pre-calculated partial 2D sums
•  » » » 5 years ago, # ^ |   0 Oh, I got it now, thanks!