### Swap-nil's blog

By Swap-nil, history, 4 weeks ago,

Thank you for participating in our contest! We hope you enjoyed it.

On a personal note (contains spoilers)

1983A - Array Divisibility

Idea: BlazingDragon
Preparation: Pew_Pew.
Editorial: Swap-nil

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

1983B - Corner Twist

Idea: Swap-nil
Preparation: Swap-nil
Editorial: Swap-nil

Hint
Solution
Implementation (C++)
Implementation (Python)
Feedback

1983C - Have Your Cake and Eat It Too

Idea: DC17
Preparation: Swap-nil
Editorial: BlazingDragon

Solution
Implementation (C++)
Implementation (Python)
Feedback

1983D - Swap Dilemma

Idea: MrSavageVS
Preparation: MrSavageVS
Editorial: MrSavageVS

Hint
Solution
Implementation (C++)
Feedback

1983E - I Love Balls

Idea: DC17
Preparation: BlazingDragon
Editorial: BlazingDragon

Solution
Implementation (C++)
Feedback

1983F - array-value

Idea: TimeWarp101
Preparation: MrSavageVS
Editorial: MrSavageVS

Hint
Solution
Implementation (C++)
Feedback

Idea: AwakeAnay,TimeWarp101
Preparation: ShivanshJ, Swap-nil, Pew_Pew.
Editorial: Swap-nil

Hints
Solution
Implementation (C++)
Feedback
• +103

 » 4 weeks ago, # | ← Rev. 2 →   +5 First. It does seem like B has a nice proof. I guessed it during the contest, so seeing the proof is very nice.
•  » » 4 weeks ago, # ^ |   0 ya proof is nice,another proof: in a row after modifying all first n-1 elements equal to the first n-1 element in Matrix B, the last element should be equal to its respective element in B, if it is not we can't make it equal, because if we want to make this equal to its respective element in B, we have to select a previous element in that row ( which is already equal to its respective element in B) for a rectangle selection, which will leads to change the that previous element, which will not equal to its respective element in B and then if we going to make this element equal we have to change another element which is already equal to its respective element in B ...so 1 element is always remain unequal as in B.similarly in column..hence the last elements of row and columns should be equal to their respective elements in B after all modifying the A_n-1xm-1 equal to B_n-1xm-1
•  » » » 4 weeks ago, # ^ |   0 Oh nice. This is a more intuitive proof I think, thanks for sharing.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 very good proof
•  » » 4 weeks ago, # ^ |   0 me too
•  » » 4 weeks ago, # ^ |   0 I also guessed at time of contest. After proof by submission I came up with the actual proof.
•  » » 4 weeks ago, # ^ |   -8 For B I just checked each row and column to see if their sum mod 3 was equal in starting and ending array. If this was true for all rows and columns, answer was Yes, otherwise it was No. Haven't proven it yet but it passed.
 » 4 weeks ago, # |   +1 (ANOTHER) SOLUTION FOR PROBLEM DIf array 'b' can be transformed into array 'a' with an even number of swaps (swapping two arbitrary elements in array 'b'), then, the answer for the problem is 'YES'. Else, the answer is 'NO'.Example 1:a = [1, 2, 3, 4];b = [4, 3, 2, 1].In this example, array 'b' can be transformed into array 'a' with 2 operations. First, swap the 1st and the 4th elements in 'b'. The array will be: b = [1, 3, 2, 4]. Then, swap the 2nd and the 3rd ones: b = [1, 2, 3, 4]. Here, 2 is an even number, so the answer is 'YES'.Example 2:a = [1, 2, 3, 4];b = [1, 2, 4, 3]In this example, however, 'b' will be transformed into 'a' with 1 operation only. 1 is odd so, 'NO' is the answer.PROOF: I'll do that tommorrowCode: 269334590
