Topcoder SRM 711
Time: 5:30 am EDT Saturday, March 25, 2017
Calendar: https://www.topcoder.com/community/events/
Update: we moved the SRM 1 week later (and the start time has been changed).
Topcoder SRM 711
Time: 5:30 am EDT Saturday, March 25, 2017
Calendar: https://www.topcoder.com/community/events/
Update: we moved the SRM 1 week later (and the start time has been changed).
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
It clashes with VK Cup 2017 — Round 1.
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 :)
They do not know about codeforces or deliberately ignoring it.
Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
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!
Contest will start in 17.5 hours.
Can someone please explain solution for Div1 500?
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
Try all possible lengths up to upper bound.
div2 medium, StringTransform:
Go from last character of t to first and check if this character appeared before in s.
div2 hard, TreeMovingDiv2:
Fix 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:
Check all possible starting positions of the block of consecutive ones.
div1 medium, OrderedProduct:
Calculate f[i] and d[i] -- number ways to represent N as product of i numbers >= 1 and >= 2 respectively.
div1 hard, TreeMoving:
Fix edge e(0). The calculate d[i][j] -- number of ways to choose e(1), e(2), ..., e(i) such that e(i) = j.
Does random generator ensure that we get correct trees in div2 hard?
Yup, this can be proven. Look at i-th tree as rooted tree with root at roots[i].
Will there be a full fledged editorial or do you think that hints are enough? :)
Arterm whats difference bw div1 and div2 hard 1000 pts.
you gave same soln
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.
Can you please explain the solution a bit more of div1 medium?
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)
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.
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...
I managed to make different samples in div2 hard and div1 hard, but copy-pasted the explanation. Sorry for that.
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 ?
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
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)
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.
FML
Please provide Div2 hard, TreeMovingDiv2 editorial with proper explaination. I am unable to understand after looking others solutions.
When will full editorial be published ?