It is 4 hours

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.

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

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.

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

Yes it's done for sure.

Vector hashing and unordered map works fine for 11/11

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.

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

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

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

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.

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.

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

how do i edit my entry?

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