To be presented by Bryan
Meet in the middle.
Case Analysis
First preprocess the primes, build the whole map, and do the BFS for each query.
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
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.
Tags: Expression Evaluation, “next_permutation” in C++.
int a[5] = {1,2,3,4,5}
do
{
} while (next_permutation(a, a+5));
Tags: Dynamic Programming, Expectation, Probabilty, Combinatorics
See Problem D in the analysis.
To capture all the information of a state, we need to store:
Every time, we can either put a divide in front of an item or not, which will increment the value and round the cents .
Or, we do not put a divide, which will just add the price of the latest product to the cents and the money already paid.
Here is the recurrence formula:
If a divide is added:
If a divide is not added:
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).