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.