USACO February 2016 - Codeforces

9 years ago, # ^ |

you can look up USACO (that's the standard way of finding things)

→ Reply

9 years ago, # |

Question: Are we allowed to discuss scores and problem difficulty before the contest ends as long as we don't talk about the problems themselves?

→ Reply

9 years ago, # ^ |

+42

Probably not. Better not.

→ Reply

9 years ago, # |

+13

Am I correct in stating that the last participants will finish in a little over 2 hours? (If I did the time zone conversions correctly, the last participants started about 2 hours ago, which is UTC-12 23:59, so they will have about 2 hours left)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

No, if the contest time is the same as usual, you're not correct. The last participants will start competing in 10 hours and finish in 14 hours counting from now. Check here if you want to know when the last contestants will finish.

→ Reply

maximaxi

9 years ago, # |

Does anyone have ideas for the first Silver problem? My friend later told me it was quadratic optimization, but it seemed really hard for a Silver.

→ Reply

9 years ago, # ^ |

+11

Wait three more hours, because some contestants are still solving problems.

→ Reply

maximaxi

9 years ago, # ^ |

Sorry about that! I wasn't aware. Thank goodness no one posted the answer.

→ Reply

saliii

9 years ago, # ^ |

for i->n for j->n find first empty entry and fill it with the nearest(not clockwise) filled entry...

it is optimal...

→ Reply

9 years ago, # |

Auto comment: topic has been updated by kliu31415 (previous revision, new revision, compare).

→ Reply

9 years ago, # |

+18

My solutions (Platinum), in short (fix your LaTeX, CF!):

Load Balancing: try all coordinates of the vertical fence, double binary search for the minimum answer and the maximum possible range on the right+left that gives this answer (the number of cows on the right/left side in a given range with a given y-coordinate can be computed using BITs); check if the ranges have a non-empty intersection; O(N*log^3(N)) with optimisations

Fenced In: sort the N+M+2 fence parts (horizontal and vertical ones together) by length, then remove as many as necessary (without creating cycles) of each length in that order; if there are x processed horizontal and y vertical fence parts and we're processing a horizontal one next, then we need it removed all M times if x = 0 or y = 0 and M-y times otherwise, similarly for vertical parts; O((N+M)*log(N+M))

Circular Barn: there's a simple DP in O(KN^3) time, where we try all N ways of splitting the circular barn into a linear one and do a DP on the minimum cost of splitting its i-th suffix into k intervals, where we compute each state by trying all choices for the last interval (we can compute the cost of one interval from prefix sums of r_i and i*r_i); if we try only approx. N/K ways to split the barn, it becomes O(N³) with a good constant, which passes (there's an O(KN^2*log(N)) solution, but why bother)

→ Reply

9 years ago, # ^ |

+13

Load Balancing : You can remove binary search for minimum answer with something like that to make it O(N*log^2(N))).

whilen(ans > 1 and check(ans - 1))
    ans--;

Circular Barn : Someone can also solve it in O(KN^2) with convex hull trick.

→ Reply

9 years ago, # ^ |

Convex hull trick has an additional log-factor, afaik.

→ Reply

9 years ago, # ^ |

+18

If queries are non-decreasing order, you don't need to binary search.

→ Reply

PrinceOfPersia

9 years ago, # ^ |

← Rev. 2 →

I solved it using Knuth optimization in O(n³) but low constant made it too fast (100ms max).

→ Reply

ed1d1a8d

9 years ago, # ^ |

Doesn't Knuth optimization make it O(kn²)?

→ Reply

PrinceOfPersia

9 years ago, # ^ |

No, the n part is still there. My dp first ran in O(kn²) and after Knuth it runs in O(n(n + k)) which is O(n²) and so it's O(n³) in total.

→ Reply

ed1d1a8d

9 years ago, # ^ |

Could you share your code? I tried coding up Knuth but get TLE... https://ideone.com/9P7N6x

→ Reply

PrinceOfPersia

9 years ago, # ^ |

Load Balancing: Finding left and right ranges can be done without binary search using just a BIT. If for example left side has t points and we want to check if answer is at most m (in binary search), then the range is [((t-m)-th y in sorted order)+1, ((m+1)-th y in sorted order)-1].

So that reduces time complexity to O(n log^2(n)) ;)

P.S: CFTeX seems to be fucked up recently. Why the hell O(n log^2(n)) results in Unable to parse markup [type=CF_TEX] !?

→ Reply

rajat1603

9 years ago, # ^ |

for load balancing i tried all vertical fence and then did ternary search for optimal horizontal line since the max value will first decrease then increase for a fixed vertical line

→ Reply

kingofnumbers

9 years ago, # ^ |

+10

how did you handle the cases when there's equal values in ternary search?

→ Reply

rajat1603

9 years ago, # ^ |

i didn't , i expected a WA but it gave AC.

→ Reply

9 years ago, # ^ |

