TechJam 2018, Grand Final, Code Squad (Ponder)

Abridged Problem Statement for
TechJam Thailand 2018, Grand Final, Code Squad

Round 1 - Ponder
- 5 minutes for each problem.
- Timer starts as soon as problem statement ends.
- The contestant must arrive at an answer by using a given mini-whiteboard or their laptop.
- The answer must be written and clearly marked as such on the whiteboard or laptop.
- Contestant must rush to take the flag in the middle of the play field. No answer modification afterward.
- After 5 minutes is up, judges will check each contestant's answer for scoring.
- First to solve gets 7 points. Second to solve gets 6 points. Other solvers get 5 points.

Problem names, grouping and order here may be different from the actual competition. (I can't remember.)

==============================

Group A - Problem 1
Vault Passcode

There's a vault which requires 6-digit passcode to unlock. Let's call it S.
You also know that for each 6-digit string T[i], the length of the longest common substring of S and T[i] is A[i].
Given T[1..N] and S[1..N] (which I can't remember), find the passcode. (It's guaranteed to be unique.)

------------------------------

Group A - Problem 2
Array Counting

Let's say we have an array A of size N and these conditions:
- 0 <= A[i] <= N-1, for all i where 0 <= i <= N-1
- A[i] <= A[i+1], for all i where 0 <= i <= N-2
- A[i] = A[A[i]], for all i where 0 <= i <= N-1

Count the number of array A of size N=20 satisfying all three conditions.

------------------------------

Group A - Problem 3
3-term Arithmetic Progression

Let's define 3-term Arithmetic Progression (3AP) as an arithmetic sequence consisting of exactly 3 numbers.
Build a sequence of positive integers not exceeding 30 such that there are no subsequences which are 3AP.
Maximize the length of the sequence.

==============================

Group B - Problem 1
Energy Consumption

There are 1,000,000 creatures of the same species in an isolated environment. Each creature initially stores 1,000,000 kcal. of energy. At any given time, a creature (let's call it A) may decide to eat another creature (let's call it B). A will gain exactly half of B's energy (fractional value is possible) while B will be removed from the environment. There's also an additional limit: for every creature X, X can only eat at most 3 other creatures.

In the final state where there's only one creature left...
- what's the minimum energy possible for that creature?
- what's the maximum energy possible for that creature?

------------------------------

Group B - Problem 2
Student Classroom

There are N students, labeled A, B, C, ... They are separated into two classes: Class 1 and Class 2.
Given M conditions in form of "x and y must be in different classes."
(Can't remember what N, M, and the conditions are.)
Remove 2 conditions such that there's a valid class separation scheme.

- Find the two conditions to be removed.
- Find a list of students in the same class as student A.

------------------------------

Group B - Problem 3
Magic Square

Fill number 1 through 16 into a 4x4 board such that
- cell values are pairwise distinct
- the sum of values in row i must be equal to the sum of values in column i, for all 1 <= i <= 4

Give one such valid solution.

==============================

Group C - Problem 1
Tetris Tiling

Consider fitting Tetrominoes into a finite two-dimensional grid. (Tetrominoes are pieces from the game Tetris: I, L, J, S, Z, O and T pieces, including all of their rotations.) We'll define "gap length" as sum of the length of line segments which are right between two adjacent tiles.

If you have to fit 27 pieces into 12 by 9 grid,
- what's the minimum gap length you could have?
- what's the maximum gap length you could have?

------------------------------

Group C - Problem 2
Currency System

Consider a currency system where the possible denominations are 1, 2, 5, 10, 20, 50, 100, 500 and 1000. It's obvious that for any sums of money, greedy algorithm for finding minimum number of coins/banknotes used always outputs optimal answer.

Add one denomination such that there exists a counterexample where greedy algorithm outputs sub-optimal answer.
- What's the maximum value of such denomination?
- Give one counterexample to the greedy algorithm when that denomination exists in the system.

------------------------------

Group C - Problem 3
Hamiltonian Tiling

Consider building a shape with a lot of 1x1 blocks where
- each block's sides must be perfectly aligned with other blocks, and
- there are no holes in the shape.

Let's define a Hamiltonian Cycle as a *cyclic* sequence of blocks such that
- for block x and y which are adjacent in the sequence, y is reachable from x within 1 unit of movement (up/left/right/down),
- each block is visited exactly once

We want to build a shape such that these conditions hold:
- there exists a *unique* Hamiltonian cycle in the shape, and
- there's exactly one way to split blocks into two groups such that each group of blocks has a unique Hamiltonian cycle.

For example, 8 blocks forming 2x4 rectangle is a valid solution because
- there exists exactly one Hamiltonian cycle, and
- the only way to split is to split into 2x2 rectangle, each of which also has a unique Hamiltonian cycle.

Build a shape consisting of exactly 32 blocks following the conditions.

==============================

Group D - Problem 1
Picture Hanging

Let's say you want to hang a picture with a rope.
There are three pins on the wall: A, B, C from left to right.
Find a way to tie the rope around the pins satisfying these conditions:
- If one of A or C is removed, the picture doesn't fall.
- If B is removed, the picture falls.
- If both A and C are removed, the picture falls.

------------------------------

Group D - Problem 2
Greedy Traveling Salesman

There are 12 points lying on a Euclidean space like this:
1 2 3 4
5 6 7 8
9 10 11 12
Each pair of adjacent points on the same row or column is exactly one unit apart.

Let's say we have an algorithm to solve TSP greedily:
- pick an arbitrary starting point
- move toward the nearest point which hasn't been visited yet
- once all points are visited, return to the starting point to form a cycle
In case there are multiple "nearest points," pick one arbitrary.

In the best case scenario, the algorithm might output something like 1, 2, 3, 4, 8, 12, 11, 7, 6, 10, 9, 5 which has the total distance equals 12. But, there are also cases where the algorithm performs badly.

Find one possible output from the greedy TSP algorithm where total distance >= 160/9.

------------------------------

Group D - Problem 3
Prime Number

Find longest sequence of consecutive prime numbers which sums to 10^6.