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…