Kick Start

Kick Start 2019 Round C Originally published in Chinese on 2019-05-26; this English edition preserves the original scope and technical context. Wiggle Walk (6pts, 12pts) When moving in an R * C matrix, you can directly skip the grid you have already walked through. The data is guaranteed not to move beyond the given matrix. Solution: Simulation Use a visited array to record the grids that have been visited. If you encounter a grid that you have visited, you will directly skip it and traverse it later. Logically speaking, the time complexity of this method cannot pass the Hidden Test Set, but I don’t know why it passed. ...

Kick Start 2019 Round B Originally published in Chinese on 2019-04-21; this English edition preserves the original scope and technical context. Building Palindromes (5pts, 12pts) Determine whether the substring in the given interval is a palindrome string. Solution: Prefix Sum To determine whether a string is a palindrome, you only need to determine whether the number of odd-numbered characters in the string is less than or equal to 1. However, if you traverse the given interval every time, it will definitely time out, so we need to preprocess the given original string and calculate the prefix sum of each position (the total number of characters from the subscript 0 to the subscript i - 1 position). In this way, the time complexity of querying is only O(1). ...

Kick Start 2019 Round A Originally published in Chinese on 2019-03-26; this English edition preserves the original scope and technical context. Training (7pts, 13pts) There are N people in total, select P people from them, and calculate the sum of the differences between the maximum skill rating of these P people and the skill ratings of other people. $$ \sum_{i}^{j} max(rating) - rating[i] $$ Solution: Sort + Prefix Sum First sort the array, then traverse all consecutive subarrays of length P in the ordered array of length N, and calculate the sum of the differences between the maximum value in the subarray and other values. ...