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.

# | User | Rating |
---|---|---|

1 | tourist | 3539 |

2 | Radewoosh | 3464 |

3 | V--o_o--V | 3338 |

4 | Um_nik | 3307 |

5 | Petr | 3297 |

6 | ecnerwala | 3282 |

7 | LHiC | 3266 |

8 | wxhtxdy | 3264 |

9 | Vn_nV | 3182 |

10 | xyz111 | 3147 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 207 |

2 | Errichto | 176 |

3 | neal | 159 |

4 | Ashishgup | 158 |

5 | PikMike | 157 |

5 | Petr | 157 |

7 | majk | 156 |

7 | rng_58 | 156 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

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.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/18/2019 17:43:47 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

To organizers: could you also publish the duration of the contest beforehand? I guess it will be 3 or 4 hours?

It is 4 hours

How I can register on contest? usaco.org?

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.

Does anyone know the solution to Gold Problem 1 (Fine Dining)?

The contest isn't over for like 2 and a half more days.

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.

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

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

Contest should be over. Can anyone confirm?

Yes, the contest is over.

UPD:But it will be completely over at 16:00 UTC.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.

now that it's over, did anyone get gold #2?

I got 8/11, but the 10/11 is the same idea. Not sure although if it's ended, someone may be participating now.

oh i thought it ended 10 min ago rip

I believe we may discuss now (12/18/2018 16:31 UTC). Can anyone confirm?

Yes it's done for sure.

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.

Vector hashing and unordered map works fine for 11/11

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.

Just write a vector hashing class and use it like this:

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.

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.

Can someone please post the platinum division problems here?

Did someone manage to get P1 Platinum? I'm curious as to what ideas did you have.

It turns out that the optimal solution is given by taking the convex hull of the points (

i,r_{i}) for each 0 ≤i≤N+ 1. This is pretty intuitive; if we can get an expected value ofAat a certain point andBat 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.

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.

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.

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.

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...

You use LCA. Code

Hmm, I did the same thing as you. Guess I must have messed something up with the implementation. Thanks!

I think your solution (and many others) fail on the test:

Answer should be all 0s?

You're right. Is there an easy way to fix this?

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.

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.

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

Actually your solution is wrong. It passed because of weak tests.

Your code will fail on the case:

Answer should be all zero.

What was the solution to P2 Platinum? I thought that the solution was finding the Kth lexographically largest longest increasing sequence.

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 2

All 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.

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.

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}

I forgot about the sorting step. I believe you are correct.

P1 silver was an oof for me :( Did not consider the binary search solution during contest at all.

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.

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→bas meaning 'amust go afterb' (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 'ifaneeds to go afterb, then discard all vertices in a subtree ofbnot containinga'failson 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:Picture of the testcase: https://i.imgur.com/kNiWbSa.jpg

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:

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 :))

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.

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.

how do i edit my entry?

Well this seems redundant now... :P

Results are out at http://usaco.org/index.php?page=dec18results!

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".

Yes. From the result page: