xiaowuc1's blog

By xiaowuc1, 4 years ago, In English

Hi all,

The first contest of the 2020-2021 USACO season will be running from December 18th to December 21st this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! There are new changes to how USACO contests are run — the most notable change is that I/O is no longer done via files. Please consult the official rules for all the changes.

Edit 2: Although the contest window is almost over, please do not discuss the contest until everyone has finished it. The contest window should close four hours after it officially ends since folks who join at the last minute purportedly still get a full window, in which case the contest ends at this time.

Edit 3: The contest is officially over — hope everyone enjoyed the contest! Results should hopefully be ready by the end of the week.

Edit 4: Results are out!

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

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What time zone are the dates on the website referring to? I saw EST mentioned somewhere on the website, but that wasn't specifically talking about the contest.

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

    The contest page will have the exact rules, but I think that it's typically the most permissive possible bounds; the start time will be December 18th 00:00 UTC+13, and the end time will be December 21st 23:59 UTC-12, or something like that.

»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Looking forward to some more COWVID puns!

»
4 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Thank you xiaowuc1

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

The contest window should close four hours after it officially ends since folks who join at the last minute purportedly still get a full window, in which case the contest ends at this time.

The contest closes Dec 21 at 23:59 UTC-12 time (even if your personal clock is still running at that time, so do not wait until the very last minute to start!).

Explicitly not according to new usaco rules. I'm curious if anyone has ever done this (previous year or this year) and can confirm it was ever the case. I wouldn't be surprised if they never impl to actually cut it off tho :clown:

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I'm now doing it!

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

      The contest window was just closed. Don't ask me why I know that, I was kicked out.

      Hope you are well :(

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

Can someone explain the solutions to the platinum problems?

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

so is the contest over or not yet?

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

    Yes it is

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      ok i was curious about the solution to the second silver problem the one about subsets

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

        I also was not able to solve it. I solved the other 2 the graph one and the transitivity one but wasn't able to solve this question.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          me too but i didnt proof the graph one tho

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Here's the solution to Silver 2:

        Sort the points by x-coordinate.

        The first observation to note is that a rectangle is a contiguous range of x and y coordinates, so it will be a contiguous segment in our array (now that it's sorted).

        Brute force the leftmost and rightmost points in the subset. It is easy to see that none of these groups overlap, and they cover all possible subsets. Now you can disregard any points with an x coordinate out of the range that they cover. Because you are putting the endpoints of the current range in the current subset for sure, all of those points that are within them must be taken with the current subset. However, you have a choice to take all of the points above them and below them (but within their x-coordinate range). You can choose anyone of the points above their range, and any one of the points below their range and extend the y-coordinates of the rectangle so that they are covered. Therefore, the answer for some fixed x-coordinate bounds is:

        $$$(1+numberofpointshigher)*(1+numberofpointslower)$$$.

        Here is my accepted code.

        Let me know if you have any questions.

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

The contest is officially over as just now the contest window got over.

Can we discuss now?

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

    Anyone have a java solution for Bronze #3 that works for all cases?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      hint:sort the cows looking to the north by their x value , and the others by their y value

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

        It was my first time in USACO so I entered bronze division. I just did normal brute force no sorting needed lol. I think your solution has a better time complexity as mine is around $$$O(N^3)$$$. But anyways, constraints were very small.

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

      It was a greedy solution. We sort the North ones on basis of x co-ordinates and East ones on basis of their y coordinate.

      Now we can see that iterate in North ones and for every North direction, I iterate in East ones.

      I find the expected point of meeting and checked whether it was possible for me to block a cow or not. If yes I updated the value and continued traversing further

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

        can u give me your code for this problem?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Code Here
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Does anyone know the solutions to the Gold problems?

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When will we be able to upsolve the problems?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Usually the results come out Thursday-Friday (ish). After that, the problems will be open to upsolve.

    UPD: Results are out early!

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

some experienced person please predict the ratings of the silver problems...

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

    My very rough guess would be 1400, 1800, 1700.

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Can someone please explain the solution to cowmistry platinum? Thanks.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +47 Vote: I do not like it

    So the xor problem right? Basically just simulate the process of going down a trie of the binary representation with 3 paths at the same time, keeping which pairs have xor smaller than K for sure (I did this with a submask of 3 bits).

    Then realize this is sort of small-to-large in the splitting points and when you split for the second time you'll have a path that's already smaller than K in pairwise xor in both pairs, in this case you can take any value below this node and solve for only 2 paths (actually whenever a path is smaller than K for sure with the others, just do this to reduce the number of paths).

    Also treat nodes that have all possibilites under it as some special node that you're able to use 0 or 1 in any way (but still keep the xor pair information).

    This with memoization using a map was enough for the complete problem and it's probably barely hackable but if I use some unordered map it should be way faster. Also this can be coded without the memoization at all but implementation seemed too hard for me. Probably the intended solution is easier to code though.

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

How do you solve gold problem 3? I have a hashing solution that was too slow (and had some collisions).

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    You can use XOR-hash, note that order doesn't matter and points can't be repeated, so assigning a random integer to each point and for hashing elements, just use xor of their random values, with 64-bits integers the probablility of colision is really low, and you can use a vector instead of a set to count the number of differents and improve the algorithm, however the constraints allow to do it without optimizations.

    You need to fix $$$L$$$ and $$$R$$$, and then insert to the set the hashes of every square of size $$$R - L + 1$$$ with its left edge equal to $$$L$$$ and its right edge equal to $$$R$$$, to do this you can do a sweep line/sliding window over the y-axis, in total you will only consider $$$O(N^3)$$$ squares if you fix each pair of $$$L$$$'s and $$$R$$$'s.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I've noticed that mt19937 doesn't work on USACO. It compiles, but gives the verdict Runtime Error or Memory Limit Exceeded. Is there any good alternative for random number generation? (rand isn't a good enough generator)

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I just use srand(time(null)) and normal rand(), and for 64 bit integers ( (long long) rand() & (INT_MAX) ) * INT_MAX + rand()

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

      If anyone is interested, here's my implementation using this approach: link

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    For some reason, I can't see top scorers for both the Bronze and Silver Divisions. Does anyone know why that's the case?

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Why there's only results for top scorers?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Presumably so people don't get angry about camp selection, ie other factors, most importantly grade level, come into play when selecting the finalist camp. However you should be able to see your exact place number among all pre-college students (which I'm assuming you are, but probably same is similar for college+) in the paragraph above where it shows the contest problems.

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

      Why aren't there any results for the Bronze and Silver Divisions? I can see them for the Gold and Platinum divisions though...

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

does anyone have a working code for gold 2's subtask 2?even though the editorial explained the dp,I still find it difficult to implement the main dp