### chemthan's blog

By chemthan, history, 22 months ago, Python Solution

Author: isaf27, prepare laoriu, I_love_Hoang_Yen

C++ solution

Author: isaf27, prepare isaf27

C++ solution

Author: MikeMirzayanov, prepare MikeMirzayanov

C++ Solution

Author: laoriu, prepare laoriu, I_love_Hoang_Yen

C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Another cool problem: WEICOM.

Python Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Bonus: another beautiful problem. Tutorial of Codeforces Round #604 (Div. 2) Tutorial of Codeforces Round #604 (Div. 1) Comments (52)
 » 22 months ago, # | ← Rev. 2 →   Was eagerly waiting for the editorial. Thanks.
 » Problem 1264E has a similar which can be found at https://www.luogu.com.cn/problem/P4249, I have used the code in https://www.luogu.com.cn/problemnew/solution/P4249 to solve 1264E during the contest, which was published in 2018.Thus some people's (such as jiangly, Rose_max, LiWenHaoTianXiaDiYi, disposrestfulIy, SpiderDance and me) submissions was skipped by mistake, they are unrated. But it's not fair.Can you help us to solve this problem? Greatly thanks.The skipped submissions are jiangly/66346874, Rose_max/66347301, KotonohaKatsura/66350584, disposrestfulIy/66342618, yuguotianqing/66351221, SpiderDance/66352851.
•  » » Let ask MikeMirzayanov.
•  » » » Thanks.
•  » » » Thank you very much, my rating has come back lol. BTW, MikeMirzayanov is a very nice admin.
 » Looking at the comments my idea is similar, we first calculate answer with no checkpoints (which works, since I pass Div2E), and afterwards if we add a checkpoint j in interval [i, k], we have to decrease the answer by prod(i, j — 1) * prod(j, k) and add val[j — 1], when we delete j we need to merge intervals [i, j — 1] and [j, k], we do the opposite (add products, subtract val). This fails on first checkpoint addition on big test, so I cannot research that manually. Any ideas on what I did wrong?
•  » » Your formula for updates is wrong.Try this testcase: 3 1 100 100 50 3 The answer is 4, but your output is 5.
 » Can someone please explain,how to solve Beautiful sequence(1265D) as there was a lot of confusions while trying to get the proper solution.Also explain how did you get to the solution please. Thanks in advance.
•  » » What I tried to do is this. I tried to make a pattern of $01010101|21212121|23232323$ form. The $01$ sequence needs to terminate with a $1$, the $23$ sequence needs to start with $2$. Now, if there are too many $0$'s than $1$'s, the sequence cannot be formed as you need $1$'s beside the $0$'s. So, if $a\geq b+2$ or $d\geq c+2$, answer is $NO$. The other cases are also similar. The code is pretty much self-explanatory, so I'd suggest you have a look at it. My submission: 66486337
 » Please be aware that the tutorial is not completed yet. There may be some typo or ambiguous sentences. We are fixing them gradually.
 » Better late than never
 » 1265E is a super standard bayan problem
 » 22 months ago, # | ← Rev. 3 →   Problem E div 2By the definition of expectation value and its basic properties, the following must holds for all 1≤i≤n:ei=1+pi×ei+1+(1−pi)×e1I know the definition of expectation value, but this equality is not obvious for me.Can somebody explain this formula or give some information about expectation value to learn?
