This has a whole new meaning now lol

People use these blogs to discuss the problems after the contest window ends as well.

I'm gonna participate in this one and didn't know when it was so thanks mr blog poster.

Yes, US Open is exactly like a normal USACO contest but is longer (5 hours instead of 4) and the problems are harder.

The grader is pretty specific about most output errors. If it were the same as the sample, extra spaces should've been your first guess.

Nope, people might still be taking the contest. Wait another 35 minutes.

Gold 2 was binary search

Gold 3 was rectangle dp

My (bad) explanation for problem 2: so we have a vector of deques representing the current stacks of plates we also keep track of the maximum numbered plate that elsie has already washed and stacked when a plate comes to bessie: 1) if this plate has a number less than the maximum plate placed, there is no way that we can place this plate; output the current i 2) binary search for the stack whos bottom plate is as small as possible but greater than the target plate within the range of the 2 pointers (i.e upper_bound) 3) if all the plates in all the stacks are less than the target (this can be checked by looking at the bottom of the last stack), then create a new stack and move the second pointer forward 4) else if the target plate has label less than the top of the stack whos index we found during the binary search, then push the plate to the top of the stack 5) otherwise, move the first pointer to the index that we found with the binary search, and pop off all plates with numbers greater than the target plate (effectively we are getting rid of the plates that should come before the target). update the maximum plate to the tag of the last plate that we popped 6) push the target plate onto that stack 7) continue

orz aryaman found it trivial

It felt insane, or at least very easy to overcomplicate and hence make insane.

My 7/10 for gold #2 was a decomposition into subsequences for each globally maximum element and then an O(n) amortised analysis to determine the first index which could not be cleaned, then the minimum of all these values is taken, which took like 3 hours ... :/

How many test cases did the optimization get?

