ScarletS's blog

By ScarletS, history, 12 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
•  » » 12 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...
•  » » » 12 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.
•  » » 12 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.
•  » » » 12 months ago, # ^ | ← Rev. 4 →   Code`vector 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??
•  » » 12 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