•  » » 4 weeks ago, # ^ |   0 I had the exact same approach as you :)Code : 269276300Had 6 wa during contest :/
•  » » 4 weeks ago, # ^ |   +1 Same approach as me, but a little bit different in the detail.
•  » » 4 weeks ago, # ^ |   +1 Nice approach. Basically every swap can be represented using an odd number of adjacent swaps, so parity of total number of swaps and parity of total number of adjacent swaps are same.
•  » » 4 weeks ago, # ^ |   +1 Can you please tell the logic behind it's working
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 It goes like this, might be slightly different, than op's approach. I like it better that "permutation-parity" solution in editorial. It should be sufficient to make both $(l,r)$ and $(p,q)$ kinds of swaps on array A alone. Why ? Look at the very last $(p,q)$-swap that we would have done on array $B$ after which $A = B$ would be achieved. If we made the same swap on array $A$ we would still achive $A = B$. And so on all $(p,q)$ operations could have been made directly on $A$ instead of $B$. Now, we are making swap operations on $A$ only and the constraint is that every $k$-length swap has to be accompanied by another $k$-length swap as well. So, in general the count of swaps of any length $k$ should be even. Singly-used $k$-swaps are not allowed. But, a single $2k$ length swap could be broken down into $2 \times k$ swaps. Similarly, two different singly-used odd swaps could be combined into a bunch of even swaps + $2 \times 1$ swaps. So, we see there are a lot of variations possible and its hard to choose the correct set of swaps. Resolution: How about we decompose all required swaps into a common "unit-swap" and then see if we can satisfy the even-ness constraint ?The "unit-swap" should be "adjacent-position" swaps of $[x, x+1]$ form.Any swap $[l,r]$ can be decomposed into: ${[l,l+1], [l+1,l+2], \cdots [r-1,r]} \cup {[r-2,r-1], [r-3,r-2], \cdots [l,l+1]}$.The number of these unit-swaps is $2*(r-l) - 1$.One can see that the final state of array $A$ after these swaps is exactly the same as if a single $[l,r]$ was done. Final Claim: If the sum of all these unit-swaps isn't even, then no choice of swaps in point (3) could have satisfied the constraint.
•  » » » » 4 weeks ago, # ^ |   0 Thanks
•  » » » » 4 weeks ago, # ^ |   0 Thanks for the explanation.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 here more simple implementation ,thankyou phatdapchai int n; cin >> n; vi a(n), b(n); fr(i, n) cin >> a[i]; fr(i, n) cin >> b[i]; vi aa = a; vi bb = b; sort(all(aa)); sort(all(bb)); if (aa != bb) { no; continue; } int swp = 0; map pos; fr(i, n) pos[a[i]] = i; fr(i, n) { if (a[i] != b[i]) { int crnt_pos = pos[b[i]]; swap(a[i], a[crnt_pos]); swap(pos[a[crnt_pos]], pos[a[i]]); swp++; } } if (swp % 2 == 0) yes else no } return 0;}
•  » » 10 days ago, # ^ |   0 code : 272511253 I think I use the same logic as you. I use dfs to find the groups that member amount are even. So if the even number group is even I can find the answer, otherwise no answer. But this solution got TLE, can you tell me why? I think the time complexity is O(NlogN), logN is besause of using set.
•  » » » 10 days ago, # ^ |   0 I'm not sure that we have similar idea but I can tell why it exceed the time limit. Your declaration of vector g(mxN+5); takes roughly 2e5 operations. Imagine a test with 1e5 testcases then your code would have to do about 2e10 operations, that is O(N^2).
 » 4 weeks ago, # | ← Rev. 2 →   0 I want to ask then why in the problem A output is different than the given output.Can anyone tell me?
•  » » 4 weeks ago, # ^ |   0 There can be multiple beautiful arrays for a given n.
 » 4 weeks ago, # |   +9 DEF are good problems for me.But I think C is a little boring because it requires a lot repeating codes.
