AtCoder Beginner Contest 172 English Solutions
Difference between en2 and en3, changed 0 character(s)
#A — Calc↵

Just directly print the given sum.↵

Time Complexity: $O(1)$. [Click here for my submission.](↵


#B — Minor Change↵

The answer is simply the number of positions $i$ for which $S[i] \neq T[i]$.  This is because we must make a move fixing each of those position, and each move can only make $S[i] = T[i]$ for one new position.  Thus, we can iterate through the positions and count those where $S$ and $T$ differ, printing the total as our answer.↵

Time Complexity: $O(|S|)$. [Click here for my submission.](↵


#C — Tsundoku↵

We apply two pointers.  Iterate over the number of books to be read from desk A in decreasing order, starting with the greatest number of those books we could read without exceeding $K$ minutes.  Maintain the sum of all books to be read from desk A.  Then, while we can do so without exceeding $K$ minutes, add the next book from desk B to the list of books to be read.  We can then consider the total number of books read between desk A and desk B as a possible answer, decrement the number of books from desk A, and continue.  ↵

The basic intuition is that as we decrease the number of books we read from desk A, the number of books we read from desk B monotonically increases.  By processing the number of books to be read from desk A in order, we avoid having to recompute any sums, achieving a time complexity of $O(N+M)$.↵

Time Complexity: $O(N+M)$. [Click here for my submission.](↵


#D — Sum of Divisors↵

Let's reframe the problem by considering the total contribution each divisor makes to the answer.  For any given $i$, $i$ contributes $K$ to the sum for each $K$ from $1$ to $N$ such that $K$ is a multiple of $i$.↵

Notice that the list of these $K$ is of the form $i$, $2i$, $3i$, ..., $\lfloor \frac{N}{i} \rfloor i$, noting that the last term is the greatest multiple of $i$ less than $N$.  For simplicity, let $M = \lfloor \frac{N}{i} \rfloor.$  Then, the sum of this sequence is equal to $i + 2i + 3i + \cdots + Mi = i (1 + 2 + \cdots + M) = \frac{iM(M+1)}{2}.$↵

Thus, by computing $M$ and the above product, we can compute each divisor's contribution to the answer in $O(1)$, giving us an $O(N)$ solution.↵

Time Complexity: $O(N)$. [Click here for my submission.](↵


#E — NEQ↵

First, let's count the number of ways to choose $A$, irrespective of $B$.  There are $\dbinom{M}{N}$ ways to choose the $N$ integers to appear in $A$ and $N!$ ways to arrange them, so we have $\dbinom{N}{M} N!$ choices for $A$ in total.↵

Now, without loss of generality, assume the sequence $A$ is simply $1, 2, \cdots, N$, since the number of choices for $B$ doesn't depend on our sequence $A$.  We want to count the number of sequences $B$ where there is no position $i$ such that $B_i = i$.  ↵

We do this using the principle of inclusion and exclusion.  By PIE, we know that the number of sequences $B$ where $B_i \neq i$ for all $i$ is equal to the sum over all valid $j$ of $(-1)^j$ times the number of ways to create a sequence $B$ where at least $j$ positions $i$ have $B_i = i$.↵

Thus, it remains to compute the number of ways to compute the number of sequences $B$ with at least $j$ equal positions.  There are $\dbinom{N}{j}$ ways to choose $j$ positions where $B_i = i$.  Then, it doesn't matter what we put in the remaining positions, so there are $\dbinom{M-j}{N-j}$ ways to choose the numbers and $(N-j)!$ ways to arrange them.  Thus, the total number of ways to ensure that at least $j$ positions have $B_i = i$ is $\dbinom{N}{j} \dbinom{M-j}{N-j} (N-j)!$.↵

By precomputing all relevant factorials and their modular inverses in $O(M)$, we can compute the above product in $O(1)$ for each $j$.  We then sum these up using our PIE formula, giving us an $O(N+M)$ solution.  Since $N \leq M$, this is simply $O(M)$.↵

Time Complexity: $O(M)$. [Click here for my submission.](↵


#F — Unfair Nim↵

It is well known that the second player wins a game of Nim if and only if the bitwise XOR of the numbers of stones in each pile is equal to $0$.  Thus, we want to make the equation $A_1 \wedge A_2 \wedge A_3 \wedge \cdots \wedge A_n = 0$.  By taking the XOR of this equation with $A_3 \wedge A_4 \wedge \cdots \wedge A_n$, we have $A_1 \wedge A_2 = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$  We can immediately compute the right-hand side, since it is fixed before we make our moves.  Now, we want to find the largest $x$ between $1$ and $A_1$, inclusive, such that $x \wedge (A_1 + A_2 - x) = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$↵

We build $x$ via digit DP, determining the bits of $x$ from the most significant bit to the least significant bit.  Let $a$ be the maximum possible value of $x$ thus far such that we have found a bit in which $x$ contains a $0$ while $A_1$ contains a $1$ (so, we know that no matter what bits we add to $a$ in the future, it will be less than $A_1$), or $-\infty$ if no such value exists thus far.  Let $b$ be the value of $x$ such that thus far, all bits in $b$ are the same as those in $A_1$, or $-\infty$ if creating this value is impossible.  Note that we cannot add a $1$ to $b$ if the corresponding bit in $A_1$ is a $0$, as this would make $b$ too large.↵

Let $S = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$  If $S$ contains a $0$ in any given bit, we know that $x$ and $A_1 + A_2 - x$ must either both contain a bit or neither must contain a bit.  We can tell which case applies by determining whether after subtracting out all bits we've assigned so far, $A_1 + A_2$ is greater than $2^{k+1}$, where $k$ is the index of the current bit.  This is because the sum of all future bits will be at most $2^{k+1} - 2$, so $A_1 + A_2 \geq 2^{k+1}$ both enables us to add two $1$s at position $b$ and forces us to do so.  If we add a bit to both numbers, we add $2^k$ to $a$ and $b$, but set $b$ to $-\infty$ if $A_1$ contains a $0$ in position $k$.  Otherwise, we don't add anything to either $a$ or $b$, but if $A_1$ contains a $1$ in position $k$, we can set $a$ to $\max(a, b)$, since now we've found a position in which $x < A_1$.↵

If $S$ contains a $1$ in any given bit, we know that exactly one of $x$ and $A_1 + A_2 - x$ must contain a bit.  Thus, we can add $2^k$ to $a$, because this will not make $a$ exceed $A_1$.  If $A_1$ contains a $1$ in position $k$, we can also add $2^k$ to $b$, or we can alternatively assign a $0$ in order to guarantee that $x < A[1]$, allowing us to set $a$ to $\max(a, b)$.  ↵

At the end of this process, $a$ and $b$ are our possible values for $x$.  Of course, if $a$ and $b$ are zero or $-\infty$, they can't work (the zero case fails because we cannot move every stone from the first pile).  Moreover, we also must confirm that $a \wedge (A_1 + A_2 - a) = S$ in order to use $a$, and we must check the same equation for $b$.  This is because the total bits we assign throughout our process may not equal $A_1 + A_2$, since the number of bits we assign is largely determined by $S$.  (One countercase that demonstrates this issue is $N=3, A = 7, 5, 6$: our solution assigns one bit in position $2$, one bit in position $1$, and two bits in position $0$, but the total of these bits is $4 + 2 + 2 = 8 < 7+5.$)  Then, we take the largest of these possible values for $x$ and subtract it from $A_1$ to get our answer.↵

Time Complexity: $O(N + \log A_i).$ [Click here for my submission.](↵



  Rev. Lang. By When Δ Comment
en4 English Geothermal 2020-06-27 16:59:55 4 Tiny change: ' $\dbinom{N}{M} N!$ choi' -> ' $\dbinom{M}{N} N!$ choi'
en3 English Geothermal 2020-06-27 16:40:42 0 (published)
en2 English Geothermal 2020-06-27 16:07:58 2
en1 English Geothermal 2020-06-27 16:07:18 7804 Initial revision (saved to drafts)