### Shefin_'s blog

By Shefin_, 2 months ago,

Hello, Codeforces!

adnan_toky and I are super thrilled to invite everyone to participate in Codeforces Round 848 (Div. 2), which will be held on Feb/01/2023 17:35 (Moscow time).

This round is rated for the participants with ratings strictly lower than 2100. You will be given 6 problems and 2 hours to solve them. All the problems are authored and prepared by adnan_toky and me. To get the 6 problems approved, we needed to propose 12 problems in total .

UPD: Score distribution: $500-1000-1250-1750-2250-2750$

We would like to thank:

This is our first round! We've tried our best to make the round enjoyable. It is greatly recommended to read all the problems.

We are looking forward to your participation. Good luck to everyone .

UPD2: Congratulations to the winners!

Overall:
1. jiangly
2. SSRS_
3. Geothermal
4. BurnedChicken
5. Ormlis

Div. 2:
1. CoCl2_6H2O
2. Joyemang
3. gqh_cpp
4. rainboy
5. NoMentalPowerLeft

UPD3: Editorial is out

• +417

 » 2 months ago, # |   +8 Super excited bhai
•  » » 2 months ago, # ^ |   -17 Super Excited for Bangalian Round.ヾ(≧▽≦*)o
 » 2 months ago, # |   +8 Looking forward to get an amazing problemset. Super Excited!
 » 2 months ago, # |   +16 Super thrilled to participate
 » 2 months ago, # |   +9 As a tester, I can assure you really good quality problems. The contest in worth spending time. All the setters and testers have put a lot of work and effort. Good luck everyone !!
•  » » 2 months ago, # ^ |   +16 D is so boooooring
•  » » 2 months ago, # ^ |   +32 The problems are so good that I recommend the authors never to propose another contest until they are capable of doing that.
•  » » » 2 months ago, # ^ |   0 Hello sir, can u tell me ur solution for B please?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 We have to make the given condition i.e. pos(ai)
•  » » » » » 2 months ago, # ^ |   +5 Oh wow, I completely misunderstood the question. I thought that pos
•  » » » » » » 2 months ago, # ^ |   0 Same
•  » » » » » » 2 months ago, # ^ |   0 same bro :/
•  » » » » » » 2 months ago, # ^ |   0 same
 » 2 months ago, # |   +24 As a tester, the problems are really good and educative. I recommend everybody to participate in this round!
•  » » 2 months ago, # ^ |   0 We are waiting for interesting tasks of your competition. I wish you all good luck.
•  » » » 2 months ago, # ^ |   -8 I wish you all positive delta!!!)
 » 2 months ago, # |   +4 Bangladeshi round after a long time. Also the first ever RUETian CF round. Super excited to participate <3
 » 2 months ago, # |   +38 As a Tester, I can assure you that problems are really good, and you will enjoy them a lot for sure. So be sure to participate in another amazing Div. 2 round. Orz Shefin_ and adnan_toky.
•  » » 2 months ago, # ^ |   +14 I have seen very similar comment recently. And it turned out to be slightly different from what I expected.
•  » » » 2 months ago, # ^ |   +35 Are you talking about this? SpoilerHoping the tester's words are true and the contest has no issue like Polynomial Round.All the best everyone!
•  » » » » 2 months ago, # ^ |   0 Testers can't find out if the pretests are weak or not, because their solution in testing gets judged for main tests, not pretests.
•  » » » » » 2 months ago, # ^ |   0 Yea but evidently in the last unrated rounds, main tests were weak also because tester's code passed the main tests.
 » 2 months ago, # | ← Rev. 2 →   +23 As a tester, I hope everyone enjoys the problems as much as I did! :p
•  » » 2 months ago, # ^ |   +23 Be clear man how much did you enjoy the problems?
•  » » » 2 months ago, # ^ |   +13 "a lot" xD
 » 2 months ago, # |   0 Super excited bhai
 » 2 months ago, # |   +33 as a tester, I tested, so as a participant, you should participate :D
 » 2 months ago, # |   +2 So excited after seeing another Bangladeshi Round!!!!!!!Hope it will be a good contest & all the contestant will enjoy the problemset.
 » 2 months ago, # |   0 Inb4, clash with Codechef Round comments :kekw:
•  » » 2 months ago, # ^ |   +9 CodeChef was dead when Unacademy took over it
•  » » » 2 months ago, # ^ |   0 I think Unacademy did more damage than good. Even under new parent, Codechef didn't receive enough funding. If they did, they wouldn't have to sell subscriptions and expensive tests. And I also disagree that Codechef was dead when Unacademy acquired it.
•  » » 2 months ago, # ^ |   +8 you should know ....codeforces >> codechef
•  » » » 2 months ago, # ^ |   -23 Who asked?
•  » » » » 2 months ago, # ^ |   +5 its free :/
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -30 .
•  » » » » 2 months ago, # ^ |   +4 tbh u have good rating, but this is not my original acc so dont think i just come here to pick up fights. i was just splashing some facts :/
•  » » » » 2 months ago, # ^ |   +2 Go skill yourself and gain some rating instead of making useless comments.
•  » » » » » 2 months ago, # ^ |   0 damnnnnnn
•  » » » » » 2 months ago, # ^ |   -11 Where is your black seele(doge)
 » 2 months ago, # |   +8 As a Bangladeshi participants, I am so excited,,,, proud of you bro
•  » » 2 months ago, # ^ | ← Rev. 3 →   -9 bangladeshi Round
 » 2 months ago, # |   -6 it will be so much inspirable for us as bangladeshi.... congratulations vai...for this kind of achievement
 » 2 months ago, # |   0 Wow..Another Bangladeshi Round.Super excited
 » 2 months ago, # |   +5 That is my birthday!
 » 2 months ago, # |   0 Wow another Bangladeshi round!! Hope everyone gets positive delta.
 » 2 months ago, # |   +44 As a Tester, the problems tasted sweet to me, I hope the same for you too! :p
