### ScarletS's blog

By ScarletS, history, 3 months ago, Solution

Solution

Solution

Solution

Solution

## F — Shift and Inversions

Solution abc, Comments (40)
 » 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
•  » » 2 months ago, # ^ | ← Rev. 2 →   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
•  » » What are you doing your sum() function please explain that i can't understand that...
•  » » » 3 months ago, # ^ | ← Rev. 3 →   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.
•  » » » » Ohh thanks bro :)
•  » » Nice approach! The idea of using Binary Search never hit me.
•  » » 2 months ago, # ^ | ← Rev. 2 →   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.
•  » » » 3 months ago, # ^ | ← Rev. 4 →   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,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
•  » » » » Put the code in spoiler like below Code...
 » 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??
•  » » 3 months ago, # ^ | ← Rev. 2 →   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$.
•  » » » got it thanksss
 » 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,,,
•  » » » » » » $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$
 » User Editorial by kostia244kinda 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
 » 5 weeks ago, # | ← Rev. 3 →   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