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

To be Continued…