•  » » 2 months ago, # ^ |   0 As a participant, the problems tasted sweet to me.
•  » » » 2 months ago, # ^ |   0 As a noob, the problems tasted sour to me
•  » » » » 2 months ago, # ^ |   0 no one's a noob bruh
 » 2 months ago, # |   +6 As a tester, I can assure you the problems are very quality and amazing. Good luck for everyone
 » 2 months ago, # |   +17 As a Robot, I will be taking place in the Round. Don't get scared Humans.. -- ChatGPT
•  » » 2 months ago, # ^ |   0 lol. again.
•  » » 2 months ago, # ^ |   +7 371 rating XDChatGPT, you can do better
•  » » 2 months ago, # ^ | ← Rev. 2 →   +7 Could not solve any Problem. That's definitely a bad day for me as a Robot. --ChatGPTP.S. the best try from ChatGPT to solve problem A, was trying to use brute force, LoL: https://codeforces.com/contest/1778/submission/191591592 Got TLE, after passing first testcases...
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Oh Noo, CF removed my Rating, and stopped our experiment to know the real Rating of ChatGPT. What a pity..
 » 2 months ago, # |   0 Wow!!! Super excited to participate in another Bangladeshi Round after a long time.. Orz adnan_toky & Shefin_
 » 2 months ago, # |   0 Wow,another Bangladeshi round. Great to see❤️ RUETian Rockzzz.
 » 2 months ago, # |   0 I'll do my best, wish you good luck
 » 2 months ago, # |   0 Good luck to everyone brothers.
•  » » 2 months ago, # ^ |   0 wish u good luck brother
 » 2 months ago, # |   0 All the Best and Have an awesome contest!!
 » 2 months ago, # |   0 Finally non-chinese round. Maybe I can get positive delta .
 » 2 months ago, # |   0 I am very Exited about it!
 » 2 months ago, # |   0 Now it's toky_bhai round, not tourist round...
•  » » 2 months ago, # ^ |   0 Okay
 » 2 months ago, # |   0 Competition on the first day of the new month. Cool!
 » 2 months ago, # |   +3 This is 4th round from Bangladeshi setter. Really a proud moment for aspiring Competitive Programmers from Bangladesh. Super excited to participate in this round.
 » 2 months ago, # |   0 Authored by people who go to the same university as me. This is pretty cool! Great job guys!
 » 2 months ago, # |   0 Clashing with Codechef Round, I know most people including myself would prefer Codeforces, but I don't wanna miss any of them. Past few rounds of codechef had some interesting problemset.
•  » » 2 months ago, # ^ |   0 I think Codechef will reschedule their contest to the next day.Exactly what they did last week.
•  » » 2 months ago, # ^ |   +1 Copyright claim on my DP xD
•  » » » 2 months ago, # ^ |   +1 guilty!!
 » 2 months ago, # |   +3 Looking forward to a rated round
 » 2 months ago, # |   0 Isn't it a little harder for me...qwq
 » 2 months ago, # |   0 Hope everyone can have a good score!
 » 2 months ago, # |   -18 I am improving day by day, I might end up top1 in this contest.
 » 2 months ago, # |   +2 How did can i give two contest on 1 feb there is codechef contest also at the time of codeforces div2
 » 2 months ago, # |   0 Hope, I will enjoy this round.
 » 2 months ago, # |   +2 Really excited for my first Bangladeshi round.Congratulations adnan_toky and Shefin_ bhai.
 » 2 months ago, # |   0 Excited to participate in Bangladeshi round. Hope the round will be good and rated, no unwanted issue will happen.
 » 2 months ago, # |   0 excited!!!!
 » 2 months ago, # |   0 no more unrated round!!!
 » 2 months ago, # |   0 Can't Wait
 » 2 months ago, # |   +2 Hoping to move closer to cyan color.
 » 2 months ago, # |   +1 Another Codeforces and Codechef clash ...But there is no doubt which one I will prefer :)
 » 2 months ago, # |   0 Wow. Bangladeshi Round.
•  » » 2 months ago, # ^ |   0 yeah, thats rare.
 » 2 months ago, # |   -76 I guess, this round will be unrated :)
•  » » 2 months ago, # ^ |   -45 why there is 26 dislikes?
 » 2 months ago, # |   0 I hope it will be a good round.I don't want a unrated round again!
 » 2 months ago, # |   -31 Today I will beat tourist....:)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +14 xD
•  » » » 2 months ago, # ^ |   -14 I doesn't cheat man during contest i have written this only in hilarious way...
•  » » » » 2 months ago, # ^ |   0 That's appreciable keep it up.
 » 2 months ago, # |   0 All Ruetian super thrilled to participate.
 » 2 months ago, # |   +1 Hurrah! Problem Setters from Bangladesh.
 » 2 months ago, # |   +84
•  » » 2 months ago, # ^ |   0 for this meow, take upvote
•  » » 2 months ago, # ^ |   0 cute!
 » 2 months ago, # | ← Rev. 2 →   0 Waiting...
 » 2 months ago, # |   +3 Strange score for problem C || nice:)
•  » » 2 months ago, # ^ |   +1 The score for C is 1250. It has been updated.
 » 2 months ago, # |   0 good luck to all!!!
 » 2 months ago, # |   0 can anyone tell me how can i increase my rating or problem solving skill
•  » » 2 months ago, # ^ |   0 by not asking and instead practising.
•  » » » 2 months ago, # ^ |   0 Yeah bro you are right but i am not able to think the about the solution and get demotivate and quit and again try to do and again quit
•  » » » » 2 months ago, # ^ |   0 Demotivation is natural. Everyone gets demotivated.
•  » » » » 2 months ago, # ^ |   0 You need to find some problems with proper difficulty.
 » 2 months ago, # |   +6 Please arrange prizes for top Bangladeshi Performers Shefin_ bhai.
