In SRM there were 849 registered participants — DIV1 383, DIV2 410 + 56 newcomers
DIV2 — easy (250)
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)
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)
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
I had similar idea for hard problem, but I'm not convinced now, that all corner cases are handled properly, I'll try .