### ScarletS's blog

By ScarletS, history, 3 years ago,

Solution

Solution

Solution

Solution

Solution

## F — Shift and Inversions

Solution
• +116

| Write comment?
 » 3 years ago, # |   +1 In F, the change should be n — 1 — 2*a[i].
•  » » 3 years ago, # ^ |   +2 Thanks! I missed that when I was copying from my code to this editorial :S
 » 3 years ago, # |   -9 problem F was very interesting
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 Your solution is very elegant!
 » 3 years ago, # |   +8 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
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you explain how you figured the range will be till 2000000?I tried till 1000000 and didn't work.
•  » » » 3 years ago, # ^ |   0 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
 » 3 years ago, # |   0 Can someone give a solution for C without using bitmasking?
•  » » 3 years ago, # ^ |   +4 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.
•  » » » 3 years ago, # ^ |   0 Ya I understood.Thank you so much.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   0 Codevector numbers ;void recurse(vector &x,vector &y,int t,int n,vector v){ if(t==n-1){ numbers.push_back(v) ; return ; } t++ ; v.push_back(x[t]) ; recurse(x,y,t,n,v) ; v.pop_back(); v.push_back(y[t]) ; recurse(x,y,t,n,v) ; }void solve(){ `int n,m ; cin>>n>>m ; vector> a(m) ; rep(i,m){ cin>>a[i].first>>a[i].second ; } int k ; cin>>k ; vector x(k),y(k) ; rep(i,k){ cin>>x[i]>>y[i] ; } recurse(x,y,-1,k,{}) ; int mx=0 ; for(int i=0;i<(int)numbers.size();i++){ int digit[101],ans=0 ; for(int i=0;i<=100;i++){ digit[i]=0 ; } for(auto x:numbers[i]){ digit[x]=1 ; } for(int j=0;j
•  » » » » 3 years ago, # ^ |   +3 Put the code in spoiler like below Code...
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 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! :)
•  » » » 3 years ago, # ^ |   0 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.
•  » » » » 3 years ago, # ^ |   +3 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.
 » 3 years ago, # |   0 Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
 » 3 years ago, # |   0 Hello, thanks for the great editorial. I just wanted to ask that why there is a second If in solution of staircase sequence??
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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$.
 » 3 years ago, # |   0 Thanks for the editorial! BTW can you explain why the sequences in F will change by moving the first element to the end?
•  » » 3 years ago, # ^ |   +8 What do you mean?
•  » » » 3 years ago, # ^ |   0 "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?
•  » » » » 3 years ago, # ^ |   +3 for each $k$ in $[0, n - 1]$, $b_i = a_{i + k \mod n}$plug in the values figure out yourself
•  » » » » » 3 years ago, # ^ |   0 https://ideone.com/KJFNgG I printed out all the numbers but I sill don't get it.
•  » » » » » » 3 years ago, # ^ |   0 It should be $num_{i+k}$ not $num_i+k$.
•  » » » » » » » 3 years ago, # ^ |   0 I'm so sorry,,,
 » 3 years ago, # |   0 User Editorial by kostia244kinda sus
•  » » 3 years ago, # ^ |   0 I asked him to add it for me.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 For problem D, my output was 2 times the number of odd divisors of N. Submission
 » 3 years ago, # |   0 Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
 » 3 years ago, # |   0 Problem F was an owsam one to me