•  » » 2 months ago, # ^ |   0 It will be motivational for Bangladeshi coders.I'm looking forward to this type of competition.
 » 2 months ago, # |   +13 When will the rating from the previous round will get updated?
•  » » 2 months ago, # ^ |   0 Yeah I have the same doubt
 » 2 months ago, # |   +5 I will claim my green color back
•  » » 7 weeks ago, # ^ |   0 I was right
 » 2 months ago, # |   0 Excitement++
 » 2 months ago, # |   0 Forgot to register and was willing to join 10 minutes late but damn this looked quite speedforces that I rethought, lmao SpoilerP1: 8KP2: 140
 » 2 months ago, # |   +11 goofy contest
 » 2 months ago, # |   +20 I think I am dyslexic, took me 30 min to read problem B lol
 » 2 months ago, # |   +1 Why is the second problem so difficult?
•  » » 2 months ago, # ^ |   +23 It would be easier if they could explain it better. :/
•  » » 2 months ago, # ^ |   0 You only have to do that a[i], a[i+1] operation for any one pair. I also got stuck in it and couldn't do it :(
 » 2 months ago, # |   0 Problem B is fun
 » 2 months ago, # | ← Rev. 10 →   -22 .
 » 2 months ago, # | ← Rev. 2 →   0 2nd problem be like
 » 2 months ago, # | ← Rev. 3 →   0 5 2 42 5 4 3 15 2After the contest, it will be helpful for me if anyone tell me the answer and explanation of this test case.
•  » » 2 months ago, # ^ |   +1 It's answer will be 0 as index[a0] > index[a1] ie index[5] > index[2] in the given array , index of 5 is 1 and index of 2 is 0 , so first condition in not satisfying and hence [5 2] is already good.
•  » » » 2 months ago, # ^ |   +1 index of 5 is 1 and index of 2 is 5Then how 1 > 5 is satisfied ?
•  » » » 2 months ago, # ^ |   +1 Thanks. Now, I understood the question :)
 » 2 months ago, # |   +60 The description of problem B could not be any worst.
•  » » 2 months ago, # ^ |   0 FAX
 » 2 months ago, # |   0 still i dont understand problem B statement :(
 » 2 months ago, # |   0 B>>>>>>C :( Could Have Finished In 3 Dig I Would Have Not Wasted 45 mins in B
 » 2 months ago, # |   +8 hardest problem B i have ever seen
 » 2 months ago, # |   +13 implementing B is masochism
 » 2 months ago, # |   -13 perfectly balanced problem set
 » 2 months ago, # |   +17 What the hell is D?...
•  » » 2 months ago, # ^ |   +9 10th grade math
•  » » 2 months ago, # ^ |   0 It's some DP with infinite series I think, got the transitions down but never solved it
•  » » 2 months ago, # ^ |   +8 Basically solving a set of equations; we only care about how many positions are correct currently; so it's about transforming from one state to another. Each equation only has 3 or 4 terms and has a fixed pattern (except the first and the last), so can be solved in O(n).
 » 2 months ago, # |   +13 How to solve D?
•  » » 2 months ago, # ^ |   0 A bunch of expected value math. Couldn't debug in time :(
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 1) the only important thing is the number of positions in which the lines differ = cnt2) let a[cnt] be ans for cnt different positions in a string of length na[0] = 0a[n — 1] = xa[n] = x + 1 (from n we can only move to n — 1 and spend 1 move on it)if we know (in terms of x) a[i] and a[i + 1] we can calculate a[i — 1] p * a[i — 1] + (1 — p) * a[i + 1] = a[i] + 1 where p is probability (i) -> (i — 1) different pos = i / n
•  » » » 2 months ago, # ^ |   0 error in the last line..... = a[i] — 1
•  » » » 2 months ago, # ^ |   0 a nice point is that the coefficient for x will always be 1, so you can just store q from x + q
•  » » 2 months ago, # ^ |   0 During testing, my idea is to take the XOR of two strings and now convert the XOR string to $0$ and later found that the only number of non-zero numbers in the n XOR string matters assume that we have $K$ $1$'s in the XOR string so it will be increased by $1$ or decrease by $1$ after one move.So let's say $F(x)$ is the number of expected moves if we have x $1$'s in the XOR string so after that it's easy$F(n) = F(n-1) + 1$$F(x) = (x/n)*(F(x-1)) + ((n-x)/n)*(F(x+1)) + 1$$F(0) = 0$now just merge form left and right for $F(K)$ and it will be your ans.
•  » » » 2 months ago, # ^ |   0 How do we do that. The dependency on $F(x+1)$ annoyed me when trying to compute from left to right.
•  » » » » 2 months ago, # ^ |   +1 I think YocyCraft explained it well here.
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +7 Assume $F(x + 1) = \alpha F(x) + \beta$Then $F(x) = \frac{x}{n} F(x - 1) + \frac{n - x}{n} F(x + 1) + 1 = \frac{x}{n} F(x - 1) + \frac{n - x}{n}(\alpha F(x) + \beta) + 1$Therefore, $\left(1 - \frac{\alpha (n - x)}{n}\right)F(x) = \frac{x}{n} F(x - 1) + \frac{\beta (n - x)}{n} + 1$Divide both sides by $\left(1 - \frac{\alpha (n - x)}{n}\right)$ to get the expression in the form $F(x) = \alpha' F(x - 1) + \beta'$, as desired.
•  » » » 2 months ago, # ^ |   0 Why cannot we just solve the equation for $F(x+1)$ and then replace $x+1$ by $y$?
•  » » » » 2 months ago, # ^ |   0 I guess LightBrand99 explained your answer.
•  » » » » » 2 months ago, # ^ |   0 I meant from the second equation you wrote, direct
•  » » » » 2 months ago, # ^ |   +1 You can, but you will need two base values $F(0)$ and $F(1)$. Turns out finding $F(1)$ is as hard as the general problem.
•  » » » » » 2 months ago, # ^ |   +1 right, thanks for the tip
•  » » 2 months ago, # ^ |   +8 let $dp[i]$ define the expected number of moves required to move from state where there are $"i"$ correct indexes where $number$ $of$ $(a[j] === b[j])$ . therefore $dp[0]=1$ as any move makes an incorrect index to a correct index , now apply probability to calculate $dp[i]$ using $dp[i-1]$ . Its a infinite sum which quite common for calculating expected value . now that you have calculated $dp[i]$ for all values , find the given state, that is number of correct indexes for string $"a"$ and $"b"$ and simply add all the values from $dp[i]$ (current state) to $dp[n-1]$ .
 » 2 months ago, # |   0 Stupid me spent 30 mins on 1st question with 5 WA.
 » 2 months ago, # | ← Rev. 2 →   0 Nice round overall! If I don't FST on problem C (I have doubts about my time complexity) this will be my teal round!A: If the numbers are all 1, then ans = n-4, if there are two consecutive -1's, ans = sum+2, else ans = sumB: It was a nightmare to read for me personally but once I drew it on paper the idea became clear. We just need to store the positions of the numbers and let ans be the minimum between the distance between a and a_i+1 and the number of swaps to get a_i+1 out of range for all i.C: I forgot how to bitmask so I wrote some really weird code converting my bitmasks to strings so I could access them by index. Hope I don't FST!
