Google Code Jam 2021 Round 1a Solution
Append Sort
Problem
Given n-length array, $n \leq 100$, each number is in $1 \leq X_i \leq 10^9$, make this array strictly-increasing by appending digit to any number. Return minimum number of digit needed.
Solution
Greedy, if $X_i \geq X_{i + 1}$, try to make $len(X_{i + 1})$ equal to $len(X_i)$ or $len(X_i)+1$ by comparing their prefix.
Prime Time
Problem
Given a set of at most $10^{15}$ primes, each prime within $2 \leq p_i \leq 500$, return maximum value of $\sum_{p_i \not\in S} p_i = \prod_{p_i \in S} p_i$ if there exist valid solution.
Solution
Test set 1-2 (at most 100 total primes): Since $W = \sum_{p_i \not\in S} p_i \leq \sum p_i \leq 50000$, the product of primes is inside 50000, so we can search for set S such that $\sum_{p_i \in S} p_i + \prod_{p_i \in S} p_i = W$. This can be done in a DP-like way.
Test set 3: W is very large. $\prod_{p_i \in S} p_i \leq \sum p_i \leq 5 \times 10^{17}$, each prime is at least 2, so $|S| \leq 60$, so $\sum_{p_i \in S} p_i \leq 60 \times 500=30000$. Then the valid solution is in $[W - 30000, W]$ because $ans = \prod_{p_i \in S} p_i = W - \sum_{p_i \in S} p_i$.
And the solution value is products of primes in $[2, 500]$. So try and factorize every number in this region and see if it can be expressed by product of available primes and has valid sum.
Hacked Exam
Problem
There are Q true/false problems, given n people’s solution sequence and number of correct answer, all consistent answer sequence have same probability, return a sequence with maximum expected number of correct answer.
Solution
Test set 1-2 ($n \leq 2, Q \leq 40$): We can use DP to compute number of consistent sequence, and for each bit, compute the number of consistent sequence specifying this bit is true/false. Then we have the expected value of each bit being true/false, and sum because of the linearity of expectation.
Test set 3 ($n \leq 3, Q \leq 120$): There are limited types of questions: when n = 3, there are 8 types of questions: FFF, FFT, …, TTT. Symmetrically (by flipping the result in the end to make FFT type -> TTF type), there are only 4 types of questions. We can brute-force number of consistent sequences by counting number of T out of all available T/F (or number of questions in such type) in each of four type, times some combinatorics number, this takes $O((Q/4)^4)$. Then do in a similar way as previous case and count number of consistent sequences after specifying T/F for each bit.