Fuwa 2019冬講習コン #1 Reflection

December 13, 2019

Contest Website

Front Note

Overslept before the contest and cannot join the contest on time.
The number in the bracket is the order of attempt.

Sorting String (1st, solved)

The first problem attempted in the contest. Somehow guessed that KK doesn't matter (it doesn't), and just check whether the multiset of characters in SS and TT are the same.

Rough idea of proof that KK doesn't matter:
Swap the first two elements KK times. Then to swap two adjacent elements, swap them 109+710^9 + 7 times so the total number of swaps(mod109+7)\pmod {10^9 + 7} is not changed.

2D reverse (3rd, solved)

This should be the easiest question in the contest, but I wasted some time as I misread the problem (I mixed up the final and the intermediate state). Also spent some time trying to figure out which is 列 and which is 行.

麻布動物園 (5th, solved)

While attempting this problem I had 2 wrong hypotheses:

  1. For each edge built, merge the two nodes in a DSU. Output the number of disjoint sets.
  2. For each edge built, built a edge on graph from from the higher to lower node. When the nodes are of equal height, build a pair of edges between them. Output the number of nodes with indegree 00.

The second hypotheses is almost right: instead of building a pair of edges between them, merge the two nodes in a DSU. The problem is then solved.

Text Editor (2nd, solved)

This problem seems the most direct problem in the contest so I attempted this after finishing Sorting String.

I implemented a doubly linked list, using the C++ idea of pointers (i.e. adding a null element at the end). It took about 40 lines of code (and I ignored the dangling pointers).

Just after finishing this problem, I realized this problem can be solved using two stacks much more easily. Just store the characters on the left of the cursor in one stack and the characters on the right of the cursor in another.

ビル跳び (4th, 40%)

The first idea that come to my mind is dynamic programming, but then I looked at the scoreboard (nobody scored more than 40) and the constraints for subtasks 1 and 2 (N200N \leq 200), and realized that it can be done by Floyd-Warshall algorithm. Total complexity O(N3)O(N^3).

Tried to look at subtask 3 and 4 to derive a O(N2)O(N^2) solution, but could not think of a solution more efficient then O(N2logN)O(N^2 \log N).