This contest is the first time I tried to collaborate with some others. So far, the contest goes well with Rory.
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.
First sort all snake by length. Thus, we will get snakes whose length is already . Then, we do binary search in . What we need check is if
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
If and only if the number of participants is even, we can find a formation.
It is obvious that the cost is minimum when the summit of the temple is biggest. Thus, we maintain a prefix which is the highest temple can be built when we use as the summit of the temple, and we do the exactly same of suffix . Thus, the highest summit we can get is .
We are asked to find to minimize , and also satisfy that
We can easily find that the cost function is unimodal, so we can use a ternary search to find that point.
Because the other 3 problems are solved by my teammate Rory, I do not have solutions for them. XD
To be Continued…