### xiaowuc1's blog

By xiaowuc1, history, 5 weeks ago, ,

Hi all,

The first contest of the 2018-2019 USACO season will be running from December 14th to December 17th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

•
• +85
•

 » 5 weeks ago, # |   +3 To organizers: could you also publish the duration of the contest beforehand? I guess it will be 3 or 4 hours?
•  » » 5 weeks ago, # ^ |   +4 It is 4 hours
 » 5 weeks ago, # | ← Rev. 2 →   0 How I can register on contest? usaco.org?
•  » » 5 weeks ago, # ^ |   0 Just make an account on the website. Then you will be automatically “registered” and can start your 4 hour block any time during the weekend.
 » 5 weeks ago, # |   -7 Does anyone know the solution to Gold Problem 1 (Fine Dining)?
•  » » 5 weeks ago, # ^ |   +6 The contest isn't over for like 2 and a half more days.
•  » » 5 weeks ago, # ^ |   +5 Contest rules prohibit the discussion of contest problems until the 4 day larger contest window is over. After the contest has finished, the problem setters will post an editorial for each question which usually comes with a C++ and/or Java solution.
•  » » 5 weeks ago, # ^ |   +14 What I did was modified Dijkstra. First, run normal Dijkstra from node N calculating dist[i]. Then do multi-source Dijkstra pushing all special nodes to priority queue with initial dist dist[i] — t if i is special and infinity otherwise (go from n to i and eat there) Let's call dist2[] the produced array. Then for each node we output 1 iff dist[i] >= dist[2].Code here
•  » » » 4 weeks ago, # ^ |   0 I had the same idea, but I was too lazy so I wrote it in one dijkstra-like spfa. Bad complexity wise, but it passes.https://pastebin.com/fJMRbnTv
 » 5 weeks ago, # |   0 Contest should be over. Can anyone confirm?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +6 Yes, the contest is over.UPD: But it will be completely over at 16:00 UTC.
•  » » 5 weeks ago, # ^ |   +26 People can't start the contest now, but some could still be doing it. I think everyone will be finished 30 minutes before the end of CF round 527.
 » 5 weeks ago, # |   0 now that it's over, did anyone get gold #2?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I got 8/11, but the 10/11 is the same idea. Not sure although if it's ended, someone may be participating now.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 oh i thought it ended 10 min ago rip
 » 5 weeks ago, # |   0 I believe we may discuss now (12/18/2018 16:31 UTC). Can anyone confirm?
•  » » 5 weeks ago, # ^ |   0 Yes it's done for sure.
 » 5 weeks ago, # | ← Rev. 2 →   +5 My solution to P2 in Gold division was inclusion-exclusion. So the answer for one person will be constructed in the following way: Add people who have the same ice-cream flavors as the current person, delete the people who have the same 2-ice-cream flavors, add the people with the same 3-ice-cream flavors, delete the people with the same 4-ice-cream flavors and finally add the ones who have the same 5-ice-cream flavors. Obviously this is done by bitmasks in 2^5 * n * logn( if you use map to store the vectors).This is a 8/11 solution. You can sort the entire array and this will work faster and you will get 10/11. I know that this can be somehow optimised by hashing the vectors or using trie, but may be there is a more beautiful solution. Here is the 10/11 solution of my friend claudy. He also used parsing for input but it's not necessary.
•  » » 5 weeks ago, # ^ |   +3 Vector hashing and unordered map works fine for 11/11
•  » » » 5 weeks ago, # ^ |   0 Well how did you use unordered_map? for c++11 it doesn't work, or you wrote it by hand, not as c++ STL? Also i tried hashing but it didn't work, i think they had strong tests and i needed some kind of elegant hashing.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Just write a vector hashing class and use it like this: unordered_map, int, hasher> m; 
•  » » 5 weeks ago, # ^ |   +6 You can use unordered_map instead of map, but you need to write vector hasher(because you can't use vector as key of unordered_map).For example, you can use sum of elements of a vector as vector hash. (Yes, different vectors can have same hash, but you just need to minimize number of collisions).I got 11/11. My code.Sorry for my bad english.
•  » » » 5 weeks ago, # ^ |   0 Ok thanks, but i am not sure how the sum of the vectors got 11/11 xd, it's kind of too weak. I tried to hash by multiplying the digits of each number in the vector to the power of some prime, and it didn't work :D.
 » 5 weeks ago, # |   +1 Can someone please post the platinum division problems here?
 » 4 weeks ago, # |   +3 Did someone manage to get P1 Platinum? I'm curious as to what ideas did you have.
