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:

- darkkcyan for incredible coordination and help with the problem preparation
- Alexdat2000 for the Russian translations and precious help regarding the statements and limits
- KAN for upgrading the quality of statements
- Gary2005, awoo, Huah, feecle6418, vinfat, marvinthang, Psychotic_D, tallbee23, Black_Be4rD, Hasnaine_, tanus_era, thisIsMorningstar, __FaRiA_eFa__, masood_, Ryu204, badlad, TomiokapEace and ayhan23 for testing this round and providing valuable feedbacks
- MikeMirzayanov for the amazing Codeforces and Polygon platforms
**You**, for participating in this round

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

Super excited bhai

Super Excited for Bangalian Round.ヾ(≧▽≦*)o

Looking forward to get an amazing problemset. Super Excited!

Super thrilled to participate

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 !!

Dis so boooooringThe problems are

so goodthat I recommend the authors never to propose another contest until they are capable of doing that.Hello sir, can u tell me ur solution for B please?

We have to make the given condition i.e.

pos(ai)<pos(ai+1)≤pos(ai)+dfalse. We can make make this condition false by 2 ways. We can make either the conditionpos(ai)<pos(ai+1)false by crossing them in original array using swapping OR we can make second i.e.pos(ai+1)≤pos(ai)+dfalse by either shifting theaielement left in the original array or by shifting theai+1element right in the original array. Out of these three ways the minimum cost way will be the answer. Corresponding code: [submission:https://codeforces.com/contest/1778/submission/191583606]Oh wow, I completely misunderstood the question. I thought that pos<pos(ai+1)<=pos(ai)+d for ALL I, not for just one. Sooo wow that's unfortunate. I spent all my time solving the wrong question. And now that I look at C, that was also really easy... I hate how bad the explanation for B was.

Same

same bro :/

same

As a tester, the problems are really good and educative. I recommend everybody to participate in this round!

We are waiting for interesting tasks of your competition. I wish you all good luck.

I wish you all positive delta!!!)

Bangladeshiround after a long time. Also the first everRUETianCF round. Super excited to participate <3As 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.I have seen very similar comment recently. And it turned out to be

slightlydifferent from what I expected.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!

Testers can't find out if the pretests are weak or not, because their solution in testing gets judged for main tests, not pretests.

Yea but evidently in the last unrated rounds, main tests were weak also because tester's code passed the main tests.

As a tester, I hope everyone enjoys the problems as much as I did! :p

Be clear man how much did you enjoy the problems?

"a lot" xD

Super excited bhai

as a tester, I tested, so as a participant, you should participate :D

So excited after seeing another

BangladeshiRound!!!!!!!Hope it will be a good contest & all the contestant will enjoy the problemset.

Inb4, clash with Codechef Round comments :kekw:

CodeChef was dead when Unacademy took over it

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.

you should know ....

codeforces >> codechef

Who asked?

its free :/

.

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 :/

Go skill yourself and gain some rating instead of making useless comments.

damnnnnnn

Where is your black seele(doge)

As a Bangladeshi participants, I am so excited,,,, proud of you bro

bangladeshi Round

it will be so much inspirable for us as bangladeshi.... congratulations vai...for this kind of achievement

Wow..Another Bangladeshi Round.

Super excited

That is my birthday!

Wow another Bangladeshi round!! Hope everyone gets positive delta.

As a Tester, the problemstasted sweetto me, I hope the same for you too! :pAs a participant, the problems tastedsweetto me.As a noob, the problems tasted sour to meno one's a noob bruh

As a tester, I can assure you the problems are very quality and amazing. Good luck for everyone

As a Robot, I will be taking place in the Round. Don't get scared Humans.. -- ChatGPT

lol. again.

371 rating XD

ChatGPT,

you can do betterCould not solve any Problem. That's definitely a bad day for me as a Robot. --ChatGPT

P.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...

~~Oh Noo, CF removed my Rating, and stopped our experiment to know the real Rating of ChatGPT. What a pity..~~Wow!!! Super excited to participate in another Bangladeshi Round after a long time.. Orz adnan_toky & Shefin_

