SCTF16 – Schensted

This was a rather simple challenge in contrast to the value in number of points given (110).

I found this sequence of numbers… can you give me the length of the longest increasing subsequence? Submit in the format sctf{answer}.

We are given a file with $2 \cdot 10^6$ digits. What makes this is easy: the numbers will only consist of single digits.

Obviously, this problem has a big resemblence with $\textsc{Longest increasing subsequence}$, but we have to transform the problem. Hmm…

If we count the number of occurences of each digit, we find:

#0 = 222146, #1 = 222503, #2 = 221808, #3 = 222479, #4 = 222496, #5 = 222060, #6 = 221332, #7 = 222791, #8 = 222385, #9 = 0]

OK, so if we fix a counter for each 0, and replace that digit with the number on the counter, every 0 will be in a sequence $\{0,1,2,...\}$. Then, we do the same with the ones, but we add the number 222146 (the number of 0’s) to the counter for the 1’s. Then, we know that the zero-counter will never exceed this number. Doing so for all digits, we have transformed the problem to $\textsc{Longest increasing subsequence}$.

import schensted, Common

# compute the largest count of any number
coeffs = [schensted.q.count(str(i)) for i in range(0, 10)]

# bookmaking table
counts = {}
for i in range(0, 10): counts[i] = 0
print "[ ] Transforming problem..."

# transform problem into longest increasing subsequence
L = []
for char in schensted.q:
num = int(char)
counts[num] += 1
L.append(num*coeffs[num]+counts[num])

print "[ ] Running LIS algorithm..."
print "[+] Longest subsequence is", len(Common.LongestIncreasingSubsequence(L))


Running the algorithm…

…we find the flag which is sctf{224619}.