When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

adnan_toky's blog

By adnan_toky, 14 months ago, In English

1778A - Flip Flop Sum

Tutorial
Code

1778B - The Forbidden Permutation

Tutorial
Code

1778C - Flexible String

Tutorial
Code

1778D - Flexible String Revisit

Tutorial
Alternative Solution
Code
Alternative Code

1778E - The Tree Has Fallen!

Tutorial
Code

1778F - Maximizing Root

Tutorial
Code
  • Vote: I like it
  • +129
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Better round than I expected, kudos to the authors!

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

Special thanks to Psychotic_D for the special case of problem D.

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

In problem b why we are not updating the position of the element after we have counted the number of swaps. how this is not affecting the ans?

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

    Seems like you misunderstood the problem just like me. Actually, we just need to change one such pair that satisfies the given inequality to make the array good. I feel so stupid now and was wondering why is B so difficult and how are people solving it.

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

      negation(for all)= there exits. i too could not see that.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      But what if the question was originally what you thought it was... that you need to make all pairs good in the array? Would that be dp?

      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        I can't figure out how to solve that question by dp,since previous moves may affect these rear one. That's why I don't solve the problem LOL

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

      me too

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

      me too.I will be sad all day.

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

      damn damn damn damn same thing happened to me and I just realized now. I tried to solve the problem for a whole day yesterday and rolled in guilt why I cant get a B problem now that I know I misunderstood the problem after reading this comment.

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Me too.

      $$$pos(a_i)<pos(a_{i+1})≤pos(a_i)+d$$$ for all $$$1≤i<m$$$.

      I'm so foolish and careless.

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

I got stuck at B because I didn't read the question correctly learned a big lesson thank s for the contest.

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

    Same for me, I did't realise that only one pair was enough for the answer.

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

Anyone care to explain the "After some calculations" part of the Alternative solution for D? I'd really like to see the idea behind this :)

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

    One possible way to show this is using Markov chains (you might want to look up Ehrenfest Urns)

    In particular, suppose that we don't stop after having $$$0$$$ differences between $$$a$$$ and $$$b$$$: instead, we keep repeating the index choosing infinitely. Then, the probability of being in state $$$0$$$ differences in the long run is $$$\pi_0 = 2^{-n}$$$. It is a fact of "recurrent" Markov chains that the expected time to return to a state $$$i$$$ is $$$1/\pi_i$$$. In particular, if currently there are $$$0$$$ differences between the two strings, then the expected time until we return back to having $$$0$$$ differences is $$$2^n$$$ moves. However, note that when we leave $$$0$$$ differences, we always move to $$$1$$$ difference. So, the expected time to go from $$$1$$$ difference to $$$0$$$ differences must be $$$2^n - 1$$$.

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

      This is so cool! Thank you so much.

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

      Cool

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

      Could u tell me how why the probability is 2^(-n)?

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

        Suppose you have a long run probability $$$\pi_i$$$ of being in state $$$i$$$ and probability $$$\pi_{i+1}$$$ of being in state $$$i + 1$$$. Then, notice that the number of times you go $$$i\rightarrow i + 1$$$ is within one of the number of times you go $$$i + 1\rightarrow i$$$. In the limit, this means that of the $$$i\rightarrow i + 1$$$ and $$$i + 1\rightarrow i$$$ transitions, exactly $$$\frac 12$$$ of them are $$$i\rightarrow i + 1$$$.

        Since the probability of going from $$$i$$$ to $$$i + 1$$$ is $$$\frac{n - i}{n}$$$ and the probability of going from $$$i + 1$$$ to $$$i$$$ is $$$\frac{i + 1}{n}$$$, it follows that

        $$$\pi_i \cdot \frac{n - i}{n} = \pi_{i+1} \cdot \frac{i + 1}{n}.$$$

        Rearranging, you have $$$\pi_{i+1} = \pi_i \cdot \frac{n - i}{i + 1}$$$. Then, by induction you can verify that this implies that $$$\pi_{i+1} = \pi_0 \cdot \binom {n}{i + 1}$$$.

        Since $$$\sum_{i=0}^{n}\pi_i = 1$$$, adding these up implies that $$$\sum_{i=0}^{n}\pi_0 \cdot \binom ni = 1$$$. Since $$$\sum_{i=0}^{n}\binom ni = 2^n$$$, this gives $$$\pi_0 = 2^{-n}$$$.

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

          Dude, that was soooo beautiful!! Thanks a lot!! Could u suggest which topics I should study to be able to do these on my own? Thanks a lot in advance.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here's another simple way to show the stationary probability is $$$\frac{1}{2^n}$$$ more simply. We are taking a random walk on the vertices of the boolean hypercube with vertices $$$\{0,1\}^n.$$$ (Each of the $$$n$$$ bits corresponds to one dimension of the cube), and toggling one bit corresponds to moving along an edge. This is clearly symmetric with respect to each of the $$$2^n$$$ vertices. By symmetry of the cube, the stationary probability is the same for each vertex and so each is equal to $$$\frac{1}{2^n}.$$$

        More generally the stationary distribution on an unweighted finite graph (neighbors picked uniformly at random) is $$$\pi_v = \frac{deg(v)}{2E}$$$ where $$$E$$$ is the number of edges.

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

