### xiaowuc1's blog

By xiaowuc1, history, 6 months 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

 » 6 months ago, # |   +3 To organizers: could you also publish the duration of the contest beforehand? I guess it will be 3 or 4 hours?
•  » » 6 months ago, # ^ |   +4 It is 4 hours
 » 6 months ago, # | ← Rev. 2 →   0 How I can register on contest? usaco.org?
•  » » 6 months 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.
 » 6 months ago, # |   -7 Does anyone know the solution to Gold Problem 1 (Fine Dining)?
•  » » 6 months ago, # ^ |   +6 The contest isn't over for like 2 and a half more days.
•  » » 6 months 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.
•  » » 6 months 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
•  » » » 6 months 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
 » 6 months ago, # |   0 Contest should be over. Can anyone confirm?
•  » » 6 months ago, # ^ | ← Rev. 5 →   +6 Yes, the contest is over.UPD: But it will be completely over at 16:00 UTC.
•  » » 6 months 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.
 » 6 months ago, # |   0 now that it's over, did anyone get gold #2?
•  » » 6 months 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 oh i thought it ended 10 min ago rip
 » 6 months ago, # |   0 I believe we may discuss now (12/18/2018 16:31 UTC). Can anyone confirm?
•  » » 6 months ago, # ^ |   0 Yes it's done for sure.
 » 6 months 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.
•  » » 6 months ago, # ^ |   +3 Vector hashing and unordered map works fine for 11/11
•  » » » 6 months 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.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Just write a vector hashing class and use it like this: unordered_map, int, hasher> m; 
•  » » 6 months 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.
•  » » » 6 months 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.
 » 6 months ago, # |   +1 Can someone please post the platinum division problems here?
 » 6 months ago, # |   +3 Did someone manage to get P1 Platinum? I'm curious as to what ideas did you have.
•  » » 6 months 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.
•  » » 6 months 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.
•  » » » 6 months 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.
•  » » » 6 months 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.
 » 6 months 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...
•  » » 6 months ago, # ^ |   0 You use LCA. Code
•  » » » 6 months ago, # ^ |   0 Hmm, I did the same thing as you. Guess I must have messed something up with the implementation. Thanks!
•  » » » 6 months 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?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 You're right. Is there an easy way to fix this?
•  » » » » » 6 months 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.
•  » » » » » 6 months 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.
•  » » 6 months 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
•  » » » 6 months 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.
 » 6 months ago, # |   +5 What was the solution to P2 Platinum? I thought that the solution was finding the Kth lexographically largest longest increasing sequence.
•  » » 6 months 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.
•  » » » 6 months 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.
•  » » » 6 months 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}
•  » » » » 6 months ago, # ^ |   0 I forgot about the sorting step. I believe you are correct.
 » 6 months ago, # |   0 P1 silver was an oof for me :( Did not consider the binary search solution during contest at all.
•  » » 6 months 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.
 » 6 months 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
•  » » 6 months 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 :))
•  » » » 6 months 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.
 » 6 months 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.
•  » » 6 months ago, # ^ |   0 how do i edit my entry?
•  » » » 6 months ago, # ^ |   0 Well this seems redundant now... :P
 » 6 months ago, # |   0 Results are out at http://usaco.org/index.php?page=dec18results!
 » 6 months 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".
•  » » 6 months 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).