CodeJam 2021: Prime Time

I enjoyed trying the problem Prime Time from CodeJam 2021 and wanted to share my approach. Here is the problem statement.

You are given primes $p_1 \leq p_2 \leq ... \leq p_N$. A partition of the cards into two disjoint sets $S$ and $P$ is called good iff 

$$\sum_{p\in S}{p} = \prod_{p\in P}{p}$$

The score of a good partition is defined as the sum of the primes in $S$ (which is equal to the product of the primes in $P$) . What is your maximum possible score?

We are given three test sets:

• Test set $1$: $2\leq N\leq10$
• Test set $2$: $2\leq N\leq100$
• Test set $3$: $2\leq N\leq10^{15}$

Notation: Let $\text{sum}(S)=\sum_{p\in S}{p}$ and $\text{prod}(P)=\prod_{p\in P}{p}$.

Initial Observations:

1. We can pass test set $1$ using the brute-force approach requiring $O(N\cdot2^N)$ time: $2^N$ possible partitions, each needing $O(N)$ time to verify goodness.
2. Since each prime is at most $499$, we have the upper bound $\text{sum}(S)<499N$.
3. Since multiplication grows much faster than addition, it makes sense for $|P|\ll|S|$. We know, $2^{|P|} < 499N$, hence $|P| < \log_{2}{499N}$.
4. From $(3)$, for test set $2$, we have $|P|<16$.
5. From $(3)$, for test set $3$, we have $|P|<55$.
6. From the fundamental theorem of arithmetic we know for each set $P\subseteq\{p_1, p_2, ..., p_N\}$, $\text{prod}(P)$ is each time a unique number.

From $(2)$, we know that $\text{prod}(P)$ can take at most $499N$ distinct values, where each value maps to a unique set $P$. 

Fix the value of $\text{prod}(P)$ to some $2\leq x\leq499N$, and suppose we have its prime factorization $x=p_1^{k_1}p_2^{k_2}...p_N^{k_N}$. It is only possible to achieve $x$ with $P$ if we have at least $k_i$ instances of $p_i$. If $x$ is possible, then we check in $O(N)$ if the remaining primes sum to $x$.

This approach takes time $O(499N\cdot T(499N) \cdot N)$ where $T(x)$ is the time needed to compute the prime factorization of $x$.

It is known that $T(x) \in O(\sqrt{x})$. However, we only need to check for prime factors of $x$ up to $499$ since $p_i \leq 499$. So we have $T(x) = O(1)$ meaning our solution takes time $O(499N^2)$.

This solves test set $2$. However, this is as far as I got. It seems as though $(5)$ was not used and I feel like it could be very useful to make my solution more efficient for test set $3$.

 

Diane

Below is my solution to the Codeforces div2 735 problem D: Diane.

We want to find the simplest way to construct a string $s$ which has no substrings occuring an odd number of times. Let us consider the string $a^{k}$. If $k$ is even then we have the followin substring properties.

If $k$ is odd, then we have the opposite parities. Observe that if we could separate $a^k$ and $a^{k+1}$ then because $k$ and $k+1$ have opposite parity, the substrings each occur an odd number of times.

Thus $s=a^kba^{k+1}$ generates strings of length $2k+2$, i.e. $2, 4, 6, \cdots$. Furthermore, $s=a^kbca^{k+1}$ generates strings of length $2k+3$, i.e. $3, 5, 7, \cdots$. Finally, if $n=1$, we trivially set $s=a$. Note the time required to print out the string is $O(n)$, so this solution passes.

Explorer space

 This is my solution to Codeforces round 718 div2 + div1 problem D: Explorer Space.

First we observe that it is only possible to return to $(i, j)$ iff $k$ is even. This is because for every step away from $(i, j)$ we need one step back, so we can pair up each step of a walk meaning $k$ must be even.

Next we observe that we can never have a different path in to $(i, j)$ than the path taken out from it. To prove this, suppose we could take a different path in, call it $p_{\text{in}}$, then we know the cost of $p_{\text{in}} \leq p_{\text{out}}$. But then we can swap $p_{\text{out}}$ with $p_{\text{in}}$, giving us a lower cost path.

Now we can use dynamic programming to compute the minimum cost path of length $k$. Concretely, let $dp_{i, j, k}$ denote the minimum cost path to $(i, j)$ with exactly $k$ steps. Then

$$dp_{i, j, k} = \min_{\text{all edges $e$ incident to $(i, j)$}}{dp_{e, k-1} + w_e}$$

This solution takes $O(nmk)$ time.

Start of BMO series!

I'm going to be attempting some BMO1 questions over the course of the next few blog posts. Starting with 2017-2018 Problem 1 and working my way up from there.

Problem: Helen divides $365$ by each of $1, 2, 3, . . . , 365$ in turn, writing down a list of the $365$ remainders. Then Phil divides $366$ by each of $1, 2, 3, . . . , 366$ in turn, writing down a list of the $366$ remainders. Whose list of remainders has the greater sum and by how much?

Solution: First thing to notice is that Helen and Phil are dividing by consecutive numbers respectively. This is important because

$$365 = qk + r \quad \text{ where } 0 \leq r \leq k - 1 $$

$$366 = qk + (r + 1)$$

This implies that $365 \equiv r \pmod{k}$ and $366 \equiv r + 1 \pmod{k}$. From this we can derive the following rules:

