xiaowuc1's blog

USACO 2018-2019 First Contest
By xiaowuc1, history, 6 years ago, In English

Hi all,

The first contest of the 2018-2019 USACO season will be running from December 14th to December 17th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

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

Comments Comments (53)
| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

To organizers: could you also publish the duration of the contest beforehand? I guess it will be 3 or 4 hours?

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

How I can register on contest? usaco.org?

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

    Just make an account on the website. Then you will be automatically “registered” and can start your 4 hour block any time during the weekend.

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

Does anyone know the solution to Gold Problem 1 (Fine Dining)?

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

    The contest isn't over for like 2 and a half more days.

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

    Contest rules prohibit the discussion of contest problems until the 4 day larger contest window is over. After the contest has finished, the problem setters will post an editorial for each question which usually comes with a C++ and/or Java solution.

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

    What I did was modified Dijkstra. First, run normal Dijkstra from node N calculating dist[i]. Then do multi-source Dijkstra pushing all special nodes to priority queue with initial dist dist[i] — t if i is special and infinity otherwise (go from n to i and eat there) Let's call dist2[] the produced array. Then for each node we output 1 iff dist[i] >= dist[2].

    Code here

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

Contest should be over. Can anyone confirm?

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

    Yes, the contest is over.
    UPD: But it will be completely over at 16:00 UTC.

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

    People can't start the contest now, but some could still be doing it. I think everyone will be finished 30 minutes before the end of CF round 527.

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

now that it's over, did anyone get gold #2?

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

    I got 8/11, but the 10/11 is the same idea. Not sure although if it's ended, someone may be participating now.

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

I believe we may discuss now (12/18/2018 16:31 UTC). Can anyone confirm?

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

My solution to P2 in Gold division was inclusion-exclusion. So the answer for one person will be constructed in the following way: Add people who have the same ice-cream flavors as the current person, delete the people who have the same 2-ice-cream flavors, add the people with the same 3-ice-cream flavors, delete the people with the same 4-ice-cream flavors and finally add the ones who have the same 5-ice-cream flavors. Obviously this is done by bitmasks in 2^5 * n * logn( if you use map to store the vectors).This is a 8/11 solution. You can sort the entire array and this will work faster and you will get 10/11. I know that this can be somehow optimised by hashing the vectors or using trie, but may be there is a more beautiful solution. Here is the 10/11 solution of my friend babin. He also used parsing for input but it's not necessary.

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

    Vector hashing and unordered map works fine for 11/11

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

      Well how did you use unordered_map? for c++11 it doesn't work, or you wrote it by hand, not as c++ STL? Also i tried hashing but it didn't work, i think they had strong tests and i needed some kind of elegant hashing.

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

        Just write a vector hashing class and use it like this:

        unordered_map<vector<int>, int, hasher> m;
        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You can use unordered_map instead of map, but you need to write vector hasher(because you can't use vector as key of unordered_map).
    For example, you can use sum of elements of a vector as vector hash. (Yes, different vectors can have same hash, but you just need to minimize number of collisions).
    I got 11/11. My code.
    Sorry for my bad english.

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

      Ok thanks, but i am not sure how the sum of the vectors got 11/11 xd, it's kind of too weak. I tried to hash by multiplying the digits of each number in the vector to the power of some prime, and it didn't work :D.

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

Can someone please post the platinum division problems here?

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

Did someone manage to get P1 Platinum? I'm curious as to what ideas did you have.

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

    It turns out that the optimal solution is given by taking the convex hull of the points (i, ri) for each 0 ≤ i ≤ N + 1. This is pretty intuitive; if we can get an expected value of A at a certain point and B at another point then the recurrence should allow us to achieve at the midpoint, and repeatedly taking midpoints should give us the line. Now just running the convex hull algorithm and sweeping through the points gives the right answer.

    Unfortunately, I used long doubles to store my answer which isn't precise enough (you have to store everything as a long long and divide at the very end, apparently). I think this happened to a few others as well.

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

    Is there a way to solve this problem without seeing the convex hull? I tried using the idea that your decision is fixed at each location, no matter how you got to a location, you are always going to jump off or continue. However, I was unable to link this to convex hull, and ended up not solving this.

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

      You use that fact along with solving it for taking l and r. The points between l and r will be taken from the segment between points (l, a[l]) and (r, a[r]). From this, you should be able to see that the optimal answer is the convex hull.

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

      Technically you can solve it without noticing the Convex Hull as I was able to get 11/11 without it. However my algorithm provably calculates the convex hull in a terrible manner, but with enough optimizations I got it down.

      I doubt there is an intended solution that doesn't hinge on the convex hull even if you prove it without mentioning a convex hull.

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

How do we solve Plat P3? I coded something with LCA but only managed to grab 7/15, rest Wrong answer.

upd: found my stupid bug...

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

    You use LCA. Code

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

      Hmm, I did the same thing as you. Guess I must have messed something up with the implementation. Thanks!

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

      I think your solution (and many others) fail on the test:

      4 3
1 2
1 3
1 4
2 3
3 4
4 2

      Answer should be all 0s?

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

        You're right. Is there an easy way to fix this?

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

          I haven't looked carefully, but it's likely that the only case when your solution is wrong is when the answer is 0 for every node. However, it can be checked in O(n) whether there exists some root that works by repeatedly removing legal nodes.

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

          Perhaps the way to deal with the possibility of this case is to construct a graph with the m pairs of cows as edges, and checking if there are any cycles.

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

    After some thought, I reduced the problem to finding which nodes could be the root of the tree, without violating the following condition: for every pair (A, B), B can't be in the subtree of A. This is because, in order for any node v to leave, all of its sub-tree must leave first. This is also the reason why, if you consider any node as the root, this will be the last one to leave. To do this, root the tree in node 1 (or any other one, doesn't really matter), and, for each pair (A, B), do the following: If B isn't in the subtree of A, then any node in the subtree of A CAN'T be the root. Otherwise, let's name K as the first node in the path from A to B. In this case, all nodes that aren't in the subtree of K CAN'T be the root node (I managed to prove these, but it is a little tedious and requires a little more thought). Finally, if you assume that at first, all nodes can be the root node, and process each pair one by one, in each pair eliminating all nodes that CAN'T be the root (with a Segment Tree + Lazy, after linearizing the tree with a post/pre-order traversal), you get an algorithm that works in O ( M lg N ). Code

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

      Actually your solution is wrong. It passed because of weak tests.

      Your code will fail on the case:

      5 2