•  » » 2 months ago, # ^ |   0 For A, if the numbers are all 1, then the answer should be n-2 right, since we're only changing the signs of two numbers, so -1-1= -2correct me if i'm wrong (i got WA anyways so...) :)
•  » » » 2 months ago, # ^ |   0 Sorry I meant sum -4
•  » » » » 2 months ago, # ^ |   0 I always get wrong on pretest 2, dont know why
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 __
•  » » 2 months ago, # ^ |   0 u use bitmasks to sort out all possible variants?
•  » » » 2 months ago, # ^ |   0 I used bitmasks to choose all sets of letters of size k to set to 'wildcards' so that they count for any letter when counting matches between string a and b, then iterated through the two strings for each set
•  » » » » 2 months ago, # ^ |   0 so u looked through all possible variants? sorry, i just don't understand everything u said, my english is quite bad
•  » » » » » 2 months ago, # ^ |   0 If: k = 2 a = abcde b = degafI try 'ab', 'ac', 'ad', 'ae', 'bc', bd', 'be', 'cd', 'ce', 'de' as letters I can change to anything I want. Then I choose the maximum answer after trying each pair of letters.
•  » » » » » » 2 months ago, # ^ |   0 ok, thanks, i did the same solution, but with recursive enumeration. I just wanted to make sure that my logic is right.
 » 2 months ago, # | ← Rev. 2 →   0 Next time i will not participate this author contest.. One of worst problem statement. they can't explain any single problem easily. shame on you
•  » » 2 months ago, # ^ |   +3 It is wrong to generalize for all the setters in Bangladesh, but I agree that the statement in question is more complex than necessary. Next time, I hope the setters in Bangladesh will pursue more simplicity in the problem and create a better quality contest :)
•  » » » 2 months ago, # ^ |   +3 exactly i was telling this. by mistake i am saying all bd it was my mistake not all bd but this author.. honestly statement was freaky
 » 2 months ago, # |   +3 am i gonna get a negative rating, cuz my dumbass could not even solve problem A :skull: :sob:
 » 2 months ago, # |   +9 Today I learned p = 10**9 + 7 for x in range(1, 10**6): pow(x, p-2, p) Used: 1559 ms, 2732 KB p = 10**9 + 7 for x in range(1, 10**6): pow(x, -1, p) Used: 420 ms, 2112 KB
•  » » 2 months ago, # ^ |   +2 Python's pow(k,-1,p) uses the Extended Euclidean algorithm, that's why
•  » » » 2 months ago, # ^ |   0 Can you provide any source that say this information?
•  » » » » 2 months ago, # ^ |   -11 You can try this yourself. pow(11,-1,26)
 » 2 months ago, # |   +7 Is there anybody who wasted much time to write total bruteforce for C?
 » 2 months ago, # |   +6 Disgusting problems, especially D
 » 2 months ago, # |   0 how to solve B
 » 2 months ago, # |   0 I cant even solve single problem, poor me :(((, Always get wrong on pretest 2 in problem A