•  » » 4 weeks ago, # ^ |   +17 It turns out that the optimal solution is given by taking the convex hull of the points (i, ri) for each 0 ≤ i ≤ N + 1. This is pretty intuitive; if we can get an expected value of A at a certain point and B at another point then the recurrence should allow us to achieve at the midpoint, and repeatedly taking midpoints should give us the line. Now just running the convex hull algorithm and sweeping through the points gives the right answer.Unfortunately, I used long doubles to store my answer which isn't precise enough (you have to store everything as a long long and divide at the very end, apparently). I think this happened to a few others as well.
•  » » 4 weeks ago, # ^ |   0 Is there a way to solve this problem without seeing the convex hull? I tried using the idea that your decision is fixed at each location, no matter how you got to a location, you are always going to jump off or continue. However, I was unable to link this to convex hull, and ended up not solving this.
•  » » » 4 weeks ago, # ^ |   +5 You use that fact along with solving it for taking l and r. The points between l and r will be taken from the segment between points (l, a[l]) and (r, a[r]). From this, you should be able to see that the optimal answer is the convex hull.
•  » » » 4 weeks ago, # ^ |   0 Technically you can solve it without noticing the Convex Hull as I was able to get 11/11 without it. However my algorithm provably calculates the convex hull in a terrible manner, but with enough optimizations I got it down.I doubt there is an intended solution that doesn't hinge on the convex hull even if you prove it without mentioning a convex hull.
 » 4 weeks ago, # | ← Rev. 3 →   +8 How do we solve Plat P3? I coded something with LCA but only managed to grab 7/15, rest Wrong answer.upd: found my stupid bug...
•  » » 4 weeks ago, # ^ |   0 You use LCA. Code
•  » » » 4 weeks ago, # ^ |   0 Hmm, I did the same thing as you. Guess I must have messed something up with the implementation. Thanks!
•  » » » 4 weeks ago, # ^ |   +31 I think your solution (and many others) fail on the test: 4 3 1 2 1 3 1 4 2 3 3 4 4 2 Answer should be all 0s?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You're right. Is there an easy way to fix this?
•  » » » » » 4 weeks ago, # ^ |   +42 I haven't looked carefully, but it's likely that the only case when your solution is wrong is when the answer is 0 for every node. However, it can be checked in O(n) whether there exists some root that works by repeatedly removing legal nodes.
•  » » » » » 4 weeks ago, # ^ |   0 Perhaps the way to deal with the possibility of this case is to construct a graph with the m pairs of cows as edges, and checking if there are any cycles.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 After some thought, I reduced the problem to finding which nodes could be the root of the tree, without violating the following condition: for every pair (A, B), B can't be in the subtree of A. This is because, in order for any node v to leave, all of its sub-tree must leave first. This is also the reason why, if you consider any node as the root, this will be the last one to leave. To do this, root the tree in node 1 (or any other one, doesn't really matter), and, for each pair (A, B), do the following: If B isn't in the subtree of A, then any node in the subtree of A CAN'T be the root. Otherwise, let's name K as the first node in the path from A to B. In this case, all nodes that aren't in the subtree of K CAN'T be the root node (I managed to prove these, but it is a little tedious and requires a little more thought). Finally, if you assume that at first, all nodes can be the root node, and process each pair one by one, in each pair eliminating all nodes that CAN'T be the root (with a Segment Tree + Lazy, after linearizing the tree with a post/pre-order traversal), you get an algorithm that works in O ( M lg N ). Code
•  » » » 4 weeks ago, # ^ |   0 Actually your solution is wrong. It passed because of weak tests.Your code will fail on the case: 5 2 1 2 2 3 1 4 4 5 2 5 4 3 Answer should be all zero.
 » 4 weeks ago, # |   +5 What was the solution to P2 Platinum? I thought that the solution was finding the Kth lexographically largest longest increasing sequence.