Ideas for plat P3 (I was out of time, so couldn't get AC with this. Feel free to point out errors):

We first precalculate the length of LIS ending at each point. With this information, we can easily have a naive n^2 DP solution: Let DP[i] be the smallest possible area, and do the transition for all pair that is a part of LIS.

To optimize this, we batch process all pairs i, j, such that DP[i] = x, DP[j] = x + 1, and (i, j) is "comparable" if X_i < X_j, Y_i < Y_j holds. Now, we do these three observation.

• First, notice that for all i with DP[i] = x, they form an "antichain": If sorted in increasing order of x, the y coordinate is decreasing, leaving no "comparable" pairs in the set. Of course, this also holds for DP[j] = x + 1, so we are essentially spreading DP information "wave-to-wave", with each wave being a decreasing chain.
• Second, with the "wave model" in mind, we can see that the DP transition is range query for a certain interval of i (in sorted order). Thus, for every j, we should find the minimum value of DP_i + (X_j - X_i)(Y_j - Y_i) for a certain interval of i. This is insufficient to solve the problem, as the formula is hard to optimize (maybe 3D convex hull trick might work or not...)
• Third, Let's assume that every pair is "comparable": If DP[i] = x, DP[j] = x + 1 holds, then (i, j) is always guaranteed to be comparable. In this special case, we can utilize a well-known optimization technique. Suppose opt(j) be a point in x-wave which gives a minimum answer for j. We can see that opt(j) is monotonic in opposite direction: if j₁ < j₂ in order of x coordinate, opt(j₁) ≥ opt(j₂) always hold, as otherwise we can swap them to obtain strictly smaller cost. This kind of monotonicity allows "divide and conquer optimization", solving the restricted problem for time.

It seems we are almost done, but in reality, the "incomparable" pair gives a lot of trouble, and it would be impossible to build a divide and conquer based on this.

To overcome this, let's imagine a "magical segment tree", which will somehow respond to a range query asking for the minimum of DP_i + (X_j - X_i)(Y_j - Y_i). Then, for each query, you will decompose it to intervals which belongs to a certain node in a segment tree. In the end, every node will receive a total of queries which ask the minimum of DP_i + (X_j - X_i)(Y_j - Y_i) in the interval represented by it.

You can notice, that every query point stacked in each node are comparable with all points in interval represented by its node. Thus, you can actually simulate that "magical segment tree" in an offline fashion, by collecting all points in each node and running divide-and-conquer optimization to solve the problem in each node. The time complexity is for each wave, and summing to in total.

Although I introduced this solution as a "segment tree" approach, this is better to interpret as a divide-and-conquer solution. You don't actually need an explicit segment tree structures too: a divide-and-conquer which solves the "conquer step" with another divide-and-conquer will suffice. I believe the code will be actually quite pretty.

One of my friends came up with a solution which is sufficient to get all the test cases. He used Divide and Conquer, but I'll present the solution without since his idea can easily be modified that way.

First, we partition the sequence into sets of elements with the same LIS value in increasing x-coordinate order (as usual). And we also do the DP where DP[i] = max(DP[j]+(x[i]-x[j])(y[i]-y[j])) where j ranges over all elements with LIS equal to LIS[i]-1 within the range of i (so it has to satisfy an increasing subsequence).

Let's ignore the condition for now that the chosen flowers have to form an increasing sequence, just that the LIS works (i.e. it goes from 0 to 1 to ... to max(LIS), hitting all consecutive numbers). Now, we claim that the best j to transition to goes in reverse order of x-coordinate as the x-coordinate increases within the same LIS value. You could prove this using simple inequalities, subtracting the differences for example.

Now, we break all elements with the same LIS into buckets. We still ignore the condition for now, and for each bucket we keep track of the best flower within that bucket to transition to given the current flower in the next LIS subsequence. To do this, we keep a "hull" set where for each adjacent flowers we can binary search when one passes another, and use this information to keep track of which flowers can ever be the transition (i.e. it passes the last flower at a point before the next flower passes this flower) and exactly at what point to switch to the next flower. This binary search takes time. We store the points when to switch flowers so that when we compute the DP we know when to switch between current bests within each bucket. At most O(N) such points, so this switching part takes O(N) time.

Now, we sweep across all flowers of the current LIS sequence which we want to compute the DP values of. Because the sequence of good transitional flowers form a consecutive interval as easily checked, note that at most 2 buckets partially intersect the sequence of possible transitions (the ones that satisfy the condition that it forms an increasing sequence), so we check all the values of the 2 buckets as possible transitions. For the rest of the buckets, if they don't intersect with the good interval at all we ignore it, otherwise they intersect entirely and we simply check the current best of the interval as a possible transition. You're checking at most values per transition, so the complexity is .

Do you mean p2 of Platinum division? I also got a NY^2 solution, but with some optimization, the complexity can be reduced a little bit, so it can fit into the time limit.

If you want, I can try to elaborate my solution.

I had an idea that also involved counting the complement, but I used generating functions and polynomial multiplication using FFT. Unfortunately I had a stupid overflow error during the actual contest, but I think this works.

I had an O(N² + CYlog(Y)) solution, where C = N - M is the number of connected components, which involves C fast polynomial multiplications. But when I submitted my "brute" solution using naive multiplication just to ensure correctness, it magically runs in 2.6 seconds :o So I didn't have to implement FFT. You can read my code here, it's quite easy to understand.

Define a_i as the probability of each cow not returning the invitation. Define the sequence b_i as 1 / a_i - 1. Consider an interval from indices l to r. Then the probability of exactly one cow returning the invitation is (b_l + b_l + 1 + ... + b_r) * (a_l * a_l + 1 * ... * a_r).

Consider the interval obtained from extending the interval by one index to the right. We are interested in when (b_l + b_l + 1 + ... + b_r + b_r + 1) * (a_l * a_l + 1 * ... * a_r * a_r + 1) > (b_l + b_l + 1 + ... + b_r) * (a_l * a_l + 1 * ... * a_r). You can cancel a ton, and eventually you get that this is equivalent to b_l + b_l + 1 + ... + b_r < 1.

Now, we can simply use two pointers with this condition, and compare the maximum intervals starting from each index. This gives an O(n) solution.

vamaddur and some other experienced people suggested that there would be a low cutoff (<700) for promotion from gold to plat. We'll get to know soon enough.

I was thinking about sliding window approach but then I only had 10 minutes left when I started #3

I think you mean gold P3? If so, 2D Kadane's algorithm and a line sweep while maintaining maximum subrectangle on both sides of the line should work (for right-left and up-down separately). Unfortunately my own implementation had a bug and I could only get 11/14 testcases but I verified the technique with at least one person who got a full solve.