•  » » It is the linearity of expected value, i.e. if $X$ and $Y$ are two random variables, then $E[\alpha X+\beta Y] = \alpha E[X] + \beta E[Y]$ for any $\alpha,\beta$ constants. The variable $X_i$ is the number of days to get happy if she's at the $i$-th mirror. For this random variable, we must have the relation $X_i = p_i\cdot(1+X_{i+1}) + (1-p_i)\cdot(1+X_1)=1+p_i X_{i+1} + (1-p_i) X_1$, since with probability $p_i$ she can move on to the next mirror with a day gone, and with $1-p_i$ she goes back to the first. Now, $E[X_i] = E[1+p_i X_{i+1} + (1-p_i) X_1] = 1+p_iE[X_{i+1}]+(1-p_i)E[X_1]$.Or, without intuitive useage of random variables, you could say that the probability of $X_i$ taking the value $d$ (i.e. exactly $d$ days to get happy), we must have $P(X_i=d) = p_i\cdot P(X_{i+1}=d-1) + (1-p_i)\cdot P(X_1=d-1)$, since after passing $i$-th with $p_i$ probability she has to get happy in exactly $d-1$ days from $i+1$-st, or failing at the $i$-th gives her $d-1$ days to pass from the first one. So we need only the definition of expected value to get $E[X_i] = \sum_{d=1}^\infty d\cdot P(X_i=d) = p_i\sum_{d=1}^\infty d\cdot P(X_{i+1}=d-1) + (1-p_i)\sum_{d=1}^\infty d\cdot P(X_{1}=d-1),$where $d\cdot P(X_{i+1}=d-1) = (d-1)\cdot P(X_{i+1}=d-1) + P(X_{i+1}=d-1)$means $E[X_i]=p_i\sum_{d=0}^\infty d\cdot P(X_{i+1}=d)+p_i\sum_{d=0}^\infty P(X_{i+1}=d)+\\+(1-p_i)\sum_{d=0}^\infty d\cdot P(X_{1}=d) +(1-p_i)\sum_{d=0}^\infty P(X_{1}=d)$Finally this leads to $E[X_i]=p_iE[X_{i+1}]+p_i\cdot 1 + (1-p_i)E[X_1]+(1-p_i)\cdot 1.$
 » Here's my approach to 1264F - Beautiful Fibonacci Problem, hoping it provides some additional insight:I was aware that the Fibonacci sequence is periodic for any modulus, and the period is called Pisano period. I checked that for $x\geq 3$, the Pisano period $\mod 10^{x}$ is $15\cdot 10^{x-1}$. At first, I was considering an easier task, with limits at $10^3$ instead of $10^6$, i.e. I was looking for arithmetic sequences of indices such that the corresponding Fibonacci numbers contain all the $3$-length digit substrings, hoping to discover some useful relation. I found out that over a period, the last three digits won't produce all substrings, so i was looking at the next block of $3$ digits, for which i realized that if I jump the lengths of Pisano period $p=1500$ in the index, then the numbers $F_{1+k\cdot p}/1000 \mod 1000$ (the second $3$-digit blocks from the end of the number) are in arithmetic progression $\mod 1000$, and since in this case $F_{1+1\cdot p}/1000 \mod 1000 = 949$ is relative prime to $1000$, so it generates all the digit strings. I will provide a proof in the end of this post. Now, the value of index $k$ in order to have the string $001$ in $F_{1+k\cdot p}$ is easy to get by Euler-theorem, it is $k=949^{\varphi(1000)-1}\mod 1000=949^{399}\mod 1000 = 549$. So, if we need a digit string $a$ to be found, we could just take $F_{1+a\cdot k\cdot p}$, since the strings are generated in arithmetic progression, as I mentioned before. Moreover for $a+l\cdot d$ we could choose $F_{1+(a+\cdot l\cdot d)\cdot k\cdot p} = F_{1+a\cdot k\cdot p + d\cdot l\cdot k\cdot p}$, i.e. obviously the indices here would be in arithmetic progression too, so we can simply output our answer $b=1+a\cdot k\cdot p$ and $e=d\cdot k\cdot p$.The same holds if we have the problem's original limits and we need the $6$-length substrings: consider the above with $\mod 10^6$, when the Pisano period is $p=15\cdot 10^5$, get the generator of the $6$-length digit strings $F_{1+1\cdot p}/10^6 \mod 10^6 = 677499$, compute the index of $000001$ which is $k = 677499^{399999} \mod 10^6 = 445049$, and so the answer is $b=1+a\cdot 445049\cdot 15\cdot 10^5$ and $e=d\cdot 445049\cdot 15\cdot 10^5$. Link to submission: 66473963The fact that the numbers $F_{1+k\cdot 15\cdot 10^{x-1}}/10^x \mod 10^x$ are in arithmetic progression $\mod 10^x$ can be verified for the given limits by a simple program, but we can prove it formally too: for this, we need the formula $F_{1 + (k+1)\cdot p} = F_{1+kp}\cdot F_{1+p} + F_{kp}\cdot F_{p}$, which is a special case of the formula mentioned by the editorial, but nonetheless its easy to verify either using the generator function or the recurrence matrix of the sequence. Since $p$ is the Pisano period, we know that both terms of the second product are congruent to $0 \mod 10^x$, i.e. they end with $x$ zeroes, so the product ends with at least $2x$ zeroes, so it won't affect the second $x$-length digit block from the end, consequently $F_{1+(k+1)\cdot p}/10^x \mod 10^x = (F_{1+kp}\cdot F_{1+p}) / 10^x \mod 10^x$. The last $x$ digit block in both of these right hand side terms is $00\ldots 01$ (by Pisano period), so the second $x$ digit block from the end (notating by $B_l$ the second $x$ digit block of $F_l$ for any $l$ index), is obtained by multiplying blockwise $(A_{1+kp}\cdot 10^{2x}+B_{1+kp}\cdot 10^x + 00\ldots 01)\cdot (A_{1+p}\cdot 10^{2x}+B_{1+p}\cdot 10^x + 00\ldots 01)$to get $X\cdot 10^{2x} + (B_{1+kp}+B_{1+p})\cdot 10^x + 00\ldots 01$, i.e. $B_{1+(k+1)p} = B_{1+kp}+B_{1+p}\mod 10^x$, the second $x$-digit block is the sum of the second $x$-digit blocks of the $1+kp$ and $1+p$ Fibonacci numbers, thats what we wanted to show.
