cgy4ever's blog

Topcoder SRM 716
By cgy4ever, history, 7 years ago, In English

SRM 716 will start in 1 day,

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

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

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it on Monday?

→ Reply
»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Could you tell me the time in EEST time zone?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve div. 1 hard?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +76 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Solution for Div2 Hard?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      Can you please explain this part again?

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply