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. Rearranging further, we get $$$a = \frac{\frac{2N}{i}-i+1}{2}$$$. 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(\sqrt{N})$$$ 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. We can now 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(K(N + M) + 2^K * K^2)$$$ 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 removes $$$a_i$$$ inversions and adds $$$N-a_i-1$$$, changing the total number of inversions in the new sequence by $$$N - 1 - 2a_i$$$ for each $$$i$$$ from $$$0$$$ to $$$N-2$$$.
Time complexity: $$$O(NlogN$$$ for calculating inversions $$$)$$$ My solution
In F, the change should be n — 1 — 2*a[i].
Thanks! I missed that when I was copying from my code to this editorial :S
problem F was very interesting
Your solution is very elegant!
For problem D, I iterated over the length of the series from 1 to 2000000. Then I binary searched the start element for the cur length and if we found the sum exactly equal to n, then add 2 to the answer.
My submission
Can you explain how you figured the range will be till 2000000?
I tried till 1000000 and didn't work.
The longest length series you can make in worst case out of natural numbers should start from 1.
Lets say that length is $$$l$$$. Then $$$\sum_{i=1}^n l = \frac{l(l+1)}{2} = n$$$
Here n is the sum we want.
So $$$l \leq \sqrt{2 * n}$$$
Hence $$$l$$$ will be less than 2000000
Can someone give a solution for C without using bitmasking?
You can use recursion to find all the ways to pick either $$$C_i$$$ or $$$D_i$$$, but it ends up doing the exact same thing as bitmasks, only slower and messier.
Ya I understood.Thank you so much.
`
vector<vector> numbers ;
void recurse(vector &x,vector &y,int t,int n,vector v){
}
void solve(){
} `
Put the code in spoiler like below
...
can anyone tell me how to find these time complexities...I can find easy ones like O(n) and O(n^2) but not like -O(K(N+M)+2K∗K2)..how to learn that...I'm struggling with this for a week.
Hi, sorry for the late response. I don't think you need to learn/find these non-standard complexities, rather, you should learn to recognise and break down problem statements and work on approaching unfamiliar problems. In that problem the $$$K(N+M)$$$ and the $$$2^K*N^2$$$ are essentially separate sub-problems, first to calculate distance to all nodes with BFS ($$$O(N+M)$$$), $$$K$$$ times, for each gem. From there, we can reduce it to a classic $$$O(2^K*K^2)$$$ bitmasking problem. I hope this helped! :)
hello, I'm a beginner and I want to ask you one more thing "if the jth bit is "on" (i.e. i AND 2j=2j)" what is the meaning of this? I mean if the jth bit is on then how are we deciding that we will give the ball to C[j] or d[j](what it means if the jth bit is on in the context of this problem)...I hope you know what I mean.
It's just a technique to iterate over all combinations of $$$0$$$s and $$$1$$$s. While iterating from $$$0$$$ to $$$2^{K-1}$$$, all masks of length $$$K$$$ can be achieved. You may have seen the recursive version before, think of this as another way to do that only faster and less liable to mistakes.
Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
Hello, thanks for the great editorial. I just wanted to ask that why there is a second If in solution of staircase sequence??
We can find all the divisors of $$$N$$$ in $$$O(\sqrt{N})$$$ by only checking up to $$$\sqrt{N}$$$, as every every divisor below the square root has a conjugate divisor above it. The exception to this is $$$\sqrt{N}$$$ itself if $$$N$$$ is a square number, since its conjugate divisor is also $$$\sqrt{N}$$$. We can avoid double counting by ensuring that the second addition to the answer is only done if $$$i^2 \neq N$$$.
Thanks for the editorial! BTW can you explain why the sequences in F will change by moving the first element to the end?
What do you mean?
"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." How is that?
for each $$$k$$$ in $$$[0, n - 1]$$$, $$$b_i = a_{i + k \mod n}$$$
plug in the values figure out yourself
https://ideone.com/KJFNgG I printed out all the numbers but I sill don't get it.
It should be $$$num_{i+k}$$$ not $$$num_i+k$$$.
I'm so sorry,,,
User Editorial by kostia244
kinda sus
I asked him to add it for me.
For problem E,if the problem description change to “find the minimum number of distinct stones needed to form such a sequence.”,how to solve it? thx.
If I'm not wrong, this reduces to finding a minimum steiner tree connecting the set of vertices given by C. Unfortunately, this problem is in NP.
For problem D, my output was 2 times the number of odd divisors of N. Submission
Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
Problem F was an owsam one to me