•  » » 4 weeks ago, # ^ |   +14 You may want to look into std::next_permutation.
•  » » » 4 weeks ago, # ^ |   0 Even after looking at the next permutation, we still have to print the answer in the same order ( l[a] to r[a], and l[b] to r[b] , and l[c] to r[c] ) . That's where things got complicated. If we had to simply print "YES" or "NO" . Or we had to simply print any three partition irrespective of the order ( which person the partition belongs to ) , next_permuatation implementation was quite straight forward.
•  » » » » 4 weeks ago, # ^ |   +8 Sounds like a skill issue to me. When looking at $p_i$, the $i$-th element of our permutation, use $p_i$-th row of prefix sums to find the range and write it to $p_i$-th index of the answer. Maybe looking at my code 269239985 will help? Unlike the editorial, I didn't hardcode the number of people, so I assume it's cleaner.
•  » » » » » 4 weeks ago, # ^ |   0 harsh
•  » » » » » » 4 weeks ago, # ^ |   +20 Honestly is often harsh. Either we can accept and learn from it, Or we can ignore it, and blame it on others by saying they are rude. It was skill issue on myside, I couldn't think in that direction.
•  » » » » 4 weeks ago, # ^ |   +8 You can use a vector to put the answers into before printing them. Maybe take a look at my code: 269257208
•  » » » » 4 weeks ago, # ^ |   -8 My submission might help: Submission
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -7 Since there are only 3 people, A simple loop would also work.UPD: Learned that shouldn't have suggested a kinda rudimentary method. Viva la next_permutation!
•  » » » » 4 weeks ago, # ^ |   0 It is worse because $(i, j, k)$ are not in a collection and cannot be processed uniformly with a for loop.
•  » » » » » 4 weeks ago, # ^ |   0 It's a good point. I agree it's the best practice to use next_permutation if feasible, but anyway I'm talking about a simple substitute to it when the processing is not very complex
•  » » 4 weeks ago, # ^ |   +3 Actually,you can use an array to store the index of each person instead of copying the same code for 6 times. Like me,I used next_permutation to finish this work. Here is my code.
•  » » 4 weeks ago, # ^ |   0 this is one way to do it Code... #include using namespace std; #define all(a) a.begin(),a.end() #define ll long long int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tt=1; cin >> tt; while(tt--) { int n; cin>>n; vector>v(3,vector(n+1,0)); for(int i=0;i<3;i++){ for(int j=1;j<=n;j++){ cin>>v[i][j]; } } for(int i=0;i<3;i++){ for(int j=1;j<=n;j++){ v[i][j]+=v[i][j-1]; } } long long tot= (v[0][n]+2)/3; vector>ans(3,vector(2,0)); int f=0; for(int i=0;i<3;i++){ if(f)break; for(int j=0;j<3;j++){ if(f)break; if(j==i)continue; for(int k=0;k<3;k++){ if(f)break; if(k==j || k==i)continue; // cerr<=tot && sm2 >=tot && sm3>=tot){ ans[i][0]=1;ans[i][1]=x; ans[j][0]=x+1;ans[j][1]=it; ans[k][0]=it+1;ans[k][1]=n; f=1; } } } } } } if(f){ cout<
•  » » 4 weeks ago, # ^ |   0 269300957 Pretty cute implementation for C id say.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 i am not able to think what am i missing i have done the same thing as editorial just precalulated values for all possible cases so where am i wrong it failed on test case 2 code#include #define pb push_back #define fst first #define scd second #define mkp make_pair #define nl "\n" using namespace std; void print(vector&p){ // cout<<"yes\n"; for (auto i:p) { cout<>n; vector a(n+1,0),b(n+1,0),c(n+1,0); for (int i = 0; i < n; i++) { cin>>a[i+1]; a[i+1]+=a[i]; } for (int i = 0; i < n; i++) { cin>>b[i+1]; b[i+1]+=b[i]; } for (int i = 0; i < n; i++) { cin>>c[i+1]; c[i+1]+=c[i]; } long long int sum = a[n]; sum=ceil(sum/3.0); int p=-1,q=-1,r=-1; for (int i = 0; i <= n; i++) { if(p!=-1&&q!=-1&&r!=-1)break; if(p==-1){ if(a[i]>=sum)p=i; } if(q==-1){ if(b[i]>=sum)q=i; } if(r==-1){ if(c[i]>=sum)r=i; } } int x=-1,y=-1,z=-1; for (int i = n; i >= 0; i--){ if(x!=-1&&y!=-1&&z!=-1)break; if(x==-1){ if((a[n]-a[i])>=sum)x=i; } if(y==-1){ if((b[n]-b[i])>=sum)y=i; } if(z==-1){ if((c[n]-c[i])>=sum)z=i; } } long long int diff; if(p=sum){ y++; cout<<1<<" "<=sum){ z++; cout<<1<<" "<=sum){ x++; cout<=sum){ z++; cout<=sum){ x++; cout<=sum){ y++; cout<>t; while(t--) solve(); return 0; } can anyone help bcz i cant even see which test case i am wrong on 269290282
•  » » » 4 weeks ago, # ^ |   0 Take a look at Ticket 17456 from CF Stress for a counter example.
•  » » » » 4 weeks ago, # ^ |   0 oh thank u i didn't knew we can generate test cases
 » 4 weeks ago, # |   0 In E I had a different solution. First a O(nk) DP is ez to get. The DP is $f_{n,k}$ denoting the expect value of special balls Alice get when there are n balls in total and k balls special. When u brute force it and print a chart, it has a clear pattern( u can try it yourself,remember print fractions,not double). Simply implement this passed the pretests. You can see the submission here,in which the calc function is the pattern.
 » 4 weeks ago, # | ← Rev. 3 →   +14 Here's an alternative way to count subarrays with value $\le m$ in 1983F - array-value: Hint 1If $x < y < z$ then $\min(x \oplus y, y \oplus z) < x \oplus z$. Hint 2The minimum pair xor of a (sub)array occurs among pairs of consecutive (in sorted order) elements. Hint 3Use a sliding window to find the shortest good subarray (with value $\le m$) ending at each position $1 \le r \le n$. Hint 4Maintain a multiset of subarray elements to quickly find adjacent elements in sorted order, and maintain a multiset of adjacent pair xors to find the smallest pair xor quickly.Code: 269281742.
 » 4 weeks ago, # | ← Rev. 2 →   +41 In problem E, where did the formulae come from? I would assume that the people who are reading the editorial for problem E couldn't exactly come up with the formulae themselves, therefore could the editorial please give some more explanation about this? Also how does the expected number of normal balls that alice takes not affected by the number of special balls there are? (the only thing that changes is n $\rightarrow$ n - k, which is just the change in the number of normal balls)EDIT: I understand why the expected result did not change, it's because the turn changes everytime someone picks a normal ball, and as long as they keep picking the special balls, their turn repeats. Hence per turn each player picks exactly one normal ball (except perhaps the last turn) and hence the formula for expected number of normal balls picked my alice remains the same.
