In SRM there were 849 registered participants — DIV1 383, DIV2 410 + 56 newcomers

DIV2 — easy (250)

(link)

if k == 1, the answer is 0 (we have consecutive sequence of length 1 already)

For k == 2, one can use sort, find the smallest difference d and return d-1.

Unfortunately elements in input were distinct, so one corner case less :-(

DIV2 — medium (500)

(link)

It's a graph problem, one have to find how far we can move in 1000 steps. On empty board our max coordinates are like -1000..1000, so I modified those to be in 0..2000 and used 2D array to prevent visiting (processing) same point twice during BFS from (0, 0) coordinate... To prevent moving on invalid coordinate I simple marked those as visited before queue processing.

So I used queue, added (0, 0) to it with 0 as number of steps. Then while q is not empty I removed first position from queue, marked this position as visited and added next steps if the number of steps so far is less than k.

My Java code which I used in contest available on ideone.

Note: My solution is checking current x coordinate, in problem statement is asked "where you can get in (exactly) k seconds (steps)", but notice, that also to stay at the same position is valid move.

DIV2 — hard (1000)

(link)

All solutions I saw just handle few cases. fluxay's simply found values for LEY ( Less than or Equal Your score), LEY3 (...your score + 3), LEY6 (...your score + 6), R (rest, which is basically greater than you score + 6). Then he calculated the number of victories V = LEY + LEY3 + LY6 + R + 1 (basically number of teams, plus one for our team). We can let LEY and R to win twice -> V -= 2 * (LEY — R) and let those teams in LEY3 win once -> V -= LYE3. Now we have to check, whether we didn't let too many teams to win (V is lower than zero, if so set it to 0) and the result is R + (V+1)/2 + 1 (+1 for 1-based index)

In pseudo code:

// LEY, LEY3, LEY6 and R calculated from input
V =  LEY + LEY3 + LY6 + R + 1
V -= 2 * (LEY — R)     // let those, that has more points to win twice and also those that cannot go ahead of us
V -= LYE3              // we can still be better, it those in this group win just once
return R + (V+1)/2 + 1 // every second victory remaining moves us one rank down

Opened questions:

I had similar idea for hard problem, but I'm not convinced now, that all corner cases are handled properly, I'll try .

Links:

• I liked the most fluxay's solution
• CF announcement
• official editorial