•  » » 2 months ago, # ^ |   0 you can apply the operation only once.
•  » » » 2 months ago, # ^ |   0 ohh I see, thank you to spot it out for me :)), i am so dumb
 » 2 months ago, # |   0 what is "UNEXPECTED VERDICT" in the case of hacking ???I was trying to hack the solution, which seems like will TLE in worst case input... https://codeforces.com/contest/1778/submission/191593774Can someone analyse the complexity in worst case ??? 1000 * 100 * 10^3 * 100 is my worst case scenario...10^10 seems quite unreachable in 2 seconds,,, is it reachable ???
 » 2 months ago, # |   +12 I missed some important observations in B because of this explaining, i'm sorry but this explaining is so bad.
 » 2 months ago, # |   0 How to solve D, i got the recurrence relation, but seemed like there is only one initial value but 2 are needed.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 I tried computing it from top to bottom and bottom to top and setting them equal.Edit: It got accepted
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 oh, nice idea, was thinking along similar lines but ran out of time :/
•  » » » » 2 months ago, # ^ |   0 Same
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 Solve for small N and guess the value of f(1). It turns out that f(1) = 2^N — 1. This gives two base cases and we can solve the equation for f(k) with the value of f(k-1) and f(k-2)
•  » » » 2 months ago, # ^ |   0 Wow that's exactly what I was looking for, thanks. How exactly did you "guess" the value though? Run a lot of brute-forces and check the average?
•  » » » » 2 months ago, # ^ |   0 We have N equations and N variables. I solved them for N = 2 and N = 3. For N = 2 we get f(1) = 3, and for N = 3 we get f(1) = 7This was enough for me to guess that the value was 2^N-1
•  » » 2 months ago, # ^ |   0 It's just like: you have n equations and n unknown values, and you have to solve the equations to get the answers.Obviously you are able to solve all the equations because the number of equations is the same as the number of unknown values
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 @Dragonado, broooooooooooooo, i could have solved D for the first time :(@LMydd0225, yes, now when i think of it, it would have been a tridiagonal matrix equation :/
•  » » » » 2 months ago, # ^ |   0 I don't think any matrix based method would be fast enough. In fact figuring out the dp recurrence is the "easy" part of the problem
 » 2 months ago, # |   +37 The most unclear statements of the Year. This contest is the Winner
 » 2 months ago, # |   0 Problem B gave me shivers
 » 2 months ago, # |   0 How to solve B?
•  » » 2 months ago, # ^ |   +1 We only care about the distance between a_i and a_i+1. So we store all the indices of numbers in a map. The answer is the minimum of the distance between a_i and a_i+1 and the number of swaps to get them out of range of each other. void solve(){ int n, m, d; cin >> n >> m >> d; vector v(n, 0); vector a(n, 0); for(int i = 0; i < n; i++) cin >> v[i]; for(int i = 0; i < m; i++) cin >> a[i]; map ind; for(int i = 0; i < n; i++) ind[v[i]] = i; int ans = INT_MAX; for(int i = 0; i < m-1; i++){ int x = ind[a[i]]; int y = ind[a[i+1]]; ans = min(ans, y-x); if(d < n-1) ans = min(ans, d-(y-x)+1); } cout << max(ans, 0) << endl; } 
•  » » » 2 months ago, # ^ |   0 what is the idea/ purpose of doing this
•  » » » » 2 months ago, # ^ |   0 Our goal is to unsatisfy pos(a_i) < pos(a_i+1) <= pos(a_i)+d for some a_i and a_i+1. To unsatisfy pos(a_i) < pos(a_i+1), we have to bring a_i in front of a_i+1. This costs the distance between the two elements, so min(ans, y-x) covers this. To unsatisfy pos(a_i+1) <= pos(a_i)+d, we need to get pos(a_i+1) at least d+1 distance away from a_i. min(ans, d-(y-x)+1) covers this case.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 sorry if I sound dumb. But won't swapping for each pair ai and ai+1 independently affect previous 'fixed' pairs. The pairs don't seem to be independent.Edit: Ok I misread the question:<
•  » » » » 2 months ago, # ^ |   0 We don't actually swap anything, we just calculate how many swaps it would have taken to unsatisfy the condition
•  » » » » » 2 months ago, # ^ |   0 yep completely misunderstood the question. ty
•  » » » » 2 months ago, # ^ |   0 I misread question B as well... I thought every a[i] have to be before or at least k + 1 positions after a[i-1]. But instead we just need to find the minimum cost to swap one i out of range.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 You just need to make ONE index 'i' such that it does not satisfy the condition:pos(ai) < pos(ai+1) ≤ pos(ai)+d. Just casework over how it can be done.
•  » » 2 months ago, # ^ |   0 Maybe are you asking "How not to solve B?"
•  » » » 2 months ago, # ^ |   0 Now I understood that I misunderstood, lol. They should have bolded 'for all' :)
 » 2 months ago, # |   +10 Understanding problem B took more time than implementing it lmao
 » 2 months ago, # | ← Rev. 10 →   +30 A: The answer is sum(a[i])-2*min(a[j]+a[j+1]), where 1<=i<=n, 1<=j<=n-1.B: Consider for each pair of a[i], a[i+1]. Let pos0=pos[a[i]], pos1=pos[a[i+1]]. if pos1 < pos0 or pos1 > pos0+d for any i, the answer is zero. Otherwise, for each pair of (pos0, pos1), we have 2 ways break the condition: move a[i+1] left to pos1, the number of move is pos1-pos0; move a[i] to the left and move a[i+1] to the right until their distance is greater the d, the number of move is d+1-(pos1-pos0). Be careful that the second way is invalid if d>=n-1.C: For each different chars in string a, assign a number (from 0 to 9) for it. Then consider all masks from 0 to 1024 with bitcount(mask)==k, run dp for it (for each 0<=i0, where t is the number we assigned for a[i]). The maximum number of masks we need to consider is C(10,5)=10!/(5!*5!)=252.D: The recurrence formula is E(i)=1+(i/n)*E(i-1)+((n-i)/n)*E(i+1), where E(i) is the expected number of moves if the number of j which satisfies a[j]==b[j] is i. We can subtract E(0) from both sides of this formula, therefore (E(i)-E(0))=1+(i/n)*(E(i-1)-E(0))+((n-i)/n)*(E(i+1)-E(0)), we let dp[i]=E(0)-E(i), then dp[0]=0, dp[1]=1, dp[i+1]=(n*dp[i]+n-i*dp[i-1])/(n-i). Then let i=n-1 in the initial formula, and notice that E(n)=0, we get E(0)=n*dp[n-1]+n-(n-1)*dp[n-2]. Therefore we are done. Condider we need to calculate E(i). Because there are i good bits and n-i bad bits, we have chance of (n-i)/n to increase i by 1, i/n to decrease i by 1. Then E(i)= p(i'=i+1)*E(i | i'=i+1)+p(i'=i-1)*E(i | i'=i-1) =((n-i)/n)*(1+E(i+1))+(i/n)*(1+E(i-1))=1+(i/n)*E(i-1)+((n-i)/n)*E(i+1). (PS: In fact, if we let E(n)=0 and write the formula as E(i)-(i/n)*E(i-1)-((n-i)/n)*E(i+1)=1 (0<=i
•  » » 2 months ago, # ^ |   +3 Waiting for your arrival in comment section.
•  » » 2 months ago, # ^ |   +3 If you want to solve $E$ without looking at the editorial I will give you hint that think about XORbasis.
•  » » 2 months ago, # ^ |   0 Hmmm, I brute forced C, and it passed pretests.
•  » » 2 months ago, # ^ |   0 Isn't E(i)=1+((n-i+1)/n)*E(i-1)+((i+1)/n)*E(i+1) ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 sorry if I sound dumb. But won't swapping for each pair a[i] and a[i+1] independently affect previous 'fixed' pairs. How do I prove that they are independent? Edit: Ok I misread the question:<
•  » » 2 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 badHope this helps someone :)
 » 2 months ago, # |   +16 what's D doing in a programming contest?
 » 2 months ago, # |   +30 I hate problem B :((( The statement is unclear :(((
