awoo's blog

By awoo, history, 5 weeks ago, translation, In English

1511A - Review Site

Idea: BledDest

Tutorial
Solution (adedalic)

1511B - GCD Length

Idea: BledDest

Tutorial
Solution (awoo)

1511C - Yet Another Card Deck

Idea: BledDest

Tutorial
Solution (Neon)

1511D - Min Cost String

Idea: BledDest

Tutorial
Solution (Neon)

1511E - Colorings and Dominoes

Idea: BledDest

Tutorial
Solution (BledDest)

1511F - Chainword

Idea: BledDest

Tutorial
Solution (awoo)

1511G - Chips on a Board

Idea: BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +77
  • Vote: I do not like it

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

solved 1st 3 ques very fast but got struck on 4th ques,btw nice contest :)

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

Can someone please explain the solution that's given in tutorial of problem D thanks. I have done a simple solution in that that prints a + ab + ac + .... + az and so on , but I want to understand how the editorial solution works for this

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

    Can you explain your solution? I dont get it

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

      The idea is to use all the substring of length 2 and then just repeat the answer string again and again until you get length n.

      a + ab + ac + ...

      you can see this first we are using all the different substring of length 2. once you are done with all of them you are just going to repeat your string. because you cannot do better than that as you have used all distinct substring of length 2.

      I saw the first example test case , which used the same pattern.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lol yeah even I got the same logic like suppose n = 8 and k = 2 then a simple string can be aa+ab+ba+bb which is "aaabbabb" in any case where n is > k² we just repeat this array !!! Am I right ?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          your way of thinking is correct , but the way you construct string will have repetition

          aa + ab + ba + bb = > aaabbabb

          if you see you will get repetitions

          that's why you have to construct like

          a + ab + ..... this way you will get all string unique and then you can simply repeat

          You are trying to do the right thing but the implementation that you are telling if you see closely will have repetitions because some substring of size 2 will occur before only. like in the example that you have given ab is repeating.so you have to do the implementation taking care of that

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

        I think you are missing one point -> lets say k = 4 then you can do ab ac ad bc bd cd a i.e d -> a which i dont think your solution considers, although it gets accepted!

        NVM I found the mistake, and now feel like a fool, but your solutions is insanely clean and intuitive so GG.

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

    What a solution !

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is the same as you and I quickly solve this problem. Amazing.

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

For 1511B — GCD Length it can be another easy approach

cout<<(ll)pow(10, a-1)<<" "<<(ll)(pow(10, b-1)+pow(10, c-1))<<"\n";

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

    Can u please explain this qn. it took lot of time and i didnt got soln and even not understood the editorial also

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

      same. i could not understand the editorial.

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

      First solve the case with $$$c = 1$$$. This is easy, we just need two coprime numbers of a certain length, which we can get in many ways. For example $$$10^{a-1}$$$ and $$$10^{b-1}+1$$$.

      Now note that given a solution to the problem $$$a,b,1$$$, we can transform it to a solution of $$$a+c-1, b+c-1, c$$$ by multiplying by $$$10^{c-1}$$$.

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

      I think a example can help you to understand

      Let , a = 4, b = 5, c = 3

      X be a number of length a & Y be a number of length b

      X can be obtained by many ways but an optimal value of X can be 10^(a-1) -> as example the X is 1000 (10 ^ (4 — 1))

      same goes for Y. Y is 10000 (10 ^ (5 — 1))

      Now here comes the GCD part. GCD of X, Y (1000, 10000) is 1000

      But g = 1000 is having a length of 4 that is not what we wanted.

      Same as X & Y, we can have the g. g = 10 ^ (3 — 1) = 100

      Our GCD has to be 100. We can have this GCD easily by adding it to Y. So, our new Y is Y + g = 10000 + 100 = 10100.

      Now, the GCD of X, Y = GCD(1000, 10100) will be 100, it is having the length of C.

      I guess this will help.

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

        thank you very much for your response.very much appriciated

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

        Really Nice Explanation!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the help. Really good explanation buddy .

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks dude, really nice explanation

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        nice explanation

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But , How did it came to your mind ? I mean , what was the intution

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

          I think the approach behind it is: gcd(X,Y)=gcd(X,X%Y) Now what they did is they just add the gcd that is 100 in this case to Y, because initially, Y will always be divisible by X since both X and Y are the power of 10. So whatever we will add in Y is going to be the remainder. and that remainder will be the gcd.

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

        thanks.it helped a lot!!!

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

    how but?

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

