grphil's blog

Codeforces Round #549 Editorial
By grphil, history, 6 years ago, In English
Tutorial is loading...

Authors: grphil and vekarpov

Tutorial is loading...

Author: MikeMirzayanov

Tutorial is loading...

Authors: grphil and vekarpov

Tutorial is loading...

Authors: grphil and vekarpov

Tutorial is loading...

Author: qoo2p5

Tutorial is loading...

Authors: grphil and vekarpov

Tutorial is loading...

Authors: grphil, qoo2p5, super_azbuka

Tutorial is loading...

Author: grphil

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

Comments Comments (37)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

@grphil Can you please add a link to the editorial in the announcement post or the contest website :)

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I love how elegant the solution to U2 was. Just a simple transformation and a difficult problem can be solved by finding the convex hull.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

why (a-b)%c,(a+b)%c,(b-a)%c,(-a-b)%c will give me ans. if anyone explain it will be helpful

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw many solutions of B and did not find any by Dynamic programming approach. I solved the problem by Dynamic programming. If anyone want to try this approach Here is the code. Its basic Digit DP. https://codeforces.net/contest/1143/submission/52039066

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All problems are interesting. A great round.Thanks. And there's a shorter solution to div1D (with complexity of O(N·11) ).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial.

→ Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

For div2 E, could someone go more into detail for how to use binary lifting? (the only way I've used it before is to find lca)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    You need to calculate $$$b[b[b[\ldots b[i] \ldots ]]]$$$ $$$n - 1$$$ times. You can do the following: first you calculate $$$b[b[i]]$$$, then $$$b[b[b[b[i]]]]]$$$, then the same thing 8 times, 16 times and so on. To calculate this you can use the same algorithm as it was for calculating binary lifting fo LCA. And then you can calculate $$$b[b[b[\ldots b[i] \ldots ]]]$$$ $$$n - 1$$$ times the same way as the $$$k$$$-th ancestor in the tree using the binary uplifting (first you compare $$$2^{20}$$$ and $$$n$$$, if $$$2^{20}$$$ is less, then you go upwards by $$$2^{20}$$$ and decrease $$$n$$$ by $$$2^{20}$$$, then you do the same with $$$2^{19}$$$, $$$2^{18}$$$ and so on.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D The parameters of all numbers that come from x will still be defined because if we increase a by 11, these parameters will be the same modulo 11, if we increase b by 11, a and b parameters of all numbers that come from x are increase by 0+1+2+…+10=(11⋅10)/2=55 which is 0 modulo 11. The same is with c parameter.

Can someone explain that why it is the same when changing parameter c?

I find it hard to understand the editorial, please make the editorail more specific..

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With $$$c$$$ it is the same because if you increase $$$c$$$ by 11, $$$a$$$ parameter for numbers that come from $$$x$$$ will increase by 11 which is 0 modulo 11, $$$b$$$ parameter will not change and $$$c$$$ parameter will increase by $$$0 + 1 + 2 + \ldots + 10 = 10 \cdot 11 / 2$$$ which is 0 modulo 11

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now I fully understand. Thanks for the explanation and the awesome problem!

      → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Lynyrd Skynyrd can be solved in linear time, using DFS instead of binary lifting.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain why c can take only 4 values? My first thought was find all possible locations of the first visited restautant and find all possible locations of second visited restaurant. Then find all corresponding values of l but this will obviously timeout. Can anyone share the correct approach.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It doesn't matter where the first and second restaurants are, only the distance between them. So N different distances, times 4 for different ways to place first and second points around them.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please elaborate on the second part? Why N different distances?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        you can see my answer below，i drew a picture，maybe it can help you

        → Reply
»
6 years ago, # |
← Rev. 10   Vote: I like it 0 Vote: I do not like it

question about 1142 C. How to understand, what lines are top and what are not?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Div 1 C: what if there isn't a way to draw some parabolas that satisfy the statement? Like... (1,2) and (1,3)? Edit: Nevermind i was dumb

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

In div1D, I have a short (~20 lines) solution which doesn't depend on starting numbers, it only uses the fact that if we know that $$$x$$$ is the $$$k$$$-th inadequate number and we want to create $$$10x+d$$$ from it, then we just need to look at the $$$k\%11$$$-th inadequate number (let's denote it by $$$a$$$), at the first inadequate number $$$\ge 10a$$$ (let's say that it's $$$l$$$-th) and then, if $$$10x+d$$$ is the $$$m$$$-th inadequate number, we know that $$$m \equiv l+d$$$ modulo $$$11$$$.

Now I just process the characters in the string in order while remembering how many inadequate substrings ending at the current position have which remainder mod $$$11$$$. The above shows that with minimum precomputation, the transition to the same information (number of substrings for each remainder) after appending the current character $$$c$$$ is uniquely given by $$$c$$$ and can be computed in $$$O(11)$$$ time, so the total is $$$O(11|S|)$$$.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

emm...The div1D use int[1e5][11][11][11] get memory limit，use unsigned short[1e5][11][11][11] get wrong answer because the max(unsigned short)=65535<100000

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For div2 D, could someone go more into detail ? Where does the values of c come form ? and how a,b,c are inter-related through the step size ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    a,b is relative to input,and i think the 'c' in ((a+b)%c,(a−b)%c,(b−a)%c,(−a−b)%c) is typo, correct is ((a+b)%k,(a−b)%k,(b−a)%k,(−a−b)%k)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay, can you please explain what exactly is c and how theoretically how it is related to a and b?. I mean what exactly c denotes? Also how come l is related to k and x? Can you please explain this? Thank You very much!

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        we denote the start place is A ，the first step place is B

        then c is the shortest distance between A and B， and there are four situation for A and B

        there are a cycle every k positions

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you very much for replying!.. But I still don't understand. what exactly is c? And why is l = kx+c.. how l is related to k and x? Thank you for your patience

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            and the four value of c is

            b-a

            (k-b)-a

            b-(k-a)

            (k-b)-(k-a)

            → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 10   Vote: I like it +6 Vote: I do not like it

        for example k=5，n=3,a=1,b=2 the road show below (R is restaurants ,E is empty)

        REEEEREEEEREEEE

        then c=2 below

        RaEbEREEEEREEEE (l=0*k+c)

        RaEEEREEbEREEEE (l=1*k+c)

        RaEEEREEEEREEbE (l=2*k+c)

        c=-1 below

        REEbaREEEEREEEE (l=0*k+c)

        REEEaREEbEREEEE (l=1*k+c)

        REEEaREEEEREEbE (l=2*k+c)

        c=-2 below

        REbEaREEEEREEEE (l=0*k+c)

        REEEaREbEEREEEE (l=1*k+c)

        REEEaREEEEREbEE (l=2*k+c)

        c=1 below

        RabEEREEEEREEEE (l=0*k+c)

        RaEEEREbEEREEEE (l=1*k+c)

        RaEEEREEEEREbEE (l=2*k+c)

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          .

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But it looks like the possible values of a and b for c = 1 and -1, and for c = 2 and -2, are same (just flipped and rotated), which should not affect the answer.

          I mean won't the answer be same for c = 1 and c = -1, and for c = 2 and c = -2 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes，there are different ， you can caleculate the value of “l” and you would find the difference

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, can someone go into details with problem U2?, and explain what's going on. I mean, some hints to get to the solution (perhaps some demonstration, too :)). thanks

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You wrote too many wrong words,which add too much difficulty to me to understand.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I had learnt a way to solve problem D from _rqy（we can find him from the first page of this contest's standing）.His solution can solve the problem D in n·11 time . His solution is short . I wonder if it is also general . Why or why not ?

→ Reply