Author: Ryan Leonel Somali
First, let’s take a look on how long the string S will be (noted by |S|). As mentiones in the problem statement, |S| can be calculated by the formula:
and it is equal to:
You can do those things either by working on the math equation or simply by observing the length pattern.
[Edit: Oh! I forgot that the string length has been mentioned in the problem statement]
The largest n was 31, so we can’t just generate Sn as |S31| is 231 (2,147,483,648) – we need 2GB memory! not mentioning the time to generate it.
Finding the substring (k, m) – length m and start from k-th character – directly is quite difficult. It will be much easier if we build a function F to find the i-th character of S, so to get the substring (k, m) we only need to iterate i in F from k to (k + m).
Let F(i, n) be the i-th character in Sn (zero-based index). If i is either 0 or 2n-1, then we just have to return ‘(‘ or ‘)’ as they should be the first and the last character respectively. Otherwise, we should find j where the i-th character is located in Sj, and solve it recursively. Note that the i-th character of Sn will be equal to the (i – 2j + 1) character of Sj. So, F(i, n) can be written as:
function F(i, n) if i = 0 then return '(' if i = 2n-1 then return ')' for j = 1..n-1 if i <= 2i+1-2 then return F(i - 2j + 1, j)
The time complexity of F(i, n) is O(n) or equal to O(lg |S|). So the total time complexity to find substring (k, m) in Sn is O(m.n), which is enough to pass all the tests within time limit.
This problem was solved by 16 teams. The first team to solve this problem: KbPeckers (minute 68). Seed who was the second team also got accepted in minute 68.
- Title Page
- Problem A – Anti Brute Force Lock
- Problem B – Bonus Treasure
- Problem C – Panda Land 7: Casino Island
- Problem D – Disjoint Paths
- Problem E – Expert Enough?
- Problem F – Free Parentheses
- Problem G – Greatest K-Palindrome Substring
- Problem H – Hyper-Mod
- Problem I – ICPC Team Strategy
- Problem J – Jollybee Tournament