My (faster) solution to G, using binary jumping/lifting/whatever:
It's obvious that for range $$$[L, R]$$$ we want to consider a game of nim where a token at column $$$L\leq i\leq R$$$ corresponds to a pile of size $$$i-L$$$.
Let $$$x[i][j]$$$ denote the xorsum of tokens in the range $$$[i, i+2^j)$$$, where the left border is $$$i$$$ (i.e, a token at $$$i+k$$$ contributes $$$k$$$ to the xorsum).

If we know $$$x[i][j]$$$ for all $$$i, j$$$, the xorsum of $$$[L, R]$$$ can be computed as follows.
(Below, $$$\oplus$$$ denotes xor)
Initialize the xorsum $$$G = 0$$$.
For each $$$k$$$ in descending order, if $$$L+2^k \leq R$$$, do:
1. $$$G = G \oplus x[i][k]$$$
2. If there are an odd number of tokens in the range $$$[L+2^k, R]$$$, further do $$$G = G\oplus 2^k$$$
3. $$$L = L+2^k$$$
At the end of this process, $$$G$$$ is exactly the xorsum we want, so we simply check whether it is $$$0$$$ or not.

So, we want to be able to compute all the $$$x[i][j]$$$ fast — this can be done with a similar process:
1. $$$x[i][0] = 0$$$ for all $$$1\leq i\leq m$$$.
2. $$$x[i][j] = x[i][j-1] \oplus x[i+2^{j-1}][j-1]$$$
3. If there are an odd number of tokens in $$$[i+2^{j-1}, i+2^j)$$$, further do $$$x[i][j] = x[i][j] \oplus 2^{j-1}$$$

Note that we need to be able to check whether some range contains an odd number of tokens, but that's easily done with prefix sums.
Time complexity is $$$\mathcal{O}(mlogm)$$$ for the binary jumping precalculation, and then each query is answered in $$$\mathcal{O}(logm)$$$.

My submission: 112843116

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

    Hi! I didn't really get why you need $$$x[i][j]$$$. It's just a xorsum on a segment. Can't you just use prefix xors too to find it?

    My solution is also $$$\mathcal{O}(m \log m)$$$ but uses a different idea and actually needs $$$\mathcal{O}(m \log m)$$$ memory. But it seems like yours needs only prefix sums and xorsums.

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

      It's not quite the xorsum of a segment, more like the shifted xorsum of a segment.
      For example, if there are tokens are at columns $$$1, 3, 6, 14, 104$$$, I would have $$$x[2][5] = (3-2)\oplus (6-2)\oplus (14-2) = 9$$$.

      I'm not quite sure how you would do the shifting with prefix xors.

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

        Oh, I'm sorry. I misunderstood your explanation.

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

    Nice solution!

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

    Very nice solution!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fantastic stuff, I did something similar using a segtree with offline queries.

    My memory complexity is linear, but total time complexity is $$$O(m \log^2 m)$$$.

    The idea is that you can maintain a xor-lazy segment tree, if you want to add/subtract $$$2^k$$$ from all stored elements, you can do that by issuing lazy xor-updates in groups of $$$2^k$$$. You can "visit" all subtractions from $$$1$$$ to $$$m$$$ recursively, starting from low values of $$$k$$$. For example, with $$$m=7$$$, you can have these additions/subtractions in order: $$$[-1, -2, -4, +4, +2, -4, +4, +1, -2, -4, +4, +2, -4, +4]$$$ and you will visit all numbers from $$$1$$$ to $$$7$$$. Notice that $$$2^k$$$ is added/subtracted exactly $$$2^{k+1}$$$ times, so there are $$$O(m \log m)$$$ segment tree updates.

    This idea was completely new to me when I first solved this problem.

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

BledDestForces

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

