Kakao Code Festival 2018 Finals: Top Score of 6 Problems Solved Out of 8

Kakao held the offline finals of Code Festival 2018 at its Pangyo office on August 25. Sixty-four participants who passed the preliminaries competed, and a total of 8 problems were presented in the finals.

Problem Solutions and Difficulty

The final problems required advanced knowledge of algorithms and data structures. The solution approaches for the key problems were as follows:

• Match Prediction: Solvable via brute-force search considering 36 possible cases.
• KakaoMoney: A problem requiring analysis of contradictions in log data and using the Greatest Common Divisor (GCD) concept to reverse-calculate the currency unit.
• Islands: Utilized the graph theory concept of Articulation Points to determine connectivity changes when removing a specific island, or used Flood-Fill on planar graphs to analyze containment relationships.
• Opening Treasure Boxes: A DP problem calculating the minimum replacement cost to make a string a palindrome in linear time O(N).
• Creating a Quiet Dormitory: A problem minimizing the sum of path costs in a tree structure, solvable in O(N log²N) time by combining Dynamic Convex Hull and Small-to-large techniques.
• Magnet Toy: A problem determining node removal order using Clique structures in a graph, approached with an O((N+M)logN) time algorithm.
• Helicopter: A shortest path problem within an orthogonal polygon allowing exactly one diagonal move, solved with O(N² logN) time complexity using vertices of new regions and ternary search.

Results and Feedback

In the finals, the first-place winner solved 6 out of 8 problems. As pre-announced, certificates and prizes were awarded to the top 31 participants. Although there was significant feedback that the final problems were more difficult than the previous year, participants continued to show enthusiastic engagement.