Wow,another Bangladeshi round. Great to see❤️ RUETian Rockzzz.

I'll do my best, wish you good luck

Good luck to everyone brothers.

wish u good luck brother

All the Best and Have an awesome contest!!

Finally non-chinese round. Maybe I can get positive delta .

I am very Exited about it!

Now it's toky_bhai round, not tourist round...

Okay

Competition on the first day of the new month. Cool!

This is 4th round from Bangladeshi setter. Really a proud moment for aspiring Competitive Programmers from Bangladesh. Super excited to participate in this round.

Authored by people who go to the same university as me. This is pretty cool! Great job guys!

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.

I think Codechef will reschedule their contest to the next day.Exactly what they did last week.

Copyright claim on my DP xD

guilty!!

Looking forward to a rated round

Isn't it a little harder for me...qwq

Hope everyone can have a good score!

I am improving day by day, I might end up top1 in this contest.

How did can i give two contest on 1 feb there is codechef contest also at the time of codeforces div2

Hope, I will enjoy this round.

Really excited for my first Bangladeshi round.

Congratulations adnan_toky and Shefin_ bhai.

Excited to participate in Bangladeshi round. Hope the round will be good and rated, no unwanted issue will happen.

excited!!!!

no more unrated round!!!

Can't Wait

Hoping to move closer to cyan color.

Another Codeforces and Codechef clash ...

But there is no doubt which one I will prefer :)

Wow.

BangladeshiRound.yeah, thats rare.

I guess, this round will be unrated :)

why there is 26 dislikes?

I hope it will be a good round.I don't want a unrated round again!

Today I will beat tourist....:)

xD

I doesn't cheat man during contest i have written this only in hilarious way...

That's appreciable keep it up.

All Ruetian super thrilled to participate.

Hurrah! Problem Setters from Bangladesh.

for this meow, take upvote

cute!

Waiting...

Strange score for problem C || nice:)

The score for C is 1250. It has been updated.

good luck to all!!!

can anyone tell me how can i increase my rating or problem solving skill

by not asking and instead practising.

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

Demotivation is natural. Everyone gets demotivated.

You need to find some problems with proper difficulty.

Please arrange prizes for top Bangladeshi Performers Shefin_ bhai.

It will be motivational for Bangladeshi coders.I'm looking forward to this type of competition.

When will the rating from the previous round will get updated?

Yeah I have the same doubt

I will claim my green color back

I was right

Excitement++

Forgot to register and was willing to join 10 minutes late but damn this looked quite speedforces that I rethought, lmao

SpoilerP1: 8K

P2: 140

goofy contest

I think I am dyslexic, took me 30 min to read problem B lol

Why is the second problem so difficult?

It would be easier if they could explain it better. :/

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 :(

Problem B is fun

.

2nd problem be like5 2 4

2 5 4 3 1

5 2

After the contest, it will be helpful for me if anyone tell me the answer and explanation of this test case.

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.

index of 5 is 1 and index of 2 is 5

Then how 1 > 5 is satisfied ?

Thanks. Now, I understood the question :)

The description of

problem Bcould not be any worst.FAX

still i dont understand problem B statement :(

B>>>>>>C :( Could Have Finished In 3 Dig I Would Have Not Wasted 45 mins in B

hardest problem B i have ever seen

implementing B is masochism

perfectly balanced problem set

What the hell is D?...

10th grade math

It's some DP with infinite series I think, got the transitions down but never solved it

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).

How to solve D?

A bunch of expected value math. Couldn't debug in time :(

1) the only important thing is the number of positions in which the lines differ = cnt

2) let a[cnt] be ans for cnt different positions in a string of length n

a[0] = 0

a[n — 1] = x

a[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

error in the last line

..... = a[i] — 1

a nice point is that the coefficient for x will always be 1, so you can just store q from x + q

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.

How do we do that. The dependency on $$$F(x+1)$$$ annoyed me when trying to compute from left to right.

I think YocyCraft explained it well here.

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.

Why cannot we just solve the equation for $$$F(x+1)$$$ and then replace $$$x+1$$$ by $$$y$$$?

I guess LightBrand99 explained your answer.

I meant from the second equation you wrote, direct

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.

right, thanks for the tip

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]$$$ .

