Stop daydreaming...

Where is div2 announcement?

No

J can be solved by binary search on the answer and using max flow to check if it can be done.

For L, notice that in a valid tree, there is an edge between nodes a and b if and only if the sum of the size of a's set containing b and the size of b's set containing a is equal to n. Then once we have all the pairs which must be edges, we check if it forms a valid tree.

J: Binary search the answer. Suppose we have to check if each student can send no more than k gifts. Create a flow with a source s, a sink t, m vertices represent a student pair (p_i mean i-th pair) and n vertices on the right (stu_i mean i-th student). For pair i, create edge (s, p_i, 1) and two edges (p_i, stu_xi, 1), (p_i, stu_yi, 1). For student i, create edge (std_i, t, min(deg_i, k)) with deg_i mean the number of student pair that has student i. Run Dinic max flow algorithm (which work in O() due to Karzanov theorem) and check if max flow equal to m.

There's a O(m^2) solution for J without binary search.

http://catalog.lib.kyushu-u.ac.jp/handle/2324/14869/IJFCS-revision.pdf

Official rank list

Official rank list + unofficial commands

First observation. Let's wait only in the start point. Now to eat the i-th food the dog need to start in any moment from
[t_i — i, T — i -1].

Now we need just count the intersection of maximum number of segments.

when m = n your solution is O(N^2) :)

Think about binary search.

First of all, it's not that easy. The fact tourist solves it in 4 minutes doesn't make it easy for a 1800 person. Don't let the standings deceive you.

Check this problem (solution is in the editorial for CF round 200).

343C — Read Time

You can use some data structure like binary search tree to get an O(nlgn) algorithm. In C++, you can use std::set conveniently. Just keep updating the answer queues while iterating the array. Without storing all answer queues, we can use next[] array to record the next item of the current item in the final answer queue. And we use std::set to store the last items of each queues. Then we can use upper_bound to find out the proper queue we should append the new item to.

This is my solution: http://codeforces.net/contest/847/submission/30470282

Greedily, the answer must happens when the dog waits at the start point for some seconds and then run&eat without waiting. So we just need to try how much time the dog waits at the start point.

Optimize the trivial O(nT) DP solution.

Guess I am too late but probably might help others.

Let $$$M$$$ be the max possible sum we can generate. Then, $$$M=\frac{N * (N - 1)}{2}$$$. Firstly, if $$$K > M$$$, then ans = "Impossible". Otherwise, we can prove that we can always generate a sum of $$$K$$$.

My observation was this: We can obtain $$$M$$$ by sequentially nesting all brackets. Something like this "(((...)))". We can represent this by a sequence $$$S = 0,1,...,N-1$$$ which corresponds to the nesting values of the opening brackets from left to right. Now let's say we want to make a sum of $$$M-1$$$, what we can do is, simply change the nesting value of the rightmost opening bracket, which is currently $$$N-1$$$ to $$$N-2$$$. So, $$$S = 0,1,...N-2,N-2$$$. Similarly, if we want to make $$$M-2$$$, we can decrease the second last number, which is currently $$$N-2$$$ to $$$N-3$$$. So, $$$S=0,1,...,N-3,N-2$$$. We can regenerate the resulting string from sequence $$$S$$$ by any ad-hoc method.

What we are essentially doing is: every time we want to decrease the sum by $$$1$$$, we decrease the nesting value of the leftmost occurrence of the max nesting value in the sequence $$$S$$$ by 1. Using this pattern you can generate all sums from $$$0$$$ to $$$K$$$. Others might have a more elegant approach, but unfortunately it wasn't discussed.