I believe that everyone wonders how top 1 risujiroh use O(n^2) brute force to solve G without being hacked. Can someone explain why this solution 112827572 run so fast:)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    That is basically because of two things:
    1. Using GNU C++17 (64) instead of the 32 bit version.
    2. The presence of these two lines at the top:

    #pragma GCC optimize("O3")
    #pragma GCC target("avx2")
    

    Remove any of those and you get a TLE :)

    Edit: Why so many downvotes? I don't think I said anything wrong. If you don't believe me then try for yourselves.

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

      In this case it seems that you can make it even faster if you submit in C++14 but add the line:

      #pragma GCC optimize("unroll-loops")
      

      See here (it runs in around 4000ms instead of the 4700ms for the original). I'm not sure how exactly this whole thing with pragmas works, this was just an experimental discovery.

      Another thing that seems to contribute to it passing is the usage of

      cout << "AB"[x == 0];
      

      Instead of something like

      cout << (x == 0?"B":"A");
      

      See here. Again, not at all sure why this makes such a difference, but it does.

      Maybe someone can say why these things are the way they are?

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

Could someone pls tell the combinatorics / dp approach for E ? I saw in the announcements page but is very unclear.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    we can do it in the following way,first of all lets calculate what will be the answer if we would have 1 segment with length i that contains only 'o'.its can be done in the following way

    cnt_odd[i] = 2^(i-2) * cnt_odd[i - 2];

    dp[i] = dp[i - 1] *2 + cnt_odd[i -1]

    where cnt_odd[i] it is mean how much segments [0..i] that has sufix wich contains only '0' and has odd len. than for each consecutive segments of 'o' ans+=dp[len of that segment ] * (count of all possible сoloring of all other matrix).we should do it for horizontal and vertical segments. it's may become more clear if u look at code 112952569. Also i can explain better how we calculate cnt_odd or othere things if needed.

    P.S sorry for my pure english)

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

      Yeah. Could you pls explain that (calculating count odd ad etc) ? Also how do you merge after calculating dp arrays horizontally and vertically ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        first of all lets name strings that has sufix which contain only symbol 'o' of odd len good.

        cnt_odd[1] = 1. becouse string "o" is good. As well as “**”

        cnt_odd[2] = 1. becouse there is string "*o"."oo" has even len so its not good.

        let assume that we have string of len i that has last symbol equal to 'o'. Than to be good (i-1)-th symbol of that string should either be '*' than we dont care about others symbol so there can be all possible coloring 2^(i-1).Otherwise (i-1)-th symbol is 'o',so to be good string [0..i -2] should be good as well.so cnt_odd[i] = 2^(i-1) + cnt_odd[i -2].

        Now about merging.We have some horizontal consecutive segments of 'o' and some vertical.Let solve them separately.we know that 1 consecutive segment of len i create dp[i] domino. however it will create dp[i] domino for every of possible coloring of the rest of matrix.For example we have segment "ooo" and "o" than answer will be 6 becouse segment "ooo" create 3 domino if second string colored red and 3 if second string colored blue.So 1 segment add to the answer len * 2^(count_of_white -len).

        I dont know how to explain why we can do separately for horizontal and vertically but i think that is not hard to undestand if u think a little.

        has it become clearer,or should i try to explain one more time? Do u also need an explanation how we calculate dp?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you explain how you got the transition function for the dp i.e the relation dp[i] = dp[i - 1] *cnt_odd[i -1]

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i have mistakenly write not correct formula in the post(in a code its correct). I am realy sorry for that.

            So correct formula is dp[i] = dp[i -1] * 2 + cnt_odd[i-1]. if we know an answer for segment of len (i — 1).Than let us take a look at a segment of len i.We can see that answer for dp[i] is at least 2-times bigger becouse we will add at least dp[i -1] if we would color i-th element in blue and add at least dp[i -1] if we would color i-th element in a red.However for each segment [0..i-1] that has sufix of only 'o' and its len is odd we will add one more domino. Has it become more clear or should i explain anything more? P.S take a look at code it's may become more clear 112952569

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

              Sorry , I could not understand the explanation . Can you explain this a bit more ( with a simple diagram , if possible ).

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

For problem E, can anyone tell the way to find the OEIS sequence (incase anyone else did by finding contributtion method).

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