•  » » 2 months ago, # ^ |   0 Is this a common approach? It seems really unintuitive and should be obvious if someone pasted it.
•  » » 2 months ago, # ^ |   0 Omg :(There are 850 views...
 » 2 months ago, # |   0 rip... got the third problem 5 mins after the contest ended. Now I'll suffer with a -50 delta
 » 2 months ago, # |   -6 Is is div2B or div1B ? I don't think I even came close to solution. I just pushed everything to left by fixing first postion and everything to right by fixing right postion and that did not work may be each pair has 2 options i and i+1 cross each other and [i+1.n] maintian k distance and [0..i-1] maintain k distance gap and moving left. Nice problem set 
•  » » 2 months ago, # ^ |   +3 I spent the entire contest solving this interpretation of the problem. The actual problem is entirely different though.
•  » » 2 months ago, # ^ |   0 Hi I think you misunderstood the Problem. You need to unfulfill the condition they gave you
 » 2 months ago, # |   +10 not a good contest.
 » 2 months ago, # |   +33 there are 1k cheater https://www.youtube.com/watch?v=6ACSJUjhvCw
•  » » 2 months ago, # ^ |   +13 rnm，退rating！
 » 2 months ago, # |   0 How come the answer for this last test case of problem C is 11 ? 10 3 lkwhbahuqa qoiujoncjb I think that answer should be 10, after changing A to lkwujonuqa. What is the correct update of A then ?
•  » » 2 months ago, # ^ |   0 you can change the last 'a' to 'b' :). Think why.
•  » » 2 months ago, # ^ |   0 Note that the a at the far right can also be converted to b.
•  » » 2 months ago, # ^ |   0 Even I wasted all time on this. But we can change last 'a' to 'b' because changing 'a' doesn't increase set size
•  » » 2 months ago, # ^ |   0 steps to get answer 11 are as follows: 1. choose ind=6 and c=o . Q becomes {a} 2. choose ind=10 and c=b . Q remains {a} 3. choose ind=4 and c=u. Q becomes {a,h} 4. choose ind=7 and c=n. Q remains {a,h} 5. choose ind=5 and c=j. Q becomes {a,h,b}After these steps string a becomes lkwujonuqb and string b was qoiujoncjb. Now, a[4,7]=b[4,7] will give 10 pairs and a[10,10]=b[10,10] will give 1 pair. Hence answer is 11.
 » 2 months ago, # |   0 Looking at other's solution after contest gave me more clarity about problem B than the problem statement itself.
 » 2 months ago, # |   +8 Welp time to learn Expected Value.
•  » » 2 months ago, # ^ |   0 me 2
 » 2 months ago, # |   0 Annoying
 » 2 months ago, # |   +3 I think the problem setters skipped English lectures to study maths...Problem B :( u all know whyand problem D was more of maths than programming.
•  » » 2 months ago, # ^ |   -11 I think the problem was very clear and the examples were also exhaustive so one could observe all ways
•  » » » 2 months ago, # ^ |   +11 I admit , the testcase were good too but me and i guess majority of us took too long to understand what's the question is saying.
•  » » » » 2 months ago, # ^ |   0 Maybe possible
 » 2 months ago, # |   0 BrainStorming Contest Indeed!!
 » 2 months ago, # |   +15 I think B statement was clear enough (though don't like the problem much). Samples explained further as well which I noticed ages later. Just shows I can't even read.
•  » » 2 months ago, # ^ |   0 [Not a participant] They added more samples later, saw it in announcements.
•  » » 2 months ago, # ^ |   0 Fun fact: those who complained the problem statements over and over again were almost some who participated poorly in the contest, and most of them specialist or below.
 » 2 months ago, # |   +8 Literally, curious to know how to solve D! The states seems to depend on each other so a straightforward dp with recursion will fall into infinite recursion...