•  » » 4 weeks ago, # ^ |   0 I also don't understand the formula
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +54 Suppose you have $n$ normal balls and $k$ special balls.In every turn, you would pick any one of the normal balls and at least one normal ball. Out of those $n$ runs of picking a normal ball and passing of turns, $\left\lceil \frac{n}{2} \right\rceil$ times Alice would pick balls. Total score gained by Alice = $\left\lceil \frac{n}{2} \right\rceil \times \text{expected_value_per_ball}$Now, for simplicity, consider there is only one special ball. Here the chance that it is picked up on the first turn is $\frac{1}{n+1}$ (this gets picked up before the other balls). Similarly, picking it in the second turn has probability $\left(\frac{n}{n+1}\right) \times \frac{1}{n}$ (not picked in the first, picked in the second). For the third turn: $\left(\frac{n}{n+1}\right) \times \left(\frac{n-1}{n}\right) \times \frac{1}{n-1}$. Now comes an observation that all these evaluate to $\frac{1}{n+1}$. There will be a total of $n+1$ chances of picking up a special ball ($n$ times before some normal ball and once when no balls are available) with equal probability each. Total number of turns = $n+1$Alice has a probability of $\frac{\left\lceil \frac{n+1}{2} \right\rceil}{n+1}$ to pick this special ball.For the case with multiple special balls: Suppose we want to calculate the probability of the first special ball (or any particular special ball) being picked on a turn. Here it only matters if the first special ball was picked before any normal ball was picked, because picking another special ball still leaves the same situation and the first special ball can still be picked up in this turn.
•  » » » 4 weeks ago, # ^ |   0 That makes sense, thank you so much!
•  » » 4 weeks ago, # ^ |   0 can anyone explain why tutorial just use first k to calculate avg_special thanks
•  » » » 4 weeks ago, # ^ |   +1 read second last line in input format
•  » » » » 4 weeks ago, # ^ |   0 thansk
•  » » 4 weeks ago, # ^ | ← Rev. 5 →   +22 Yes, exactly. First we can observe that the value of every normal ball can be replaced by the expected value of the normal balls(average basically) and same for special balls. Now we need to compute the number of normal balls Alice gets, and expected number of special balls Alice gets.Let's say that we randomly shuffle the N balls and arrange them in a line. Now Alice will keep picking up balls until she gets the 1st normal ball. Then Bob does the same until he gets the 2nd normal ball. We can see that Alice will get ceil(X/2) normal balls(this is exact, not expected). X is the number of normal balls (n — k)So it is like the normal balls create sections in between which there are special balls. If there are X normal balls then we get X+1 sections and the expected number of special balls in each section is K / X+1, if K is the number of special balls.Now Alice will pick up balls from ceil(X/2) sections. So expected number of special balls Alice gets is ceil(X+1/2)*K / X+1.Now that we know the expected number of special balls Alice gets, and the number of normal balls, we can easily calculate the answer. You can take a look at the implementation in the editorial, given the context I'm sure it would be easy to understand.PS: This solution can be extended for any number of players as well.
•  » » » 4 weeks ago, # ^ |   0 Ah true, thats quite a neat way of thinking about it, thanks!
•  » » » 4 weeks ago, # ^ |   0 Could you explain why can we replace the value of every ball for it's expected value? I'm having trouble understanding why we don't need to compute something like this for every ball (using $p(X)$ as "probability of $X$"): EV of choosing ball $i$ on the $j$-th turn $=$ $p($ ball $i$ survives $j-1$ turns $) \times p($ choosing ball $i$ on the $j$-th turn $) \times v_i$.
•  » » » » 4 weeks ago, # ^ |   0 You can think about all the permutations of the balls. If you think about how many times we can get each ball at certain place, it turns out that out of all $n!$ permutations they can draw the balls in, $v_{1}$ is drawn as a 1st ball $(n-1)!$ times ($(n-1)!$ is the number of ways in which you can draw the rest of the balls), $v_{2}$ is drawn as a first ball also $(n-1)!$ times and so on which shortens into the $\frac{\sum^{n}_{i=1}v_{n}*(n-1)!}{n!} = \frac{\sum^{n}_{i=1}v_{n}}{n}$ which is also the $EV$. You can think similarly for all the next draws as well as for the special draws.
•  » » » » » 4 weeks ago, # ^ |   0 Thank you, the solution is entirely clear for me now. We can represent the normal and special balls picked as two permutations during a game, so the expected value of the amount of special or normal balls picked by Alice/Bob is independent from the expected value of the ball's value at any turn, so we apply $E[XY] = E[X] \times E[Y]$
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It depends on the implementation, it's not entirely necessary. The problem boils down to computing the expected number of balls taken out of every bundle (the special and the non-special one). Given the expected number of balls picked from each we can get the original answer, regardless of the distribution of values on the balls. Below is a quick justification.Let $B$ be all balls of a bundle, $v(\cdot)$ their values and $X$ be a random variable on the (equiprobable) selection of $B$. Then \begin{align} \mathbb{E}[v(X)] &=\sum_{\ell=0}^{|B|} \mathbb{E}[v(X)\mid\#X=\ell] \mathbb{P}(\#X=\ell) \\ &=\sum_{\ell=0}^{|B|} \mathbb{E}\left[ \sum_{x \in X}^{}v_{x} \mid\#X=\ell \right] \mathbb{P}(\#X=\ell) \\ &=\sum_{\ell=0}^{|B|}\mathbb{P}(\#X=\ell) \sum_{i \in B}^{} v_{i}\mathbb{E}\left[ \mathbf{1}\{ i \in X \} \mid\#X=\ell \right] \\ &=\sum_{\ell=0}^{|B|}\mathbb{P}(\#X=\ell) \sum_{i \in B}^{} v_{i}\mathbb{P}\left( i \in X \mid\#X=\ell \right) \\ &=\sum_{\ell=0}^{|B|}\mathbb{P}(\#X=\ell) \sum_{i \in B}^{} v_{i} \frac{\ell}{|B|} \\ &=\frac{v(B)}{|B|}\sum_{\ell=0}^{|B|}\mathbb{P}(\#X=\ell)\ell \\ &=\frac{v(B)}{|B|}\mathbb{E}[\#X]. \end{align}If $(v_{i})_{i \in B}$ were random variables then since they would be independent of $X$ we would get the result $\mathbb{E}[v(X)]=\frac{\mathbb{E}[v(B)]}{|B|}\mathbb{E}[\#X].$
 » 4 weeks ago, # |   +2 I think this is a wonderful contest,and I love BD very much. Thank you!
 » 4 weeks ago, # |   0 NO issue bhaiya problems were good I enjoyed them(got -ve delta) it was great learning from B too.
 » 4 weeks ago, # |   0 For me, B and D have the weirdest solutions ever. It took me a lot of time to solve both of them. The idea behind B and D was quite tricky, confusing, and vague. Honestly, I don't really know how I got Accepted.
 » 4 weeks ago, # |   0 Why was my submission 269283722 TLE? Can anyone explain, please.
 » 4 weeks ago, # |   +2 Nice round. Actually, I got the idea for B in 5 minutes, but I couldn't solve D quickly. I didn't guess the solution mentioned in tutorial and solved D in a different way. However, I solved E in 15 minutes because the idea was too simple (I finished coding when the contest was over for 1 minute and passed after the system test was over). C is not fun enough, I didn't find any difference to "fix the order they choose". It just made the implementation more difficult.
 » 4 weeks ago, # |   +5 I feel you should have swapped the order of B and C, if B was to be left in the set at all.For me it is very hard to submit without proving, and B wasn't provable all that easily (for me and other people, judging by comments) — generally I think it is better if problem solutions are reached in a way along the path of a proof, and not have to guess the solution from samples.I had to guess B and the time it took just made me lose motivation to solve the rest of the problemset.
 » 4 weeks ago, # |   +12 I liked problem E a lot, but next time please make sure to write essential information like the special balls being the first k ones on the actual problem statement, and not at the end of the input section.
 » 4 weeks ago, # |   +8 The way editorial of E written is similar to the way it is in the note section of the problem, LOL. Likewise, the problem statement confused people by putting a crucial detail in the input section.
 » 4 weeks ago, # |   0 can anyone plz describe why the sum of all coloumns and rows in problem B must have to be same?