I didn't know ternary search, so I used a square root decomposition method that ran in O(N*sqrtN*logN), which gave me 11 AC and 4 TLE. Looking back on my code, I think I see a mistake and I should've gotten lots of WA... https://ideone.com/LUGOLn

→ Reply

chaosagent

9 years ago, # ^ |

I got all WA with a ternary search D:

→ Reply

-Wave-

9 years ago, # ^ |

← Rev. 2 →

I actually got all but one case in Fenced In with a O(N^4) solution. For some reason I didn't think of the prefix trick and so I had O(KN^3) DP states. I had two hours left, so I did a lot of heuristic optimizations and it (almost) worked. Grader not having the tests bunched + no penalty for resubmission helped a lot.

(Of course, retrospectively, stopping to think for 10 minutes would've probably been a better idea)

→ Reply

9 years ago, # ^ |

"Grader not having the tests bunched + no penalty for resubmission helped a lot."

I used this a lot — just wrote the first thing that seemed fast enough and then hammered it into the TL. Why bother finding faster solutions if there's other stuff to do and the grading system is too simple...

→ Reply

ko_osaga

9 years ago, # ^ |

if we try only approx. N/K ways to split the barn

I can't understand this part. How can you try only N/K ways to split the barn? One interval will have N/K length in average, but it's not the case in worst case.. am I missing something?

→ Reply

9 years ago, # ^ |

It's called fitting the program to the test cases.

→ Reply

tabasz

9 years ago, # ^ |

← Rev. 2 →

An O(nlogn) solution for Load Balancing: we swipe from left to right with vertical fence. We keep a segment tree over an y-axis. In vertex of the segment tree corresponding to interval [b, c], we keep 2 numbers: number of points with y from b to c that are on the right of vertical fence and number of points with y from b to c that are on the left of vertical fence. It is easily updated while we move with the fence to the right. Now for every vertical fence we want to "binsearch" the best horizontal fence using the segment tree. We start in the root and go down to one of the sons always trying to decrease the number of points in the area that contains the most points. We do it until we reach a leaf of the tree. (We always consider the horizontal line that divides the segment of the vertex in half — that means it goes between segments of sons). We have checked logn horizontal lines and one of them was the best one for this vertical line.

→ Reply

9 years ago, # |

Overall how do you guys think the difficulty of this contest compared to the previous ones (talking about Platinum specifically). I personally thought it was somewhat easier, and definitely easier than the February 2015 Gold contest.

→ Reply

9 years ago, # ^ |

I think this contest had very interesting and fun to solve problems, specially the 2nd one. Comparing it to the previous one, I think it was easier, but it was definitely harder than the December Contest. The Gold contests I took part in last year were also much easier than this one, though I know that a couple of contests I didn't take part had challenging problems.

→ Reply

9 years ago, # ^ |

Interesting. I got an 844 on this contest (I got 11/15 on the first problem, 10/10 on the second, and 8/10 on the third) and a 100 on the December contest (3/10 on the last problem because integer overflows).

→ Reply

9 years ago, # ^ |

I also got 844 on this contest (14/15 on the first problem, 10/10 on the second and 6/10 on the third), but I spent a lot of time solving the problems. I spent over two hours on the 2nd problem and didn't have enough time to properly think the 3rd one. On the other hand, I used only little more than an hour to solve all the problems and get a full score on the December contest.

→ Reply

9 years ago, # ^ |

That's way differently than what I did — I first used a janky solution to get 5/10 on the third problem, spent the next hour to solve the second (which turned out to be easier than I thought), went back to the third to get 8/10 by reducing my constant factor (I had O(KN^3)), and spent the rest of the time trying to think the the first. The first one really annoyed me, because I couldn't find a way to find the minimum of a bitonic function in log(n)^a time.

→ Reply

9 years ago, # ^ |

I solved the first problem rather quick. I used a sweep horizontal line and did two binary searches to find the best position to put the vertical line. I supported the queries with two BIT's, one for points above the horizontal line and the other one for points below. Each time I moved the horizontal line, I updated both BIT's accordingly.

Also I noted that I only need to process at most 100001 horizontal lines, and it fit in time. Somehow I got WA on test 14 though.

→ Reply

send_nodes

9 years ago, # ^ |

I thought the platinum contest was tougher than January's. Problems had longer solutions and there wasn't a trivial brute force problem like January. Also, the DP #3 was easy to recognize but not at all simple to code(at least for me). I will be surprised if the mean score for plat is above 400.

→ Reply

memset123

9 years ago, # ^ |

Scores will be higher, since it wasn't hard to get full points on some problems by writing some wrong solution.

→ Reply

send_nodes

9 years ago, # |

Word is that test cases will be added to #3.

→ Reply

9 years ago, # ^ |

Interesting. Where did you find that information (link)? I'm guessing they had too many successful submissions that ran in O(KN^3) when they probably wanted something running around (OKN^2).

→ Reply

P_Nyagolov

9 years ago, # ^ |

+21

I think I have contributed to that decision — http://ideone.com/cgsXeB :D If N<=400, then I do the N^3*K dp and then I hash the input and... yeah, I cheat :D

→ Reply

ed1d1a8d

9 years ago, # ^ |

← Rev. 2 →

+10

Maybe this will convince them to switch over to batched tests. It's weird because they have a batched system for their selection camp contests, so it isn't like the infrastructure isn't there. Moreover, batched tests seem to be the standard for OI style contests now.

→ Reply

9 years ago, # ^ |

Can you please explain what you did if n>=400? I didn't get the "hashing the input" part.

→ Reply

P_Nyagolov

9 years ago, # ^ |

Yes, sure! What I do for N<=400 is to actually try all ways to split the circle into an array (from 1 to N). When 400<=N<=1000, then there are some optimal ways to split the array and each of them is from 1 to 1000. So I first submitted a solution which tries to split the cirlce only from position 1 to 50. Then from 51 to 100, then from 101 to 150 and so on. This way I knew for each case which was the interval I need to look at. The only thing left was to find a way to check which case our program is being tested on at the moment. So we can easily hash the input in some way (I used rolling hash with base 1331), then we find the last few bits of the hash for each test (4 were enough here) this way:

if(h&1) assert(0);
else while(1) {}

and then

if((h>>1)&1) assert(0);
else while(1) {}

and so on we will finally know the hash for each test case :)

