### cgy4ever's blog

By cgy4ever, history, 3 years ago, ,

Topcoder SRM 711

Update: we moved the SRM 1 week later (and the start time has been changed).

• +47

 » 3 years ago, # |   +11 It clashes with VK Cup 2017 — Round 1.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 It is interesting to me how this kind of keeps happening. It seems like <5min of work when scheduling rounds to check Codeforces, and a few big annual contests like FBHC and GCJ and make sure there is no time conflict. But I suppose we can rely on dedicated volunteers like you to point it out :)
•  » » » 3 years ago, # ^ |   +5
 » 3 years ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 3 years ago, # |   +2 I've started Data Science Weekly Challenges series for competitors in Algorithm and Marathon tracks. SRM 711 is the chance to jump in the first challenge — the lowest-rated person who will get a bye to Stage 2 of Algorithm Competition will get a TCO'17 t-shirt!
 » 3 years ago, # |   +73 Contest will start in 17.5 hours.
 » 3 years ago, # |   +14 Can someone please explain solution for Div1 500?
 » 3 years ago, # |   +46 Hello, I was the writer of this round. This time we tried to make problems easier than usual. May be div1-hard should be more challenging. What do you think? Here's short hints:div2 easy, SquareMaking hintTry all possible lengths up to upper bound.div2 medium, StringTransform: hintGo from last character of t to first and check if this character appeared before in s. div2 hard, TreeMovingDiv2: hintFix edge e(0). The calculate d[i][j] -- number of ways to choose e(1), e(2), ..., e(i) such that e(i) = j.div1 easy, ConsecutiveOnes: hintCheck all possible starting positions of the block of consecutive ones. div1 medium, OrderedProduct: hintCalculate f[i] and d[i] -- number ways to represent N as product of i numbers >= 1 and >= 2 respectively.div1 hard, TreeMoving: hintFix edge e(0). The calculate d[i][j] -- number of ways to choose e(1), e(2), ..., e(i) such that e(i) = j.
•  » » 3 years ago, # ^ |   -13 Does random generator ensure that we get correct trees in div2 hard?
•  » » » 3 years ago, # ^ |   0 Yup, this can be proven. Look at i-th tree as rooted tree with root at roots[i].
•  » » » » 3 years ago, # ^ |   0 Will there be a full fledged editorial or do you think that hints are enough? :)
•  » » 3 years ago, # ^ |   -8 Arterm whats difference bw div1 and div2 hard 1000 pts.you gave same soln
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -6 In div2 hard n and m up to 50, which allows O(mn^3) solutions.In div1 hard n and m up to 500, intended solutions works in O(mn^2) and O(mn^2 \log n). Unfortunately, some O(mn^3) managed to pass too.
•  » » 3 years ago, # ^ |   +5 Can you please explain the solution a bit more of div1 medium?
•  » » » 3 years ago, # ^ |   +15 contains_one(int n): number of sequences of length n with at least one one with product X, greater_one(int n): number of sequences of length n with each element greater than one with product X.To calculate contains_one go over amount of ones (we should take at least one): contains_one(n) = sum(i = 1..n-1) choose(i, n) * greater_one(n-i) greater_one(n) = total(n) — contains_one(n)total(n): number of sequences of length n with product X (no restrictions on elements). To calculate total(n) we iterate exponents and assign primes[i] independently, hence: total(n) = product(i) choose(a[i], a[i]+n-1) Result is sum of greater_one(i)
 » 3 years ago, # |   -52 Come on guys, I don't remember when was the last time I solved any TC problem faster than today's Div1 500. It deserves to be 250 pts at most xd.
 » 3 years ago, # |   +4 I take some time to investigate where is wrong in my input parser of Div.1 Hard. And Finally find the wrong thing is the explaining of example...
•  » » 3 years ago, # ^ |   +15 I managed to make different samples in div2 hard and div1 hard, but copy-pasted the explanation. Sorry for that.
 » 3 years ago, # |   0 In Div2 Hard if try removing every edge that is not a bridge in the resulting graph after adding removed edge from previous tree to calculate dp. Is this method correct ?
 » 3 years ago, # | ← Rev. 2 →   0 For Div 2 hard, I used the recurrence F(i, j, k) =number of valid ways using the first i trees,selecting edge number j from last tree ,and edge k picked from tree m - 1 (to maintain cyclic property). I start this recurrence by calling solve() trying and removing each edge related to tree m - 1 one at a time, and going to tree 0. This procedure is followed for each tree thereon recursively. However, on sample 3 I get WA. Am I doing something wrong ? Code
 » 3 years ago, # |   +23 If we code bruteforce for Div1Hard it will perform n^3 operations "add constant on a path in tree", however random path in a random tree is very short. Were there tests to cause such solutions to get TLE? I think it may be impossible to create them, but it is also sad if such solutions passed (I didn't investigate that)
•  » » 3 years ago, # ^ |   +10 You can interchange flowers (graphs of diameter 2) and bamboos. This should cause TL for such solutions. I though about that only after the contest, that's sad.
 » 3 years ago, # |   +29 FML
 » 3 years ago, # |   +6 Please provide Div2 hard, TreeMovingDiv2 editorial with proper explaination. I am unable to understand after looking others solutions.
•  » » 3 years ago, # ^ |   0 The editorial here can help https://www.topcoder.com/blog/single-round-match-711-editorials/
 » 3 years ago, # |   +11 When will full editorial be published ?
•  » » 3 years ago, # ^ |   0