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

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

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.

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

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

we should start preparing the contest lol

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

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

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

    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.

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

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

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

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

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

    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.

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

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

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

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

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

I believe the contest has ended, can anybody confirm?

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

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

»
5 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится
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

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

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
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    My method for plat 1 was slightly different:

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

    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

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

    Thank you for the solutions!

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

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

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

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

Solutions and results are available.

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

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.

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

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?

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

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

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

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

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

        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$$$?

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

          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!

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

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

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

    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.