IOI 2006
All 4 IOI tasks from 2006, organized as individual solution pages.
Problem set
Each entry below goes straight to the public problem page, with the statement, editorial, code, and raw resources kept together.
Beans (Mexicane\ n
Linear Case (No Wrap-Around) Consider first the simpler problem where the beans are arranged in a line. Define: dp[i][0] &= maximum sum using beans 1,, i with bean i not selected, dp[i][1] &= maximum sum using beans 1...
Deciphering the Mayan Writing
Aho-Corasick Multi-Pattern Matching Build a trie from all patterns, recording which pattern ends at each terminal node. Compute failure links via BFS from the root: for each node u with child v on character c, the fai...
Forbidden Patterns (Writing)
Aho-Corasick Automaton + DP We build an Aho-Corasick automaton from all forbidden patterns and then run a DP over the automaton states. Build the automaton. Insert all forbidden patterns into a trie, then compute fail...
Pyramid
2D Prefix Sums Precompute the 2D prefix-sum array so that any rectangle sum can be queried in O(1): S[i][j] = _ r=1 ^ i _ c=1 ^ j grid[r][c]. Then: rectSum(r_1, c_1, r_2, c_2) = S[r_2][c_2] - S[r_1 - 1][c_2] - S[r_2][...