•  » » Thanks. It is better to read participant's solution because it is more natural than author's one.
 » How to derive the mathematics formula for D2?
 » Would this approach work for 1265E Beautiful Mirrors?Since we need to calculate expected number of days..So let Pi=Probablity of becoming happy at ith daySo that implies that P1,P2,....P(n-1) = 0 as he cant be happy on days he's not asking the last mirror,So , he can be happy on Pn,P2n,..... days.Now probability of having success on nth day is = p1*p2*p3*....*pnAnd on (2n)th day is =(Pn)*(Pn)And on (3n)th day is =(Pn)*(Pn)*(Pn)And so on...So now according to formula E= n*(Pn) + (2n)*(P2n) + (3n)*(P3n) + .......=> E = n*(Pn) + (2n)*(Pn)^2 + (3n)*(P3n)^3 + .......So now the answer turns out to be an infinite Arithmetic-Geometric Progression seriesand we should now be able to use the summation formula for it, Would this approach work??
•  » » You can't say probability for having success on 2nth day is Pn*Pn. because in doing that, you are ignoring things like: 1--->2---->1---->2--->1---->2---->…… 1 (after n steps we are at 1) --->2---->3--->4---->n(in next n steps we reach the end, but this scenario is not even considered in your formula) Also, how can you square Pn , because once you have achieved Pn, it means you have reached the right end.... if probability of success of first day of something is p then probability of success on second day is NOT p^2, it is (1-p)*p AS FIRST DAY IS A FAILURE DAY So, your formulas won't work like this. Another approach is needed
 » We can solve the Div2E problem WITHOUT having to find the modular inverse of all the $P_i$ existing. Let, $E_k$ is the expected number of days after having asked $k$ mirrors i.e. about to ask the $k+1^{th}$ mirror. So, clearly from this definition, $E_n=0$, and $E_0$ is our answer to this problem. Now, we can see that $E_k = 1 + \frac{P_{k+1}}{100} \cdot E_{k+1} + (1-\frac{P_{k+1}}{100}) \cdot E_0$Let this be eqn1, which holds for all $k (0\leq k \leq n-1)$. Let’s express every $E_k (0\leq k \leq n)$ in $constant + efficient \cdot E_0$ form. So, $E_n = 0 + 0 \cdot E_0$. Using that, we can find $E_{n-1}, E_{n-2}…E_0$ by plugging in the values of $constant$ and $efficient$ in eqn1 and updating them. So, at the end of the iteration, we will have $E_0 = constant + efficient \cdot E_0$. Thus, $E_0 = \frac{const}{1-eff} \% MOD$ . Do your modular operations properly, be careful of overflow, and it will lead to the answer. All we need to do is to evaluate modular inverse of $100$ at the beginning, and that of $(1-eff)$ towards the end. My submission: 66363163
•  » » This was my approach too. Unfortunately, I think it's harder to get the insight needed to solve the Div1 version from this approach.
•  » » » Completely agreed. After looking at the problem of div1 version and the editorial of div2 version, I also thought the same. Now I'm trying to solve the div1 version in "my" way. If I can't, I will try the way it's showed in the editorial. Let's see what happens.
•  » » I don't understand why the tutorial and many people here complicate things a lot. We could compress the Markov states of first N nodes to one node with N transitions back to itself. Those transitions refer to N scenarios failing back to day 1 with different cost(how many days) and different probability(easy to calculate). Then there will be only two states in the Markov graph. Then use your approach with the equation to solve the expectation.
 » Let us solve D by dp!!! you may say are you crazy?Be patient,my friend we can naively denote the status dp[i][e][a][b][c][d] is when we are at i position and the end is "e"(0,1,2,3) element we has a zeros ,b ones ,c twos ,d threes ,so the transform is obvious so, we have many status....TLE? NO,many status can just be neglected let us denote x,y is the element we want to put ,and denote nd:=min(cnt[x],cnt[y]) nd+1,nd is the number we can put ,other condition in fact will finally transfer into the status my code: Your text to link here...66490372
 » Can Anyone Explain me why my solution is wrong for Div2(b) — Beautiful numbers. https://codeforces.com/contest/1265/submission/66503775
