square1001's blog

TCO Wildcard Round / Fun SRM / They collides with RCC online mirror
By square1001, 7 years ago, In English

Topcoder Open 2017 Wildcard Round and Fun SRM will start in 5.5 hours!

Informations

  • If you're not qualified the Regional Rounds, you can only participate in Fun SRM.
  • You can compete with login in topcoder and go to https://arena.topcoder.com .
  • The registeration phase starts at 16:00 MSK. Pay attention that registeration phase ends in 5 minutes.
  • The contest starts at 19:00 MSK (thanks flashmt).
  • The both contests are rated.
  • The difficulty of the contest is likely to be Div 1.5 (or maybe higher but also maybe not) of normal SRM.
  • Topcoder doesn't reveal who the writer is, but this is Wildcard Round, so probably the writer is some red coder(s).

Sadly, it collides with RCC online mirror, but you can choose which contest you will participate.
Good luck and have fun, and also let's discuss after the contest!
  • Vote: I like it
  • +13
  • Vote: I do not like it

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

Friendly suggestion: please post the contest time as a link so that people can check their local time easily.

Sunday September 10 2017 at 12:00 (UTC -4)

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

Div 1.5 for round that gives direct qualification to TCO finals? I don't think so. Regionals are very easy, but I do not expect wildcard round to be easier than typical SRM.

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

How solve 900?

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

    Lets first fix number of changes day->night and night->day. After that we have following problem:

    1. We have k phases
    2. On each phase any number of items can be visited
    3. phase we visit a[i] should be <= phase we visit b[i]
    4. visiting each item on each phase have some cost (never mind, they are many equal, we will not use it).

    Such problem can be solved using maxflow-mincut, in following network. Vertex is pair of (item, phase), where day varies from 0 to k inclusive, also source s, and sink t. Following edges:

    1. (x, d) -> (x, d + 1) with capacity cost of item x on day d (stands for visiting x on day d, if in mincut)
    2. s -> (x, 0) with capacity inf (stands for nobondy is visited before day 0)
    3. (x, k) -> t with capacity inf (stands for everybody is visited after day (k — 1))
    4. (a[i], k) -> (b[i], k) with capacity inf (stangs for "if a[i] is not visited before day k, then b[i] is not visited too"

    mincut in this network have exactly one cut on each line (x, *) — this is number of day to visit item x. infinite edges make this solution always valid.

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

    Let's fix the type of the first attraction (day or night), the number of dayToNight, and the number of nightToDay. There are 2n possibilities. For example, if we start with day, dayToNight = 2, and nightToDay = 1, we are interested in sequences of the form "day, ..., day, night, ..., night, day, ..., day, night, ..., night".

    Now, let's assign an integer between 0 and 3, inclusive, for each attraction. 0 and 2 means day and 1 and 3 means night, so for example, if we assign 2 to attraction i, it costs day[i]. We want to minimize the sum of these costs under the constraint that for each i, the number assigned to b[i] must be greater than or equal to the number assigned to a[i]. This can be reduced to a mincut problem.

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

Does anyone know where I can find these contests in Practice Rooms?

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

How to solve 450?

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

    Select one vertex, let's call it root. Group all vertices into three sets by distance from the root mod 3. In the smallest of those sets, choose one vertex and connect all other vertices in the set to it. Also, connect one vertex at distance 2 from the root, if any, to the root. That's it. To see why this is enough, notice that the distance between any vertex in the graph and some vertex in the smallest group is always at most 2, and the distance between any two vertices in the smallest group is also at most 2.

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

      ...or just connect all the vertices in the smallest group to the root.

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

        I know this works. But I don't understand why it works ?

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

          Which part of it?

          Imagine any spanning tree, with root at the top. We group the vertices by the distance from root mod 3, and connect all the vertices from one of those groups to root. Then, as drinkless said, from any vertex you have to go at most 2 levels up to reach a vertex from the selected group or root. So, you only need 3 edges to get from any vertex to root.

          If you choose the smallest group, you will add at most n/3 edges.

          → Reply