Stupid me spent 30 mins on 1st question with 5 WA.

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 = sum

B: 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!

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= -2

correct me if i'm wrong (i got WA anyways so...) :)

Sorry I meant sum -4

I always get wrong on pretest 2, dont know why

__

u use bitmasks to sort out all possible variants?

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

so u looked through all possible variants? sorry, i just don't understand everything u said, my english is quite bad

If: k = 2 a = abcde b = degaf

I 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.

ok, thanks, i did the same solution, but with recursive enumeration. I just wanted to make sure that my logic is right.

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

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 :)

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

am i gonna get a negative rating, cuz my dumbass could not even solve problem A :skull: :sob:

Today I learned

Used: 1559 ms, 2732 KB

Used: 420 ms, 2112 KB

Python's

`pow(k,-1,p)`

uses the Extended Euclidean algorithm, that's whyCan you provide any source that say this information?

You can try this yourself.

`pow(11,-1,26)`

Is there anybody who wasted much time to write total bruteforce for C?

Disgusting problems, especially D

how to solve B

I cant even solve single problem, poor me :(((, Always get wrong on pretest 2 in problem A

you can apply the operation only once.

ohh I see, thank you to spot it out for me :)), i am so dumb

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/191593774

Can 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 ???

I missed some important observations in B because of this explaining, i'm sorry but this explaining is so bad.

How to solve D, i got the recurrence relation, but seemed like there is only one initial value but 2 are needed.

I tried computing it from top to bottom and bottom to top and setting them equal.

Edit: It got accepted

oh, nice idea, was thinking along similar lines but ran out of time :/

Same

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)

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?

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) = 7

This was enough for me to guess that the value was 2^N-1

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

areable to solve all the equations because the number of equations is the same as the number of unknown values@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 :/

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

The most unclear statements of the Year. This contest is the Winner

Problem

Bgave me shiversHow to solve B?

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.

what is the idea/ purpose of doing this

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.

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:<

We don't actually swap anything, we just calculate how many swaps it would have taken to unsatisfy the condition

yep completely misunderstood the question. ty

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.

You just need to make

ONEindex '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.

Maybe are you asking "How not to solve B?"

Now I understood that I misunderstood, lol. They should have bolded 'for all' :)

Understanding problem B took more time than implementing it lmao

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<=i<n, consider i is valid position if a[i]==b[i] or mask&(1<<t)>0, 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.

(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<n), we can get a tridiagonal equation system, where the coefficient matrix is a tridiagonal matrix. )

E: No idea.

Waiting for your arrival in comment section.

If you want to solve $$$E$$$ without looking at the editorial I will give you hint that think about XORbasis.

Hmmm, I brute forced C, and it passed pretests.

Isn't E(i)=1+((n-i+1)/n)*E(i-1)+((i+1)/n)*E(i+1) ?

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:<

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 someone :)

what's D doing in a programming contest?