1. If $k$ divides $365$ and $366$ evenly, then Helen and Phil both get remainder $0$.
2. If $k$ divides $366$ evenly and not $365$, then Helen gets remainder $k - 1$ while Phil gets remainder $0$.
3. Else, Phil gets remainder $1$ greater than Helen.

So if we determine which values of $k$ divide $365$ or $366$ then we can use our rules to determine the difference in remainder sums between Helen and Phil. We can do this by listing the factors of $365$ and $366$.

$$\text{Factors of 365} = \{1, 5, 73, 365\}$$

$$\text{Factors of 366} = \{1, 2, 3, 6, 61, 122, 183, 366\}$$

In all but $7$ cases (for the $7$ factors of 366 excluding $1$), we have rule 3. This means Phil's remainder sum is $365 - 7 = 358$ more than Helen at this stage.

$2, 3, 6, 61, 122, 183$ all divide $366$ evenly but not $365$. Hence Helen's remainder sum is increased by $1 + 2 + 5 + 60 + 121 + 182 = 371$. So Helen's remainder sum is $371 - 358 = 13$ larger than Phil's. We don't take into account $366$ as a factor because it is not included in Helen's list so does not affect the difference in remainder sums.

There you have it. The key to solving this problem is to stay systematic and clear. The actual approach required is the obvious one, but it's easy to make small counting errors if you don't keep organised.

Big-Ohhhh!

Problem: Let $f : \mathbb{Z_{\geq 0}} \mapsto \mathbb{Z_{\geq 0}}$ be a non-decreasing function satisfying the inequality

$$f(n) \leq \frac{2}{n - 1} \left(n^2 + \sum^{n - 1}_{i = 1}f(i)\right)$$

Prove that $f(n) = O(n\log n)$.

Solution: Notice that $\frac{1}{n - 1} \dot \sum^{n - 1}_{i = 1}f(i)$ is the average value of $f$ over the interval $[1, n - 1]$. This suggests expanding the inequality is a good idea because we can simplify our expression.

$$f(n) \leq \frac{2n^2}{n - 1} + 2f(j) $$

Where $f(j) > \frac{1}{n - 1}\sum^{n - 1}_{i = 1}f(i)$  for the minimum $j$. Note that $\frac{2n^2}{n - 1}$ is $O(n)$ so

$$f(n) \leq O(n) + 2f(j)$$

What happens if we recursively apply the process we have just applied for $f(n)$, to $f(j)$? And how many times do we apply this process in the worst case so that $f(j) = f(1)$?

At worst we apply this process $O(\log n)$ times. Therefore, following through with recursion we are left with

$$f(n) \leq \underbrace{O(n) + O(n) + ... + O(n)}_{O(\log n) \text{ times}} + 2^{O(\log n)}f(1) = O(n \log n) + O(n)f(1) = O(n \log n)$$

I came across this problem in a past paper for one of my algorithms course and enjoyed the process of solving it. It felt like a real thinking questions which you couldn't prepare for that much.

Intuitive intro to polynomial time reductions.

The concept of a reduction is fundamental to organising computational problems by relative difficulty. Intuitively, this is useful because if we know problem $A$ to be "hard", and we can establish that problem $B$ is "at least as hard" as $A$, then we know $B$ must also be "hard". This can save a lot of time that could have been spent searching for some fast algorithm for $B$ which may not exist. 

So what is a polynomial time reduction?

Suppose we have two problems $X$ and $Y$. Now suppose that we already know how to solve $Y$ in polynomial time using procedure $P_Y$. If we could construct some procedure, $P_R$, which transforms any instance, $I_X$, of $X$ to an instance, $I_Y$, of $Y$, then we could use our solution to $Y$ to solve $X$ in polynomial time given that:

• $P_R$ runs in polynomial time.
• $I_Y$ as input to $P_Y$ outputs the correct answer for $I_X$.

This is an example of a polynomial reduction from $X$ to $Y$ (written $X \le_P Y$). Intuitively, it helps me to think of this as saying: $X$ is no harder than $Y$, or $Y$ is at least as hard as $X$. Just as relative easiness of a problem can be shown using polynomial reductions, so can relative hardness.

Suppose that there is no polynomial time solution for $Y$. If $Y \le_P X$, then it must be that $X$ is at least as hard as $Y$ and so there is no polynomial time solution for $X$.

Proof. Suppose for contradiction that there exists a polynomial time solution for $X$. Then by the definition of a polynomial time reduction, there would exist a polynomial time solution to $Y$. A contradiction.

Notice that this logic only works if $P_R$ runs in polynomial time.

Snazzy application of pigeonhole principle.

Problem: Prove that a simple graph $G$ with $n > 2$ vertices has at least two vertices with the same degree.

Solution: Notice that there is no guarantee that $G$ is connected. However let us suppose that it is. Then each vertex has degree $d$ where $d \in \{1, 2, ..., n - 1\}$. Since we have $n$ vertices and $n - 1$ degree choices, it must be that at least two vertices in $G$ have the same degree.

This proves the case when $G$ is connected, but what about when it is unconnected?

In this case, each vertex can connect to at most $n - 2$ vertices because for $G$ to be unconnected, there must exist a vertex which is connected to no other vertex. Therefore, each vertex has degree $d$ where $d \in \{0, 1, ..., n - 2\}$. By the same argument used in the connected case, $G$ must have at least two vertices of the same degree.

I thought this was a pretty snazzy approach. There is something so elegant about the pigeonhole principle.