defcon 20 ctf u300 writeup

by NOI金牌贾开,以后这类算法题都归你了:),呵呵

题目给出了一个地址和一个密码,telnet上去后输入密码,得到如下返回信息:

Password: Here come 100000 uint16_t, please tell me how to sort them into

ascending order by sending me pairs of indicies to exchange, one

per line, in the format: <index1>:<index2>

For example to exchange elements 123 and 9821 you should send:

123:9821

Valid indicies are in the range 0..99999 inclusive. Send a blank

line when you are done. If you correctly sort the array in

sufficiently few moves I will give you a key!

You have about 10 seconds to finish, and a 5 minute wait between

successive connections.

<some binary data>

看起来没什么陷阱,只是对题意的理解上有点疑问:

  1. 数据是大端还是小端的?
  2. 输出的下标,是每个数原始的下标,还是基于以前已经输出的交换操作后该数当前的下标

不过,多尝试几次就可以解决这两个问题。(结论分别是:小端;当前的下标)

下面考虑算法的问题。如果输入数据无重复的数,那么每个数在最终序列中的位置是确定的,排序操作相当于一个置换,可以将其分解为环置换的乘积,设共有n个数,分为k个环,第i个环长度为l[i],则每个环所需交换次数为l[i]-1,总共所需最少交换次数为sum(l[i]-1 for 1<=i<=k) = n-k。维护一个指针p,初始位置为数组起始,每次选取p之后的最小数与*p交换并p++,于是每次操作增加了一个环,显然该贪心策略能产生最优解。具体实现时,为保证快速出解,可使用堆或平衡二叉搜索树来维护数据,复杂度为O(n log n)。

但原题数据中显然有大量重复的数,于是无法保证得到最优解;事实上在有重复数据的情况下,求最少交换次数是NP-Hard问题。不过,无论如何,该贪心策略可以保证交换次数最多是n-1的。经过测试,defcon能接收这样的解。

另外这道题还有个很坑爹的地方。原题要求10秒内送回答案,但我的网速较慢,每次送到60%左右时就出现broken pipe。

我一直以为是交换次数太多导致的,但后来让一位网速较快的同学帮忙跑了下,就过了。。。

此条目发表在技术报告分类目录。将固定链接加入收藏夹。

评论功能已关闭。