CSAcademy Round 34

CSAcademy Round 34 was today, It was a while since I did competitive programming and surprisingly I ranked 9, it seems I perform relatively fast when facing easy problems.
The hardest problem was about counting the number of sub-polygons that contains a given point . My approach was solving the inverse problem i.e the number of sub-polygons that does not contain the point.

For every vertex of the polygon, we can find the furthest vertex j such that is at the left of the segment ij, now we can create a subpolygon that does not contain just by choosing of the vertices that are between and

CodeChef June Cook-Off 17

Last sunday was my CodeChef Cook-Off round. Problems were not difficult, but I tried to deliver a nice problem set. Problems were inspired in chess (KNICOV), convex structures (ADADET), the double cycle cover conjecture (SNACKUP), the difference between the center and the centroid in a tree (CENTREE), and invariants on binary strings when fliping segments (ADACRY).
I didn’t had too much time for testing and some other notorious coincidences were the cause of an inconvenient in the chess problem. The statement was very simple: Place the minimum number of knights on a board of nxm () in such a way that every cell either contains a knight or is attacked by one. For there is a simple pattern, I thought that the same pattern applies for , but the additional row makes possible to use less knights. During testing we found that the naive approach of minimum vertex cover is incorrect, but we missed the dynamic programming solution.
Problem SnackUp was about finding a set of cycles that covers every edge twice, I expected it to be at least the second hardest problem of the contest, but it turns out that I overcomplicated my solution, and it was indeed the second easiest problem.
Problem CENTREE was also an easy problem, but even ACRush and tourist got one wrong answer.