Codechef Snackdown 2017

This contest is the first time I tried to collaborate with some others. So far, the contest goes well with Rory.

Qualification Round

Snake Procession

Simple implementation.
Use a counter to count the numbers of heads, and ignore all ‘.’ characters. With every tail, the counter decrease by one. Whenever the counter is bigger than 1 or smaller than 0, the sequence is invalid.

Temple Land

Simple implementation.
Check \left [ A_i=\frac{n+1}{2}-\left | \frac{n+1}{2}-i \right | \right ]

Snake Eating

Binary Search.
First sort all snake by length. Thus, we will get x snakes whose length is already >=k. Then, we do binary search in [1,n-x]. What we need check is if \sum_1^{mid} L_i>= \sum_{mid+1}^{n-x} {k-L_i}

Same Snake

Two snakes are the same and they are not parallel to each other, if and only if their intersection point is at their ends.


Preliminary Round A

Team Formation of Snackdown

If and only if the number of participants is even, we can find a formation.

A Temple of Snakes

It is obvious that the cost is minimum when the summit of the temple is biggest. Thus, we maintain a prefix Pre_i which is the highest temple can be built when we use P_i as the summit of the temple, and we do the exactly same of suffix Suf_i. Thus, the highest summit we can get is max(min(Pre_i,Suf_i)).

Consecutive Snakes

We are asked to find x to minimize \sum_0^{n-1} \left | x+L*i-A_i \right | , and also satisfy that L<=x, x+L*i<=R
We can easily find that the cost function is unimodal, so we can use a ternary search to find that point.

Other Problems

Because the other 3 problems are solved by my teammate Rory, I do not have solutions for them. XD


Elimination Round

 

To be Continued…