•  » » 4 weeks ago, # ^ |   0 Sum should not be same sum%3 should be same. This is because whenever we apply an operation the sum of any row or column changes by 0 or 3. That is modulo remains same. Thus if modulo is not same its not possible to convert A to B. Its a necessary condition I was not able to prove that it's sufficient.
 » 4 weeks ago, # |   0 In problem C, has anyone solved it using concept of sliding window? My approach was finding all the windows of sum k for alice, bob and charlie. After that, finding the non-overlapping ranges bw them. Codevpii findSegments(vi &v) { ll n = sz(v); ll i = 0, j = 0; ll sum = 0 ; vpii ranges; while (j < n) { sum += v[j]; if (sum >= k) { while (sum >= k) { ranges.push_back({i, j}); sum -= v[i]; i++; } } j++; } return ranges; } But I was not able to implement it fully. Kindly help me out with my query or tell if I am thinking in wrong direction.Thanks.
•  » » 4 weeks ago, # ^ |   0 My approach was very similar I stored all possible indexes for each a,b,c such that sum is greater than equal to k and then I found out 3 no overlapping pairs. But I got memory limit exceeded on test case 3. Anyone help?My Submission
•  » » 4 weeks ago, # ^ |   +4 I used 6-pointers technique which i made up during contest
 » 4 weeks ago, # |   +6 We wanted to introduce new and uncommon problems, like the usage of permutation parity here would have been for a div2D.Using permutation parity isn't new for Div2D, I've seen it twice already: here and here.
 » 4 weeks ago, # |   0 Not only did i go blank in B, frankly speaking, i just got lazy in C, after writing the first 2 cases, and realising how long it will go.
 » 4 weeks ago, # |   0 https://youtu.be/uRURZo52IwsC question detailed video editorial
