Блог пользователя cgy4ever

Topcoder SRM 716
Автор cgy4ever, история, 7 лет назад, По-английски

SRM 716 will start in 1 day,

Time: 9:00 pm EDT Monday, June 26, 2017

Calendar: https://www.topcoder.com/community/events/

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Isn't it on Monday?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Could you tell me the time in EEST time zone?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there a good reason to allow registrations only in the half hour just before the contest?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve div. 1 hard?

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +76 Проголосовать: не нравится

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.

→ Ответить
»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Solution for Div2 Hard?

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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)

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить