xiaowuc1's blog

USACO 2019-2020 Second Contest
By xiaowuc1, 5 years ago, In English

Hi all,

The second contest of the 2019-2020 USACO season will be running from January 17th to January 20th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! Please do not spoil anything about the contest publicly until the contest is over for everyone, and please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here.

Edit 2: Due to a configuration error, the contest is running for 12 more hours than originally stated. The contest window is still open, please wait for the window to expire at 4:00 AM UTC on January 22nd before discussing.

Edit 3: Results can be found here.

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

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

we should start preparing the contest lol

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

For all others who cannot joke about the USACO contests ( yet:) )

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

    Quality

    These problems are way easier than the actual USACO. Last year I got full score on the mock Gold contest but I only got 300 in the actual contest.

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

      I mean, that doesn't mean that the quality of problems is bad. Also in general I find it helpful to mock things that are one level higher than what I am currently in (e.g. Plat if I'm in Gold currently).

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

I am not sure if the contest is over but how to solve second problem from platinum?

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

    While the contest should technically be closed (it is past 4:00 am in UTC-12 time), the page for the contest is still open (this might be due to an issue on part of the contest organizers), so it is safer to not yet discuss.

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

      Yeah, please refrain from discussing until 11:00 pm eastern time (12 hours later than normal).

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

is silver cutoff gonna be like 600? everyone says it was super hard lol

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

    discussion is not allowed yet, just wait for until the time Benq mentioned above to discuss

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

I believe the contest has ended, can anybody confirm?

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

Does anyone know how to solve the second gold problem, my solution was n^2 but got MLE.

→ Reply
»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it
Cave
Nondec O(nk^3+qk^2)
Nondec O(nk^2+qk)

For P3 I have a bad solution which fortunately passes due to low constraints.

Screencast

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

Gold P3 is Balkan 2011 Trapezoid I think. Maybe that's why P1 is named "Time is Mooney"

Anyway, very short spoilers:

plat 1
plat 2
plat 3
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    My method for plat 1 was slightly different:

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

    Did not realize the equivalence of Gold P3 and Trapezoids. :| Admittedly, it didn't seem particularly original.

    For Plat 2 my $$$O(nk^2+qk^2\log n)$$$ solution with segment tree passes $$$q=10^5$$$, not sure whether you can pass $$$q=2\cdot 10^5$$$ with this?

    For Plat 3 we added some cases with large hulls which made one of our $$$O(n^2)$$$ solutions TLE, but apparently this didn't suffice.

    Solutions

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

    Thank you for the solutions!

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

Where can I see the all questions before the results come out (when would that be, though?), given the contest has now ended ?

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

http://usaco.org/index.php?page=jan20results

Solutions and results are available.

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

For Silver Wormholes, I thought of using DSU ( Union Find ). Sort all edges in decreasing order of weights, and then after connecting each edge in this order, check if now all cows can sort themselves. So, I thought, let's view given array as permutation. Then we consider the index $$$i$$$ as value $$$i+n$$$. And then check whether each $$$i$$$ can reach $$$i+n$$$, but this is obviously TLE. How to do it faster? I have this feeling that there is a much easier approach.

My code.

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

For Silver problem "loan", does anyone have a proof for the correctness of binary search solution?

I had to do a lot of math to prove it. Did I miss anything?

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

    What's wrong with the analysis? (aside from the "mlik" typo, I don't think anyone proofread this >:( )

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

      I think it can be rather difficult to prove the correctness of binary search. It's easy to guess but hard to prove.

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

        Oops, I misunderstood. Suppose that $$$X_1<X_2.$$$ Isn't it easy to show that if $$$A\le B$$$, then $$$A-\max\left(M,\lfloor \frac{A}{X_1}\rfloor\right)\le B-\max(M,\lfloor \frac{B}{X_2}\rfloor)$$$ since $$$f(x)=x-\max(M,\lfloor \frac{x}{X_1}\rfloor)$$$ is monotonically increasing with $$$x$$$?

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

          Oh, I didn't notice that monotonicity. I tried to prove $$$LHS - RHS \leq 0$$$ and break it into several cases because of $$$\max$$$ and $$$ \operatorname{floor}$$$ function. That needs lots of work. Thanks!

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

Can someone explain the maxmatch concept in the official USACO solution for the Silver loans problem? (line 11 onward in Nick's code)

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

    You can verify (with a bit of math) that $$$\lfloor \frac{N-G}{X}\rfloor=Y$$$ remains the same after $$$t=\lfloor\frac{N-G-XY}{Y}\rfloor$$$ days (meaning that we subtract $$$Y$$$ from $$$N$$$ exactly $$$t+1$$$ times). After subtracting $$$t+1$$$ times, then $$$N-G<XY$$$, so $$$\lfloor \frac{N-G}{X}\rfloor$$$ has changed.

    → Reply