1 2
2 3
1 4
4 5
2 5
4 3

      Answer should be all zero.

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

What was the solution to P2 Platinum? I thought that the solution was finding the Kth lexographically largest longest increasing sequence.

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

    I think it was finding the kth lexicographically smallest complement of a LIS, which is not the same thing.

    Consider the sequence: 3 5 4 1 2

    All the longest increasing subsequences:

    3 5 (Complement: 4 1 2)

    3 4 (Complement: 5 1 2)

    1 2 (Complement: 3 5 4)

    The greatest (3rd smallest) LIS is 3 5. The smallest (3rd greatest) complement of an LIS is 3 5 4.

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

      The 3rd largest LIS is 1 2, and its complement, the 3rd smallest complement is 3 5 4. If I'm not mistaken, computing the Kth largest LIS should be the same as computing the Kth smallest complement. Anyways, what is the algorithm for solving this? I tried using a segment tree, but my algorithm completely failed.

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

      But if the sets are sorted in increasing order, it becomes

      3 5 (Complement: 1, 2, 4)

      3 4 (Complement: 1, 2, 5)

      1 2 (Complement: 3, 4, 5)

      Now the smallest (or 3rd greatest) complement is {1, 2, 4}

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

P1 silver was an oof for me :( Did not consider the binary search solution during contest at all.

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

    I understand you. :( I'm my case I got Silver P1 rather quickly but P2 killed me even when I had the right approach, but could not find a bug in my program and after I fell asleep for the rest of the contest (oops). Hope we're better prepared for the january contest.

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

So it seems the data for P3 platinum was rather weak. Consider the testcase at the bottom (excuse my blurry phone camera). You can interpret an arc a → b as meaning 'a must go after b' (I think it was the other way around in the statement, sorry about that). Then if we root the tree at the highest vertex the answer will be 'impossible', because this means orienting all edges downward, and this will introduce a cycle. In particular, the solution 'if a needs to go after b, then discard all vertices in a subtree of b not containing a' fails on this test. Notice that when you root at the highest vertex, this vertex is never contained in such a subtree. Yet from what I understand this solution passes all tests

I'm curious to know what the intended solution was (hopefully this wasn't the intended solution). I thought of the above approach early on and quickly dismissed it since one can pretty quickly arrive at the counterexample below. It's a bit frustrating to then see that this would get you all points, as in life there is nothing more important than winning and collecting virtual points.

Here is the testcase corresponding to the picture. You should get 0 for all vertices:

7 3

1 2
2 3
1 4
4 5
1 6
6 7

2 5
4 7
6 3

Picture of the testcase: https://i.imgur.com/kNiWbSa.jpg

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

    The same story for me, this case made me wonder whether any LCA approach would have any chance to pass. An easier case would be as stated earlier:

    4 3
1 2
1 3
1 4
2 3
3 4
4 2

    To be honest I wonder whether just checking at the end whether an arbitrary node with answer 1 works and if not discarding all 1 nodes solves the issue.

    P.S.: Please, resize the picture :))

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

      P.S.: Please, resize the picture :))

      Can this be done in Markdown? I’m on my phone so don’t really have access to any editing tools. EDIT: Ok, I just replaced it w/ a link.

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

As some of the more impatient contestants, myself and eyg made this Google Form to tabulate preliminary results from the CF Community.

One can view the spreadsheet with sorted results here (it updates every few minutes with the most recent entries from the form).

If there are any issues, please comment below.

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

Results are out at http://usaco.org/index.php?page=dec18results!

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

Did they added tests to P3 Platinum? Becuase I am pretty sure during the contest I passed all the tests but now in the ranking it appears that I have the last 2 tests with "Wrong answer".

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

    Yes. From the result page:

    Note that the coaches decided to add some extra test cases to the last problem before computing final scores, since the original test data was not as exhaustive as hoped (recall that as per our rules, the coaches can always add or remove test cases prior to final grading if needed, so you should always test your code thoroughly and not assume it will earn perfect marks just because it solves the test cases present in the contest itself).

    → Reply