Monday, March 23, 2015

BCTF 2015: Experiment


Pertama kali membaca soal ini dan mencoba konek, sepertinya cukup mudah:

Hi, we have a short survey with 50 questions. You can get a flag as award once you finished it.





Seperti ini awalnya:


Karena berpikir bahwa kasusnya akan selalu seperti itu, langsung saya coding, memakai eval python. Tapi ada pertanyaan berbahaya:

Is __import__('os').popen('rm -ri *').read() an integer or not? Answer (yes/no):


Jika ini tanpa -i dan jika saya jalankan di server penting, sudah hilang data saya. Setelah beberapa pertanyaan, tiba-tiba semua berubah:

Time for calculating weird integer sequences.

Contoh-contoh sequence yang diminta:

Description: The prime numbers.
The sequence starts with: 2,3,5,7,11,13,17,19,23,29
(first term is for n = 1)
n = 524, Answer:

Description: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
The sequence starts with: 0,1,1,2,3,5,8,13,21,34
(first term is for n = 0)
n = 689, Answer:

Ini masih relatif gampang, tapi setelah itu mulai random:

Description: Triangle T(n,k) = number of polyhedra (triconnected planar graphs) with n edges and k vertices (or k faces), where (n/3+2) <= k <= (2n/3). Note that there is no such k when n=7.

The sequence starts with: 1,1,1,1,2,2,2,2,8,2
(first term is for n = 6)
n = 26, Answer:

Description: Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.
The sequence starts with: 1,1,2,5,12,33,90,261,766,2312
(first term is for n = 1)
n = 656, Answer:

Dan seterusnya. Setelah dipelajari, sequencenya berasal dari oeis.org, dan kita bisa mendownload sequencenya dari deskripsinya (jika n kecil) atau dari file text b.

Tapi di 5 pertanyaan terakhir, semuanya berbeda, 5 pertanyaan random ini muncul, dan tidak bisa dijawab dengan OEIS:

1. Description: The Prime Numbers Revenge
The sequence starts with: 2,3,5,7,11,13,17
(first term is for n = 1)
n = 23333055, Answer:

2. Description: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers. The sequence starts with: 1,1,2,5,14,42,132
(first term is for n = 0)
n = 3921, Answer:

3.  Number of sets of rooted connected graphs where every block is a complete graph.

The sequence starts with: 1,1,2,5,14,42
(first term is for n = 0)
n = 839, Answer:

4. Description: Shapes of height-balanced AVL trees with n nodes. The sequence starts with: 1,1,2,1,4,6,4,17,32,44,60,70
(first term is for n = 1)
n = 1003, Answer:

5. Description: a(n) = number of partitions of n (the partition numbers) modulo 1000000007
The sequence starts with: 1,1,2,3,5,7,11,15,22,30,42,56,77
(first term is for n = 0)
n = 23371, Answer:

Untuk pertanyaan soal prime, saya memakai https://primes.utm.edu/nthprime/index.php

Untuk catalan numbers,  saya memakai wolfram di raspberry pi 2 (berdasarkan formula dari http://oeis.org/A000108)

Export["catalan.txt", Table[ CatalanNumber@ n, {n, 0, 4000}]]

Untuk Number of sets of rooted connected graphs where every block is a complete graph saya juga memakai wolfram dengan cara yang sama dengan potongan program OEIS.

Untuk soal No 4 Shapes of height-balanced AVL trees with n nodes, menghasilkan tabel dengan Wolfram terlalu lama, akhirnya saya buat versi python berdasarkan deskripsi algoritma dari link ini:


Dan untuk yang terakhir, saya jawab secara manual (copy paste soal ke worlfram), dan hasilnya:

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}




No comments:

Post a Comment