I had the same solution as mentioned in the editorial for question B but i got wrong answer on pretest 2.

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

I would like to point out that there is a much easier way for D. You can find through some checking that if A and B differ in exactly 1 bit, then the expected value is 2^n-1. Then you can just create an array and calculate the answer recursively, using some Modulo properties which make it much easier.

An implementation can be found here. Ignore the copy-pasted GeeksforGeeks implementation of Modular Inverse :clown:

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Elaborate the relation of ans[i] please !! unable to understand completely.

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

Another solution for D: let $$$f(i)$$$ be the expected time to go from $$$i$$$ differences to $$$i - 1$$$ differences for the first time. Then, our answer is $$$\sum_{i=1}^{k} f(i)$$$.

The claim is that $$$f(i) = 1 + \frac{n-i}{n}(f(i + 1) + f(i))$$$. Indeed, with probability $$$\frac in$$$ , we move to $$$i - 1$$$ differences and are done in one move. Else, we move to $$$i + 1$$$ differences. Then, the expected time to get to $$$i - 1$$$ is $$$f(i + 1) + f(i)$$$.

So, we can rearrange to get $$$f(i) = \frac ni + \frac{n-i}i f(i + 1)$$$. Now, in $$$O(n)$$$ we can calculate all $$$f(i)$$$ starting from $$$n$$$ and ending at $$$1$$$, and $$$O(n)$$$ to compute the desired sum.

Submission: 191566655

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

    Wow, nice solution

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

    Cool.

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

    amazing!

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    I've also used this method to solve D. I'd like to add some explanations in order to give others a further understanding.

    ​We can know that if we are considering $$$f(i)$$$, we could move to $$$i - 1$$$ by $$$1$$$ step with probability $$$\dfrac{i}{n}$$$, or we could move to $$$i + 1$$$ by $$$1$$$ step then move to $$$i - 1$$$ by step $$$f(i) + f(i - 1)$$$ with probability $$$\dfrac{n - i}{n}$$$.

    ​So we can find that $$$f(i) = \dfrac{i}{n} \times 1 + \dfrac{n - i}{n} \times (f(i) + f(i + 1) + 1) \iff f(i) = 1 + \dfrac{n - i}{n}(f(i) + f(i + 1))$$$ like what applepi216 said.

    ​It is OK if we have $$$f(i)$$$ on both sides of the equal sign, we just have to move all $$$f(i)$$$ to the same side like: $$$f(i) = 1 + \dfrac{n - i}{n}(f(i) + f(i + 1))\iff \dfrac{i}{n}f(i) = 1 + \dfrac{n - i}{n}f(i + 1) \iff f(i) = \dfrac{n}{i} + \dfrac{n - i}{i}f(i + 1)$$$

    ​Then we can easily write a program to solve this problem!

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    This formula can be explained in another way.

    Assume we have $$$\displaystyle i$$$ one's. The probability of that number decreasing is exactly $$$\displaystyle \frac{i}{n}$$$. That means that it will decrease on the $$$\displaystyle \frac{n}{i}$$$-s attempt on average. Therefore, we claim that we expect $$$\displaystyle \frac{n}{i} - 1$$$ increases and exactly $$$\displaystyle 1$$$ decrease.

    So, we get that $$$\displaystyle dp_i = (\frac{n}{i} - 1) * (dp_{i+1} + 1) + 1$$$, because we have to waste one extra move for each increase.

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

    Thank you so much

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

