chemthan's blog

By chemthan, history, 10 months ago, In English
Tutorial is loading...
Python Solution

Author: isaf27, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...
C++ solution

Author: isaf27, prepare isaf27

Tutorial is loading...
C++ solution

Author: MikeMirzayanov, prepare MikeMirzayanov

Tutorial is loading...
C++ Solution

Author: laoriu, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...
C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...
C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...
C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...
C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Tutorial is loading...
C++ Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Another cool problem: WEICOM.

Tutorial is loading...
Python Solution

Author: chemthan, prepare laoriu, I_love_Hoang_Yen

Bonus: another beautiful problem.

 
 
 
 
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
10 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Was eagerly waiting for the editorial. Thanks.

»
10 months ago, # |
  Vote: I like it +49 Vote: I do not like it

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, KotonohaKatsura, 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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1264/submission/66453921 — Div 1C WA4

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?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Your formula for updates is wrong.

    Try this testcase:

    3 1
    100 100 50
    3
    

    The answer is 4, but your output is 5.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
10 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Please be aware that the tutorial is not completed yet. There may be some typo or ambiguous sentences. We are fixing them gradually.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Better late than never

»
10 months ago, # |
  Vote: I like it -41 Vote: I do not like it

1265E is a super standard bayan problem

»
10 months ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Problem E div 2
By 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)×e1
I 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?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    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.$$$
»
10 months ago, # |
  Vote: I like it +115 Vote: I do not like it

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

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Thanks. It is better to read participant's solution because it is more natural than author's one.

»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to derive the mathematics formula for D2?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 day

So 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*....*pn

And 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 series

and we should now be able to use the summation formula for it,

Would this approach work??

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks a lot for the reply .. I had been thinking about this for hours, Thanks for clearing the doubt.

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This was my approach too. Unfortunately, I think it's harder to get the insight needed to solve the Div1 version from this approach.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone Explain me why my solution is wrong for Div2(b) — Beautiful numbers. https://codeforces.com/contest/1265/submission/66503775

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B new_posmin = max(old_posmin, posm)? this should be new_posmin = min(old_posmin, posm).

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your Problem E's std Time Complexity is(O(n*logn)) https://paste.ubuntu.com/p/PYdVxM3VZB/

»
10 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give proof of correctness of problem D?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why I am getting this error for Problem C Beautiful Region ` 66646880

What is no problem splits between gold and silver?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It means there is a gold medalist and a silver medalist solved the same number of problems.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That should not be possible I think. Is there a way I can see that particular test case?

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why $$$F_{n+1} = 8t10^k +1$$$ ?

»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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[0]; 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

»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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[0]; 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???

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please ask, can '1264E — Beautiful League' only be solved by network flow? Can other algorithms be used? I can't think of it.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like 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!

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve D ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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