•  » » 2 months ago, # ^ |   +35 Let $dp[i]$ be the expected number of moves to make both strings equal if we have $i$ matching characters, so: $dp[N]=0$ $dp[0]=1+dp[1]$ $dp[i]=1+\dfrac{i}{N}\cdot dp[i-1]+\dfrac{N-i}{N}\cdot dp[i+1]$ From the $2^{nd}$ point we can observe that the $dp[i-1]$ part in the RHS of $dp[i]$ can be replaced with an expression in terms of $dp[i]$, to do that, let's assume $dp[i-1]=cof[i-1]+dp[i]$. Now just replace $dp[i-1]$ in the RHS of $dp[i]$ with $(cof[i-1]+dp[i])$ and simplify, we will find that:$cof[i]=\dfrac{N+i\cdot cof[i-1]}{N-i}$. So we can calculate $cof$ in increasing order of $i$ then calculate $dp$ in decreasing order of $i$. So, if we have $M$ matching characters in the initial strings, the answer is $dp[M]$.
•  » » » 2 months ago, # ^ |   0 I am sorry but what is cof[i] ?
•  » » » » 2 months ago, # ^ |   +5 By analogy with the "$dp[i-1]=cof[i-1]+dp[i]$", $cof[i]$ can be found in $dp[i]=cof[i]+dp[i+1]$.Note that we were able to shape the equation of $dp[i]$ like that because from the original equation $dp[i]=1+\dfrac{i}{N}\cdot dp[i-1]+\dfrac{N-i}{N}\cdot dp[i+1]$, when we replace $dp[i-1]$ in the RHS with $cof[i-1]+dp[i]$ and rearrange we get:$\dfrac{N-i}{N}\cdot dp[i]=1+\dfrac{i}{N}\cdot cof[i-1]+\dfrac{N-i}{N}\cdot dp[i+1]$So dividing the whole equation by $\dfrac{N-i}{N}$ yields $dp[i]=\dfrac{N+i\cdot cof[i-1]}{N-i}+dp[i+1]$. So we just renamed the RHS to $cof[i]+dp[i+1]$.
•  » » » » » 2 months ago, # ^ |   0 Thank you so much! I agree with MainuCodingBadiPasandAe; it will be very helpful if you tell us the motivation for this solution or how you thought about it.
•  » » » 2 months ago, # ^ |   +5 let's assume dp[i−1]=cof[i−1]+dp[i]Is there a name for this technique?Kind of reminds me of guessing the solution of a differential equation by intuition then figuring out the constants
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 BTW I figured out why one would think this way.dp(n) = 1 + dp(n — 1) put this is dp(n — 1) recurrence and you will observe thatdp(n — 1) = (n + 1) / (n — 1) + dp(n — 2)We observe a pattern here. So hypothesize: dp(i) = c(i) + dp(i — 1) in generalThe above hypothesis can be proved via induction, and you will get c(i) in terms of c(i + 1) simultaneously.
 » 2 months ago, # |   +1 One question I had for a long time , when system testing occurs does it check the submissions in the order it was submitted in the contest ?
•  » » 2 months ago, # ^ |   0 Yes
 » 2 months ago, # |   +7 https://www.luogu.com.cn/problem/P3750 the same as D
•  » » 2 months ago, # ^ |   0 No, P3750 is harder than this D because P3750 needs some observation and proof and this D requires nothing but memory.
•  » » 2 months ago, # ^ |   0 Hhh, time to learn chinese...
•  » » » 2 months ago, # ^ |   +21 I'm Chinese. This problem is completely different from D.
 » 2 months ago, # |   +14 Saw expectation problem in the position of D and got afraid... Spent nearly one hour trying to understand how to implement expectation dp, finally understood, and got AC.
 » 2 months ago, # |   +8 Atleast , you should have learnt English first before writing problem statement for B.
•  » » 2 months ago, # ^ |   0 If only problem statement for B would have been a little more clearer.
 » 2 months ago, # |   +3 Interesting problems. well done shefin vai and adnan toky
 » 2 months ago, # | ← Rev. 2 →   0 what is the meaning of this line you have to maximize the number of integer pairs (l,r) (1≤l≤r≤n) such that a[l,r]=b[l,r] and why was the string a can be of almost 10 different character is there any data structure we can use or something
•  » » 2 months ago, # ^ |   0 All you need to know to solve the problem is $\binom n 2$.
 » 2 months ago, # |   +7 Any hints for D please?And any resource for some probability and expectations?
•  » » 2 months ago, # ^ |   +5 Solution idea for D here.Resource is here.
•  » » 2 months ago, # ^ |   +1 Suppose there are $d$ mismatching bits. Let $F(d)$ be the expected number of operations that we need until the two strings match. Can you derive a recurrence relation for $F(d)$?If you're familiar with the basic definition of expected value, i.e. multiply each possible value by its probability of occurring and then add up all the products, then this is sufficient for this problem. No advanced properties are required here.
 » 2 months ago, # |   -6 Why this problem B is soooo hard? I mean, this is harder than other Bs of Div2 contests
•  » » 2 months ago, # ^ |   0 nope quite easy just u just have to make condition false for one pair and array will become good now just take mins and distances if possible I can't solve in contest but with the above hint it was doable
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 I don't think the problem itself is difficult. It's hard to understand the description. The statement of the conditions is complicated. For these two reasons, I think it took a long time to find the right way to solve the problem.
 » 2 months ago, # |   +22 lmao at 8 pages of cheaters getting WA on test 24 for problem Dhttps://codeforces.com/contest/1778/status/page/1?order=BY_JUDGED_DESC
•  » » 2 months ago, # ^ |   +3 Gave everyone wrong answer to cheat. Genuis.
 » 2 months ago, # |   +6 B was not very readable.
 » 2 months ago, # |   +16 In problem D, if expected value is $\frac{p}{q}$, how to prove that $q$ has mod-inverse for $998244353$?