I have an easier solution for E without using Euler tour. I use re-rooting technique and answer the queries offline. Submission here.

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

In problem B i think i should fix all i and don't solve the problem at the end ಥ⁠‿⁠ಥ

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

To find the node $$$c$$$, one can also use binary lifting/k-th ancestor techniques. The relevant node will be the $$$dep[r] - dep[v] - 1$$$'th ancestor of $$$r$$$.

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

In problem B, do we need to check if the array has become good after every swap?

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

    yes, we only need only one index which does not follow the condition of not good array. So after swapping an element we check minimum numbers of swaps for every time.

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes. Because if all inequalities are satisfied, sequence a is a bad sequence.

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

For problem D, it is pretty intuitive that the answer only depends on the count of positions with different characters in the two strings, but can someone show me how to prove this formally/mathematically?

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Suppose $$$a$$$ is different from $$$b$$$ at $$$k$$$ places. First notice that it only matters if $$$a_i = b_i$$$ or $$$a_i \neq b_i$$$, and not what the exact values are. That means that we if we flip both $$$a_i$$$ and $$$b_i$$$ the answer won't change. So we can assume that $$$b$$$ consists only of zeros, and $$$a$$$ has exactly $$$k$$$ ones. Now, if $$$X$$$ is uniformly distributed, then so is $$$p(X)$$$, where $$$p$$$ is some permutation of $$$1...n$$$. That means that if we permute $$$a$$$ and $$$b$$$ in the same way the answer won't change. So we can assume that $$$a = 0...01...1$$$ with $$$k$$$ ones and $$$b = 0...0$$$. Since all tests with the same $$$k$$$ can be transformed into the same "canonical" form without changing the answer, they all share the same answer.

»
14 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Can someone help prove that using sliding window greedily is incorrect for problem C ? I tried to use this idea but got WA. My submission is 191628511

The idea I tried to implement is that we keep a running map that reflects the unique letters of set Q. Whenever the Q's size is < k or a letter has already existed in Q, we can safely make a[i] == b[i], in case they are different.

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

Here is an another calculation for D:

we have $$$f(n-1) = 1 + \frac{n-1}{n}f(n-2)+\frac{1}{n}f(n)$$$ and $$$f(n) = 1 + f(n-1)$$$ ,

then get $$$f(n-1) = f(n-2) + \frac{n+1}{n-1} $$$.

Noted that the second part is only related to $$$i$$$, so we can caculate this part for every $$$i$$$ from $$$n-1$$$ to $$$1$$$, with $$$f(0) = 0$$$, all $$$f(i)$$$ can be calculated.

My submission: https://codeforces.com/contest/1778/submission/191601709

»
14 months ago, # |
  Vote: I like it -6 Vote: I do not like it

There were better ways of explaining question B but bro wake up and choose violence.

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

B taught me to read problems properly T.T

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

Seems like I'm not the only one who got brainfucked in B, thinking we have to make all the pairs good :)

Nice contest tho!

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

Geothermal can you please explain your solution to D ?

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

    Let $$$x_m$$$ be the expected number of steps to make two strings equal if they are different in $$$m$$$ of the $$$n$$$ positions. We observe that $$$x_0 = 0$$$, $$$x_n = 1 + x_{n-1}$$$, and for all other $$$m$$$, we have $$$x_m = 1 + \frac{m}{n} x_{m-1} + \frac{n-m}{n} x_{m+1}.$$$ This is because there are $$$m$$$ positions that, if chosen, will change the character at that position from being different among the two strings to being the same, and $$$n-m$$$ positions at which changing the character will change that position from being the same across both strings to being different.

    Now, iterating $$$m$$$ from $$$n$$$ to $$$1$$$, we can solve for each $$$x_m$$$ in terms of $$$x_{m-1}$$$. Afterwards, we can substitute $$$x_0 = 0$$$ into our equation for $$$x_1$$$, then substitute our value for $$$x_1$$$ into our equation for $$$x_2$$$, and so on to derive all of the $$$x$$$'s. Our answer is then $$$x_m$$$, where $$$m$$$ is the number of differences between the two input strings.

