### cgy4ever's blog

By cgy4ever, history, 3 years ago, ,

Hi there,

Topcoder SRM 698 will start in about 9 hours (Sept 17, 12:00 noon EDT).

Thanks for participating! The Div1-Medium and Hard were prepared to be used in TCO Round 3B, but shangjingbo told me they are too easy (he got the idea for each of them in 10 minutes). It turns out they are not that easy. :P

• +120

 » 3 years ago, # |   -28 wow! SRM after CF round
 » 3 years ago, # |   +19 Let me be the first one. How to solve Div1 Hard?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +56 spoiler
•  » » » 3 years ago, # ^ |   -10 let's spoil it :)
•  » » » 3 years ago, # ^ |   +23 I still don't follow. Can you explain further?
•  » » » » 3 years ago, # ^ |   +5 I think there is one detail not obvious at first: 2-SAT solution may choose, for example, pieces like this: ##. .## ... ... ### ... + ... + #.. + ..# = #.# ... ... #.. ..# #.# which is not a good shape, so one might think this solution is not really correct, but actually it doesn't matter because in every such case the resulting "bad" shape contains a good sub-shape, so if there is a solution with some "bad" shapes, then there is also a solution where all shapes are good.
•  » » » » » 3 years ago, # ^ |   +5 Thanks, that's the part I hadn't understood.
 » 3 years ago, # |   +5 Anyone please explain the approach of Div2 hard...
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 SolutionLet's the solve task indepently for all the bits. The answer will be (2^0 * ) + (2^1 * ) + ...So, we can reduce our task. Now, we must solve the following task: the vertexes of the tree are marked with "0" or "1" and we must count number of subtrees that has "1". How can we solve it? We can calculate the number of subtrees that has only "0" and subtract it from total number of subtrees.So, let's calculate the total number of subtrees. Use dp[i] that means the numbers of subtrees with root i. The answer will be dp[0] + ... + dp[n-1]. How to calc it: dp[i] = 1; // if it's a leaf dp[i] = dp[v0] * d[v1] * d[v2] * ...; //v0, v1, v2 ... are the children of i And how to count the number of subtrees that has only "0"? We can just remove all the "1" vertexes and get some trees. Then, count the total number of the subtrees for all of them and add them.
•  » » » 3 years ago, # ^ |   +5 Really elegant and clever, Thanks ! :)
•  » » 3 years ago, # ^ |   +14 We can solve the problem for each bit, and then sum them up. For each bit, it becomes: compute the number of subtrees such that at least one node has weight 1. It equals to: (number of all subtree) — (number of subtree that all nodes has weight 0). Both can be solved by tree DP.
•  » » » 3 years ago, # ^ |   +5 Great ! Thanks =)
 » 3 years ago, # |   0 Div2 Hard ?
 » 3 years ago, # |   +5 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 3 years ago, # |   +10 Lol, because someone got an idea in 10 minutes for that problem you put significantly easier problem on TCO xD. And hard looks pretty unsolvable during that time (just first impression). It has some flow flavor in its looks, but dunno.
•  » » 3 years ago, # ^ |   0 Yes, this Hard is not ideal: if you don't have a template for 2-SAT, then it will be too hard to code it in time. And it is vulnerable to bruteforce search.
 » 3 years ago, # |   +8 Hints for Div1 500?
•  » » 3 years ago, # ^ |   +6 Good pairs = all pairs — bad pairs.Pair is bad if at least one of sets has <3 points or if they form two legit polygons that have no intersection.
•  » » » 3 years ago, # ^ |   +1 Figured out this much. Can't figure out how to find the total number of possible non-intersecting pairs of polygons. Thanks for the help though!
•  » » » » 3 years ago, # ^ |   +11 So now think how we can count legit nonintersecting polygonal. They can be separated by a line. It would be good to make that line unique.
 » 3 years ago, # |   +15 Nice Contest :)
 » 3 years ago, # |   +13
 » 3 years ago, # |   +27 SRM 698 Div 1 250 — linkSRM 497 Div 2 1000 — link
 » 3 years ago, # |   +5 I haven't been able to participate in recent matches since hackerrank stopped showing SRM in it's calendar. What are other alternatives? How do you remember contests?
•  » » 3 years ago, # ^ |   +8 Visit clist.by
 » 3 years ago, # |   0 I cannot find the editorial.How to solve the problem RepeatString?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Break the string in two parts(there n-1 ways to it) and find it's LCS. Answer will be 2 * maximum of all those LCS.Complexity -> O(n^3)Code
•  » » » 3 years ago, # ^ |   0 Is it possible to use here Minimum Edit Distance algorithm?The description of the algorithm looks suspiciously similar to the problem description. At least the algorithm supports the same kind of operations: insertion, deletion and substitution.