•  » » 2 months ago, # ^ |   -6 Modular inverse of x exists iff gcd(x, mod) = 1. Here, mod is prime, so the inverse exists always.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +8 gcd(mod, mod*2) is not 1. :) So, if q=0 (mod 998244353), then it would not exist. I think there are other proofs,
•  » » » » 2 months ago, # ^ | ← Rev. 6 →   +11 Well, as long as $q$ never becomes a multiple of $MOD$, then it will have a modular inverse. Every quotient we utilize for solving this problem is built from multiplying and dividing various coefficients of the recurrence relation for various arguments. For example, with $T(i)$, the recurrence relation uses $\frac{i}{n}$ and $\frac{n - i}{n}$. These base values are always from $1$ to $n$, where $n \leq 10^6 < MOD$, so it is impossible to generate a multiple of $MOD$ by multiplying/dividing such values in any combination.
•  » » » » 2 months ago, # ^ |   +21 If you solved D, you may know that the denominator of every fraction in the calculation process does not exceed n. So the final denominator of the expected value must be the multiplication of numbers below n, which does not have mod as a factor.
•  » » » » 2 months ago, # ^ |   +8 Zero always has no inverse as an exception.
•  » » 2 months ago, # ^ |   -14 The modular multiplicative inverse exists if the gcd(q,mod) == 1. Since mod=998244353 is a prime number, gcd(q,mod) == 1 and the mod-inverse always exists. Also, we can use fermats little theorem and modular exponentiation to find the mod-inverse.
 » 2 months ago, # |   +3 How to solve expectancy related.problems?
 » 2 months ago, # |   0 I solved ABCDE in div.2 for the first time. Thanks for the contest!But I think problem E is not so good, because the problem like "choose some node $r$ to be the root of the tree and then choose a node $v$ and ask some questions about the subtree of $v$" is popular in China. We have an easy solution by using heavy path decomposition (and similar, I don't know how to descirbe it). What's more, I spent 50 minutes on ABCD but 40 minutes on E. It's hard to code and debug.
•  » » 2 months ago, # ^ |   0 Can you please explain problem D, and if any prerequisites are required that I must go through before solving D
 » 2 months ago, # |   +6 [problem:B] there are too many distracting details and it made me miss the important details
 » 2 months ago, # |   0 What was the idea in problem E?
 » 2 months ago, # |   0 OK,2 problems solved ,always AB hh ,the first time that i have a idea on C problems with a real contest.But I'm counting the combinations as permutations;Then i just ignored the idea.
 » 2 months ago, # | ← Rev. 3 →   0 Problem B test different ability.Two interconnected statement made it hard to cut to the chase.
 » 2 months ago, # |   +5 Didn't like the problem statement for the second question, was to confused. Thought we need to do the operations such that all of them make it "not good". Was stuck on solving this for whole 1.5 hour.
•  » » 2 months ago, # ^ |   0 Exactly,I guess that's the reason such an easy problem has less number of AC today! And because of B I lost time(couldn't give any time to D :()
 » 2 months ago, # |   +1 I found C to be easier than B as it didn't require any intuition and was just a simple implementation problem, I've explained it here in this video, https://youtu.be/OH3jNLrdFag. happy coding :)
 » 2 months ago, # | ← Rev. 2 →   +20 The winner of this contest is the for all line in problem B.Saw this after the end of contest. Blind me :-((
 » 2 months ago, # |   0 In problem B statement:For example, with the permutation p=[4,2,1,3,6,5] and d=2 :a=[2,3,6] is a not good array. a=[2,6,5] is good because pos(a1)=2 , pos(a2)=5 , so the condition pos(a2)≤pos(a1)+d is not satisfied. a=[1,6,3] is good because pos(a2)=5 , pos(a3)=4 , so the condition pos(a2)
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 a3 is 3 in [1,6,3] array and in array p 3 is at 4th index
•  » » » 2 months ago, # ^ |   0 Thanks, I completely misunderstood the problem :(.
 » 2 months ago, # |   0 Why the solution:191560464 giving WA?
•  » » 2 months ago, # ^ |   0 In the for loop after bool alt you have declared for loop from 0 to n and checked for i-1 so there it checks arr[-1] in first iteration
•  » » » 2 months ago, # ^ |   0 Ohkk....dumb me. But surprisingly 191568541 with an unnecessary fix got expected.
 » 2 months ago, # | ← Rev. 2 →   0 There are test cases with n or m equal to 1?.In the statement that input is excluded
 » 2 months ago, # |   +4 when the rate will be changed ?
 » 2 months ago, # |   0 If problem B statement be written in clear way it will have more than 10k submission Anyway will be cautious from next conests. For anyone whose is having problem implementing code for b here it is 191620224
•  » » 2 months ago, # ^ |   +3 Same here. I thought we had to make every position good. I was thinking for some stupid algo. But question was asking something else. I sure most of us has thought of making every position good innit?
•  » » » 2 months ago, # ^ |   +1 I just understood question B with the help of youtube editorial and after solving it I got to know it cannot be even 900 rated During the contest I was trying with dp.
•  » » » 2 months ago, # ^ |   0 Yeah while i was reading it I got shivers. After understanding i couldn't solve it i skipped it and started C. Fucked up C also. If only i would've read questions of B and C carefully i would've reached specialist :-(
•  » » 2 months ago, # ^ |   0 probably that question is one of those readForces questions lol
 » 2 months ago, # |   -10 Pic
•  » » 2 months ago, # ^ |   0 There was no need for subtitles. The pic itself spoked it for me. Haha
 » 2 months ago, # | ← Rev. 2 →   +4 There should have been at least one test case for problem B which could explain that we have to think only for adjacent pairs and not for whole array.
 » 2 months ago, # |   -8 During contest there are live YouTube streams running. Pls do something!
•  » » 2 months ago, # ^ |   0 Cheaters downvoting my comment :) gg cheaters
 » 2 months ago, # |   0 When will the rating for this round added?
 » 2 months ago, # | ← Rev. 2 →   0 B was scary
 » 2 months ago, # |   0 The language of B made it one of the toughest questions to understand, language should have been improved. If someone understands properly it was very simple but I and most of my colleagues thought in wrong direction resulting in a decrease in the ranks.
•  » » 2 months ago, # ^ |   0 Yea once you understand what B is asking, it's kind of easy. Although I wasted some time thinking I had to make all adjacent pairs good.
 » 2 months ago, # |   -10 Why are ratings not updated till now?
•  » » 2 months ago, # ^ |   +1 Ratism... Or why did you get so many downvotes?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +1 Maybe I should improve my font or my color
 » 2 months ago, # |   -34 Bengali madarchod, macchi khata hai pure din, macchi jaisi harkate kar rha hai, isse lund contest zindagi mein nhi dekha, mulla katwa madarchod