Solutions: Placement Test

Problem A: Logo 2 by Bryan

To be presented by Bryan

Meet in the middle.

Problem D: Doors by Yuanchen

Case Analysis

Problem E: Prime Spiral by Ziyi

First preprocess the primes, build the whole map, and do the BFS for each query.

Problem F: Clock Pictures by Yuhan, Bud

For this problem, we are asked to match the position of clock arms on two clocks. We could use KMP (character matching algorithm) to realize this.

Firstly, we cannot use definite position of the clock arms for matching , as the clock could be rotated. To eliminate the effect of rotation, we could calculate the difference between nearby clock arms and use this information for matching. Before that, we could sort the positions of clock arms in convenience of calculating the differences.

Secondly, we pick a clock and use its difference string (it’s a number string with all numbers) and call that string module string, then calculate “next” array for KMP.

As the match could start at any arbitrary position on the clock and if the match stands, there will be a string of n numbers be matched. To do that, we could duplicate the other string (called “text string”), to deal with the cycle situation. And our goal is find a n-number-long match.

Thirdly, we run the KMP algorithm start at the beginning of the text string, stop if we hit the end of the text string or we find a n-number-long match.

The calculation of the next string and how KMP works would be skipped in this analysis.

Hashing is also good for this problem.

If you are interested, you can also check Lexicographically minimal string rotation

Problem G: Cuckoo Hashing by Ziyi

Build a graph where the left part is the indices of the word and the right part is the hash value, and add an edge from each word to the two hash values associated. Then the problem becomes a standard Bipartite Graph Matching using Hopcroft-Karp Algorithm.

Problem H: Guess the Numbers by Ziyi

Tags: Expression Evaluation, “next_permutation” in C++.

int a[5] = {1,2,3,4,5}
do
{

} while (next_permutation(a, a+5));

Problem I: Dinner Bet

Tags: Dynamic Programming, Expectation, Probabilty, Combinatorics

See Problem D in the analysis.

Problem K: Cent Savings by Leo

To capture all the information of a state, we need to store:

1. How many items have not been checked out yet - $i$
2. How many divides have we used yet - $j$
3. How many cents (<10) have not been rounded yet - $k$
   The dp array will then look like: $dp[i][j][k]$, which records the minimum money paid for goods up to $i$ after $j$ divider has been used up and left $k$ dollar as the cents not rounded yet (<10).

Every time, we can either put a divide in front of an item or not, which will increment the $d$ value and round the cents $k$.
Or, we do not put a divide, which will just add the price of the latest product to the cents $k$ and the money already paid.

Here is the recurrence formula:
If a divide is added:
$dp[i][j+1][ mod(p[i], 10) ]$
$= argmin_{j,k}(dp[i-1][j][k] + round(k) + round(p[i]))$

If a divide is not added:
$dp[i][j][ mod(k + p[i],10) ]$
$= argmin_{j,k} dp[i-1][j][k] + round(k+p[i]);$

The final answer is then the minimum money paid up to the last good regardless of the dividers used. (The cents left after the last good is paid needs also to be rounded into the money paid for the last good).