Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020
Updated:
日立製作所 社会システム事業部 プログラミングコンテスト 2020
Source codes
Solutions
A - Hitachi String
There are just $5$ strings.
B - Nice Shopping
The minimum is achieved either by choosing the cheapest refrigerator and the cheapest oven range or by using the discount coupons.
C - ThREE
Solution
The condition $ab = 0$ or $a + b = 0$ is equivalent to $(a, b) \neq (1, 1), (2, 2)$ in $\mathbb{Z} / 3 \mathbb{Z}$.
A tree is a bipartite graph. We color each vertex by red or blue. Then, two vertexes whose distance is $3$ must be colored differently.
Therefore, it is suffice that we assign numbers for vertexes so that there are no pair of red/blue vertex and assigned for $(1, 1)$ or $(2, 2)$. This is done by the following way.
- The case both red and blue $\geq N / 3$: We assign $1$ for red side and $2$ for blue side as much as possible. Then assign $0$ for others.
- The case red $< N / 3$: We assign $0$ for red side. Then any numbers for others.
- The case blue $< N / 3$: Same as red.
D - Manga Market
Observation
Let $c _ i = a _ i + 1$ and $d _ i = a _ i + b _ i + 1$. Then, the $i$-th shop is the machine that leaps from the time $t$ to the time $f _ i(t) = c _ i t + d _ i$.
First, we show the following lemma.
Lemma D.1: Fix the indexes $I$ of the shops that Takahashi-kun will visit. Then, the minimum time is achieved in the descending order of $\{ f _ i \} _ {i \in I}$ with the weight $(c _ i - 1) / d _ i$. Here, the division is the operator in $\mathbb{Q}$.
Proof: Assume to the contrary that the minimum time is achieved in another order of $\{ f _ i \} _ {i \in I}$ with the weight $(c _ i - 1) / d _ i$. Then, there is at least one adjacent pair $f _ i$ and $f _ j$ with $(c _ i - 1) / d _ i < (c _ j - 1) / d _ j$. We see that, in the current situation, we reach $i$-th shop at the time $t$ and then go to $j$-th shop. The resulting time is \[ T = f _ j \circ f _ i (t) = c _ i c _ j t + c _ j d _ i + d _ j. \] Swapping this order, however, we obtain the resulting time as follows. \[ T’ = f _ i \circ f _ j (t) = c _ j c _ i t + c _ i d _ j + d _ i. \] Then, we have \[ T - T’ = c _ j d _ i + d _ j - c _ i d _ j - d _ i > 0, \] which contradicts the assumption. This completes the proof.
Therefore, we can solve this problem by DP in $O(N ^ 2)$-time.
Solution
For speeding-up, we divide the shops into two sets; $c _ i \geq 2$ and $c _ i = 1$. Note that, by Lemma D.1, we always consider visiting the shops with $c _ i = 1$ after the shops with $c _ i \geq 2$.
For the shops with $c _ i \geq 2$, we try the DP above. Thanks to the constraint $c _ i \geq 2$, we just possess the second key up to $C = 32 \approx \log _ 2 T$.
Then, we visit some shops with $c _ i = 1$ for each $j = 0, \dots, C - 1$. Obviously, we try $d _ i$’s ascending order. This part can be done by partial_sum and upper_bound. The time complexity is $O(N \log T + N \log N)$.
Definition
$dp[i][j] = $ the minimum time we take to visit $j$ stores considering up to the $i$-th store.
Initial State
$dp[0][0] = 0$, otherwise $\infty$.
Answer
$dp[M][j]$ for $j = 0, \dots, C - 1$. Then, we try the shops with $c _ i = 1$.
Transition
For $i = 0, \dots, M - 1$, for $j = 0, \dots, C - 1$, we execute the following. \[ dp[i + 1][j] \gets \min\left( dp[i][j], f _ i (dp[i][j - 1]) \right) \] Here, out-of-range will be considered as $\infty$.
E - Odd Sum Rectangles
Observation
We work on the $2$-dimensional partial-sum grid instead of the original grid, i.e., \[ V[i][j] = \sum _ {x \in i} \sum _ {y \in j} ans[x][y]. \] We consider that all numbers are in $\mathbb{F} _ 2$. We will work on $\mathbb{F} _ 2$-vector space. $V$ is $2 ^ N \times 2 ^ M$. Since the elements are in $\mathbb{F} _ 2$, we can arbitrary put elements in $\mathbb{F} _ 2$ in each cell except on the $0$-th line and column.
In the viewpoint of $V$, we consider $0 \leq i _ 0 < i _ 1 < 2 ^ N$ and $0 \leq j _ 0 < j _ 1 < 2 ^ M$ to see whether the sum of the four cells $(i _ 0, j _ 0)$, $(i _ 1, j _ 0)$, $(i _ 0, j _ 1)$ and $(i _ 1, j _ 1)$ is either $1$ or $3$, or not. We want to maximize the number of the $4$-tuple whose sum is either $1$ or $3$. Thus, we think of the $i _ 0$-th row and the $i _ 1$-th row as two binaries. If we can achieve the Hamming distance between any two binaries is exactly $2 ^ {M - 1}$, it attains its maximum.
Solution
Without loss of generalities, we assume that $N \leq M$. If we can construct the solution for the case $N = M$, We can create the solution for the case $N < M$ since we can extract arbitrary $2 ^ N$ rows from the original solution. Hereinafter we assume that $N = M$.
We define $x _ i \in \mathbb{F} _ 2 ^ {2 ^ M}$ for $i \in N$ as follows.
$x _ i (j) = $ the $i$-th binary digit of $j$.
Let $W = \langle x _ 0, \dots, x _ {N - 1} \rangle$. There are $2 ^ N$ elements in $W$.
We show the following lemma.
Lemma E.1: Let $v, w \in W$ with $v \neq w$. Then, the Hamming distance between $v$ and $w$ is $2 ^ {M - 1}$.
Proof: We use $d$ to denote the Hamming distance. We see $d(v, w) = d(v - w, 0)$. Therefore, without the loss of generalities, we can assume $w = 0$. Then, what we want to show is \[ d(v, 0) = \sharp \{ i \in 2 ^ N \mid v[i] = 1 \} = 2^{M - 1} \] for $v \neq 0$. Let $v = \sum _ {i \in N} a _ i x _ i$, where $a _i \in \mathbb{F} _ 2$ for $i \in N$. Since $v \neq 0$, we can assume $a _ 0 = 1$ by rearranging the order of $x _ i$. Let $v _ k = \sum _ {i \in k} a _ i x _ i$ for $k = 1, \dots, N$. We will show $d(v _ k, 0) = 2 ^ {M - 1}$ by mathematical induction on $k$ for finite version. For $k = 1$, it is done since there are $2 ^ {M - 1}$ elements whose $i$-th binary digit is $1$, and the same for $0$. We assume the condition is satisfied for $k$. If $a _ k = 0$, it follows that $d(v _ {k + 1}, 0) = d(v _ k, 0)$. If $a _ k = 1$, we consider the effect of $x _ k$. Let $X _ l = \{ i \in 2 ^ N \mid v _ k[i] = l \}$ for $l \in \{ 0, 1 \}$. By the assumption, $\sharp X _ 0 = \sharp X _ 1 = 2 ^ {M - 1}$. For both $X _ 0$ and $X _ 1$, Exactly the half elements has $1$ as their $k$-th binary digit. Therefore, $2 ^ {M - 2}$ elements are changed from $1$ to $0$ while $2 ^ {M - 2}$ elements are changed from $0$ to $1$. Thus $d(v _ k, 0) = 2 ^ {M - 1}$. This completes the proof.
We note that $W = 2 ^ N$ from the binary point of view. Therefore, the conclusion is that it is suffice to set \[ V[i][j] = \mathrm{popcount}(i \& j) \in \mathbb{F} _ 2. \] and we compute the following. \[ ans[i][j] = V[i + 1][j + 1] - V[i + 1][j] - V[i][j + 1] + V[i][j]. \]