brycesandlund's blog

2018 North Central North America ACM-ICPC Regional
By brycesandlund, history, 6 years ago, In English

The 2018 North Central North America ACM-ICPC Regional Programming Contest is tomorrow, Saturday November 3rd, 4pm UTC. There is an open division for anyone interested in competing at: https://open.kattis.com/contests/ncna18open. The official scoreboard will be at https://ncna18.kattis.com/.

As there is no way to request or issue clarifications in the open division of Kattis, please comment here if any questions arise.

The problem set was created by myself, Alexander Scheel, xennygrimmato, NibNalin, vlyubin, Joshua Guerin, Kathleen Ericson, David Poplawski, and erena. Additional thanks to asdoc, xiaowuc1, and y0105w49 for problem solutions.

EDIT: This is happening in about three hours.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by brycesandlund (previous revision, new revision, compare).

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

This year’s problem set is nice! Though I got no idea for the two hardest problems.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Was there a solution for D not based on max flow? Also ideas for the two hardest ones?

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

    You can actually observe that from a day to the next day, if for any airport i, the number of people currently at airport i is larger than or equal to the sum of the number of people that the flights leaving airport i requires, then that day is optimal. So you can just do simulation for each day in this way.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    Pokegene: Sort the genome strings and create a tree. Reduce the problem to a series of LCA queries.

    New Salaries: Come up with a general formula for [Li, Ri], [Lj, Rj] where Li ≤ Lj ≤ Ri ≤ Rj (the case where Ri ≤ Lj instead is easy). For a fixed i,  you can compute the sum of expected damages over all relevant j with prefix sum queries.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +14 Vote: I do not like it

    More details about Pokegene:

    If you sort the set of strings in a query, the possible answer ancestors are a prefix of L consecutive strings from this set.

    With this observation, you can see that the solution is the sum of the length of the LCPs(longest common prefix) of L sized windows of the sorted set. Now, there are multiple ways to calculate the LCP length for each window, using LCA in trie, hashing+binary search, auxiliary tree etc.

    For the LCA in trie approach, notice that the LCP of strings indexed (x, ... x + L - 1) can be found from the LCA of the x th and x + L - 1 th string end nodes in the trie.

    There are a couple of edge cases to figure out about strings that are proper prefixes of other strings in the set, but they are relatively trivial.

    brycesandlund and I expected this to get more ACs, but I hope everyone still enjoyed the problem. :)

    EDIT: This was my first time problem-setting, so let me know if you have any comments or feedback about the problem.

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

How to solve Problem G Tima goes to Xentopia?

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

    Dijkstra! Make a graph with k1*k2 layers. Add an edge from one layer to another to take a red or blue edge. White edges keep you in the same layer.

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

    Alternatively, dijkstra with state[i][j][k] = t being the min time it takes to arrive at i after using j red and k blue edges.

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

When will the solution slides be posted?

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

    You know, I wasn’t sure people really looked at them last year so I wasn’t sure I was going to make them at all this year. You’re not the first person to ask, though, so I am going to put some solution sketches online. I think I’m going to make them more like what’s been done for the world finals. I can get get them up tomorrow.

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

      Sweet thanks, btw (random digression) I looked the solution slides for last year's contest a while ago, and they were helpful.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Actually students from UW-Madison are using the slides last year. I am one of the coach this year and I think some solution sketches will be really helpful, so I am glad to hear you are making it. Thank you!

      P.S. Is there another way to solve "New Salaries" without coming up a general formula for the intersecting intervals?

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

        See above. You do need to come up with a formula for two intersecting intervals. This formula can be made to work for all pairs in linear time by maintaining appropriate running sums.

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

          Ok. Thank you! I see the sketches and they are really helpful!

          → Reply