Paken Cup 2019 Reflection

December 26, 2019


Foreword & Result

Sleeping is evil.

Paken Cup 2019 Result

A: パ研合宿 2103 (100 marks)

Output BA+1B - A + 1.

B: 多数決 (100 marks)

Count the number of black and white, and output the one with more counts.

C: カラオケ (100 marks)

Calculate the score for the group for all pairs of songs then output the maximum.

D: パ研軍旗 (100 marks)

Vacation DP. Compute the cost of red, blue and white for each column beforehand, then apply O(N)O(N) DP.

E: 大きなクリスマスプレゼント (78 marks)

For subtasks 1, 2 and 3, a DFS/BFS to count the number of cells in each component will do.

For subtasks 4, 5 and 6, we can precompute the number of connected squares of size KK for each KK. Then we can perform a DFS/BFS to count the number of connected squares, considering each size KK separately.

Combine the two solutions and we can get 78 marks.

From Twitter, it seems that we can solve the problem by computing the largest square that each cell can store using 2D partial sum and binary search, then use union-find tree to merge the cells after sorting the queries...

F: クリスマス飾り 2 (38 marks)

For subtasks 1, 2 and 4, we can simply exhaust the 2 starting points and count the number of ornaments we can preserve CC. Then the answer is NCN - C. The time complexity is O(N3)O(N^3). (How do I modify this idea to be O(N2)O(N^2)...)

For subtasks 3, we can simply scan the array to count the number of distinct segments DD after each modification, and the answer is NDN - D.

G: プレゼント配り 2 (22 marks)

Implemented greedy and O(NM2)O(NM^2) DP for subtasks 1 to 3. (How do I pass subtask 4...)

H: パ研王国を守れ! (38 marks)

I implemented a greedy algorithm to check that if there are 'X' in each direction of each 'Q', and block them if there is.

Conclusion

The problems are interesting, and the subtasks are quite helpful. Thanks to @e869120, @square10011, @tatyamprime and @noimikyopro.