SRM 716 will start in 1 day,
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 14:22:17 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Isn't it on Monday?
Thanks for notice, fixed.
Could you tell me the time in EEST time zone?
Is there a good reason to allow registrations only in the half hour just before the contest?
I believe it is actually 4 hours.
How to solve div. 1 hard?
My construction works for k = 2412 and p = 4, giving a bound of 6412 which is only 3 less than the requirement.
Denote the interval [a,b) = [a,b-1]. Then for each n a multiple of 6, take the following intervals but only if they lie in [0,n-1].
[c,c+2), [c,c+3), [c,c+4), [c,c+5)
[c-2,i), [c-3,c), [c-4,c), [c-5,c)
[c,c+6), [c,c+12), [c,c+24), [c,c+48), [c,c+96), [c,c+192), [c,c+384), [c,c+768)
Then each interval is the union of at most one interval from the first line, one from the second line, and two from the third line. Because of MAGIC, there are exactly 2412 of these.
This specific construction gives more than k = 2412 for any other value of 6.
Solution for Div2 Hard?
Firstly, use a O(n^3) floyed algorthim to calculate the distance between each pair of nodes. Next, we use a O(n^2) DFS or queue to check each node whether it can be visited. Finally, for two nodes that both of them can be vsited, use an array to save the distance between them. The whole time complexity is O(n^3). Of course, if you use something else to calculate LCA instead of the floyed algorthim you can get a O(n^2) or a O(n^2*logn) algorithm. (And that maybe the solution for div1 medium)
Can you please explain this part again?
We firstly add node 0 into the queue. And then for each node that was added into the queue, we check if other nodes can been visited through this node. If another node can be visited, then we add it into the queue. Each node can been mostly added into the queue once, so the complexity is O(n^2).
Given graph is a tree. So every node can be visited from another node. So whats the point of checking for connectivity?
Are you using given S list for checking or for visiting?. If so how?
We check if other nodes can been visited through this node by using the length in the given S, in other word, if we can move from u to v.
Now I got. Thanks! Could you give a link to your code?
https://arena.topcoder.com/#/u/viewCode/16931/56404/2/330258/Tommyr7/contest
Thanks again. I found the solution here:http://felix-halim.net/tc/index.php?rd=16931
Congratulations on your win.
Thanks a lot!
You can also use a greedy strategy as follows.
First compute distance of every node from the root, also in the same dfs keep calculating the maximum height of each subtree.
Also keep a set of all the nodes at the same level sorted by their height (and also keep their indexes by using pair) in ascending order.
Repeat this process for every node.
Then to find the answer, initialize curr with 0.
As the query comes to move to distance x, then for the curr node as root, find the minimum height at the level x( for which we have maintained a set) and then set curr = that node and repeat this process for whole s, if at any point there is no element at level x for the curr root then the ans is Impossible else its possible.