xiaowuc1's blog

By xiaowuc1, 6 weeks ago, In English

Hi all,

The final contest of the 2020-2021 USACO season will be running this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

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

»
6 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

Good luck to all!

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I think the contest is over right? How did you all do?

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

    I don't think we can discuss that right now, we can discuss scores and problem questions when the USACO website tells us that the contest and over and it shows the solutions for the problems.

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

      When I posted the comment, the USACO website already said that "the contest is over and they are compiling the results".

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve the geometry problem from Gold?

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

    I think it’s dp right? I didn’t manage to get it during the test tho.

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

      yes, it's dp.

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

        Could you pls share code or somethn?

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

            If I haven't misinterpreted, the above solution is O(n^5), here is an O(n^4) solution: Code

            The solution does some math to speed up the transitions by a dimension, though it actually doesn't run that much faster than O(n^5) solutions. This is probably because the transitions are more complicated. If I knew O(n^5) would've passed I would've coded that instead :/

            Shoutout to Benq for setting easier problems :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you think 730 would be able to qualify for plat?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide link to the problems for practice, since I am not able to find the link to the problems of US open on the USACO website.

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

    I think it’s temporarily unavailable because they are still calculating the result. It probably will be open again after a few days and you can find it under “contest”.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +76 Vote: I do not like it

My solutions for platinum:

united
routing
balanced
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    It's actually possible to solve routing in $$$O(KN^2)$$$ time, because the matrix you take the determinant of is almost upper-triangular. In particular, it's upper triangular for all but at most 2 rows, so if you do Gaussian elimination in the right order, you'll only have to do $$$O(KN)$$$ row-operations.

    Just for the record: I believe the intended solution does not involve the BEST theorem or determinants, and takes $$$O(N^{K+1})$$$ runtime. Essentially, we will just try to match all inedges and outedges at each vertex; there are $$$\prod deg(i)!$$$ ways to do this. Some of these matchings may form unwanted eddy cycles, which must involve one of the $$$K$$$ backedges. Then, we can count ways to form the cycles using these $$$K$$$ edges, and we'll end up with a DP with $$$O(N^K)$$$ states and $$$O(N^{K+1})$$$ runtime. In fact, you can use some determinant-like arguments (or inclusion/exclusion if you'd prefer) to transform this into computing some path counts in $$$O(N^2)$$$, followed by taking a determinant of a $$$K \times K$$$ matrix, which is essentially equivalent to the BEST theorem/Gaussian elimination solution.

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

    I just have a slightly different solution to united I'd like to share (the complexity is the same, but we don't need lazy propagation in segment tree for example).

    If we fix our $$$L = l$$$, let $$$f(i)$$$ denote the index of first occurrence of number $$$i$$$ to the right of $$$l$$$, and $$$s(i)$$$ denote the second occurrence. We can handle some of them being non-existing by just setting them to $$$n$$$.

    Then, we need to consider the interval $$$(l + 1, f(A_l) - 1)$$$ to search for two indices for $$$M$$$ and $$$R$$$. Obviously, as $$$A_M$$$ and $$$A_R$$$ have to be unique in the chosen subarray, they are going to be $$$f(x)$$$ for some $$$x$$$. The condition for some values $$$x$$$ and $$$y$$$ being a suitable pair of values is $$$f(x) < s(y)$$$, and $$$f(y) < s(x)$$$.

    We can calculate the number of such pairs using a regular segment tree. In every node we store:

    • the number of $$$f$$$ values
    • the number of $$$s$$$ values
    • number of $$$(i, j)$$$ such that $$$f(i) < s(j)$$$
    • number of $$$(i, j)$$$ such that $$$s(i) < f(j)$$$,

    which we can easily merge in $$$O(1)$$$. From these four values, we can get the number of pairs we need. Note that when we're moving our $$$L$$$, we only have $$$O(1)$$$ updates in the segment tree, so we end up with $$$O(N\log N)$$$ complexity in the end.

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

    For united, how do you construct that segment tree? In competition, I got to the point of figuring out that kind of a structure was necessary, but couldn't figure out how to actually build such a tree. How can you toggle an element's activity and target those elements specifically?

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

      In each segment $$$[L, R]$$$ (of a node in the segment tree), we keep:

      • $$$cnt$$$, number of active positions.
      • $$$sum$$$, sum of elements in active positions.
      • $$$lazy$$$, lazy propagation.

      Then, if a we add $$$x$$$ to the segment $$$[L, R]$$$:

      • Increase $$$sum$$$ by $$$cnt \cdot x$$$.
      • Increase $$$lazy$$$ by $$$x$$$.

      Everything else is almost the same as a standard lazy segment tree.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What was the approach for #1 in the silver division?

The tricky thing was that you can go back the way you came and retrace your steps, so what I did was have a sort of vis set that stores the grids we visited at each point in the maze. But that TLE'ed on test case #10, so I'm curious to know what other people did.

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

    A set is too slow for test case #10. You could use a 3-D array to store the states you have already visited.

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

      Yeah that's what it says in the official solution.

      It's still a bit sketchy though, because my solution takes about 0.33 seconds (and the official solution took 0.2), which is quite long. Maybe we could have had a limit of a 20 x 20 grid instead, but it's already over now.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

USACO Gold Solutions:

United

That's all I solved fully (400 on this contest)

»
5 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

When do US Open/Finalist results come out?

(This won't affect me, but I'm curious)