grphil's blog

By grphil, history, 4 weeks 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  

»
4 weeks 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 :)

»
4 weeks 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.

»
4 weeks 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

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

    I think it is a mistake, it should be %k for all.

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

in problem C if the node doesn't respect it's parents and also if it's children doesn't respect it then we can make frequency array for all nodes such that for every node we count its children respecting and another array for counting for every node how many children it has and then iterate over all nodes and check if frequency[node] == children_count[node] then add this node to our solution

https://codeforces.com/contest/1143/submission/52133561

»
4 weeks 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.com/contest/1143/submission/52039066

»
4 weeks 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) ).

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

Thanks for fast editorial.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks 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)

  • »
    »
    3 weeks 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.

»
3 weeks 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..

  • »
    »
    3 weeks 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

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

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

»
3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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?

»
3 weeks 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

»
3 weeks 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|)$$$.

»
3 weeks 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

»
3 weeks 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 ?

  • »
    »
    3 weeks 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)

    • »
      »
      »
      3 weeks 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!

      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks 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)

      • »
        »
        »
        »
        3 weeks 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)

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

Some one please explain div 2 B ?How to reach the solution and topic related to it to solve further problems in contest.

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

Can someone tell one example of solving lynyrd skynyrd

»
3 weeks 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

»
2 weeks 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.

»
10 days 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 ?

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

I was able to solve Queen (https://codeforces.com/contest/1143/problem/C) without any graph iterations, but instead with hashing and some if statements. https://codeforces.com/contest/1143/problem/C