The 3rd USACO of the 2015-2016 year is open from February 19-22 (It's February 18 now, and it's open for some reason, but whatever... maybe the opening time doesn't use EST). Unless someone else has already started a blog about this (in which case it'd be nice to have a link in the comments), we should discuss the problems here after it ends.
UPD: Contest is over. Discuss! UPD: Results are here
Where can I participate??
here you need an account to participate
you can look up USACO (that's the standard way of finding things)
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?
Probably not. Better not.
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)
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.
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.
Wait three more hours, because some contestants are still solving problems.
Sorry about that! I wasn't aware. Thank goodness no one posted the answer.
for i->n for j->n find first empty entry and fill it with the nearest(not clockwise) filled entry...
it is optimal...
Auto comment: topic has been updated by kliu31415 (previous revision, new revision, compare).
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 ri and i*ri); if we try only approx. N/K ways to split the barn, it becomes O(N3) with a good constant, which passes (there's an O(KN^2*log(N)) solution, but why bother)
Load Balancing : You can remove binary search for minimum answer with something like that to make it O(N*log^2(N))).
Circular Barn : Someone can also solve it in O(KN^2) with convex hull trick.
Convex hull trick has an additional log-factor, afaik.
If queries are non-decreasing order, you don't need to binary search.
I solved it using Knuth optimization in O(n3) but low constant made it too fast (100ms max).
Doesn't Knuth optimization make it O(kn2)?
No, the n part is still there. My dp first ran in O(kn2) and after Knuth it runs in O(n(n + k)) which is O(n2) and so it's O(n3) in total.
Could you share your code? I tried coding up Knuth but get TLE... https://ideone.com/9P7N6x
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 inUnable to parse markup [type=CF_TEX]!?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
how did you handle the cases when there's equal values in ternary search?
i didn't , i expected a WA but it gave AC.
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
I got all WA with a ternary search D:
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)
"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...
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?
It's called fitting the program to the test cases.
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.
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.
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.
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).
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.
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.
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.
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.
Scores will be higher, since it wasn't hard to get full points on some problems by writing some wrong solution.
Word is that test cases will be added to #3.
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).
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
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.
Can you please explain what you did if n>=400? I didn't get the "hashing the input" part.
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:
and then
and so on we will finally know the hash for each test case :)
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.
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.
"more feedback is always helpful for beginning contestants"
There aren't beginning contestants in Platinum.
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.
LIES!
Can someone explain how to solve 1st task ? (gold division)
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...
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)?
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.
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?
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?
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)
You can search it on Google. Also you can use convex hull trick for this problem.
Auto comment: topic has been updated by kliu31415 (previous revision, new revision, compare).