Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

1778A - Flip Flop Sum

Tutorial
Code

1778B - The Forbidden Permutation

Tutorial
Code

1778C - Flexible String

Tutorial
Code

1778D - Flexible String Revisit

Tutorial
Alternative Solution
Code
Alternative Code

1778E - The Tree Has Fallen!

Tutorial
Code

1778F - Maximizing Root

Tutorial
Code
• +129

 » 10 months ago, # |   +46 Better round than I expected, kudos to the authors!
•  » » 10 months ago, # ^ |   0 I agree, the authors are cool!
 » 10 months ago, # |   +37 Special thanks to Psychotic_D for the special case of problem D.
•  » » 10 months ago, # ^ |   +8 What was the special case?
•  » » » 10 months ago, # ^ |   +16 Test case 24 of problem D where the answer is mod-1. A lot of solutions failed in the system test in this case.
•  » » 10 months ago, # ^ |   +3 Wow! Big brain. It was really so great. Orzzz Psychotic_D !
 » 10 months ago, # |   0 In problem b why we are not updating the position of the element after we have counted the number of swaps. how this is not affecting the ans?
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Maybe because there is no need to update. As we only need the number of minimum swaps/steps required to make array good.
•  » » 10 months ago, # ^ |   +2 Seems like you misunderstood the problem just like me. Actually, we just need to change one such pair that satisfies the given inequality to make the array good. I feel so stupid now and was wondering why is B so difficult and how are people solving it.
•  » » » 10 months ago, # ^ |   +3 negation(for all)= there exits. i too could not see that.
•  » » » » 10 months ago, # ^ |   0 Let me read the question once again. I too could not see that. Guess we need to use light pen to see it
•  » » » 10 months ago, # ^ |   0 me too, I did the harder version of the problem ie to make the complete array good in minimum moves XD
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 But what if the question was originally what you thought it was... that you need to make all pairs good in the array? Would that be dp?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +8 I can't figure out how to solve that question by dp,since previous moves may affect these rear one. That's why I don't solve the problem LOL
•  » » » 10 months ago, # ^ |   0 me too
•  » » » » 10 months ago, # ^ |   0 me too
•  » » » 10 months ago, # ^ |   +5 me too.I will be sad all day.
•  » » » 10 months ago, # ^ |   0 damn damn damn damn same thing happened to me and I just realized now. I tried to solve the problem for a whole day yesterday and rolled in guilt why I cant get a B problem now that I know I misunderstood the problem after reading this comment.
•  » » » » 10 months ago, # ^ |   0 lol same
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 Me too.$pos(a_i)  » 10 months ago, # | +32 I got stuck at B because I didn't read the question correctly learned a big lesson thank s for the contest. •  » » 10 months ago, # ^ | ← Rev. 2 → -7 Me too. I tried to make the whole array good that's why i found this problem so difficult •  » » 10 months ago, # ^ | -8 Same for me, I did't realise that only one pair was enough for the answer. •  » » 10 months ago, # ^ | -8 same for me, I understand proper question after 30 minutes.  » 10 months ago, # | ← Rev. 2 → +5 Anyone care to explain the "After some calculations" part of the Alternative solution for D? I'd really like to see the idea behind this :) •  » » 10 months ago, # ^ | +23 One possible way to show this is using Markov chains (you might want to look up Ehrenfest Urns)In particular, suppose that we don't stop after having$0$differences between$a$and$b$: instead, we keep repeating the index choosing infinitely. Then, the probability of being in state$0$differences in the long run is$\pi_0 = 2^{-n}$. It is a fact of "recurrent" Markov chains that the expected time to return to a state$i$is$1/\pi_i$. In particular, if currently there are$0$differences between the two strings, then the expected time until we return back to having$0$differences is$2^n$moves. However, note that when we leave$0$differences, we always move to$1$difference. So, the expected time to go from$1$difference to$0$differences must be$2^n - 1$. •  » » » 10 months ago, # ^ | +3 This is so cool! Thank you so much. •  » » » 10 months ago, # ^ | 0 Cool •  » » » 10 months ago, # ^ | 0 Could u tell me how why the probability is 2^(-n)? •  » » » » 10 months ago, # ^ | +3 Suppose you have a long run probability$\pi_i$of being in state$i$and probability$\pi_{i+1}$of being in state$i + 1$. Then, notice that the number of times you go$i\rightarrow i + 1$is within one of the number of times you go$i + 1\rightarrow i$. In the limit, this means that of the$i\rightarrow i + 1$and$i + 1\rightarrow i$transitions, exactly$\frac 12$of them are$i\rightarrow i + 1$.Since the probability of going from$i$to$i + 1$is$\frac{n - i}{n}$and the probability of going from$i + 1$to$i$is$\frac{i + 1}{n}$, it follows that$\pi_i \cdot \frac{n - i}{n} = \pi_{i+1} \cdot \frac{i + 1}{n}.$Rearranging, you have$\pi_{i+1} = \pi_i \cdot \frac{n - i}{i + 1}$. Then, by induction you can verify that this implies that$\pi_{i+1} = \pi_0 \cdot \binom {n}{i + 1}$.Since$\sum_{i=0}^{n}\pi_i = 1$, adding these up implies that$\sum_{i=0}^{n}\pi_0 \cdot \binom ni = 1$. Since$\sum_{i=0}^{n}\binom ni = 2^n$, this gives$\pi_0 = 2^{-n}$. •  » » » » » 10 months ago, # ^ | 0 Dude, that was soooo beautiful!! Thanks a lot!! Could u suggest which topics I should study to be able to do these on my own? Thanks a lot in advance. •  » » » » 3 months ago, # ^ | ← Rev. 2 → 0 Here's another simple way to show the stationary probability is$\frac{1}{2^n}$more simply. We are taking a random walk on the vertices of the boolean hypercube with vertices$\{0,1\}^n.$(Each of the$n$bits corresponds to one dimension of the cube), and toggling one bit corresponds to moving along an edge. This is clearly symmetric with respect to each of the$2^n$vertices. By symmetry of the cube, the stationary probability is the same for each vertex and so each is equal to$\frac{1}{2^n}.$More generally the stationary distribution on an unweighted finite graph (neighbors picked uniformly at random) is$\pi_v = \frac{deg(v)}{2E}$where$E$is the number of edges.  » 10 months ago, # | -9 I had the same solution as mentioned in the editorial for question B but i got wrong answer on pretest 2. •  » » 10 months ago, # ^ | 0 Me too  » 10 months ago, # | +8 I would like to point out that there is a much easier way for D. You can find through some checking that if A and B differ in exactly 1 bit, then the expected value is 2^n-1. Then you can just create an array and calculate the answer recursively, using some Modulo properties which make it much easier. An implementation can be found here. Ignore the copy-pasted GeeksforGeeks implementation of Modular Inverse :clown: •  » » 10 months ago, # ^ | ← Rev. 2 → 0 Elaborate the relation of ans[i] please !! unable to understand completely.  » 10 months ago, # | ← Rev. 2 → +206 Another solution for D: let$f(i)$be the expected time to go from$i$differences to$i - 1$differences for the first time. Then, our answer is$\sum_{i=1}^{k} f(i)$.The claim is that$f(i) = 1 + \frac{n-i}{n}(f(i + 1) + f(i))$. Indeed, with probability$\frac in$, we move to$i - 1$differences and are done in one move. Else, we move to$i + 1$differences. Then, the expected time to get to$i - 1$is$f(i + 1) + f(i)$.So, we can rearrange to get$f(i) = \frac ni + \frac{n-i}i f(i + 1)$. Now, in$O(n)$we can calculate all$f(i)$starting from$n$and ending at$1$, and$O(n)$to compute the desired sum.Submission: 191566655 •  » » 10 months ago, # ^ | +6 Wow, nice solution •  » » 10 months ago, # ^ | +1 Cool. •  » » 10 months ago, # ^ | 0 amazing！ •  » » 10 months ago, # ^ | ← Rev. 2 → +19 I've also used this method to solve D. I'd like to add some explanations in order to give others a further understanding.​We can know that if we are considering$f(i)$, we could move to$i - 1$by$1$step with probability$\dfrac{i}{n}$, or we could move to$i + 1$by$1$step then move to$i - 1$by step$f(i) + f(i - 1)$with probability$\dfrac{n - i}{n}$. ​So we can find that$f(i) = \dfrac{i}{n} \times 1 + \dfrac{n - i}{n} \times (f(i) + f(i + 1) + 1) \iff f(i) = 1 + \dfrac{n - i}{n}(f(i) + f(i + 1))$like what applepi216 said.​It is OK if we have$f(i)$on both sides of the equal sign, we just have to move all$f(i)$to the same side like:$f(i) = 1 + \dfrac{n - i}{n}(f(i) + f(i + 1))\iff \dfrac{i}{n}f(i) = 1 + \dfrac{n - i}{n}f(i + 1) \iff f(i) = \dfrac{n}{i} + \dfrac{n - i}{i}f(i + 1)$​Then we can easily write a program to solve this problem! •  » » 10 months ago, # ^ | ← Rev. 2 → +9 This formula can be explained in another way.Assume we have$\displaystyle i$one's. The probability of that number decreasing is exactly$\displaystyle \frac{i}{n}$. That means that it will decrease on the$\displaystyle \frac{n}{i}$-s attempt on average. Therefore, we claim that we expect$\displaystyle \frac{n}{i} - 1$increases and exactly$\displaystyle 1$decrease.So, we get that$\displaystyle dp_i = (\frac{n}{i} - 1) * (dp_{i+1} + 1) + 1$, because we have to waste one extra move for each increase. •  » » 10 months ago, # ^ | 0 Thank you so much  » 10 months ago, # | +16 I have an easier solution for E without using Euler tour. I use re-rooting technique and answer the queries offline. Submission here.  » 10 months ago, # | +3 In problem B i think i should fix all i and don't solve the problem at the end ಥ⁠‿⁠ಥ •  » » 10 months ago, # ^ | +3 same here bro  » 10 months ago, # | +5 To find the node$c$, one can also use binary lifting/k-th ancestor techniques. The relevant node will be the$dep[r] - dep[v] - 1$'th ancestor of$r$.  » 10 months ago, # | -22 Can anyone tell me where am I wrong here? Getting wrong answer on the last input of the first test case.ll n,m,d,i,ans1,ans2,mini=INT_MAX,cnt=0; cin>>n>>m>>d; unordered_map p; ll a[m],b[n]; for(i=1;i<=n;i++){ cin>>b[i]; p.insert({b[i],i});} for(i=1;i<=m;i++) cin>>a[i];for ( i = 1; i < m; i++){ if(p[a[i]] > p[a[i+1]] || p[a[i]]+d < p[a[i+1]]){ cout<<0<= n){ ans2=INT_MAX; } if(ans10) cout< •  » » 10 months ago, # ^ | 0 You're not supposed to paste your code in discussion.  » 10 months ago, # | 0 In problem B, do we need to check if the array has become good after every swap? •  » » 10 months ago, # ^ | 0 you dont need to swap anything in the original array. Just need to calculate how many swaps are required per pair. The minimum of all pairs is the answer (something similar is written in the solution) •  » » 10 months ago, # ^ | 0 yes, we only need only one index which does not follow the condition of not good array. So after swapping an element we check minimum numbers of swaps for every time. •  » » » 10 months ago, # ^ | ← Rev. 2 → 0 Yes. Because if all inequalities are satisfied, sequence a is a bad sequence.  » 10 months ago, # | 0 For problem D, it is pretty intuitive that the answer only depends on the count of positions with different characters in the two strings, but can someone show me how to prove this formally/mathematically? •  » » 10 months ago, # ^ | ← Rev. 2 → 0 Suppose$a$is different from$b$at$k$places. First notice that it only matters if$a_i = b_i$or$a_i \neq b_i$, and not what the exact values are. That means that we if we flip both$a_i$and$b_i$the answer won't change. So we can assume that$b$consists only of zeros, and$a$has exactly$k$ones. Now, if$X$is uniformly distributed, then so is$p(X)$, where$p$is some permutation of$1...n$. That means that if we permute$a$and$b$in the same way the answer won't change. So we can assume that$a = 0...01...1$with$k$ones and$b = 0...0$. Since all tests with the same$k$can be transformed into the same "canonical" form without changing the answer, they all share the same answer.  » 10 months ago, # | -12 Can someone help prove that using sliding window greedily is incorrect for problem C ? I tried to use this idea but got WA. My submission is 191628511The idea I tried to implement is that we keep a running map that reflects the unique letters of set Q. Whenever the Q's size is < k or a letter has already existed in Q, we can safely make a[i] == b[i], in case they are different.  » 10 months ago, # | 0 Here is an another calculation for D: we have$f(n-1) = 1 + \frac{n-1}{n}f(n-2)+\frac{1}{n}f(n)$and$f(n) = 1 + f(n-1)$, then get$f(n-1) = f(n-2) + \frac{n+1}{n-1} $. Noted that the second part is only related to$i$, so we can caculate this part for every$i$from$n-1$to$1$, with$f(0) = 0$, all$f(i)$can be calculated.My submission: https://codeforces.com/contest/1778/submission/191601709  » 10 months ago, # | -6 There were better ways of explaining question B but bro wake up and choose violence.  » 10 months ago, # | +1 B taught me to read problems properly T.T  » 10 months ago, # | ← Rev. 2 → 0 Seems like I'm not the only one who got brainfucked in B, thinking we have to make all the pairs good :)Nice contest tho!  » 10 months ago, # | 0 Geothermal can you please explain your solution to D ? •  » » 10 months ago, # ^ | +46 Let$x_m$be the expected number of steps to make two strings equal if they are different in$m$of the$n$positions. We observe that$x_0 = 0$,$x_n = 1 + x_{n-1}$, and for all other$m$, we have$x_m = 1 + \frac{m}{n} x_{m-1} + \frac{n-m}{n} x_{m+1}.$This is because there are$m$positions that, if chosen, will change the character at that position from being different among the two strings to being the same, and$n-m$positions at which changing the character will change that position from being the same across both strings to being different.Now, iterating$m$from$n$to$1$, we can solve for each$x_m$in terms of$x_{m-1}$. Afterwards, we can substitute$x_0 = 0$into our equation for$x_1$, then substitute our value for$x_1$into our equation for$x_2$, and so on to derive all of the$x$'s. Our answer is then$x_m$, where$m$is the number of differences between the two input strings.  » 10 months ago, # | -11 it's strange that no one got the third problem on Python  » 10 months ago, # | +38 Quite a great contest! The D is a bit classic but the idea itself is quite great. Problem E is an interesting DS and tree problem but also a bit classic. (I mean the algorithm part) F is a dp on tree related to number theory but for me it's a little bit easier for the position of F. The diversity of algorithm is very great in this contest and hope you guys can do better next time.  » 10 months ago, # | 0 In problem D how can we calculate F(1) •  » » 10 months ago, # ^ | +3 See my above comment: https://codeforces.com/blog/entry/112149?#comment-999324  » 10 months ago, # | +5 Why is this solution for D not correct? Let C be the number of non equal indices.We can only finish in the$C,2N-C,2N+C...$moves. Assumption 1.We call finish in any of the$C,2N+C,4N+..$type moves odd type movesWe call finish in any of the$2N-C,4N-C,..$type moves even type movesThe probability of finishing in C moves =$(C)!/N!$. -->(P2)The probability of finishing in C moves =$(N-C)!*(C!)/N!$. -->(P1)The probability of finishing in 2N-C moves =$(1-P1)*(P2)$.Probability of finishing in$i^{th}$odd move is$P2*(1-P1)^{2i}$Probability of finishing in$i^{th}$even move is$P2*(1-P1)^{2i+1}*(2N(i+1)-c)$Summing moves*probability of odd type we get$\sum_{i=0}^{+\infty} P2*(1-P1)^{2i}*(2Ni+c)$Summing moves*probability of even type we get$\sum_{i=0}^{+\infty} P2*(1-P1)^{2i+1}*(2N(i+1)-c)$The expected odd sum is$(1-P1)^2*(2N*P2)/(1-(1-P1)^2)^2$+$C*P1/(1-(1-P1)^2)$The expected even sum is$(1-P1)^3*(2N*P2)/(1-(1-P1)^2)^2$+$(2N-C)*P1*(1-P1)/(1-(1-P1)^2)$Please let me know my arithmetic or logical mistake. Thanks •  » » 10 months ago, # ^ | 0 You can finish in$C, C+2, C+4, \ldots$moves (not$2N - C$and others). For example, suppose there are$11$differences between$a$and$b$. Then, you can verify that the number of moves needed can be any odd$k\ge 11$(for example, to get$13$first flip a bit to have$12$differences, then go flip correct bits to go from$12$to$0$immediately).  » 10 months ago, # | ← Rev. 2 → 0 l  » 10 months ago, # | 0 Thank you so much for a fast editorial, problems were fun and informative to me, thanks a lot!!  » 10 months ago, # | ← Rev. 2 → 0 The time complexity of C is not O(n*pow(2, min(u, k))) because we just need to check all subsets of length min(k, u) as the subsets of length < min(k, u) are a part of subsets of length min(k, u) and being able to change more letters is never going to bad Hope this helps :) •  » » 10 months ago, # ^ | 0 You only choose subsets with length == k. And complexity will decrease enormously. •  » » » 10 months ago, # ^ | 0 yep, see the edited version :)  » 10 months ago, # | +114 A method to solve range basis query in$O(nlogn)$: (subtree and complement of subtree are weaker)Iterate$r$, we maintain the lexicographically (by index) largest basis, then the query can be handled by simply ignoring all vectors with index less than$l$.To maintain such basis, when you face two vectors on the same row, always keep the right one (one with larger index), because the left one can always use the right one to change itself. •  » » 10 months ago, # ^ | +3 star it = get it •  » » 10 months ago, # ^ | ← Rev. 2 → +26 If someone is interested in this technique, you can check out this problem: 1100F - Ivan and Burgers  » 10 months ago, # | 0 I can't understand what mean by dp[u][d]=inf if (xu*xu) is not multiple of d. Question f someone explain please  » 10 months ago, # | +5 In problem F , why do we always perform the last move on the root vertex of the subtree while calculating dp? •  » » 10 months ago, # ^ | 0 Reason is this, 1) we can only apply one operation on a node. 2) let's say we apply i'th opertion on a root node , then we cannot apply any opertion on root. So last k-i operations are of no use. Why? because the remaining k-i operations has to be performed on the nodes except the root and our answer is dependent on the root node( which is = intial_val_of_root*max_gcd_of_root we get) which will never increase by the last k-i operations , that's it. •  » » » 4 weeks ago, # ^ | ← Rev. 2 → 0 But actually, to make the GCD of the subtree of u equal to a multiple of d, we may use some operations in the subtree of u, but use no operation on u itself. Why can we ignore this case?  » 10 months ago, # | 0 No I got stuck at B....  » 10 months ago, # | +2 Pr**oblem D** There might be some wrong? ** •  » » 10 months ago, # ^ | 0 Fixed it. Thanks.  » 10 months ago, # | 0 Are there any prerequisite topics we need to learn before attempting Problem D? •  » » 10 months ago, # ^ | 0 I am watching Errichto's videos about expected value (EV), which were on my watch later list but it seems like it is time to watch them. •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 any resoureces other than that ?.I am bad at math and very bad at expected values,probabilites  » 10 months ago, # | +10 F can be solve in$O(n\times m)$(Or$O(n\times mlog(m))$? Since I use a map to store the dp value) . Where$m$is the number of divisors of$x_{1}$Consider$dp_{u,x}$as the same in the tutorial. Let$x = \prod{p_{i}^{d_{i}}}$, and$y = \prod{p_{i}^{\lceil \frac{d_{i}}{2} \rceil}}$, we only need to consider two cases:$dp_{u,x} = \sum{dp_{v,x}}$and$dp_{u,x} = 1 + \sum{dp_{v,y}}$, where$v$is all the children of vertex$u$. The first case represent we do not do any operation on vertex$u$, which requires$x | x_{u}$. The second case represent we do one operation on vertex$u$, which requires$y | x_{u}$. Special judge for$u=1$. •  » » 10 months ago, # ^ | 0 Why is that enough to only check the transition dp[v][x] -> dp[v][y] in the second case? •  » » » 10 months ago, # ^ | ← Rev. 2 → 0 This is because y would be the smallest number whose square is a multiple of x. any other such number would end up being a multiple of y. and we know that for 2 numbers n1 and n2 such that n1 is a multiple of n2, dp[n2] <= dp[n1]  » 10 months ago, # | +11 Lots of people are complaining about the contest but there are always people who complain. For me, the round was pretty good and I enjoyed problem C when I figured out how to solve it. •  » » 10 months ago, # ^ | 0 I agree. But I think the problem statements could have been made a little easier to understand.  » 10 months ago, # | 0 What is complexity of C by backtracking solution given above? Is it O(n * pow(2, min(k,u))) because this code will generate all subsets of length <= min(k,u). •  » » 10 months ago, # ^ | ← Rev. 3 → 0 u = no. of unique character in string "a". k = min(u,k). usually we talk about worst case so it will be n*(pow(2,10)).But to be precise I think it will be n*pow(2,u).It is sure,we will go through all subsets of unique characters but for answer to be maximum we will consider only subsets having exactly k elements.Hope you will get. •  » » » 10 months ago, # ^ | 0 I understood the solution but I am asking about time complexity of code  » 10 months ago, # | ← Rev. 2 → 0 Can someone tell me why this code on problem D gets a TLE? https://codeforces.com/contest/1778/submission/191678717 Thank you very much if you can help me or give me some advice. •  » » 10 months ago, # ^ | ← Rev. 2 → 0 I found the size of array is too small just now -such a joke  » 10 months ago, # | 0 What a crap description of Problem B First line they said you are given permutation of length n,an array of m distinct elements. I thought it is a permutation of m distinct integers of length nI read this line around 3-4 times to wrap my head aroundThen this negation effect, if you use negation you need to use bracket to make it clearer.Even after seeing editorial, I did not understand what the question is asking until is saw a comment  » 10 months ago, # | 0 is this Round 844 ? I am sorry Its Round (844+4)  » 10 months ago, # | 0 Can anyone explain why sum decreases by 4 i ai=a(i+1)= 1 ? •  » » 10 months ago, # ^ | 0 Because if a[i] = a[i+1] =1 then you have already added 2 to the sum So you'll decrease sum by 2 then A[i] = A[i+1] = -1 after changing so you'll add -2 to the sum hence -2 + -2 = -4  » 10 months ago, # | 0 In problem C, for the case when u=26, k=10 and n=1e5, won't the number of operations just blow up?$n$*$26 \choose {10}\approx5e11$•  » » 10 months ago, # ^ | 0 There are atmost 10 different characters in string a,so the time complexity is atmost n*$\binom {10}{5}=1e5*252 \approx 2e6$•  » » » 10 months ago, # ^ | ← Rev. 2 → 0 Misunderstood the problem, I thought 10 is the number of characters in A which are different from B. Thanks, for the correction!!  » 10 months ago, # | 0 Shouldn't complexity in E be$O(nlog^2(d))$, where$d=max(a_i)$not$d=log(max(a_i))$? •  » » 10 months ago, # ^ | 0 Yeah. Fixed it. Thanks.  » 10 months ago, # | ← Rev. 7 → 0 probably it's late but I have another solution for problem D which I think it's more easier ,it depends on linearity of expectation. Let$rem$to be the number of positions that have$a_i \neq b_i$and$n$is the size of strings.let$dp_i$the expected number of flips to go from state$i$to$i-1$.let$p_i$the probability of selecting non-equal position which will$p_i=\frac{i}{n}$. By linearity of expectation ,the answer is$\sum_{i=1}^{i=rem}dp_i$. We will calculate$dp_i$from this formula$dp_i= p_i .1 +(1-p_i)(1+dp_{i+1}+dp_i)$and then simplifying$dp_i= \frac{1+(1-p_i).dp_{i+1}}{p_i}$. finally the base case is$dp_n=1$because in this state we will definitely go to state$dp_{i-1}$only. Codeimport sys from array import array input = lambda: sys.stdin.buffer.readline().decode().strip() inp = lambda dtype: [dtype(x) for x in input().split()] debug = lambda *x: print(*x, file=sys.stderr) ceil1 = lambda a, b: (a + b - 1) // b Mint, Mlong, out = 2 ** 31 - 1, 2 ** 63 - 1, [] add = lambda a, b: (a % mod + b % mod) % mod mult = lambda a, b: (a % mod * b % mod) % mod div = lambda a, b: mult(a, inv(b)) inv = lambda a: pow(a, -1, mod) mod = 998244353 for _ in range(int(input())): n, a, b = int(input()), input(), input() rem = 0 for i in range(n): rem += a[i] != b[i] dp = array('i', [0] * (n + 1)) dp[n], den = 1, inv(n) for i in range(n - 1, 0, -1): p = mult(i, den) dp[i] = div(1 + mult(1 - p, dp[i + 1]), p) out.append(sum(dp[1:rem + 1]) % mod) print('\n'.join(map(str, out))) Sorry for my bad english it's my first try for explanation. •  » » 10 months ago, # ^ | 0 great explanation ..  » 10 months ago, # | 0 I have a question please help in problem dWe get, ai=n+i⋅ai−1n−i⋅bi−1 and bi=n−in−i⋅bi−1 for 2≤i≤n.f(i)=ai+bi⋅f(i+1).so why can't be just get value of f(i+1) directlyf(i+1) = (f(i)- ai ) / bi Why can't we directly find value like this?  » 10 months ago, # | 0 Great problems. Really enjoyed the round despite struggling with B for way too long.How can this solution still be too slow for Test #30 in problem C? (PyPy 3) Any way I can write the for-loop faster.https://codeforces.com/contest/1778/submission/191729330  » 10 months ago, # | 0 Isn't the worst case time complexity for C : O(2kn) •  » » 10 months ago, # ^ | 0 I think because of the:"if sum(cc) == k:" you will only get a time complexity of 252 * n. ( 10!/(5!*5!) = 252 ) •  » » » 10 months ago, # ^ | 0 Okay that makes sense, but there are still 2e7 operations at max which I think is a lot for 2 seconds when doing recursion. •  » » » » 10 months ago, # ^ | 0 Very true. Thank you for you helpful answer!  » 10 months ago, # | ← Rev. 3 → 0 Got clarified thanks  » 10 months ago, # | +3 I see a lot of comments for problem D, I found the alternative approach pretty interesting so I made a video on it, you can find this on the channel- here . If the video doesn't show up then please wait for a while as YT sometimes takes a bit long to process it. Happy coding :)  » 10 months ago, # | 0 How did one can come to conclusion to write f(x) = ai + bi*f(i-1) by just seeing one value for f(2) ? We already have equation f(i) = 1+ A*f(i-1)+B*f(i+1) form right ? so just concluding that f(i) just depends only on f(i-1) by taking one example of f(2) sounds unintuitive to me  » 10 months ago, # | 0 This worked for problem D so maybe it will work for problem E... Geothermal can you please explain you solution for problem E? I think people (myself) would be interested in knowing how it works. •  » » 10 months ago, # ^ | +5 For the most part, my solution is equivalent to the model solution: in particular, I compute subtree XOR bases and use them to answer queries where the root is equal to or outside the subtree of our given vertex.The component of my solution that differs from my solution is the case where the root is in the subtree of our vertex. Let c be the child of our vertex whose subtree contains the root; we can find c by binary searching on the pre-order traversal. We note that we are essentially computing the maximum XOR of all vertices outside the subtree of c. The model solution thus precomputes XOR bases for all prefixes and suffixes of the preorder traversal, then merges the bases for the prefix and suffix excluding the subtree of c to compute the answer.My solution instead uses rerooting DP to directly compute the XOR basis of all vertices outside the subtree of c for each vertex c in the tree. To perform the rerooting, I use a similar prefix basis/suffix basis idea: for each vertex, I merge the XOR bases for each prefix and suffix of its children; then, to go from a vertex to its child, I merge the XOR basis containing v and vertices outside the subtree of v with appropriate prefix and suffix bases.I think the model solution is much more elegant and easier to implement than mine; I would have implemented it had I thought of it in contest. Unfortunately, I was being a bit silly, so this is what I ended up with :) •  » » » 10 months ago, # ^ | 0 Ah that makes a lot of sense. So instead of using the euler tour for computing your prefix and suffix XOR basis you did it directly on the children of each node and found a way to transition using the prefix and suffix XOR basis of the node's siblings, nice.I agree it's not as clean, but I think it's a cool idea. Thanks for sharing.  » 10 months ago, # | 0 Problem D reminded me of https://codeforces.com/contest/1753/problem/C  » 10 months ago, # | 0 Has this round been unrated? My rating still keeps unchanged yet!  » 10 months ago, # | 0 when will the contest rating be shown to us??  » 10 months ago, # | +2 C is very strange. O(10^8) solution is also working which I think usually do not work. Moreover, I found many solutions which were accepted during contest but after contest giving TLE. One more thing my solution is accepted only after I passed the vector by reference to the recursive funtion.  » 10 months ago, # | ← Rev. 2 → +8 Don't forget to update the rating of #848 for me later. I was in div1 when registered in this contest, but that's because my negative rating in TypeDB round was rolled back temporarily, and I should be counted as div2 in this contest. MikeMirzayanov  » 10 months ago, # | 0 There are certain solutions for problem c which have been tested for28 test cases only whereas there are others which are tested for 38 test cases. Some solutions which were accepted during the contest are giving tle right now when submitted. •  » » 10 months ago, # ^ | 0 I noticed this too, my C passed main tests with 500 ms but now barely squeaks by with 1950 ms. •  » » 10 months ago, # ^ | 0 Here are two submission for c. Both are same but one which was accepted during contest is still accepted while I copy pasted it and it is giving TLE.Accepted Submission : https://codeforces.com/contest/1778/submission/191808748My Submission : https://codeforces.com/contest/1778/submission/192095509 giving TLE  » 10 months ago, # | ← Rev. 3 → 0 Is this solution for problem D correct.Let us call the bits that are not same in A and B as different bits and the bits that are same in A and B as same bits. We know that the no of moves to make the two strings can be$K + 2 t$where$t>=0$and$K$is the no of different bits.We can find the expected value by summing the terms prob(it takes i moves to make the two strings equal)*i . We can see that we have to flip the different bits odd no of times and the same bits even no of times . So we can calculate the probability of taking i moves to make the two strings same by solving the integral equation and multiply it with$(1/n)^i$as we are making i moves . The integral equation is$(2k_1+1)+(2k_2+1)+....+(2k_n) = i$where the odd terms corresspond to diff bits and even terms to same bits. The solution of this integral equation will be${C_{n -1 }^{n-1 + \dfrac{i-k} {2}}}$So the final formula is${\sum_{t = 0}^\infty \dfrac{K+ 2t} {n^{2t+K}} C_{t}^{n+t-1}}$Is there any way to proceed from this as this summation is involving infinite terms  » 10 months ago, # | 0 192167224 why is this TLE ? How do I improve it? Div2D  » 10 months ago, # | 0 Bangladeshi Guys. Wow  » 8 months ago, # | 0 Hey can anyone explain the intuition behind problem A shy the sum is reduced by 4 and increased by 4 ?  » 6 months ago, # | ← Rev. 2 → 0 Problem F can also be done with a brainless$O(36*36*n)$5D dp if you observe that only the prime factors of the root node's value matter, and each node's value has atmost 4 unique prime factors. The dp state will be:$dp[v][p][q][r][s]$which holds the minimum number of moves required to make the lowest frequency in any node in subtree of$v$of the$1$'st till the$4$'th prime factor equal to$p$,$q$,$r$and$s\$ respectively (minimums can occur in different nodes for different prime factors).Implementation:link
 » 6 months ago, # | ← Rev. 2 →   0 adnan_toky Suppose in question C we take U = 26 and K = 10 . Will the #operations won’t go over 10^10 ?
•  » » 6 months ago, # ^ |   0 okay got it !
 » 5 months ago, # |   0 Sorry for disturbing old discussion but could anyone explain how Red people or black-red people have used bitmasking in Problem C? Brute force is pretty simple but i don't get the mask idea. This is jiangly's submission which i do not seem to understand properly? why is he comparing the number of bits set in K with the number of bits set for a particular alphabet frequency. 191557742