Problem Discussion: NAQ 2018

A - Bingo Ties

Bingo game

• If two cards have a same number, that number is the last to be called.

• Need to consider the case that someone wins before the tie occurs.

• Try every pair, construct a winning sequence, and then check all possible subsequence of length 5 of that sequence.

• To check the subsequences quickly, encode the numbers using a polynomial (remember to sort it in increasing number), and put the values in the hash table (unordered_map).

C - Ebony and Ivory

Tag: DP

• Construct a table $cost[f_l][f_w][hf]$ ($f$ for finger)

• Then we can use dynamic programming $dp[cur][cur_f] = \min_{somf=1}^{5} dp[cur+1][some_fin] + cost[cur_f][some_f][half steps]$

D - Froggie

Tag: read the problem carefully, think about cases.

• Need to keep track the last car in the lane and calculate the positions of the other cars in the car.

• Need to determine which cell is safe for the frog (using the speed of the cars)

• The original position of the car is safe.

• Create all possible cars in the lane to avoid edge cases.

• The frog might re-enter the lanes.

• The frog will die if it steps out of the left edge or the right edge of the table.

E - Fruit Slicer

• Line crossing most unit circle

• Find the tangent lines of two circles (internal or external lines), and calculate the number of circles cut by it.

• Using rotation to prove the solution.