»
14 months ago, # |
  Vote: I like it -11 Vote: I do not like it

it's strange that no one got the third problem on Python

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

Quite a great contest! The D is a bit classic but the idea itself is quite great. Problem E is an interesting DS and tree problem but also a bit classic. (I mean the algorithm part) F is a dp on tree related to number theory but for me it's a little bit easier for the position of F. The diversity of algorithm is very great in this contest and hope you guys can do better next time.

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

In problem D how can we calculate F(1)

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

Why is this solution for D not correct? Let C be the number of non equal indices.

We can only finish in the $$$C,2N-C,2N+C...$$$ moves. Assumption 1.

We call finish in any of the $$$C,2N+C,4N+..$$$ type moves odd type moves

We call finish in any of the $$$2N-C,4N-C,..$$$ type moves even type moves

The probability of finishing in C moves = $$$(C)!/N!$$$. -->(P2)

The probability of finishing in C moves = $$$(N-C)!*(C!)/N!$$$. -->(P1)

The probability of finishing in 2N-C moves = $$$(1-P1)*(P2)$$$.

Probability of finishing in $$$i^{th}$$$ odd move is $$$P2*(1-P1)^{2i}$$$ Probability of finishing in $$$i^{th}$$$ even move is $$$P2*(1-P1)^{2i+1}*(2N(i+1)-c)$$$

Summing moves*probability of odd type we get $$$\sum_{i=0}^{+\infty} P2*(1-P1)^{2i}*(2Ni+c)$$$

Summing moves*probability of even type we get $$$\sum_{i=0}^{+\infty} P2*(1-P1)^{2i+1}*(2N(i+1)-c)$$$

The expected odd sum is $$$(1-P1)^2*(2N*P2)/(1-(1-P1)^2)^2$$$ + $$$C*P1/(1-(1-P1)^2)$$$

The expected even sum is $$$(1-P1)^3*(2N*P2)/(1-(1-P1)^2)^2$$$ + $$$(2N-C)*P1*(1-P1)/(1-(1-P1)^2)$$$

Please let me know my arithmetic or logical mistake. Thanks

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

    You can finish in $$$C, C+2, C+4, \ldots$$$ moves (not $$$2N - C$$$ and others). For example, suppose there are $$$11$$$ differences between $$$a$$$ and $$$b$$$. Then, you can verify that the number of moves needed can be any odd $$$k\ge 11$$$ (for example, to get $$$13$$$ first flip a bit to have $$$12$$$ differences, then go flip correct bits to go from $$$12$$$ to $$$0$$$ immediately).

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

l

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

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

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

    You only choose subsets with length == k. And complexity will decrease enormously.

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

A method to solve range basis query in $$$O(nlogn)$$$: (subtree and complement of subtree are weaker)

Iterate $$$r$$$, we maintain the lexicographically (by index) largest basis, then the query can be handled by simply ignoring all vectors with index less than $$$l$$$.

To maintain such basis, when you face two vectors on the same row, always keep the right one (one with larger index), because the left one can always use the right one to change itself.

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

In problem F , why do we always perform the last move on the root vertex of the subtree while calculating dp?

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

    Reason is this, 1) we can only apply one operation on a node. 2) let's say we apply i'th opertion on a root node , then we cannot apply any opertion on root. So last k-i operations are of no use. Why? because the remaining k-i operations has to be performed on the nodes except the root and our answer is dependent on the root node( which is = intial_val_of_root*max_gcd_of_root we get) which will never increase by the last k-i operations , that's it.

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

      But actually, to make the GCD of the subtree of u equal to a multiple of d, we may use some operations in the subtree of u, but use no operation on u itself. Why can we ignore this case?

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

