A — Very Very Primitive Game
Simply simulate the game and print out the winner.
Time complexity: $$$O(A+B)$$$ My solution
B — Magic 3
For each spell $$$i$$$, check if $$$X_i < S$$$ and $$$Y_i > D$$$. If such spell $$$i$$$ is found, the answer is "Yes"
, otherwise, if after all spells have been processed and no such spell has been found, the answer is "No"
.
Time complexity: $$$O(N)$$$ My solution
C — Bowls and Dishes
We can approach this problem using bitmasks. For each $$$i$$$ from $$$0$$$ to $$$2^K-1$$$, if bit $$$j$$$ is "on" (i.e. $$$i$$$ AND $$$2^j = 2^j$$$), we give the $$$j$$$-th dish to ball to $$$C_j$$$, otherwise we give it to $$$D_j$$$. We calculate the maximum number of satisfied conditions across all $$$i$$$, and that is our answer.
Time complexity: $$$O(2^K * M * K)$$$ My solution
D — Staircase Sequences
The sum $$$S$$$ of an arithmetic sequence with first term $$$a$$$, $$$n$$$ terms, and common difference $$$1$$$ can be found with the formula $$$S = \frac{n}{2}[2a + n - 1]$$$. Rearranging this and multiplying across by $$$2$$$, we get $$$2S = n(n+2a-1)$$$, therefore n must be a factor of $$$2S$$$, which is $$$2N$$$ in this problem. Now, we can iterate over all the factors $$$i$$$ of $$$2N$$$, and we need to check if $$$\frac{2N}{i}-i+1$$$ is divisible by $$$2$$$.
Time complexity: $$$O()$$$ My solution
E — Magical Ornament
We can represent the gems which can be placed adjacent to each other using a graph. Now, for each $$$C_i$$$, do a breadth-first search of the graph and calculate distances to all other gems. Now, we can model the solution as one with dynamic programming with bitmasks. Let $$$dp_{i,j}$$$ be our answer if we use all the gems included in the mask of $$$i$$$, ending with gem number $$$j$$$.
Time complexity: $$$O()$$$ My solution
F — Shift and Inversions
We can calculate the number of inversions in the original array in a number of ways, such as with a Fenwick tree or with merge sort. Now, notice that each of the resulting sequences essentially remove the first element of the previous sequence and insert it at the end of it. This changes the number of inversions by $$$n - 1 - a_i$$$ for each $$$i$$$ from $$$0$$$ to $$$N-2$$$.
Time complexity: $$$O()$$$ My solution