Snackdown PreElimination Round A. Consecutive Snakes. Problem Code: CONSESNK

general
,
1

How to solve this problem ?

2

I just created a post about this via “ask a question” but i can’t find it :(, so i will write it here again.

First lets sort the snakes in ascending order of their heads.
We know that the snakes will be consecutive i.e. they will form a single segment with length n*L in the end.

You need two observations:

Let’s assume this segment will end at some point X. How can you calculate the minimum score so that the snakes ‘fill’ this segment? Lets call this score f(X).
Well, greedy works here. The rightmost snake will go to the rightmost slot in the segment, the second rightmost to the second rightmost slot segment … and the leftmost snake to the leftmost slot in the segment.
This takes O(n) time for any point X. The bruteforce approach would be to try all valid for X betweem a and b. As you can see this would take O((b-a)*n) time, which is not good.

You can notice that the value of f(X) tends to go down from -infinity, until some point X’ (the minimum which we are looking for), and after that point it can only go up .
In other words this means that if it is best to end the segment at some point X’, it can only be worse to end the segment more to the left of X’ or more right of X’. It turns out, f(X) is a unimodal function. Non-increasing up to a minimum and then non-decreasing.

How can we find a minimum of a unimodal function?
By ternary search

This is maybe the first or second time i encounter the need for ternary search in a contest and my first time ever implementing it :).

I hope this helped :).

2 Likes
3

Ok.I did it in the following manner.
First I brought all the snakes within the given range and calculated the initial cost incurred in doing so.
That is all the snakes having their head coordinate less than “a” are brought to “a” and similarly for all the snakes with head position>=“b-l”.
Next I sorted the array based on x coords of their heads.
Now, notice one thing. In the final configuration all the snakes will be on a straight line and the starting point of that line will be between “a” and “b-nl".
So, initially I computed the cost when the starting point is at “a” and when at "b-nl” then did a binary search
to find the minimum cost.
What to I mean by computing cost? This means suppose I am computing cost for coord x>=“a” && x<=“b-n*l”
I position the head of first snake to x ,second to x+l and so on and compute the cost in doing so.

1 Like
4

Try to save what you wrote by using “Select all and Copy” . If server runs into error while posting it, chances are the data is lost. In that case you can then copy paste what you wrote again. :slight_smile:

1 Like
5

Can you please explain why the binary search works, when the function is not increasing/decreasing, but as i pointed out above, it is unimodal ?

6

I just found out that binary search can be modified to work on a unimodal function:

1 Like
7

Here is another approach.

Assume S_1 \leq S_2 \leq \dots{} \leq S_N, then it’s obvious that in the final configuration they will maintain the same order.

Now, suppose that a configuration starts at position K, then the cost of that configuration is C(K) = \sum\limits_{i=1}^{N} |K+(i-1)L-S_i| = \sum\limits_{i=1}^{N} |K-(S_i-(i-1)L)| = \sum\limits_{i=1}^{N} |K-w(i)|.

w(i) can be computed once after read and sorted the input.

We want to minimize that sum and so we can choose K as the median between the w(i).
Of course if that K is out the [A, B] interval we can set it as A (if is less than A) or B (if it is greater than B).

The last part is not that hard to prove. :slight_smile:

4 Likes
8

Hey vash96
I used the same approach but got WA :frowning:
Can you figure out error in my code.

Program Link:
https://www.codechef.com/viewsolution/13860037

9

were the other questions except first two were of DYNAMIC PROGRAMMING ?

10

I solved all without dp.

11

Actually we can also use binary search


long maxX = B - (L * N);
    long lo = A , hi = maxX - 1;
    long opt = A;
    while(lo <= hi) {
        long mid = (lo + hi) / 2L;
        long c = f(mid);
        long cc = f(mid + 1);
        if(c >= cc) {
            opt = mid + 1;
            lo = mid + 1;
        } else 
            hi = mid - 1;
    }

since the graph is convex , for all the points less than the minimum f(x) >= f(x + 1) and for all the points greater than the minimum f(x) < f(x + 1) using this idea we can binary search the answer

12

I also did the same.

13

I did all the maths, came up with w(i) … just this part was missing: so we can choose K as the median between the w(i)
Can you share a proof of this also.

14

I can’t beleive it. I asked this exact problem on stackoverflow 3 years back!! https://stackoverflow.com/questions/23452479 . Someone has said it perfectly, ‘too much work kills your brain’

2 Likes