In problem D how will we get a Euler cycle of length k*k + 1, do we also have to add self loop for that, because without that you cannot get an Euler cycle of k*k + 1, can someone explain, possible taking example of k = 3.

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

    This Explanation might help you. Video Explanation

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

      thanks for the reference , but I wanted to get the answer of how we are going to get a string of length k square + 1 if we print the Euler circuit for the graph of k vertices

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

How to find eulerian cycle in 1511D - Min Cost String

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

can someone explain e more properly?using dp etc

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

Have to say, problem D would have been a lot harder, if not for the Ist sample testcase :) .Again ,perhaps some participants might have found the correct approach in a more intuitive manner.

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

I problem F I had slightly different approach. I tried to compute $$$DP[L][i][j][k]$$$ which would mean the number of pairs of chainwords, such that first of them has length $$$(L + i)$$$, second $$$(L + j)$$$ and last part of longer chainword comes from $$$k$$$-th word. We can compute it quite straightforward without using any kind of tree structures. All we have to check is whether some parts of words match. We just see that it is enough to store only $$$((d * (d - 1)) / 2) * n + d$$$ interesting states (though we don't have to use symmetry to pass tests).

Code: https://pastebin.com/04kf681r

»
5 weeks ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Was anyone else confused by the legend of F, thinking it meant count the number chainwords that have resolved ambiguity? This isn't the case tho, right?

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

Is this rare way to solve B...?

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

    Lol I did the same thing, searching for prime numbers that big was a real hassle though :P

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

    I also had a fun solution while preparing the task.

    Code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I did this too, but on my alt account.

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

" Now, let's suppose there are two strings i and j such that cnti−cntj≥2. Then, if we somehow reduce the number of occurrences of the string i by 1 and increase the number of occurrences of the string j by 1, the cost will decrease " What does that mean ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "strings" here means pair of two characters like aa, ab, ac, etc.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually the solution of many participants is easier & simpler than the editorial

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

Can someone help me to in problem d (min cost string)? What's the intuition behind the greedy approach. like this

Taken from submission (random)

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

Can someone explain how to produce your logic for questions similar to problem B during competitions? I solved C and D in the second hour but I couldn't solve B after wasting the first hour in virtual participation...

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

    Let t = gcd(x, y)

    => x = At

    y = At

    So I choose t = 10^(c — 1), then choose A = 10^(a — 1 — (c — 1)), B = 10^(b — 1 — (c — 1)) + 1

    It can be proven that gcd(A, B) = 1, so gcd(x, y) = t

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

For problem F, I generate the input that requires 141 states.

case

And I believe this to be an upper bound. If there is no string that become other string prefix, the number of states will be at most 49. If there is a string that become other string prefix, the number of states will be at most 161 — 20 = 141

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the way I modeled the problem this case takes only 99 states, so I must be doing something different.

    I imagined the graph as a finite state machine where each accepting path is a way to construct a possible chainword. The states are pairs $$$(u, v)$$$ where $$$u$$$ and $$$v$$$ are proper (and possibly empty) suffixes of a word in the dictionary, and $$$u$$$ is a prefix of $$$v$$$, and they represent a look-ahead of the chainword we are building. The initial and only accepting state is $$$(\varepsilon, \varepsilon)$$$.

    Edges from $$$(u, v)$$$ to $$$(u', v')$$$ represent a way to add one character to the chainword, they fall in three cases:

    • $$$u$$$ and $$$v$$$ are non-empty so $$$u'$$$ and $$$v'$$$ are equal to $$$u$$$ and $$$v$$$ resp. minus the first character in each.

    • $$$u = \varepsilon$$$, so $$$u'$$$ is a word in the dictionary (again, minus its first character) to continue the chainword from $$$\varepsilon$$$.

    • $$$u = v = \varepsilon$$$, so $$$u'$$$ and $$$v'$$$ represent two words in the dictionary that are prefixes from one another to start building a chainword.

    I believe this approach is very similar to using a trie but there must be a difference somewhere I am not seeing. Is it that I am merging some states into one?

    Code

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The writer's solution contains unnecessary states. For example, ("abcde", ""), ("abcde", "abc"), etc. The number of unnecessary states is 42, and your answer removes these states.

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

Can someone please explain me how the logic of D work?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It works on the concept Euler circuit. you make every letter up to k as a vertex in a graph and connect every vertex to every other one because we can pair every letter with every other one.

    after that you print the euler cycle of graph which will general all distinct string of size 2 using k letters. and after that you can just repeat this string.

    Euler circuit says that you can visit every edge of the graph only once. and every edge contains two letter so you will be visiting every substring of size 2 as the graph is complete graph.

    This is the concept of the problem.

    now you can implement it by Euler circuit and graph and all. But as I didn't know how to do that I did it using two loops.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your Welcome :D

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Please explain your 2 loop solution?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            first loop I'm starting with a to less than k and adding that aplhabet to string and in the jth loop I'm starting from i + 1, that is from the next letter which I took in i loop.

            for example: if in the ith loop I have added b to the string then the jth loop I will start from c and not from a because ba would already have occured in the previous iteration when i was a.

            for a, b and c

            first iteration i = 0 string a then in jth loop i'm starting from b and adding ab, ac .. so string will be a + ab + ac => aabac

            the i will become 1 I will add b string => aabacb

            now j will start from c , because you can see ba has already occured in previous iteration

            so string will be aabacb + bc and so on

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This Video Explanation might help you.

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

Problem G can be solved with MO.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how to shift the bounds (of MO, i.e. l, r) fast enough?

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

Can someone explain the Euler cycle algorithm mentioned in the solution of Problem D? I am not able to explain myself why this algorithm will give an Eulerian cycle i.e. why each edge is visited exactly once? Thank you!

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

1511G - Chips on a Board Isn't complexity of solution from editorial should have log N outside of square root?

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I want to share my solution of 1511G - Chips on a Board.

All we need to do is to find XOR of $$$c_i - L$$$. For details "why?" look into editorial. I'll describe here how I calculate it. Notice that we can represent each number as two digit number XY in some base $$$2^k$$$. Then $$$c_i$$$ is some xy and L is XY. But this is the same as XOR all (y-Y) and (x-X) but some of them will turn into (x-X-1) when y < Y because of carry. My idea was to view it as points in table, where X digit is on X axis, and Y digit is on Y axis. Notice, that size of table is $$$2^{2k}$$$, so with appropriate k it is O(m) memory. Then we need to XOR all xy-XY. Then, to count how many times there is x among $$$c_i$$$ is just segment in column which can be calculated as prefix sums. And, to count how many times there is y among $$$c_i$$$ is just segment in row which can be calculated as prefix sums. But here is the problem: how can we tell should we subtract 1 for carry or shouldn't? This is most tricky part of whole solution. It turns out that we subtract 1 when y < Y, but it also can be calculated as prefix sum! Because we need to find out how many of x from column we should subtract 1 and how many we shouldn't but within single column x there are exactly numbers xy where v < Y we should subtract 1, and v >= Y we shouldn't, because carry won't happen. So, we can make two tables of prefix sums: for columns and rows. Each table has $$$2^k$$$ in both dimensions, and then for each X, and each Y we calculate prefix sum which is $$$O(2 \cdot 2^k)$$$ for each request. Overall complexity then is $$$O(n+m+q\cdot\sqrt{m})$$$ 113146022

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

Priyansh31dec Can you please explain your approach on problem E? 112846413

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

can you explain gcd length question i didnt get it

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

Can someone suggest some more problems which can be solved using probability for counting as mentioned in the editorial. I understood the solution but I want to practice more such problems. Thanks in advance :)

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

Alternative solution for problem 1511G - Chips on a Board
Consider each bit $$$b$$$ separately and keep a data structure that contains the remainder of the position of the coins in a suffix, modulo $$$2^{b+1}$$$. It should handle these operations:

  • range sum on $$$[2^b, 2^{b+1} - 1]$$$ (get number of coins with that bit turned on)
  • point update on $$$0$$$ (add a new coin)
  • add $$$1$$$ to all elements (add a column on the left)

So you can use a Fenwick tree with Venice trick for each bit.
Total complexity: $$$O(n \log^2(n))$$$.
113692737

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

In the author's (BledDest) solution for problem E, why is p[0] = (1 / 2)? What is p? Thanks in advance.

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

Is there any similar problem on codeforces as problem F but maybe of lower difficulty. I cannot understand the editorial at all.