I hate problem B :((( The statement is unclear :(((

Any comments about this being posted in contest time?

Is this a common approach? It seems really unintuitive and should be obvious if someone pasted it.

Omg :(

There are 850 views...

rip... got the third problem 5 mins after the contest ended. Now I'll suffer with a -50 delta

I spent the entire contest solving this interpretation of the problem.

The actual problem is entirely different though.

Hi I think you misunderstood the Problem. You need to unfulfill the condition they gave you

not a good contest.

there are 1k cheater https://www.youtube.com/watch?v=6ACSJUjhvCw

rnm，退rating！

How come the answer for this last test case of problem C is 11 ?

I think that answer should be 10, after changing

`A`

to`lkwujonuqa`

. What is the correct update of A then ?you can change the last 'a' to 'b' :). Think why.

Note that the a at the far right can also be converted to b.

Even I wasted all time on this. But we can change last 'a' to 'b' because changing 'a' doesn't increase set size

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

abecomeslkwujonuqband stringbwasqoiujoncjb. 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.Looking at other's solution after contest gave me more clarity about problem B than the problem statement itself.

Welp time to learn Expected Value.

me 2

Annoying

I think the problem setters skipped English lectures to study maths...

Problem B :( u all know why

and problem D was more of maths than programming.

I think the problem was very clear and the examples were also exhaustive so one could observe all ways

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.

Maybe possible

BrainStorming Contest Indeed!!

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.

[Not a participant] They added more samples later, saw it in announcements.

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

specialistor below.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...

Let $$$dp[i]$$$ be the expected number of moves to make both strings equal if we have $$$i$$$ matching characters, so:

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]$$$.

I am sorry but what is cof[i] ?

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]$$$.

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.

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

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 that

dp(n — 1) = (n + 1) / (n — 1) + dp(n — 2)

We observe a pattern here. So hypothesize: dp(i) = c(i) + dp(i — 1) in general

The above hypothesis can be proved via induction, and you will get c(i) in terms of c(i + 1) simultaneously.

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 ?

Yes

https://www.luogu.com.cn/problem/P3750 the same as D

No, P3750 is harder than this D because P3750 needs some observation and proof and this D requires nothing but memory.

Hhh, time to learn chinese...

I'm Chinese. This problem is

completelydifferent from D.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.

Atleast , you should have learnt English first before writing problem statement for B.

If only problem statement for B would have been a little more clearer.

Interesting problems. well done shefin vai and adnan toky

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

All you need to know to solve the problem is $$$\binom n 2$$$.

Any hints for D please?

And any resource for some probability and expectations?

Solution idea for D here.

Resource is here.

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.

Why this problem

Bis soooo hard? I mean, this is harder than otherBs of Div2 contestsnope 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

I don't think the problem itself is difficult.

For these two reasons, I think it took a long time to find the right way to solve the problem.

lmao at 8 pages of cheaters getting WA on test 24 for problem D

https://codeforces.com/contest/1778/status/page/1?order=BY_JUDGED_DESC

Gave everyone wrong answer to cheat. Genuis.

B was not very readable.

In problem D, if expected value is $$$\frac{p}{q}$$$, how to prove that $$$q$$$ has mod-inverse for $$$998244353$$$?

Modular inverse of x exists iff gcd(x, mod) = 1. Here, mod is prime, so the inverse exists always.

gcd(mod, mod*2) is not 1. :) So, if q=0 (mod 998244353), then it would not exist. I think there are other proofs,

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.

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.

Zero always has no inverse as an exception.

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.

How to solve expectancy related.problems?

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.

Can you please explain problem D, and if any prerequisites are required that I must go through before solving D

[problem:B] there are too many distracting details and it made me miss the important details

What was the idea in problem E?

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.

Problem B test different ability.Two interconnected statement made it hard to cut to the chase.

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.

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 :()

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 :)

The winner of this contest is the

for allline in problem B.Saw this after the end of contest. Blind me :-((

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)<pos(a3) is not satisfied.

How is pos(a3)=4 for the last array a?

a3 is 3 in [1,6,3] array and in array p 3 is at 4th index

Thanks, I completely misunderstood the problem :(.

Why the solution:191560464 giving WA?

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

Ohkk....dumb me. But surprisingly 191568541 with an unnecessary fix got expected.

There are test cases with n or m equal to 1?.In the statement that input is excluded

when the rate will be changed ?

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

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?

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.

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 :-(

probably that question is one of those readForces questions lol

PicThere was no need for subtitles. The pic itself spoked it for me. Haha

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.

During contest there are live YouTube streams running. Pls do something!

Cheaters downvoting my comment :) gg cheaters

When will the rating for this round added?

B was scary

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.

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.

Why are ratings not updated till now?

Ratism... Or why did you get so many downvotes?

Maybe I should improve my font or my color

Bengali madarchod, macchi khata hai pure din, macchi jaisi harkate kar rha hai, isse lund contest zindagi mein nhi dekha, mulla katwa madarchod