Everybody have 0 points right now

I found the link in other topic — http://scoreboard.ioinformatics.org/ Thanks to jonathanirvings !

As there is just one query for each input, the problem is simply shortest path with all edges have cost = 1, so a simple BFS can find out the answer, and the answer is equal to the minimum cost minus 2 as the answer does not count S and T.

Find a path from S to T. Then answer = number of bridges on that path

The official page seems to have the wrong links at the moment ... thanks!

45.45

100

6!=720>243=3^5, so it's impossible to judge this in 5 moves (however some nontrivial reasoning stands behind that and it's very easy to get it wrong).

Solving problems at home without pressure is easier than in the IOI contest hall.

There is testing and discussion in schedule. Contestant are able upsolve the problems. That should be the reason. But I do not know for sure.

The contest judge was really slow (20 min for feedback on average), so some submissions got scored only after the 5h (sometimes like 1/2h after the 5h block !)

is the issue fixed ??

Circle

Here is diagram:

I don't yet have the full idea but my impression is that the main difficulty is deciding how many "full circles" to make.

Once you decide that and complete the "full circles" you're left with two 1-D problems (one for each "half" of the circle) where the optimal strategy is clear — just keep giving the gadgets to K most distant teams.

http://codeforces.com/blog/entry/19492

But when you compare a[4] with (a[1], a[2], a[3]) then if you get a[1] as the result, then you don't know if a[1]<a[2]<a[3]<a[4] or a[4]<a[1]<a[2]<a[3] is the correct order.

Yeap, it will be only correct this way: if you have two blocks L, R.
If L.mx > R.mx then insert R in L, else insert L in R.

It will be 8 operations in total (1 for getting maximum).
That's what I wrote (it got 55,55 pts)

I was thinking about the same thing, but I'm not sure if you can really update the segment tree efficiently (at least not while also keeping the fractional cascading). If you can do it, then I'd be interested in how this is done (I've spent a bit of time thinking about this, but I might be missing something).

However, I thought about another solution which doesn't require segment tree updates (only queries — thus, with fractional cascading, we get truly O(log(N)) per query).

First, let's assume that all b[i]'s are distinct. If they aren't, it's not difficult to extend all the intervals slightly so that all the equal b[i]s are mapped to distinct positions after the renumbering (e.g. if you have 3 b[i]s equal to 7, they can become 7.1, 7.2 and 7.3).

Then we sort the k[i]s in each query and we maintain a stack with the queries which we will do next for finding the intervals which "cover" a k[i]. An element of the stack consists of two intervals [p,q] and [r,s] and represent a query in the 2D segment tree (all the intervals having p <= a[i] <= q and r <= b[i] <= s). Initially the stack is empty.

We will consider the teams in increasing order of k[i]. If the stack is empty, we add to the stack the pair of intervals ([1,k[i]], [k[i],MAX]). Otherwise, let ([p_U,q_U],[r_U,s_U]) be the intervals at the top of the stack. Because of the way the algorithm works, we will have: p_1=1, p_V=q_(V-1)+1, s_1=MAX, s_V=r_(V-1)-1. This says that the intervals [p_X,q_X] are adjacent to one another and have increasing left endpoints, while the intervals [r_X,s_X] are adjacent to one another and have decreasing right endpoints (as we move from bottom to top).

If r_U > k[i] then we add to the top of the stack the pair of intervals ([q_U + 1,k[i]], [k[i], r_U — 1]) ; otherwise we only modify q_U and set it to k[i].

After this, we go through the elements of the stack from top to bottom, until we remain with zero needed intervals (which is initially equal to k[i]) or until the stack is empty. We first make the query [p_U,q_U] x [r_U,s_U], corresponding to the top of the stack (if r_U < k[i] then we first set r_U = k[i]). If the number of intervals is less than or equal to the needed number of intervals, then we pop the element from the stack and decrease the number of needed intervals accordingly. If the stack is not empty, then we update q_(U-1) and set it to q_U (we basically extend the interval [p_(U-1),q_(U-1)], which is now at the top of the stack, to [p_(U-1),q_U]). If, however, the query for [p_U,q_U] x [r_U,s_U] has more intervals than the number of needed intervals, then we need to find X = the Y^th smallest right endpoint among all these intervals (where Y=number of still needed intervals). What this means is that among all the intervals with left endpoint in [p_U, q_U] we need to use all those which have the right endpoints in [r_U,X]. We "mark" this by setting r_U=X+1 (i.e. by reducing the old interval [r_U,s_U] to [X+1,s_U]).

If the explanation above is too technical, think of the stack as a set of disjoint queries in the segment tree, in increasing order of priority (top to bottom). Essentially, you always want to consider intervals with right endpoints close to the current k[i] (but >= k[i]) and with left endpoints <= k[i]. As we advance with the index i, we get new left endpoints which are valid for the current i (those between k[i-1]+1 and k[i]). From the intervals with these new left endpoints we want to consume first those intervals whose right endpoints are smaller than any right endpoint of a remaining interval which has a smaller left endpoint than them. And once all such intervals are consumed, we "add" the remaining intervals with larger right endpoints by extending the interval of left endpoints from the new top of the stack to also contain [k[i-1]+1,k[i]].

There are O(M) push and pop operations and, thus, there are O(M) 2D segment tree queries (which can take O(log(N)) if we use fractional cascading).

In my solution I also used an additional operation which may be called O(M) times: finding the Y^th smallest element (right endpoint) in a 2D range. Of course, we can use binary search with range count queries on the 2D segment tree to support such an operation in O(log^2(N)). But we can use another 2D segment tree with fractional cascading in order to support this operation in O(log(N)) time, too.

I would be interested to know what the contestants which scored full points during the competition implemented.

Here's my solution:

We'll optimize the naive solution using persistent segment trees. Precompute, for each i, the persistent segment tree persist[i], which contains the b values of all intervals that intersect i. As we process the values of K, keep a persistent segment tree used, which contains the b values that have already been used. We can think of the values available to us as (persist[K[i]] - used). We update used in like this:

def walk(avail, used, K) // Suppose we took the first K values available in (avail - used). Then this function returns the new persistent segment tree representing the used values
{
    if (avail.size - used.size < K)
        return FAILURE
    let leftSize = avail.left.size - used.left.size
    if (leftSize >= K)
        let newLeft = walk(avail.left, used.left, K)
        let newRight = used.right
    else
        let newLeft = avail.left
        let newRight = walk(avail.right, used.right, K - leftSize)
    return (newLeft, newRight)
}

It's on 30.7. @ 9am (Almaty time). Tomorrow is a break day.

Problem task of day 1: https://acm.math.spbu.ru/ioi-2015-day1/

I wonder if horses are inspired by the problem of computing the optimal selling points for a stock given its history.

My solution for horses ... We can notice that the answer is the maximum i that satisfies ( X[i] * X[i-1] * X[i-2] * ... X[1]) * Y[i] is our answer (modulo 10^9+7 of course) if we replace each X and each Y by its logarithm we can notice that it will turn into summation we make a simple summation segment tree with lazy probagation this solution works in N log N + M log M and gets 100 points

There exists pastebin for pasting your codes and a bunch of similar sites. It's preferrable to use them instead of writing long comments. Just describe the approach in a comment and attach a link to your code next time.