•  » » 4 weeks ago, # ^ |   0 Can anyone look into my solution of c and tell me what I am missing or in which case my code is failing to pass 269290282? thank you for your time
 » 4 weeks ago, # | ← Rev. 2 →   0 For problem D, I just checked that both the arrays have the same inversions parity rather than number, yet it still passes, can anyone hack it: link?Also, although I initially really disliked problem B, but reading your proof I think it's a pretty good problem tbh.
•  » » 4 weeks ago, # ^ |   +8 Same inversion parity is enough.Lets do operations with $r-l=q-p=1$, now the no of operations required to make array sorted is equal to no of inversions.Lets say no of inversions in A is 10, and inversions in B is 20. After first 10 swaps in A, we can keep swapping $A_{n-1}$ and $A_{n}$
 » 4 weeks ago, # |   +13
 » 4 weeks ago, # | ← Rev. 2 →   0 I was already confused in question 3 and then you guys wrongly answered my query during the contest Link
 » 4 weeks ago, # |   0 can anyone tell me where I can practice problems like E I have no idea about the expected value
•  » » 4 weeks ago, # ^ |   0 This problem is good: 1925D - Good Trip
 » 4 weeks ago, # | ← Rev. 3 →   +40 After reading the personal note, I want to leave my comments here.I think problem B wasn't bad, although it might be a little hard to prove for a B. I personally liked this problem.Same for problem D. I think it wasn't necessarily bad, although it involves a quite typical observation that appears in many similar problems. I want to ask though, why it couldn't just be an actual permutation instead of random numbers $\le 2*10^5$. These required tedious exception handling such as checking if the set of elements is the same, and some of the inversion count methods prefer compressed numbers (just like how I did it with a Fenwick tree).The one I disliked most was problem C, because this required almost no observation and made me choose between "copy-pasting 6 times carefully" and "running over a dizzy permutation".I also think problems like A are not very suitable for their position, because the best way to first approach this problem is not by "observing mathematical facts", but by "guessing that the answer must be the simplest pattern in the world because it's an A problem". It's very easy to get stuck if you just forget that this is 2A, and to be honest if the position of this problem was hidden, this problem would be probably too hard for a 2A.I don't think that the contest was too math-heavy though. I'm not sure if people are calling it math-heavy because of observations, but these kind of maths are fine for me. I prefer them to problems full of pure math equations.
