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…

Skärmavbild 2016-04-10 kl. 22.13.03

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s