Pr**oblem D** There might be some wrong? **

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

Are there any prerequisite topics we need to learn before attempting Problem D?

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

    I am watching Errichto's videos about expected value (EV), which were on my watch later list but it seems like it is time to watch them.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      any resoureces other than that ?.I am bad at math and very bad at expected values,probabilites

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

F can be solve in $$$O(n\times m)$$$ (Or $$$O(n\times mlog(m))$$$ ? Since I use a map to store the dp value) . Where $$$m$$$ is the number of divisors of $$$x_{1}$$$

Consider $$$dp_{u,x}$$$ as the same in the tutorial. Let $$$x = \prod{p_{i}^{d_{i}}}$$$, and $$$y = \prod{p_{i}^{\lceil \frac{d_{i}}{2} \rceil}}$$$, we only need to consider two cases: $$$dp_{u,x} = \sum{dp_{v,x}}$$$ and $$$dp_{u,x} = 1 + \sum{dp_{v,y}}$$$, where $$$v$$$ is all the children of vertex $$$u$$$. The first case represent we do not do any operation on vertex $$$u$$$, which requires $$$x | x_{u}$$$. The second case represent we do one operation on vertex $$$u$$$, which requires $$$y | x_{u}$$$. Special judge for $$$u=1$$$.

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

    Why is that enough to only check the transition dp[v][x] -> dp[v][y] in the second case?

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      This is because y would be the smallest number whose square is a multiple of x. any other such number would end up being a multiple of y. and we know that for 2 numbers n1 and n2 such that n1 is a multiple of n2, dp[n2] <= dp[n1]

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

Lots of people are complaining about the contest but there are always people who complain. For me, the round was pretty good and I enjoyed problem C when I figured out how to solve it.

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

    I agree. But I think the problem statements could have been made a little easier to understand.

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

What is complexity of C by backtracking solution given above? Is it O(n * pow(2, min(k,u))) because this code will generate all subsets of length <= min(k,u).

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    u = no. of unique character in string "a". k = min(u,k). usually we talk about worst case so it will be n*(pow(2,10)).But to be precise I think it will be n*pow(2,u).It is sure,we will go through all subsets of unique characters but for answer to be maximum we will consider only subsets having exactly k elements.Hope you will get.

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

Can someone tell me why this code on problem D gets a TLE? https://codeforces.com/contest/1778/submission/191678717 Thank you very much if you can help me or give me some advice.

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

Shouldn't complexity in E be $$$O(nlog^2(d))$$$, where $$$d=max(a_i)$$$ not $$$d=log(max(a_i))$$$?

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

probably it's late but I have another solution for problem D which I think it's more easier ,it depends on linearity of expectation.

Let $$$rem$$$ to be the number of positions that have $$$a_i \neq b_i$$$ and $$$n$$$ is the size of strings.
let $$$dp_i$$$ the expected number of flips to go from state $$$i$$$ to $$$i-1$$$ .
let $$$p_i$$$ the probability of selecting non-equal position which will $$$p_i=\frac{i}{n}$$$ .

By linearity of expectation ,the answer is $$$\sum_{i=1}^{i=rem}dp_i$$$ .

We will calculate $$$dp_i$$$ from this formula $$$dp_i= p_i .1 +(1-p_i)(1+dp_{i+1}+dp_i)$$$ and then simplifying $$$dp_i= \frac{1+(1-p_i).dp_{i+1}}{p_i}$$$.

finally the base case is $$$dp_n=1$$$ because in this state we will definitely go to state $$$dp_{i-1}$$$ only.

Code

Sorry for my bad english it's my first try for explanation.

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

I have a question please help in problem d

We get, ai=n+i⋅ai−1n−i⋅bi−1 and bi=n−in−i⋅bi−1 for 2≤i≤n.

f(i)=ai+bi⋅f(i+1).

so why can't be just get value of f(i+1) directly

f(i+1) = (f(i)- ai ) / bi

Why can't we directly find value like this?

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

