A – Not
Should be easy as long as you know the basics of your chosen programming language. Can be computed with an if/else statement, the ternary operator (ans = x == 1 ? 0 : 1
), or the xor operator (ans = x ^ 1
)
B – Product Max
Answer is one of: $$$a \cdot c, a \cdot d, b \cdot c, b \cdot d$$$; find the maximum of these and print it.
Proof by exchange argument: No matter what you pick $$$x$$$ to be, you can improve the product by either maximizing or minimizing $$$y$$$, based on the sign of $$$x$$$. Same argument applies when $$$x$$$ and $$$y$$$ are swapped.
C – Ubiquity
There are $$$10$$$ possible digits among $$$n$$$ positions, thus the total number of sequences that satisfy the first constraint is $$$10^n$$$.
Now we want to subtract sequences that violate the second or third constraints. We can construct $$$9^n$$$ sequences without any 0s (violating the second constraint), same with sequences without any 9s (violating the third constraint).
However if we subtract $$$2 \cdot 9^n$$$, note that we have subtracted the sequences that violate both the second and third constraints twice. There are $$$8^n$$$ such sequences (as they lack both 0s and 9s), so we add them back to get the correct count. This pattern of overcounting, adding, overcounting, subtracting, repeat until a final accurate count is known as the inclusion-exclusion principle.
Final answer is thus $$$10^n - 2 \cdot 9^n + 8^n$$$. This can be calculated in $$$O(n)$$$ via repeated multiplication, or $$$O(\log n)$$$ via fast exponentiation. If you don't know how to work with large numbers under a modulus, see my tutorial on that subject.
D – Redistribution
Can be done with basic dynamic programming. Let $$$dp_i$$$ represent the number of sequences whose sum is $$$i$$$. $$$dp_0 = 1$$$, the empty sequence. Then $$$\displaystyle dp_i = \sum_{j=0}^{i-3} dp_j$$$, i.e. the sum of $$$dp_j$$$ for all integers $$$j$$$ between $$$0$$$ and $$$i-3$$$ inclusive, representing the addition of a number $$$\ge 3$$$ to each of the previous sequences. The final answer, naturally, is $$$dp_s$$$.
This can be easily calculated in $$$O(s^2)$$$, which is good enough to pass, however it can be improved to $$$O(s)$$$ by accumulating the prefix sum.
An $$$O(\log s)$$$ solution is possible via matrix exponentiation.
E – Dist Max
We can take the following approach — for each $$$i$$$ from $$$2$$$ to $$$n$$$, try to match $$$(x_i, y_i)$$$ with the "best" previous point $$$(x_j, y_j), 1 \le j < i$$$, then update the answer.
Testing all previous points is too slow ($$$O(n^2)$$$). However, it is sufficient only to keep up to $$$4$$$ previous points to test against. $$$2$$$ of those points are the maximal and minimal of the "score" $$$x_i + y_i$$$, while the other $$$2$$$ maximize and minimize $$$x_i - y_i$$$
Why? Note that taking any point as the center, the set of points with Manhattan distance some arbitrary constant $$$d$$$, forms a "diamond" shape, i.e. a square rotated 45 degrees. Thus the furthest point must lie on at least one of the four sides of this square when $$$d$$$ is maximized. As the sides are on lines with equations of $$$x+y = C$$$ or $$$x-y = C$$$, the maximums and minimums of these values are sufficient to find the furthest point in each of the 4 possible directions.
Thus we have a solution in $$$O(n)$$$.
F – Contrast
Let $$$C$$$ be the array that holds the answer sequence. At first, we can greedily put any value of $$$B$$$ that doesn't match $$$A_i$$$ for each position from left to right.
If this strategy fails, it means that we are in a position where $$$A_i = z$$$ and all remaining members of $$$B$$$ are $$$z$$$. If we put all the remaining $$$z$$$ values into $$$C$$$, the situation looks like this:
A = [ < z ][ z ][ > z ]
C = [ maybe z ][ not z ][ z ]
{TROUBLE ZONE}
So to fix the "trouble zone", we need to swap the $$$z$$$ values in it with some other values. It can be seen that the only values we can swap with lie in the "maybe $$$z$$$" zone; we can't swap with "not $$$z$$$" as that will cause another collision.
Thus we can iterate through the "maybe $$$z$$$" zone to try to find enough non-$$$z$$$ values to swap with. If we run out of values to swap with without eliminating all collisions, the answer is No
, as there are no more values to swap with.
Can you share the O(logs) solution of D.
First prove by induction that $$$dp_i = dp_{i-3} + dp_{i-1}$$$ for all $$$i \ge 3$$$:
It can be seen to be true for $$$dp_3$$$. Now assuming that $$$dp_i = dp_{i-3} + dp_{i-1}$$$, try to prove the relation holds for $$$dp_{i+1}$$$.
$$$dp_{i+1} = \sum_{j=0}^{i-2} dp_j = dp_{i-2} + \sum_{j=0}^{i-3} dp_j = dp_{i-2} + dp_i$$$, Q.E.D.
Now construct the matrix for the transition function $$$F(dp_i, dp_{i+1}, dp_{i+2}) = (dp_{i+1}, dp_{i+2}, dp_{i+3})$$$.
$$$F(a, b, c) = (b, c, a+c)$$$, thus in matrix form $$$F = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&1 \end{bmatrix}$$$. Let vector $$$V = \begin{bmatrix} dp_0 \\ dp_1 \\ dp_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$$$. Compute $$$F^sV$$$ and take the first value of the resulting vector, that's $$$dp_s$$$.
Cool explanation. Thanks.
Cool editorial.
For C,
I thought a sequence that has at least one 9 will be 10^(n-1). Similarly for 0 also 10^(n-1). if we add both these we will be adding two times the common part which has both 9 and 0. so we will subtract it once.
Total Sequences = 10^n
Sequences which don't have either 9 or 0 = 8^n
Final Equation
10^n = 2*(10^(n-1)) — (Common Part) + 8^n
Common Part = 2*(10^(n-1)) — 10^n + 8^n
Is this correct?
No, as the position of the 9 and 0 aren't fixed.
Similarly, fixing the 9 and 0 before filling the rest won't work because the other numbers could be 9 or 0 as well.
For problem C, since the number of ways to put 10 numbers in $$$n - 2$$$ positions (since I locked in 2 positions for 9 and 0) is $$$10^{n - 2}$$$. Then the number of ways to permute this combination of $$$n$$$ numbers is $$$n!$$$. So my formula is $$$n! \cdot 10^{n-2}$$$. But this is wrong, why?
Because you are overcounting situations where more than one permutation would produce the same result. You also failed to distinguish the 9 and 0 you locked in with other 9s and 0s that may be produced.
One has to be careful in combinatorics problems, that the choices one could make in the construction has a one-to-one correspondence with the possible results, or that one could compensate for any overcounting / undercounting.