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 digits. What makes this is easy: the numbers will only consist of single digits.

Obviously, this problem has a big resemblence with , 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 . 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 .

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}`

.

### Like this:

Like Loading...