### grphil's blog

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

• +58

| Write comment?
 » 5 years ago, # |   +1 @grphil Can you please add a link to the editorial in the announcement post or the contest website :)
 » 5 years ago, # |   +8 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.
 » 5 years ago, # | ← Rev. 2 →   -6 why (a-b)%c,(a+b)%c,(b-a)%c,(-a-b)%c will give me ans. if anyone explain it will be helpful
•  » » 5 years ago, # ^ |   0 I think it is a mistake, it should be %k for all.
 » 5 years ago, # |   0 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
 » 5 years ago, # |   0 All problems are interesting. A great round.Thanks. And there's a shorter solution to div1D (with complexity of O(N·11) ).
 » 5 years ago, # |   0 Thanks for fast editorial.
 » 5 years ago, # |   +21 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)
•  » » 5 years ago, # ^ |   +48 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.
•  » » » 5 years ago, # ^ |   0 This really helps, thank you so much!
 » 5 years ago, # |   0 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..
•  » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ |   0 Now I fully understand. Thanks for the explanation and the awesome problem!
 » 5 years ago, # |   +21 Lynyrd Skynyrd can be solved in linear time, using DFS instead of binary lifting.
•  » » 5 years ago, # ^ |   0 I see.. Great!
•  » » 5 years ago, # ^ |   0 http://codeforces.com/contest/1143/submission/52292980 emmmm...like this? DFS the tree from right to left
 » 5 years ago, # | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Could you please elaborate on the second part? Why N different distances?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 you can see my answer below，i drew a picture，maybe it can help you
 » 5 years ago, # | ← Rev. 10 →   0 question about 1142 C. How to understand, what lines are top and what are not?
 » 5 years ago, # | ← Rev. 2 →   0 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
 » 5 years ago, # |   +16 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|)$.
 » 5 years ago, # |   0 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
 » 5 years ago, # | ← Rev. 2 →   0 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 ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 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)
•  » » » 5 years ago, # ^ |   0 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!
•  » » » » 5 years ago, # ^ | ← Rev. 5 →   0 we denote the start place is A ，the first step place is Bthen c is the shortest distance between A and B， and there are four situation for A and Bthere are a cycle every k positions
•  » » » » » 5 years ago, # ^ |   0 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
• »
»
»
»
»
»
5 years ago, # ^ |
0

and the four value of c is

# (k-b)-(k-a)

• »
»
»
»
5 years ago, # ^ |
Rev. 10   +6

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

# RaEEEREEEEREEbE (l=2*k+c)

c=-1 below

# REEEaREEEEREEbE (l=2*k+c)

c=-2 below

# REEEaREEEEREbEE (l=2*k+c)

c=1 below

# RaEEEREEEEREbEE (l=2*k+c)

•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 .
•  » » » » » 5 years ago, # ^ |   0 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 ?
•  » » » » » » 5 years ago, # ^ |   0 yes，there are different ， you can caleculate the value of “l” and you would find the difference
 » 5 years ago, # |   0 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
 » 5 years ago, # |   0 You wrote too many wrong words,which add too much difficulty to me to understand.
 » 5 years ago, # | ← Rev. 2 →   0 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 ?