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 01.02.2023 17:35 (Московское время).
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, tolbi, 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
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 !!
D is so boooooring
The problems are so good that 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)+d false. We can make make this condition false by 2 ways. We can make either the condition pos(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)+d false by either shifting the ai element left in the original array or by shifting the ai+1 element right in the original array. Out of these three ways the minimum cost way will be the answer. Corresponding code: [submission:https://mirror.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 :/
As a tester, the problems are really good and educative. I recommend everybody to participate in this round!
Bangladeshi round after a long time. Also the first ever RUETian CF round. Super excited to participate <3
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.
I have seen very similar comment recently. And it turned out to be slightly different from what I expected.
Hoping 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
as a tester, I tested, so as a participant, you should participate :D
So excited after seeing another Bangladeshi Round!!!!!!!
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
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.
Where is your black seele(doge)
As a Bangladeshi participants, I am so excited,,,, proud of you bro
Wow..Another Bangladeshi Round.
Super excited
That is my birthday!
As a Tester, the problems tasted sweet to me, I hope the same for you too! :p
As a participant, the problems tasted sweet to me.
As a noob, the problems tasted sour to me
no 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 better
Could 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://mirror.codeforces.com/contest/1778/submission/191591592 Got TLE, after passing first testcases...
Finally non-chinese round. Maybe I can get positive delta .
Now it's toky_bhai round, not tourist round...
Okay
This is 4th round from Bangladeshi setter. Really a proud moment for aspiring Competitive Programmers from Bangladesh. Super excited to participate in this round.
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.
Copyright claim on my DP xD
guilty!!
Looking forward to a rated round
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
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.
no more unrated round!!!
Hoping to move closer to cyan color.
Another Codeforces and Codechef clash ...
But there is no doubt which one I will prefer :)
Wow. Bangladeshi Round.
yeah, thats rare.
I hope it will be a good round.I don't want a unrated round again!
Today I will beat tourist....:)
xD
Hurrah! Problem Setters from Bangladesh.
cute!
Strange score for problem C || nice:)
The score for C is 1250. It has been updated.
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.
When will the rating from the previous round will get updated?
I will claim my green color back
I was right
5 минут осталось, жду, не дождусь, когда начнётся соревнование! Всем удачи! Надеюсь, я смогу хотя б одну задачку решить :)
Forgot to register and was willing to join 10 minutes late but damn this looked quite speedforces that I rethought, lmao
P1: 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 :(
.
5 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 B could not be any worst.
FAX
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
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 Andalus 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]$$$ .
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
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
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://mirror.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 are able 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 :/
The most unclear statements of the Year. This contest is the Winner
Любительский разбор задачи D. Гибкая строка возвращается + исходник
Пусть $$$k$$$ — кол-во совпадений в двух строках. Одна замена увеличивает совпадения на $$$1$$$, или уменьшает совпадение на $$$1$$$. То есть, из $$$k$$$ у нас есть переход в $$$(k+1) $$$ совпадение с вероятностью $$$\frac{(n-k)}{n}$$$, либо $$$(k-1)$$$ совпадение с вероятностью $$$\frac{k}{n}$$$.
Обозначим мат.ожидание шагов до условия
k == nкакE[k]— начинаем с $$$k$$$ совпадениями и делаем случайные операции пока не получим $$$n$$$ совпадений. По условию задачи,E[n] = 0, то есть, если все элементы равны, то делаем $$$0$$$ шагов.Теперь, наконец-то, применим формулы условного мат.ожидания.
Вспоминая переходы
k->(k+1)с вероятностью(n-k) / nи переходk->(k-1)с вероятностьюk/n, получаем следующее уравнение:Здесь
E[k]— текущее состояние. Мы переходим вE[k+1]с вероятностью((n-k) / n)и как бы начинаем заново оттуда (независимо), но кол-во операций увеличится на $$$1$$$ из-за перехода — отсюда $$$+1$$$ в скобке. Также мы переходим вE[k-1]с вероятностью(k / n)и начинаем заново оттуда, и кол-во операций увеличится на $$$+1$$$ из-за сделанного перехода.Теперь у нас есть $$$n+1$$$ уравнений и $$$n+1$$$ неизвестных. Уравнения
(k == 0)и(k == n)особые. Раскрываем скобки, переносим неизвестные в левую сторону, а константы — в правую. Решаем систему линейных уравнений. Она будет трёхдиагональная (ненулевые коэффициенты только $$$k-1$$$, $$$k$$$ и $$$k+1$$$), поэтому применяем метод трёхдиагональной прогонки.Ответ на задачу это
E[кол-во совпадений изначально].Исходный код решения
Спасибо за разбор
Не самая лучшая задача, так как до уравнения дойти очень легко, а дальше нужно просто знать как решать такие уравнения. Я не знал, поэтому не решил, хотя такое же уравнение написал почти сразу.
Если знаете метод гаусса, то можно вывести самому. Сначала нужно обнулить коэффициенты элементарными преобразованиями под элементом $$$A(0,0)$$$ за счёт нулевой строки, затем под $$$A(1,1)$$$ за счёт первой строки, и т.д. Так как каждое уравнение содержит не более 3-х неизвестных и все они расположены возле диагонального элемента, то это за O(1) для каждого коэффициента делается. Суммарно O(n). Потом можно снизу-вверх пойти и пообнулять уже элементы над диагональными, но лично я на контесте вбил в яндексе "метод прогонки C++" и скопипастил код из Викиучебник -> Реализации алгоритмов -> Метод прогонки, переименовав переменные.
Problem B gave me shivers
How 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
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 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.
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) ?
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...
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
Atolkwujonuqa. What is the correct update of A then ?Even I wasted all time on this. But we can change last 'a' to 'b' because changing 'a' doesn't increase set size
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
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.
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 specialist or 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 TheBhediyaOfDalalStreet; 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
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 ?
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 completely different 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 B is soooo hard? I mean, this is harder than other Bs of Div2 contests
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://mirror.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.
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.
[problem:B] there are too many distracting details and it made me miss the important details
What was the idea in problem E?
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 all line 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
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.
probably that question is one of those readForces questions lol
There 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
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
D is a very nice problem in my opinion, thanks!
ORZ. I really didn't like it tho. Felt like too much of a bash. My code is ugly :(
i just realised that in problem B, for an array to be good u just need one of the indexes to not meet the requirement. I thought you have to make it false for all indexes.
Could someone please explain how the answer is 56/3 in third testcase of D
Are there any prerequisite topics we need to learn before attempting Problem D?
Knowing how expected values work.
Any idea when ratings will be updated?
There is an issue with problem "C". Verdict is showing Accepted but the same code is getting TLE now!!!
Your code might be passing for the pretest where only few test case will be judged. But later all remaining test case will be judge against your solution during system test. That time your solution might be giving TLE for some test case.
Because your solution failed for hacked testcases which were added after the contest was over. Don't worry your solution will be judged only on the test cases intially present.
I have submitted someone's AC code in Problem C after the contest ends. But got TLE. My submission link : https://mirror.codeforces.com/contest/1778/submission/191670480 AC submission in contest time : https://mirror.codeforces.com/contest/1778/submission/191601266
maybe they are upgrading tests? Round is still unrated...
2 test cases have been added
Is it rated?
isn't taking too late to update rating ?
Why hasn't the rating been updated yet
As a newbie, when to add rating？
WHEN rating changes? my purple flying away...
Benq stay at the first place for a longer time due to the rating hasnt update.
they are in div1 , their rating will not change
Sorry，I mean the contest last time.Even the last contest hasnt update rating.
oh ok sorry, I will also keep an eye on benQ on the leaderboard.
When will the ratings change?
I think they are waiting for the rating change of the previous div1+div2 contest.
Ratings not updated yet :-/
I was hoping for a rating increase, but no update in rating :o
LateRatingForces
Please, update ratings!!! :( :( :(
why rating hasn't updated yet??
When will the ratings get updated?
Why ratings not updated yet?
Coz ratings of the previous round(TypeDB Forces 2023) is not updated yet :3
Sed ... Waitin on pupil for the first time
Why it's still unrated?
When rating will be updated of this Contest?
I think you can swap the position of D and E , D is very crazy .
Is it rated?
why didn't the rating is updated yet.Is there any problem or cheaters are being caught?
Shefin_ what exactly is the problem in backend.It is getting so late rating changes.I hope contest will be rated.
We also know the same as what prateek_saxena said. We have not received any negative response from CF about our round. So, the round is rated. You just need to wait for the plagiarism test of both rounds and the previous round's rating changes. Don't worry.
Is it rated ? rating is not added yet ?
I am new in to CF
Is the contest unrated? My rating has not been updated yet...
I would be glad to know.
When will the ratings get updated? O.o
When will we be rated?
The rating changes for round847(div3) have disappeared too.What happened?So strange.
me too，and my contest record for last div3 disappeared
yayy ratings updated, got positive delta