The ranklist will be score-based (ie ties will not be broken)

Even if you just begin declining every code which is the same as the previous one, it'll be great

why? ties aren't broken.

Can you describe your solution ?

5000 moves

Our solution does 328 moves in a 10x10 grid and the empty cell at bottom-right corner. Out solution also brings the empty cell at top-left corner first :)

If m >= 3, Then just keep repeating the same till the time there are more then 2 balls left. Move closest empty cell to (1, 1). And 2 other balls to (1, 2) and (1, 3). Then execute third query. Similar case for n >= 3.

This looks like 3*20*99 (> 5000) queries in worst case. However after first time, a third query is executed, an empty cell will always be in <= 2 distance to (1, 1). So that makes it around (2*20*99 + 2*100). In reality, the answer was always < 1200.

You can apply ternary search on distance to be moved.

Code

What i did was to binary search on the possible start point in the [a,b] range. Let us consider I am at point x as starting point and now i will calculate the distance each snake will move starting from the snake (snake are sorted based on their starting position) and at this time i will also calculate how many snake lie left and right to the position where they have to placed according to point x. If left is greater then move left otherwise right.

you can create two dp arrays one to right and the other to left , right[i] = min(right[i — 1] + 1 , arr[i]) , left[i] = min(left[i + 1 ] + 1 , arr[i] ) then at any position you can know what is the maximum hight for the temple and calculate the number of moves needed then minimize.

sorry for bad english

You are right. I ternary searched with interval divided in 3 parts, and it should've passed. I was very confused that it didn't. Now I see why. The model solution was based on interval divided in 2 parts, and that is wrong.

So this problem should be either taken off the contest, or solutions should be rejudged.

f(x) will be first be non-increasing and then only non-decreasing. So, if f(mid) = f(mid + 1), we know that for all points x less than mid, f(x) will be  ≥ f(mid). So, we can safely shift to the right in this case.

Note that the non-increasing/non-decreasing part can also hold for 0 points in some cases.

I found that we can begin the consecutive snakes from A to B — N * L and the optimal solution my be between them if you sorted the beginning of every snake and let the optimal solution at X then the result of X + 1 is greater than the result of X and X — 1 too so i used ternary search and got correct answer

The function can be transform into the form:

|x - a1| + |x - a2| + ... + |x - an|

Each |x - ai| is a convex function, so sum of them will also be convex.

So f(x) = f(x + 1) will only happen when you are at the optimal point.

I created 2 segment trees for vertical and horizotal, then coordinate compression. Notice that the same snake cannot protect both horizontally and vertically, as no snakes are allowed inside poison room. Therefore, we can separately solve horizontal and vertical.

I did a type of DP on segment trees. After separating the snakes horizontally and vertically, we can apply the solution on both set of snakes separately.

dp[ 1 + far_right[snake.l-1][snake.r] ][snake.r] = min ( dp[snake.l-1][snake.r] ) + 1

where far_right[a][b] is the rightmost position that has the value min ( dp[snake.l-1][snake.r] ).

The complexity can be brought down by maintaining segment tree to do dp.

Well, the problem is reduced to finding minimum number of intervals that can cover our range from (N — K)/2 + 1 to (N + K/ 2). So, just sort all the range according to their starting points and then keep on going for every range with starting point <= (N — K)/2 + 1, find the largest ending point. After that keep repeating the same.

I solved it with greedy approach .It's easy to see that snake can defend poison vertically or horizontally,so we will solve them seperatly.Problem is equivalent to pick the least number of intervals (snakes) such that their union is interval [(n-k)/2+1,(n+k)/2].So sort snake wrt to their left bounds of intervals,and set variable x=(n-k)/2+1,so in the interval of snakes such that l ≤ x we will pick one with largest r (right bound of interval),and update x = x + r,if we can't find snake such that l ≤ x return -1 else continue with algorithm untill .

All the problems are already available in practice section. For accessing them directly, you can remove "SNCKPA17" from URL, and go to practice page directly.

Example:

Contest problem: https://www.codechef.com/SNCKPA17/problems/TEAMFORM

Practice problem: https://www.codechef.com/problems/TEAMFORM

Sorry I misread your comment

I'd try something like this:

Fix the middle, notice that if you calculate f(x) (going x to each side), it will be a sum of

a[i] if x < |i — mid| and |a[i] — |x + 1 — |i — mid||| = |a[i] — (x + 1 — |i — mid|)| otherwise.

This means that it will be constant for some time and then it will be something that goes down and then it goes up (each part of the sum that is). This also means that the minimum will be on either the extremes of the possible interval or in the transition point from the downwards slope to the upwards slope of some part of the summation. This means that you solve only decreasing the same way you would normally and then for each i, guess that a[i] will be on some side or on the middle of the temple or the sides go until they can't grow (fixing a[i] in the middle) and you'll find the best answer.

To find the answers outside the normal part, use a trick like this: have 2 arrays where l[i] = a[i] — i and r[i] = a[i] + i. Use a merge sort tree to answer queries of the type: sum of elements in a range of an array where arr[L <= i <= R] <= k and you'll find each answer quickly. For example:

a = 1 2 3 2 1, l = 0 0 0 -2 -4, r = 2 4 6 6 6. You should use l to get the cost for the left part and r for the right part (don't forget to sum the parts where it should be 0). The cost of each side will be something like:

((number of elements <= constant) * constant — sum of elements <= constant) + (sum of elements > constant — (number of elements > constant) * constant)

If you put a sequence of a temple in l, the left side should have the same numbers and in r the right side should have the same numbers. The constant is the value of l[i] and r[i]. This same trick can be used to transform some strictly increasing problems to not strictly increasing (for example http://mirror.codeforces.com/problemset/problem/713/C). Given that this solution works, it has a complexity of O(nlog^2n) or O(nlogn) if using fractional cascading.

I'm not sure if this problem is even solvable, this is just a idea :P, it seems I overlooked some important things