xiaowuc1's blog

USACO 2018-2019 US Open
By xiaowuc1, 6 years ago, In English

Hi all,

The final contest of the 2018-2019 USACO season, the US Open, will be running from March 29th to April 1st! Good luck to everyone! As a courtesy to your fellow contestants, please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is live! Please do not post any spoilers about the problems publicly — if you have any issues with the problem statements, please follow the instructions to voice your concerns.

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

Comments Comments (37)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When does the contest usually starts? Thanks in advance :)

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

where is the contest window?

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

Guys, all the problems are by Ethan Guo

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

is anyone else not getting an email for the forgot password thing on USACO? Im pretty much locked out of my account

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

does anybody know WILLIAM LINs score?

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

How does one implement Gold Balance non-cancerously?

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

    If we don't perfom swap on ceils $$$n$$$ and $$$n + 1$$$, then the answer is difference between number of inversions in a first half and a second half. If we perfom swap on ceils $$$n$$$ and $$$n + 1$$$ we can notice, that in an optimal solution we either will move some number of 1's from a second half to a first half either we will move some number of 1's from a first half to a second half and after we finish 1s movement, we also need to add difference between inversions in a first half and a second half.

    So, the solution is as follows:

    Fix the direction in which we will move 1's.
    Move each 1 one by one, maintain number of inversions in a first and a second half.
    Relax answer with difference between inversions + actions that we spent on 1's movement.

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

      Thanks!

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

      Wow, I can't believe I didn't realise that all that the swaps across the middle amounted to was moving a certain number of ones across :/

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

What was the DP solution for Gold 1?

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

    I'm not sure my solution counts as DP but I used memoization to recursively fill the DP.

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

    My state was $$$dp[rightmost element][number of groups]$$$. I precomputed the cost for all subarrays in $$$O(N^3)$$$, then each transition is $$$O(N)$$$.

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

Can anyone explain their solution for platinum 3

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

    1. A valley is uniquely defined by the maximum height in the area. So you can enumerate possible valleys by fixing maximum height and finding the connected component that has heights all less or equal to it.

    2. Now you have $$$O(n^2)$$$ candidate, but you want to see whether the component has a hole. However, you can count a number of "global" holes, because it's a number of connected components in 8 direction.

    3. Preprocess the number of "global" holes, and let's try step 1 again. Maintain a disjoint set that contains each connected component, and the num of holes that each component has. If a component is merged, then basically all holes in each components are preserved. But, there is a "small" difference in the number of holes — that difference, could be traced because all the difference in "global" holes is attributed to that merges, thus the number is identical.

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

      I have a couple of questions. What is a "global" hole and how do you preprocess them? Also, when two components are merged, how do we know if the merge creates a new hole or not? Thanks in advanced!

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

        OK. I will clarify the definitions. A "Hole" is 8-directionally connected component consisted of cells that have a higher height than the specified maximum. (Note that we consider border cells as height $$$\infty$$$.) When I said "component $$$X$$$ has a hole", then it means there is a hole component, completely inside a connected component $$$X$$$. When I said "global hole", it is simply the number of connected components of such.

        We can't know whether the merger creates a hole or not, but we just deduce it from the difference of precalculated number of "global holes" for each phase, because the number would be the same.

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

    I solved it with Euler's formula, which stated that number of faces in a connected planar graph is equal to (# of edges) - (# of vertices) + 2.

    I add cells into the graph one by one from the lowest to the hightest. For each connected component, it can be considered as a planner graph, with neighboring cells forming an edge, and each cell as a vertex.

    I maintained # of edges and # of vertices in each connected component. These are easy to maintain.

    I also maintained # of 2 by 2 squares in each component, because each of them forms a face when turning into graph, but that's not what we considered a "hole". When adding new cells, this could be updated by directly checking whether this cells forms a 2 by 2 square.

    After updating each counter, I checked whether (# of edges) - (# of vertices) + 2 - (# of 2 by 2 squares) is equal to one (region outside the component is also considered a face). If not, then there must be a hole in it.

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

Does anyone have solution for Gold 3?

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

Could someone please explain their thought process to attack Platinum 2 (Compound Escape)? I got to "count the number of MSTs," but didn't make much progress afterward.

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

    I did a weird dp: dp[r][b][s] = {min cost, #ways} , where r = row processed, b = whether hor edges in that row have been processed, and s = connectivity state, which represents how the nodes in the last row are related (ie 112211 means node in pos 0,1,4,5 are in one component and pos 2,3 are another). For k=6, there are only around 130 total connectivity states, and if you precompute the state transitions it runs pretty quickly.

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

      My bruteforce code below tells me that there are 203 connectivity states. Did you optimize more?

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

        I found 203 connectivity states as well, and after some quick research it appears that the number of connectivity states is known as a bell number and that 203 is the amount when k = 6.

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

        Bell numbers count the possible partitions of a set. But in this problem, not every partition method is valid.

        For example, when $$$k=4$$$, it won't happen that the first and the third cell are in one component, and the other two cells are in another component. (You can try drawing it on a paper.)

        So when $$$k=6$$$, only around 130 connectivity states are valid, as stated by jasony123123.

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

          Partitions that are valid connectivity states are called crossing-free partitions. The number of those is exactly the nth Catalan number.

          → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

For Gold 2, I can only think of a greedy approach (9/15 test cases, rest is TLE). Sort all pair (i, j) by their distance, then use DSU to form groups.

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

    Answer is MOD-48n-84(k-1).

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

      Can you explain why?

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

        You always get the sets {1},{2}, ..., {K-1}, {K,K+1,...N}

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

          I don't understand how this observation is connected to @dorijanlendvaj's solution. Can you explain its relevance?

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

            The smallest pair is always going to be achieved by taking K-1 and N, which you can see in the construction jebaited posted.

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

              How do you know that k-1 and n will always produce the smallest number, though?

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

    I forget the problem. I can't access 2019US OPEN's problem on USACO now? Can you tell me what the problem is? Please.

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

Can anyone predict promotion cutoffs for Gold to Plat?

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

    I feel like it's going to be 750, as there was significant partials available and the difficulty wasn't too bad.

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

Why are results still not out?

→ Reply