•  » » 4 weeks ago, # ^ |   0 I think it was finding the kth lexicographically smallest complement of a LIS, which is not the same thing.Consider the sequence: 3 5 4 1 2All the longest increasing subsequences:3 5 (Complement: 4 1 2)3 4 (Complement: 5 1 2)1 2 (Complement: 3 5 4)The greatest (3rd smallest) LIS is 3 5. The smallest (3rd greatest) complement of an LIS is 3 5 4.
•  » » » 4 weeks ago, # ^ |   +5 The 3rd largest LIS is 1 2, and its complement, the 3rd smallest complement is 3 5 4. If I'm not mistaken, computing the Kth largest LIS should be the same as computing the Kth smallest complement. Anyways, what is the algorithm for solving this? I tried using a segment tree, but my algorithm completely failed.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +10 But if the sets are sorted in increasing order, it becomes 3 5 (Complement: 1, 2, 4)3 4 (Complement: 1, 2, 5)1 2 (Complement: 3, 4, 5)Now the smallest (or 3rd greatest) complement is {1, 2, 4}
•  » » » » 4 weeks ago, # ^ |   0 I forgot about the sorting step. I believe you are correct.
 » 4 weeks ago, # |   0 P1 silver was an oof for me :( Did not consider the binary search solution during contest at all.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 I understand you. :( I'm my case I got Silver P1 rather quickly but P2 killed me even when I had the right approach, but could not find a bug in my program and after I fell asleep for the rest of the contest (oops). Hope we're better prepared for the january contest.
 » 4 weeks ago, # | ← Rev. 2 →   +10 So it seems the data for P3 platinum was rather weak. Consider the testcase at the bottom (excuse my blurry phone camera). You can interpret an arc a → b as meaning 'a must go after b' (I think it was the other way around in the statement, sorry about that). Then if we root the tree at the highest vertex the answer will be 'impossible', because this means orienting all edges downward, and this will introduce a cycle. In particular, the solution 'if a needs to go after b, then discard all vertices in a subtree of b not containing a' fails on this test. Notice that when you root at the highest vertex, this vertex is never contained in such a subtree. Yet from what I understand this solution passes all testsI'm curious to know what the intended solution was (hopefully this wasn't the intended solution). I thought of the above approach early on and quickly dismissed it since one can pretty quickly arrive at the counterexample below. It's a bit frustrating to then see that this would get you all points, as in life there is nothing more important than winning and collecting virtual points.Here is the testcase corresponding to the picture. You should get 0 for all vertices: 7 3 1 2 2 3 1 4 4 5 1 6 6 7 2 5 4 7 6 3 Picture of the testcase: https://i.imgur.com/kNiWbSa.jpg
•  » » 4 weeks ago, # ^ |   0 The same story for me, this case made me wonder whether any LCA approach would have any chance to pass. An easier case would be as stated earlier: 4 3 1 2 1 3 1 4 2 3 3 4 4 2 To be honest I wonder whether just checking at the end whether an arbitrary node with answer 1 works and if not discarding all 1 nodes solves the issue.P.S.: Please, resize the picture :))
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 P.S.: Please, resize the picture :)) Can this be done in Markdown? I’m on my phone so don’t really have access to any editing tools. EDIT: Ok, I just replaced it w/ a link.
 » 4 weeks ago, # |   0 As some of the more impatient contestants, myself and eygmath made this Google Form to tabulate preliminary results from the CF Community. One can view the spreadsheet with sorted results here (it updates every few minutes with the most recent entries from the form).If there are any issues, please comment below.
•  » » 4 weeks ago, # ^ |   0 how do i edit my entry?
•  » » » 4 weeks ago, # ^ |   0 Well this seems redundant now... :P
 » 4 weeks ago, # |   0 Results are out at http://usaco.org/index.php?page=dec18results!
 » 4 weeks ago, # |   +11 Did they added tests to P3 Platinum? Becuase I am pretty sure during the contest I passed all the tests but now in the ranking it appears that I have the last 2 tests with "Wrong answer".
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +12 Yes. From the result page: Note that the coaches decided to add some extra test cases to the last problem before computing final scores, since the original test data was not as exhaustive as hoped (recall that as per our rules, the coaches can always add or remove test cases prior to final grading if needed, so you should always test your code thoroughly and not assume it will earn perfect marks just because it solves the test cases present in the contest itself).