•  » » 4 weeks ago, # ^ |   0 Nice review, I completely agree with you.
 » 4 weeks ago, # |   0 Can someone explain why my submission (269286766) for problem C is wrong? I'm not able to find the issue.
 » 4 weeks ago, # |   +8 Can anyone tell me what I am doing in this solution of Ç giving wrong ans on tc3 This is the submission link Solution
•  » » 4 weeks ago, # ^ |   0 nvm got it
 » 4 weeks ago, # |   0 Hey guys i couldn't enter the contest yesterday. This screen appeared for over 15 minutes after which i decided to not give the contest can anyone pls help how to avoid this. Codeforces.com Verifying you are human. This may take a few seconds needs to review your security of ur connection It was saying their was no internet connection pls connect to internet. But i could use google and also started other apps to check whether my internet connection was working fine
 » 4 weeks ago, # |   0 G is too pain to implement
 » 4 weeks ago, # |   0 in B i got this part We see that it is always possible to make all the elements in the first n−1 rows and m−1 columns equal using this method.but what about the last row and last column ?
•  » » 4 weeks ago, # ^ |   0 My guess: If we are going to fix them then we have to change at most 2 of the already fixed value. So after all operations, the N'th row and M'th column need to be the same as the B grid.
 » 4 weeks ago, # |   0 Can we solve E using DP?
•  » » 4 weeks ago, # ^ |   0 Had a similar thought during the contest, let me know if you have any ideas
 » 4 weeks ago, # |   +3 Really cool B. Although my solution was based on intuition, I really like the proof and how the problem setters came up with the problem. And about the contest being not good, that is very much not true. Really good contest. Really good for developing observational skills.
 » 4 weeks ago, # |   0 Solution to D becomes trivial if you've solve this Problem before. (Essentially same problems)
 » 4 weeks ago, # |   0 Can we use hungarian algorithm in C?
 » 4 weeks ago, # |   0 Now, we will prove that when both arrays have the same number of inversions, then it is definitely possible to make them equalfor D i think it should be when both arrays have the same parity of inversion?
 » 4 weeks ago, # | ← Rev. 2 →   0 https://mirror.codeforces.com/contest/1983/submission/269401066 this one is giving tle https://mirror.codeforces.com/contest/1983/submission/269401494 this one getting acceptedjust change in template gives complete different resultsruined my contest yesterday