→ Reply

-Wave-

9 years ago, # ^ |

I did something similar actually, but I only hashed the input when I wanted to distinguish between the last two cases. Simply summing the array and binary searching with assert(sum>=something) was enough to do that.

I will shamelessly abuse their grader until they finally do something about it. I think I had about 40 submissions on that problem.

→ Reply

rpeng

9 years ago, # ^ |

+14

Thank you for further spreading the awareness of how feedback can be used in this manner. I don't think there are plans to do anything about this: more feedback is always helpful for beginning contestants.

On the other hand, to my knowledge, the coaches do read codes of most camp invitees. So actual cows be warned.

→ Reply

9 years ago, # ^ |

+19

"more feedback is always helpful for beginning contestants"

There aren't beginning contestants in Platinum.

→ Reply

rpeng

9 years ago, # ^ |

+13

With the current divisions format, a primary concern is that contestants starting in bronze/silver in DEC can reach plat by FEB / OPEN, at which point they're being considered for the Gurnseys group at camp.

With the reduced number of contests, a contestant in these plat contests can easily have < 20 hours of 'live' programming contest experience. You'd be surprised about how many 'big cows' first reached USACO camp this way.

→ Reply

rpeng

9 years ago, # ^ |

+33

LIES!

→ Reply

Life

9 years ago, # |

Can someone explain how to solve 1st task ? (gold division)

→ Reply

lsmll

9 years ago, # |

← Rev. 3 →

I solved the first two problems in Platinum.In the third Circular Barn problem,I used a monotonic queue DP solution(which I proved,maybe proof was wrong or stupid bug) to improve the time complexity from O(KN^3) to O(KN^2) but got wrong answer.I'm surprised O(N^3) can pass...

→ Reply

9 years ago, # ^ |

The dp which I used is like that, dp[i] = i<=j min(x[j] + y[i] + z[j] * i)

How did you optimize it to O(KN^2)?

→ Reply

lsmll

9 years ago, # ^ |

← Rev. 4 →

My DP was like this:

f[i]=min{f[j]+z[j][i]} (j<i)

where z[j][i]=sum(r[k]*(k-j)) (k=j..i, r[k] is the number of cows in position k)

For any x<y, z[x][i+1]-z[x][i]>z[y][i+1]-z[y][i] (in fact the difference is (y-x)*r[i+1]). So with i increasing, if x is worse than y at some point,it will never be better than y.So we can use monotic queue to optimize the DP to O(KN^2).

This is the main idea of the solution.Maybe it's very wrong.Or just bug in implementation.I don't know.I stress tested it against a bruteforce but can only find error when n>200 so I can't debug it.

→ Reply

9 years ago, # ^ |

Why does "So with i increasing, if x is worse than y at some point,it will never be better than y." mean you can use monotonic queue? For example you can use divide and conquer optimization with this observation but how can you use monotonic queue?

→ Reply

lsmll

9 years ago, # ^ |

← Rev. 3 →

I think I know why it's wrong.With this observation we can only prove decisions removed from the queue will never be optimal but can't guarantee the best decision is at the front of the queue(i.e. the queue is actually not monotonic).In the contest I didn't think about this.Could you describe how to use divide and conquer optimization?

→ Reply

kingofnumbers

9 years ago, # ^ |

← Rev. 2 →

What you're doing is called convex hull trick.

it's not necessary optimal decision is in front of queue, but optimal decisions will be always increasing in index so you can still use queue and achieve O(kn^2)

→ Reply

9 years ago, # ^ |

You can search it on Google. Also you can use convex hull trick for this problem.

→ Reply