chemthan's blog

By chemthan, history, 5 years 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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Was eagerly waiting for the editorial. Thanks.

»
5 years 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, 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.

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

https://codeforces.net/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?

  • »
    »
    5 years 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.

»
5 years 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.

  • »
    »
    5 years 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

»
5 years 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.

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

Better late than never

»
5 years ago, # |
  Vote: I like it -41 Vote: I do not like it

1265E is a super standard bayan problem

»
5 years 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?

  • »
    »
    5 years 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.$$$
»
5 years 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.

  • »
    »
    5 years 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.

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

How to derive the mathematics formula for D2?

»
5 years 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??

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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.

»
5 years 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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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 years 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

»
5 years 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.net/contest/1265/submission/66503775

  • »
    »
    5 years 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.

»
5 years 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).

»
5 years 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/

»
5 years 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?

»
5 years 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?

  • »
    »
    5 years 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.

»
5 years 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.

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

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

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

How to solve D ?

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In the solution to 1265C, the following step may be redundant in my opinion:

while (b <= g && i < pp.size())
    b += pp[i++];

The goal is to greedily maximize the bronze medals while the awardees are less than n/2. However, this step only ensures that there are more bronze than gold medals. Funnily enough, the number of bronze medals are maximized to n/2 right after this step.

»
21 month(s) ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Last day, a similar problem was questioned in the contest Codeforces Round 848 (Div. 2) (problem D).

Here is my solution for the problem E:

Let $$$F_i$$$ denotes the expected number of times until we are able to go to the next mirror when we are at the mirror $$$i$$$. For the sake of simplicity, call $$$P_i$$$ the probability of being beautiful at the mirror $$$i$$$. Now the mirror either tells us we are beautiful with probability $$$P_i$$$ and allows us to switch to the other mirror, or we start again with the first mirror with probability $$$(1 - P_i)$$$. With these observations, we can write the general formula

$$$F_i = 1*P_i + (1 - P_i) * (1 + F_1 + F_2 + F_3 + ... + F_i)$$$

If we rearrange the formula and use a variable named $$$sum_i$$$ that keeps the prefix sum of F, we get

$$$F_i = (1 + (1-P_i) * sum_{i-1}) / P_i$$$

We can compute all F_i one by one now.

By definition, $$$F_i$$$ gives us the expected number of times to switch $$$(i+1)$$$ th mirror from $$$i$$$ th mirror. To get the answer, we must jump from the first mirror to the second, from the second mirror to the third, and so on. So in conclusion, we can express the equation

$$$answer = F_1 + F_2 + F_3 + ... + F_n$$$

The code I wrote:
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for the very intuitive and beautiful explanation. Extremely helpful. However, I believe there is a slight mishap in writing, the correct generalization should be

    $$$F_i = 1 + ((1 - P_i) * (1 + sum_{i-1}) / P_i$$$

    Derivation:

    $$$F_i = 1*P_i + (1 - P_i) * (1 + F_1 + F_2 + F_3 + ... + F_{i-1} + F_i)$$$
    $$$=> F_i = P_i + (1 - P_i) * (1 + sum_{i-1} + F_i), where, sum_{i-1} = F_1 + F_2 + F_3 + ... + F_{i-1}$$$
    $$$=> F_i = P_i + (1 - P_i) * (1 + sum_{i-1}) + (1 - P_i) * F_i$$$
    $$$=> P_i * F_i = P_i + (1 - P_i) * (1 + sum_{i-1})$$$
    $$$=> F_i = 1 + ((1 - P_i) * (1 + sum_{i-1}) / P_i$$$
    AC code
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, you can regulate your equation and see it's the same as mine. Despite this, I realized I had miswritten $$$sum_i$$$, it should be $$$sum_{i-1}$$$. I fix it now. Thanks.