Isn't the worst case time complexity for C : O(2kn)

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

    I think because of the:

    "if sum(cc) == k:"

    you will only get a time complexity of 252 * n. ( 10!/(5!*5!) = 252 )

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

      Okay that makes sense, but there are still 2e7 operations at max which I think is a lot for 2 seconds when doing recursion.

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

I see a lot of comments for problem D, I found the alternative approach pretty interesting so I made a video on it, you can find this on the channel- here . If the video doesn't show up then please wait for a while as YT sometimes takes a bit long to process it.

Happy coding :)

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

This worked for problem D so maybe it will work for problem E... Geothermal can you please explain you solution for problem E? I think people (myself) would be interested in knowing how it works.

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

    For the most part, my solution is equivalent to the model solution: in particular, I compute subtree XOR bases and use them to answer queries where the root is equal to or outside the subtree of our given vertex.

    The component of my solution that differs from my solution is the case where the root is in the subtree of our vertex. Let c be the child of our vertex whose subtree contains the root; we can find c by binary searching on the pre-order traversal. We note that we are essentially computing the maximum XOR of all vertices outside the subtree of c. The model solution thus precomputes XOR bases for all prefixes and suffixes of the preorder traversal, then merges the bases for the prefix and suffix excluding the subtree of c to compute the answer.

    My solution instead uses rerooting DP to directly compute the XOR basis of all vertices outside the subtree of c for each vertex c in the tree. To perform the rerooting, I use a similar prefix basis/suffix basis idea: for each vertex, I merge the XOR bases for each prefix and suffix of its children; then, to go from a vertex to its child, I merge the XOR basis containing v and vertices outside the subtree of v with appropriate prefix and suffix bases.

    I think the model solution is much more elegant and easier to implement than mine; I would have implemented it had I thought of it in contest. Unfortunately, I was being a bit silly, so this is what I ended up with :)

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

      Ah that makes a lot of sense. So instead of using the euler tour for computing your prefix and suffix XOR basis you did it directly on the children of each node and found a way to transition using the prefix and suffix XOR basis of the node's siblings, nice.

      I agree it's not as clean, but I think it's a cool idea. Thanks for sharing.

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

Has this round been unrated? My rating still keeps unchanged yet!

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

C is very strange. O(10^8) solution is also working which I think usually do not work. Moreover, I found many solutions which were accepted during contest but after contest giving TLE. One more thing my solution is accepted only after I passed the vector by reference to the recursive funtion.

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

Don't forget to update the rating of #848 for me later. I was in div1 when registered in this contest, but that's because my negative rating in TypeDB round was rolled back temporarily, and I should be counted as div2 in this contest. MikeMirzayanov

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

There are certain solutions for problem c which have been tested for28 test cases only whereas there are others which are tested for 38 test cases. Some solutions which were accepted during the contest are giving tle right now when submitted.

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

192167224 why is this TLE ? How do I improve it? Div2D

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

Hey can anyone explain the intuition behind problem A shy the sum is reduced by 4 and increased by 4 ?

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

Problem F can also be done with a brainless $$$O(36*36*n)$$$ 5D dp if you observe that only the prime factors of the root node's value matter, and each node's value has atmost 4 unique prime factors.

The dp state will be: $$$dp[v][p][q][r][s]$$$ which holds the minimum number of moves required to make the lowest frequency in any node in subtree of $$$v$$$ of the $$$1$$$'st till the $$$4$$$'th prime factor equal to $$$p$$$, $$$q$$$, $$$r$$$ and $$$s$$$ respectively (minimums can occur in different nodes for different prime factors).

Implementation:link

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

adnan_toky Suppose in question C we take U = 26 and K = 10 . Will the #operations won’t go over 10^10 ?

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

Sorry for disturbing old discussion but could anyone explain how Red people or black-red people have used bitmasking in Problem C? Brute force is pretty simple but i don't get the mask idea. This is jiangly's submission which i do not seem to understand properly? why is he comparing the number of bits set in K with the number of bits set for a particular alphabet frequency. 191557742

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

In the code of B, which is given in the editorial. It is not needed to check for all adjecent pairs in array "a" , only take the two elements which are farthest in position