### ScarletS's blog

By ScarletS, history, 3 months ago,

Solution

Solution

Solution

Solution

Solution

## F — Shift and Inversions

Solution

• +116

 » 3 months ago, # |   +1 In F, the change should be n — 1 — 2*a[i].
•  » » 3 months ago, # ^ |   +2 Thanks! I missed that when I was copying from my code to this editorial :S
 » 3 months ago, # |   -9 problem F was very interesting
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 Your solution is very elegant!
 » 3 months 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 months ago, # ^ |   0 What are you doing your sum() function please explain that i can't understand that...
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Arithmetic series formula,$S_n = \frac {n \cdot (a + a_n)} 2$Where $a= a_1, d = a_{i + 1} - a_i, a_i = a + (i - 1) \cdot d, i \in Z^+$We can rewrite, $S_n = \frac {n \cdot (a + a + (n - 1) \cdot d)} 2 = \frac {n \cdot (2 \cdot a + (n - 1))} 2$ since, $d = 1$ for the desired sequence.
•  » » » » 3 months ago, # ^ |   0 Ohh thanks bro :)
•  » » 3 months ago, # ^ |   0 Nice approach! The idea of using Binary Search never hit me.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you explain how you figured the range will be till 2000000?I tried till 1000000 and didn't work.
•  » » » 2 months 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 months ago, # |   0 Can someone give a solution for C without using bitmasking?
•  » » 3 months 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 months ago, # ^ |   0 Ya I understood.Thank you so much.
•  » » » 3 months 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 months ago, # ^ |   +3 Put the code in spoiler like below Code...
 » 3 months 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 months 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 months 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 months 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 months ago, # |   0 Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
 » 3 months 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 months 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 months ago, # ^ |   0 got it thanksss
 » 3 months 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 months ago, # ^ |   +8 What do you mean?
•  » » » 3 months 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 months ago, # ^ |   +3 for each $k$ in $[0, n - 1]$, $b_i = a_{i + k \mod n}$plug in the values figure out yourself
•  » » » » » 3 months ago, # ^ |   0 https://ideone.com/KJFNgG I printed out all the numbers but I sill don't get it.
•  » » » » » » 3 months ago, # ^ |   0 It should be $num_{i+k}$ not $num_i+k$.
•  » » » » » » » 3 months ago, # ^ |   0 I'm so sorry,,,
•  » » » » » » 3 months ago, # ^ |   0 $n = 4$Say we have a sequence $a_0, a_1, a_2, a_3$ $b_i = a_{i + k \mod n}$for $k = 0,$ $b_0 = a_{0 + 0 \mod 4}$ $b_0 = a_{0 \mod 4} = a_0,$ $b_1 = a_{1 + 0 \mod 4} = a_1,$ $b_2 = a_{2 + 0 \mod 4} = a_2,$ $b_3 = a_{3 + 0 \mod 4} = a_3$for $k = 1,$ $b_0 = a_{0 + 1 \mod 4}$ $b_0 = a_{1 \mod 4} = a_1,$ $b_1 = a_{1 + 1 \mod 4} = a_2,$ $b_2 = a_{2 + 1 \mod 4} = a_3,$ $b_3 = a_{3 + 1 \mod 4} = a_0$for $k = 2,$ $b_0 = a_{0 + 2 \mod 4}$ $b_0 = a_{2 \mod 4} = a_2,$ $b_1 = a_{1 + 2 \mod 4} = a_3,$ $b_2 = a_{2 + 2 \mod 4} = a_0,$ $b_3 = a_{3 + 2 \mod 4} = a_1$for $k = 3,$ $b_0 = a_{0 + 3 \mod 4}$ $b_0 = a_{3 \mod 4} = a_3,$ $b_1 = a_{1 + 3 \mod 4} = a_0,$ $b_2 = a_{2 + 3 \mod 4} = a_1,$ $b_3 = a_{3 + 3 \mod 4} = a_2$
 » 3 months ago, # |   0 User Editorial by kostia244kinda sus
•  » » 3 months ago, # ^ |   0 I asked him to add it for me.
 » 3 months 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 months 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.
 » 2 months ago, # |   0 For problem D, my output was 2 times the number of odd divisors of N. Submission
 » 2 months ago, # |   0 Auto comment: topic has been updated by ScarletS (previous revision, new revision, compare).
 » 2 months ago, # |   0 Problem F was an owsam one to me
 » 5 weeks ago, # | ← Rev. 3 →   0 i dont understand problem C they said there are conditions and that condition i could be satisfied with Ai and Bi have one or more balls on them. However when in the sample input there is 1 2 1 3 2 4 3 4 but the sample output is 2 `all of Ai and Bi have more than 1 balls inside, why is the sample output 2, is my understanding of the question completely wrong?and the people will put balls on Ci and Di. Where do the balls come from? Issit from A or B or somewhere else? could someone explain it to me? thanks in advance