Блог пользователя xiaowuc1

Автор xiaowuc1, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How I can register on contest? usaco.org?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Contest should be over. Can anyone confirm?

  • »
    »
    5 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Vector hashing and unordered map works fine for 11/11

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone please post the platinum division problems here?

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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...

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You use LCA. Code

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +42 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

      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}

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :))

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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".

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    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).