•  » » 4 weeks ago, # ^ |   0 help anyone
•  » » » 4 weeks ago, # ^ |   0 fast io
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 You missed a closing bracket while taking array B. sadge:(
 » 4 weeks ago, # |   0 can anyone help me with more problems that have proofs like b ?
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anybody please tell whats wrong with this Solution ?Is there something wrong with finding the inversion count?
 » 4 weeks ago, # |   +8 What I did for B was a little bit different, I just had a strong hunch that if you fix all of the rows naively up until the last row, the last row will either be fixed = 'YES' or not fixed = 'NO', I tried it out a lot but since I war already really late, didn't have the time to prove it.D was nice but was solved a lot surprisingly.I would've switched E and F tbh.
 » 4 weeks ago, # |   0 I am having some difficulty solving Problem F, I used a struct for defining my nodes of the Trie. Initially I was not deleting the nodes used for the binary searched value so got MLE, but after deleting all the nodes used for a particular searched value I am getting TLE. Can someone please explain me why and help resolve the issue.Link to MLE solution : 269444765Link to TLE solution : 269456951
 » 4 weeks ago, # |   0 for E can someone explain how the INV function is working exactly ?
 » 4 weeks ago, # |   0 I have another (probably) solution for problem F. It only uses a trie which can add elements, delete elements and find the minimal xor for given value.Do binary search on the answer. Then we want to find maximal $l$ for each $r$, so that min xor on segment $[l, r]$ is not greater than $mid$ ($l = 0$ if min xor on prefix $r$ is greater than $mid$). Then the number of segments with min xor not greater that $mid$ will be equal to sum of all $l$. In order to find this $l$ for each right edge $r$ we'll use two pointers. When moving from $r$ to $r + 1$, we only need to move $l$ while there exists $a_i (l \le i \le r), a_i \oplus a_{r+1} \le mid$. The solution works in $O(n \ log^2 A)$
•  » » 3 weeks ago, # ^ |   +8 Why should we only check that there exists $a_i$ such that $a_i⊕a_{r+1}≤mid$? I mean, isn't it possible that this condition doesn't hold, but the minimum XOR of the pairs is less than $mid$?
•  » » » 3 weeks ago, # ^ |   +1 I'm moving $l$ while there is a xor that is $\le mid$, so when I finish moving it for $r$, all xors are bigger than $mid$. Then, it might happen that $a_{r+1} \oplus$ some element on current segment is $\le mid$, so we need to further move $l$. All other pairs already give greater xor, so we don't care about them
•  » » » » 3 weeks ago, # ^ |   0 Oh nice. I got it. Thanks!
 » 4 weeks ago, # |   0 My approach to the problem B is completely different. 269255620
•  » » 4 weeks ago, # ^ |   0 I was using the exact same logic, idk why I was not getting the correct answer on my IDE. Thanks this helped.
 » 4 weeks ago, # |   0 I found problem G is too annoying to implement. Is there any simple implementation for it? (Editorial's code is also too long.)
 » 4 weeks ago, # |   0 "Keep using operations for array a of the form l=1 and r=2 while changing the operation p,q to different values to make the elements at indices 3,4,…n the same in array b as they are in array a . Now, since both the arrays should have the same parity of inversions at the end, a1=b1 and a2=b2 , and so, our arrays a and b will become equal"if we wont ever use a2 and b2 how can we ensure its the same as a1 and b1?
 » 4 weeks ago, # |   0 May be it would have been better if B was given at C or D position with asking to perform operation.
 » 4 weeks ago, # |   0 https://mirror.codeforces.com/contest/1983/submission/269611660 This is my submission for problem C. Can someone point out what is wrong in my code??
 » 4 weeks ago, # |   0 Interesting. My $O(n(logn)^3)$ solution is passing for F even though it shouldn't.
 » 4 weeks ago, # |   0 I am using bit-trie for solving F, but I am getting TLE in testcase 2submission link -> 269731104Can someone please help me optimise this code.
 » 4 weeks ago, # |   0 problem C title "Have Your Cake and Eat It Too"is that a reference to the sitcom "Friends" ? XD
•  » » 3 weeks ago, # ^ |   0 Maybe, but it might just refer to the famous idiom in English
 » 3 weeks ago, # |   +11 I believe problem C can also be solved in $\mathcal O(NK + K 2^{K})$ time via bitwise DP, which might be useful if it were extended to $K \le 20$ people.Might be kinda trivial, anyways here is an implementation: 270151191
 » 3 weeks ago, # |   0 can someone please explain how problem E is working here?? As, I am supposed to find the expected value of the scores of both players, which is the weighted average of score with their probabilities. But since there exists k>=1 special balls which lead to many different combination of balls each players can have. So how we are supposed to find the probability here ?? Wouldn't the different combination of balls lead to different scores and hence different expected values ?? then how can we uniquely determine the expected score for each given set of balls ??I am just confused. Please help.
 » 3 weeks ago, # |   0 For problem F, I have a solution that can pass the tests, but I don't know how to prove that the time complexity of my code is small enough. https://mirror.codeforces.com/contest/1983/submission/270741083
 » 13 days ago, # |   +3 Found a cool way to invalidate pointers without explicitly using any pointers in F: #include using namespace std; struct Trie; vector heap; struct Trie { int child_index = -1; void add(int depth) { if (depth == 0) return; if (child_index == -1) { child_index = heap.size(); heap.push_back(Trie()); } heap[child_index].add(depth-1); } }; int main() { Trie root; root.add(2); } (This exact code crashes in MSVC, might need a bigger example for GCC/clang.)But the idea is that this line heap[child_index].add(depth-1); seems to work similarly to e.g. auto child = &heap[child_index]; child->add(depth-1); And then when push_back causes vector resize, then the child reference will be invalidated.So, on the surface it looks like no pointers or references were used, but they be sneaky like that.
 » 13 days ago, # |   0 Cool round
 » 8 days ago, # |   0 I followed the solution of Problem F, implementing with struct, and got TLE. Can some one help me check where is the problem? Thanks!!! 273029376
•  » » 8 days ago, # ^ |   0 Oh I found that the time I used for delete is too long.Here is the Accepted solution: 273036038