xiaowuc1's blog

USACO 2017-2018 December Contest
By xiaowuc1, history, 7 years ago, In English

Hi all,

The first contest of the 2017-2018 USACO season will be running from December 15th to December 18th. Good luck to everyone as we start our season! Please wait until the contest is over for everyone before discussing problems here.

Update 1: The contest is now live!

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

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

How to register on this contest?

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

    if you make an account, you are automatically registered.

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

They say "pipe stdin / pipe stdout", but actually it's not. File names for Platinum :

  • Standing Out from the Herd : standingout.in / standingout.out
  • Push A Box : pushabox.in / pushabox.out
  • Greedy Gift Takers : greedy.in / greedy.out

It'd be great if someone share the filenames for other divisions too.

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

    This has been resolved.

    EDIT: I'm passing along a request from the contest admin, who would also like to request that for any sorts of technical issues, to contact directly as opposed to posting about them on social media. The admin isn't actively tracking all forms of social media where these issues might be discussed but will respond to any direct queries, and hopes that contestants who notice issues will escalate them properly so everyone can have a smooth contest.

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

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

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

UPD: found out

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

Is there a way to submit a solution after I have finished my window (to check if a solution is correct) or I must wait until the whole contest finishes?

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

    You need to wait until the entire contest is finished. However, you can still view the problem statements.

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

      Hey, can you post the link to the problem statements?

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

How to solve G2: Barn Painting?

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

    DP On Trees, DP[i][j] is how many diferent coloring can we generate in the subtree of i if we give i the color j , dp[i][j] *= (dp[x][(j+1)%3] + dp[x][(j+2)%3]) , x is a son of i, do this for every x son of i, take care of the nodes who already have a color. Code

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

      I have a question about how already colored nodes are handled.

      For example, if node 6 is a leaf node that is colored 2

      According to your code I think something like this would happen:

      (changed to 1-based index for simplicity)

      dp[1][6] = 1 dp[2][6] = 1 dp[3][6] = 1

      Wouldn't it conceptually make sense that

      dp[1][6] = 0 dp[2][6] = 1 dp[3][6] = 0

      For some reason the above one seems to work even though it doesn't make much sense

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

        if c[6] == 2 , then "if(c[x] !=i && c[x] != -1)" guarantee that dp[1][6] = dp[3][6] = 0 , am i missing something here?

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

          Thanks, you are right. I wrote a very similar code but am getting WA. I am trying to find out how our codes differ.

          Edit: Found the bug. I spend 3 hours looking for some type of logic error but it turns out I just wrote '&' instead of '%'. I guess the smallest things count :P

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

    Here's my Java solution for reference as well.

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

How to solve Platinum P3. Greedy?

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

    Simply binary search on the first cow which does not get a gift.

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

    Find a prefix such that each cow in that prefix will enter the queue inside the prefix. If this happens all remaining cows will not reach the front of the queue. You need to find such smallest prefix. I solved it in O(n log n) because I use max-segment tree but it can be solved with two sweeps in O(n) I believe.

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

      Alternatively, you can find this prefix by noticing that two cows jumping to position i are as good as a cow jumping to position i and a cow jumping to position i - 1.

      So you can create a set with all positions {0, ..., n - 1}, and then go through the cows one by one, for each cow removing the last position no greater then n - 1 - ci. Once you remove 0 you have found such a prefix. (Because if you removed positions 0 through k - 1 and not k, you have k cows in your prefix all jumping to a position less than k.)

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

How to solve Plat 1 ?

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

    Suffix Array + LCP Array

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

      Can you elaborate?

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

        I used hashing to sort the suffixes. Link

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

          I am completely speechless that this actually works.

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

            What's wrong with this approach?

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

              I guess it would be better to say "in awe" :)

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

                Do you mean it's too slow? Computers are pretty fast, right?

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

                  No, not at all. I mean I'm surprised that I've never seen anyone implement it like this before! It's really great.

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

                  So ekzhang, how did you solve this problem?

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

                  @vb7401: I used O(N log N) suffix array and LCP array.

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

    I have a solution with suffix automaton.

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

      Can you elaborate?

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

        I also has automaton solution. First you build automaton for string s_1 + 0 + s_2 + 1 + ... + s_n + (n — 1)

        Now for each vertex you want to know if there is only 1 number labeled edge reachable from it not using number labeled edges. If yes all string corresponding to this vertex are unique for that word.

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

When will editorial be out? Edit: Editorial is out

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

How to solve Plat. 2 ?

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

    DP[X][Y][4] — is cell (X,Y) reachable from B if the player was last is one of the 4 adjacent cells. Then the transition can be done by seeing if we can push the box to the four directions (cells of type (X+dirx[p],Y+diry[p])). That's possible if from the current player's cell we can reach cell (X-dirx[p],Y-diry[p]) without stepping on the cell with the box (cell (X, Y)). Well this is equivalent to checking if these two cells are in the same biconnected component (I'm not sure if that's the correct name, but I mean components such that by removing each vertex the component remains connected). During the contest I wasn't able to pass the problem as I implement Tarjan's algorithm in a wrong way, but I'm almost certain this solution should work.

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

      That was what I tried too, I tried to use block-cut tree to check if it is possible to reach but, unhappily I received MLE (Maybe the implementation was wrong)

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

      I used block-cut tree and it worked perfectly :)

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

      actually checking if you can go from a node to another without passing through a particular node can be done with a simple dfs tree(http://wcipeg.com/problem/coi06p2). (I ragequit after getting a WA so if something sounds wrong please tell me)

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

      AC on Cases 1-4 for "pushabox"

      My observation is that if a box is not at an articulation point, Bessie can move to any side of it, given that the side is not a '#' character; however, if the box is an articulation point, two sides must be in the same biconnected component if Bessie were to travel between them. Is this observation incorrect, or is my implementation faulty in some way?

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

    Could somebody please explain why bridge tree / finding 2-edge connected components isn't sufficient for solving this problem?

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

Anyone have any idea when the results will be announced?

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

    "The USACO December 2017 contest has just ended. Results are being tabulated and will be posted soon." — On the front page as of now.

    I assume that means within a day.

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

      Historically, it has been a bit longer. Closer to 4-7 days.

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

        Huh, you're right.

        Seems like usaco "soon" is not codeforces "soon"

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

          Results are up. But why is there not complete results for Platinum? They have always released complete results except for Open round...

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

            What do you mean complete results. Do you mean it only shows contestants >=750?

            I'm not sure why they changed format, you can email bcdean@clemson.edu for these questions.

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

              Usually they release scores of all pre-college Platinum contestants in monthly contest. This time they only release result of top scorers, or >= 628

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

            Has anyone emailed USACO asking what is up with the new score displaying?

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

To anyone who hasn't seen it yet, you can now check your rank in the contest by logging in to usaco.org and going to the December 2017 contest page.

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

Why does USACO consider the last submission to find the result? I got a good score first and then made some changes and score reduced and the time got over. I didn't know they checked as per the last submission. :(

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

Pretty sure I just failed by a one line bug

→ Reply