•  » » Because your logic was wrong. You solution failed on this simple test case: 1 4 3 1 4 2 Checkout the editorial for more details.
•  » » » thank a lot
 » In problem B new_posmin = max(old_posmin, posm)? this should be new_posmin = min(old_posmin, posm).
•  » » Thanks for pointing out. Fixed.
 » Your Problem E's std Time Complexity is(O(n*logn)) https://paste.ubuntu.com/p/PYdVxM3VZB/
•  » » This link is O(n)
 » 22 months ago, # | ← Rev. 4 →   On the editorial C++ solution of 1265E: What is the idea behind the code?  int a = 1, b = 0; for (int i = 0; i < n; i++) { a = (long long) a * inv(p[i]) % MOD; b = (long long) b * inv(p[i]) % MOD; a = (a + (long long) (p[i] - 1) * inv(p[i])) % MOD; b = (b - inv(p[i]) + MOD) % MOD; } It seems that a is always equal to one at the end of each cycle. Also why b is taken negative?
•  » » Actually, it a simple approach as described here.
 » Can someone please give proof of correctness of problem D?
 » Can anyone tell me why I am getting this error for Problem C Beautiful Region  66646880What is no problem splits between gold and silver?
•  » » It means there is a gold medalist and a silver medalist solved the same number of problems.
•  » » » That should not be possible I think. Is there a way I can see that particular test case?
 » seems that there's a typo in d1D(hard ver.) Let a be the number of '(' before the i-th position i, b be the number of ')' after the i-th position.
•  » » I fixed it. Thanks for pointing out.
 » Why $F_{n+1} = 8t10^k +1$ ?
•  » » Do induction or just directly calculating.
»

# include <bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; int m=0,arr[n],hash[n]={0}; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=0;i<n;i++) { hash[m]++; if(arr[i]!=arr[i+1]) m++; } int sum=0,k=n/2,g=0,s=0,b=0; g=hash; int u=1; while(1) { s+=hash[u]; if(s<=g) { u++;

}
else
break;
}
int j=u+1;
while(1)
{
b+=hash[j];
if(b<=g)
j++;
else
{
while(1)
{
if(g+s+b+hash[j+1]<=k)
{
b+=hash[j+1];
j++;
}
else
break;
}
break;
}
}
if(b+g+s>k)
cout<<"0 0 0\n";
else
cout<<g<<" "<<s<<" "<<b<<"\n";
}

} what is wrong in my code

»

# include <bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; int m=0,arr[n],hash[n]={0}; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=0;i<n;i++) { hash[m]++; if(arr[i]!=arr[i+1]) m++; } int sum=0,k=n/2,g=0,s=0,b=0; g=hash; int u=1; while(1) { s+=hash[u]; if(s<=g) { u++;

}
else
break;
}
int j=u+1;
while(1)
{
b+=hash[j];
if(b<=g)
j++;
else
{
while(1)
{
if(g+s+b+hash[j+1]<=k)
{
b+=hash[j+1];
j++;
}
else
break;
}
break;
}
}
if(b+g+s>k)
cout<<"0 0 0\n";
else
cout<<g<<" "<<s<<" "<<b<<"\n";
}`

} what is wrong with this code???

 » Please ask, can '1264E — Beautiful League' only be solved by network flow? Can other algorithms be used? I can't think of it.
 » Could someone please explain Problem B (Beautiful Numbers), i can't seem to figure out the reason for doing POSmax- POSmin + 1 or why we want POS array in the first place ! Thankyou!
 » How to solve D ?
 » What is wrong in my solution to Div 2C?It says out or bounds on line 22. Her is the link- https://codeforces.com/contest/1265/submission/78485671
 » Hello, can someone explain like ELI5 the correctness of the solution proposed in Div2B, mainly because I can not get what is meant by pos(max) and pos(min).. It would be a huge help and favor
•  » » suppose we are checking if m = 5 is beautiful num or not .. for this what we are doing is just checking that every num from 1 to m(5) is in the range i.e max pos of any num from 1 to 5 — min pos of any num from 1 to 5 is less than 5 or not ..... if it is less then congratulations m is beautiful ................ proper example for this is subtask 1 of testcase 1
 » 11 months ago, # | ← Rev. 2 →   Can someone please explain Problem B of Div2 (Beautiful Numbers).I don't get how it works and how to arrive at such a solution. I read the editorial but don't really understand how does storing the max and min positions ensure that we have covered/included the numbers that were supposed to be in the middle.