### grphil's blog

By grphil, 4 weeks ago, translation, ,

Hi Codeforces!

I'm glad to invite you to Codeforces Round #549 (Div. 1) and Codeforces Round #549 (Div. 2), which will be held on Mar/30/2019 20:10 (Moscow time). The round will be rated for both divisions.

Problems were prepared by me, Vladimir vekarpov Karpov, Daniil qoo2p5 Nikolenko, Askhat super_azbuka Sakhabiev and Mike MikeMirzayanov Mirzayanov.

Thanks to KAN and arsijo for helping us, and MikeMirzayanov for the great Codeforces and Polygon platforms.

UPD: You will be given 6 problems in the second division, 5 problems in first division and 2 hours to solve them.

Good luck and Have fun!

The scoring distribution will be announced later.

UPD1: Top 12 participants of div1 round, who are ICPC world finalists, will get branded Codeforces hats. Further details are here.

UPD2: The score distribution is 500-1000-1000-1500-2000-2500 for the second division and 500-1000-1500-2000-2500 for the first division.

List of the winners of the contest:

Div1

Div2

UPD3: Sorry for the delay, the editorial is available here

•
• +325
•

 » 4 weeks ago, # |   +24 I hope the problem statements are short as the announcement
•  » » 4 weeks ago, # ^ |   -40 no coments
•  » » » 4 weeks ago, # ^ |   -23 comments* :P
•  » » 4 weeks ago, # ^ |   -19 Typical "friendly" person in cf
•  » » 4 weeks ago, # ^ |   -14 it is good
 » 4 weeks ago, # |   -87 If the problem with the 5kk depth of recursion will be again, please write in advance, we should not suffer with runtime errors, like adamant.
 » 4 weeks ago, # |   +7 Wishing everyone a wonderful contest after almost a week!
 » 4 weeks ago, # |   +38 Just wondering, how many weeks do you waited for proposal queue to organize this round in Codeforces?
•  » » 4 weeks ago, # ^ |   +11 We waited around 6 weeks before our problems were first reviewed, but after that we haven't waited much for everything else
•  » » » 4 weeks ago, # ^ |   +7 Do they announced or told that you are going to wait even more after you waited for 2 weeks?
 » 4 weeks ago, # | ← Rev. 2 →   +97
•  » » 4 weeks ago, # ^ |   +8 What app/website you're using? Good day to you.
•  » » » 4 weeks ago, # ^ |   +17 clist.by
 » 4 weeks ago, # | ← Rev. 2 →   -44 This time is not friendly to Chinese people.>_<
•  » » 4 weeks ago, # ^ |   +9 The last div1 round was at a time that was much friendlier to Chinese, but not to me. Fair turnaround, I guess.
•  » » 4 weeks ago, # ^ |   +257 What are you talking about, you can see problem statements 12 hours ahead of us.
 » 4 weeks ago, # |   -33 can you make it at 20:20 every contest i can't participate because the bad time
•  » » 4 weeks ago, # ^ |   +22 OK they delayed it 5 minutes for you
•  » » » 4 weeks ago, # ^ |   +3 and the electricity delayed 30 minutes and **** me
 » 4 weeks ago, # |   +31 10:00 on a Saturday morning! California thanks the round setters!
 » 4 weeks ago, # |   +10 Div2 round is rated for non-rated user? (for me)
•  » » 4 weeks ago, # ^ |   +21 Yes. It is rated for everyone whose rating is less than 1900 and also if the user is unrated, it is rated for them too.
•  » » » 4 weeks ago, # ^ |   +7 Okay, thanks
 » 4 weeks ago, # |   0 Sounds good...hope the problem statement will be also great like this announcement.
 » 4 weeks ago, # |   +34 Yeay! My first Div 1!
 » 4 weeks ago, # |   +12 Round delayed by 5 min ":(
 » 4 weeks ago, # | ← Rev. 2 →   +51
•  » » 4 weeks ago, # ^ |   +4 I'm not an ICPC finalist, but I will happily receive a hat if you want xD
 » 4 weeks ago, # | ← Rev. 2 →   0 I gave up the div1 contest because the description of problem A was too difficult to understand, and even did not give the picture.
•  » » 4 weeks ago, # ^ |   0 So?
•  » » » 4 weeks ago, # ^ |   +11 Lack of understanding? literal meaning
 » 4 weeks ago, # |   +10 I get the error ~~~~~ You have submitted exactly the same code before ~~~~~ even though i haven't submitted anything yet. Anyone knows why?
 » 4 weeks ago, # |   -23 Could someone tell me that, if in a round all the participators' rating is higher than me, and I get the last place in the round(the lowest point), will I lose my rating?I found that I can't solve the Div1B and div1A is a little difficult for me. But only Master and International Master Solve that in 15min.QAQ...
 » 4 weeks ago, # |   +1 Can't submit code anymore. Can't even send feedback in the contest page. I keep on getting the error "You have submitted the same code before" and I don't see any submissions in my submission page.
 » 4 weeks ago, # |   +11 Cheating notice: rusau and King_01 submissions on problem B are same
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I don't even know that guy dude! ... neither a single connection between us
•  » » 4 weeks ago, # ^ |   +4 Check this out!!
•  » » » 4 weeks ago, # ^ |   +3 Hahahah nice!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 GFG is saviour :)
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 They both know GFG ;)
 » 4 weeks ago, # |   0 I was stuck on pretest 4 of div. 1 B. any help?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 My code that failed pretest 4 broke with this:3 4 11 2 31 2 2 31 4
•  » » » 4 weeks ago, # ^ |   0 Hmm, that didn't break mine. Guess I'll just wait for sys tests to finish.
 » 4 weeks ago, # |   0 Div2/B is available in geeksforgeeks. https://www.geeksforgeeks.org/find-the-number-in-a-range-having-maximum-product-of-the-digits/
 » 4 weeks ago, # |   +9 Div2B is a copy of this: https://www.geeksforgeeks.org/find-the-number-in-a-range-having-maximum-product-of-the-digits/
•  » » 4 weeks ago, # ^ |   +11 Sorry, my bad. I offered the problem, and it coincides.
•  » » » 4 weeks ago, # ^ |   -86 I think the contest should get unrated
•  » » » 4 weeks ago, # ^ |   -32 I think that problem should be removed from scoring distrubution. As its unfair to other candidates who tried on their on.Before creating the problem, one should search google.
•  » » » » 4 weeks ago, # ^ |   0 If not google, one should search on codeforces. Same problem in codeforces https://codeforces.com/gym/100886/problem/G
•  » » » » » 4 weeks ago, # ^ |   +37 SURPRISINGLY, it is a Grand Prix of Saratov :)
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   +2 I have seen many people have copied the code exactly from the above-mentioned website. Not fair for all those who tried on their own.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 You can also have a prewritten code that make an integer segment decomposition over base-k segment tree. The problem is too standard for talks like "omg this is googlable".
 » 4 weeks ago, # |   +6 Div2 B is just B. Does anybody know a solution without dp?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -14 .
•  » » 4 weeks ago, # ^ |   +7 My idea: I found product of digits of Some integers from 1 to n that they have the greatest digits(kinda integers have more 9), in this way:if n=d3d2d1d0 for every digits greater than zero in n except d0 like d1 i subtracted one from d1 and digits on the right of the d1 turn to 9 which product of them are d3*d2*(d1-1)*9like if n=1099 they are 1099,1089,099 or if n=100000 they are 100000,99999i didn't know how to explain better https://codeforces.com/contest/1143/submission/52059415
•  » » » 4 weeks ago, # ^ |   0 I named this solution as the solution with dp))
•  » » 4 weeks ago, # ^ |   +3 Just precalc)
•  » » » 4 weeks ago, # ^ |   0 it was calculated with the help of a computer that for any number from interval [m[i].first, m[i + 1].first) the answer is m[i].second?
•  » » » » 4 weeks ago, # ^ |   0 Yes. Precalc took 2 minutes.
•  » » 4 weeks ago, # ^ |   0 This solution is kind of dp, but looks more like brute force.One can notice that the number of different possible products is not really big. For example, I considered that for a d-digit number there should be around $9 ^ d / d!$ distinct products. Then, I just did a recursion memorizing the products already computed.Solution
 » 4 weeks ago, # |   0 Any idea how to solve div.2 E,F ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +72 In F, when you convert all points in the input $(x, y)$ to $(x, y - x^2)$, then the problem reduces to finding the number of lines that pass through atleast a pair of points where no points are strictly above the line, instead of parabola (since, the new equation becomes $y^l = bx + c$ from $y - x^2 = bx + c$). This is just the size of the upper convex hull of the transformed points. (Need to take care of the case with lines of same x coordinates, i.e vertical lines)
•  » » » 4 weeks ago, # ^ |   0 wauw. this is beatiful
 » 4 weeks ago, # |   +4 What was the intended solution for Div2E/Div1B? My solution seemed ridiculously complicated, and I imagine there was a simpler way to solve it.
•  » » 4 weeks ago, # ^ |   +1 You want to pick some position in the range [l, r] and $N-1$ times repeat: if you're currently at $a_j = p_i$, then jump to the next $a_k = p_{(i+1)\%N}$ (for the smallest possible $k \gt j$); at the end, you shouldn't be at $j > r$. The rest is just simulating this efficiently with precomputation and RMQ.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It seems like this should be $O(n)$ per query, did you use binary lifting to simulate it efficiently or is there another way to do it that I'm missing?
•  » » » » 4 weeks ago, # ^ |   +5 Yeah, binary lifting is probably what it's called.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 This will probably work For each position find r[i] — first position of next value in permutation(p[2] for p[1], p[1] for p[n] and so on). Now for each position calculate R[i] — min pos where subsequence exists using r and binary jumps, and answer for each query is just checking if minimum of R on segment <= r.
•  » » 4 weeks ago, # ^ |   +3 My solution was to first find the largest $l$, for every $i$, such that there is a subsequence in $[l, i]$, which is a cyclic shift of permutation. For finding this $l$, what we can do is add an edge from each ind $i$ to the nearest ind $j$ in left, such that $a_j$ is the left element of $a_i$ in the permutation. Now, we can easily find $l$ for each $i$ using the approach of binary lifting. Once, we find $l$ for each $i$, we maintain a segment tree, which gives a maximum $l$ for a range. So, for query $[ql, qr]$, if the maximum $l$ in the range is greater than or equal to $ql$, then subsequence exists.
•  » » » 4 weeks ago, # ^ |   0 Hmm, I did the same thing without the segment tree (I think we can delete certain $[l, i]$ intervals and store the rest in a set, and use a lower_bound call, but I could be wrong), but I couldn't really see a nice way to do the binary lifting and ended up having to import my LCA code lol
 » 4 weeks ago, # | ← Rev. 2 →   +37 Me in div1A: number of steps = lcm(L, NK) / L = (L / gcd(L, NK) * NK) / L. Can you spot the fail here?Fortunately, I fixed it, resubmitted and hoped I'd get some points back by hacking, since pretests don't handle it. >Mfw everyone else used NK/gcdUPD: And now it turns out I actually could have hacked people, just not on this...
•  » » 4 weeks ago, # ^ |   0 Why is NK / gcd wrong?
•  » » » 4 weeks ago, # ^ |   +16 It's right, that's the problem. I couldn't hack anyone because of that.
•  » » » 4 weeks ago, # ^ |   0 NK/gcd is right, but what he wrote can overflow
 » 4 weeks ago, # |   0 How can I solve problem D?.. T^T. I just read and read D for 1 hour... OMG..
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 same T_T
•  » » » 4 weeks ago, # ^ |   0 It was also difficult to understand the problem...
 » 4 weeks ago, # |   +13 Any idea of what test case 4 for div2 E(div1 B) is?
 » 4 weeks ago, # |   0 What is was testcase 14 in problem D?
•  » » 4 weeks ago, # ^ |   0 It was (i assume, since this is how i fixed it) n=100000 k=100000 so that n*k overflows if you use int for intermediate results.
 » 4 weeks ago, # |   +5 Is it only me who didn't get that we can go to different vertices by different colors in E? I am too stupid to look into samples, so it took me 5 minutes and a question to find it out. (I thought that there has to be a color and a vertice such that...)
•  » » 4 weeks ago, # ^ |   0 It definitely wasn't clear to me as well and lost some time because of this.
 » 4 weeks ago, # |   +1 How to solve Div2 C?
•  » » 4 weeks ago, # ^ |   0 take every node that have zero respect child and insert it in array and then sort array and print , get pass in test case wish will not failed on main test
•  » » » 4 weeks ago, # ^ |   0 Can you please prove if this would give the correct result?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If we have a node that doesn't respect parent and have zero respect child,it should be removed, in case of tie, remove the one with smaller number. That gives indication that they should be deleted in sorted order, we now need to prove 2 things1) If we deleted a node, is there another node in the sorted list won't be delete-able?2) If we deleted a node, is there another node will be added to the list?let's prove the first, the only case that a node won't be delete-able, if a respecting node will be attached to it, that won't happen, because a respecting node will go up iff its parent got deleted, and its parent can't be deleted because it has respectful child (contradiction).let's prove the second, to make a node delete-able, you have to make all it's children disrespectful, and you can't delete a respectful node to create space for disrespectful child.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 There is a simpler solution. For every vertex u from 1 to N if u has 0 respect to its ancestors mark u and its parent. Then just iterate for all vertices from 1 to N and add vertex to your answer array if it's marked.
 » 4 weeks ago, # |   +19 I lost interest while reading DIV2D. Can someone say the technique to patiently read such problems?
•  » » 4 weeks ago, # ^ |   +22 What's the problem with this statement? It is relatively short.
•  » » » 4 weeks ago, # ^ |   +2 Maybe too many variables to remember
•  » » » » 4 weeks ago, # ^ |   +8 I think "solve more problems" is the right approach here I think, once again. The more you struggle through such statements, the more accustomed your brain becomes to processing such information.Also taking notes or writing a short summary of the statement by yourself has helped me in the past. It also helps you to get closer to solving the problem because it makes you rephrase the question, which may in turn make it simpler in the end.
•  » » » » » 4 weeks ago, # ^ |   -6 How do you come up with making summary/notes of the problem statement, can you please post an example for div2.D. I end up writing the whole sentences xd.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I did not really feel the need to make a summary here.Just to satisfy your curiosity. Please do not take this as an example on "how to take notes". Also, this was a relatively simple problem, too. In general, there's no recipe of what you need to write during problem-solving. You should write down what you feel you need to write down.
 » 4 weeks ago, # |   +8 How to solve Div1.D? Thanks in advance.
•  » » 4 weeks ago, # ^ |   +5 Let $b$ be an integer between $0$ and $9$ inclusive. Then the position $\pmod{11}$ of $10a+b$ in the sequence is uniquely determined by $b$ and the position $\pmod{11}$ of $a$ in the sequence.
•  » » 4 weeks ago, # ^ |   +24 Consider an inadequate number x with $k+1$ digits, or in other words $x \in [10^k, 10^{k+1})$. It turns out that following information is sufficient to know whether $10x+l$ is inadequate:1) d1: Number of inadequte numbers $<10^k$ 2) d2: Number of inadequate numbers $<10^{k+1}$ 3) c: Index of x in a list of inadequate numbers mod 11Moreover this information is sufficient to recalculate this information as well for k:=k+1 and x:=10x+l in case 10x+l is inadequate.Everything heavily relies on fact that $11 | 0+1+...+10$.This is already sufficient to solve this problem in $O(n^2)$ since in constant time you can determine whether number after appending some digit is inadequate.Moreover it turns out that number of inadequte numbers < 10^k falls into a cycle 9, 10, 9, 10, ... and if you look at formula keeping information about c then knowing that (d1, d2) is either (9, 10) or (10, 9) you can deduce that it actually doesn't matter what out of these two pairs (d1, d2) is, new value of c just becomes (l+c(c-1)/2+10)%11. This means that if you fixed some beginning position in our string and processed some digits, we need to keep only one number (between 0 and 10) to determine whether after appending new digits our number stays inadequate. This allows you to write O(n*11) dp.
•  » » » 3 weeks ago, # ^ |   0 I think these kinds of problems are pretty "cancer".
 » 4 weeks ago, # |   +30 Duh, not a fan of D, it was kinda hard to digest what am I asked about and the problem itself is not very interesting as well. At least the resulting code was very clean.
 » 4 weeks ago, # |   0 Can anybody look at my problem C code and tell me where am I going wrong https://codeforces.com/contest/1143/submission/52037703
•  » » 4 weeks ago, # ^ |   0 You don't have to remove the root. Since it doesn't have a parent it cannot disrespect its ancestors.
 » 4 weeks ago, # |   +60 C looked so much like problems where magically you must calculate the convex hull. I gave up after 5 minutes of that approach. Turns out the solution is the convex hull...
•  » » 4 weeks ago, # ^ |   +60 But this time you are looking at the solution from the beginning, you just need to see it. Rewrite $y=x^{2}+bx+c$ as $y-x^{2}=bx+c$ and you are done.Funny problem, thanks to authors. Actually, I liked all of todays problems, more or less.
 » 4 weeks ago, # |   0 FALLLLINNG DOWN!!!!
 » 4 weeks ago, # |   +1 Does anybody have an idea for n =10^5 nodes recursion is giving runtime error in python even after using setrecursionlimit()My submission
•  » » 4 weeks ago, # ^ |   0 Even if you write 10**6 as a recursion limit,Python won’t increase it more,than 10000-20000(I don’remember the exact num)
•  » » » 4 weeks ago, # ^ |   0 previously I used so many times dfs for 10^5 nides in python
 » 4 weeks ago, # |   0 Waiting for rating!~
 » 4 weeks ago, # | ← Rev. 2 →   +6 RIP to those submissions which initialized minimum as 1e9 in DIV2 D. TC #33 .
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1143/submission/52055235 I'm getting WA in pretest 8. Why is it not 888999999? please help!
•  » » 4 weeks ago, # ^ |   0 because it can be 799999999, which gives a larger product.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Can you please explain your approach to problem b?
•  » » 4 weeks ago, # ^ |   0 maybe 799999999?
•  » » 4 weeks ago, # ^ |   0 Because it's 799999999
 » 4 weeks ago, # | ← Rev. 2 →   -14 I will never forget this contest because of the problem D! It's a sad story about inf!!!!!!
 » 4 weeks ago, # |   +159 Quick instruction for those wondering: Don't give a fuck about any kind of training, virtual participation or upsolving whatsoever Participate in every CF round you may for 7 years (219 so far) ?????? Wait for another color revolution or black day for CF database to wipe out every trace of you ever being red
•  » » 4 weeks ago, # ^ |   +14 Congratulations on making it to the Red level! I've noticed you've been an active member since quite a time. You deserved it.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +48 You were pretty adamant in doing contests.
 » 4 weeks ago, # |   +12 Am I the only one who read "subsequence" as "substring" in Div1B(Div2E)?It was so sad to find out such mistake after struggling with my Hash code, which is able to solve "substring" one. QAQ
•  » » 4 weeks ago, # ^ |   0 You're not :-)
 » 4 weeks ago, # |   0 Can someone confirm that Div2C test 10 is 100000 nodes with i being the only child of i+1 (and node 100000 is the root)?
 » 4 weeks ago, # |   +17 Thank you grphil and others for setting nice problems.This contest was quite enjoyable for me ! At last I have succeeded to cross the 1600 rating barrier !
 » 4 weeks ago, # |   -12 2nd question of div2 was easily googlable!!
 » 4 weeks ago, # | ← Rev. 3 →   0 How to solve div2 B? thanks in advance.
•  » » 4 weeks ago, # ^ |   0 Precalc or dp. Precalc: link
•  » » 4 weeks ago, # ^ |   0 Lemma.If m is optimal for n, then there exists such position p that: in positions 0..p-1 digits of n and m are equal,in position p digit of m is less by one,in next positions m has digit '9'.52044460
 » 4 weeks ago, # |   0 that moment when I noticed I switch the positive and negative sign for Div 1 A and debugged for 2 hrs... and stupid mistake for Q2. I can kill myself
 » 4 weeks ago, # |   +59 please upload the editorial of this contest...
 » 4 weeks ago, # | ← Rev. 63 →   +10 Can anyone explain why my submission for Div2E/Div1B is getting TLE?$\text{next}[i]$ is the closest right index where next permutation number occurring, $\text{next}_{n-1\text{ th}}[i]$ is equivalent to $\text{next}[\text{next}[... (n-1 \text{ times nested}) ..\text{next}[i]]]]..]]$. I used read-only segment tree to determine if the given query is possible or not.I think time complexity of calculating $\text{next}$ (in main) is $O((n+m)\text{ log}(n+m))$, $\text{next}_{n-1\text{ th}}$ (in construct_nextn) is $O(n+m)$, and the time complexity of each query is $O( \text{log}(m))$.But I can see it barely passes some large test cases, while other users pass in less than quarter of my submission's used time..Can anyone explain? Thank you.
•  » » 4 weeks ago, # ^ |   +15 Your code uses quadratic time in a case like this: n 2n 1 1 2 3 ... n 1 1 1 ... 1 1 2 3 ... n 1 2n Where the sequence first has n copies of 1, and then the integers from 1 to n.The queries can be whatever. What happens is that while construct_nextn(i) is not called for i that are already checked, none of the n ones ever get marked as checked before being handled. So for each of the ones, your code goes through the entire n-length loop in construct_nextn(i). Therefore the code does O(n^2) work in this instance.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 Thanks for detailed explanation. I got accepted using different approach for $\text{next}_{n-1\text{th}}$.
 » 4 weeks ago, # | ← Rev. 2 →   0 What's the approach for Div2D(Div1A) please ?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Let's denote $S$ as starting point, $L$ as moving length, $R_{i}$ as $i+1$ th restaurant met. $R_{0}$ is the closest restaurant to point $S$, and $R_{i}$ is the closest restaurant to point $S+L$. You can check 4 scenarios for $i$ in $[0, n]$.Scenario 1: $S \rightarrow R_{0} \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow R_{i} \rightarrow S+L$ : $a + b + i*k = l$Scenario 2: $R_{0} \rightarrow S \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow R_{i} \rightarrow S+L$ : $a + l = b + i*k$Scenario 3: $S \rightarrow R_{0} \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow S+L \rightarrow R_{i}$ : $l + b = a + i*k$Scenario 4: $R_{0} \rightarrow S \rightarrow R_{1} \rightarrow ... \rightarrow R_{i-1} \rightarrow S+L \rightarrow R_{i}$ : $a + l + b = i*k$In each scenario, calculate $l$. Then the number of stops for that case is $\text{gcd}(l, nk)$. Of course you should not calculate when $l \le 0$.
 » 4 weeks ago, # |   0 seems like problemsetters are jojo fans)
 » 4 weeks ago, # |   0 Can someone help me understand why solution for Div2 C was getting MLE on TC 10 (skewed tree)https://codeforces.com/contest/1143/submission/52052934
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Assume you didnt't call vector.clear() after moving children to the parent of current node, space complexity will be O(n^2) which will get MLE.In fact, vector.clear() makes its size = 0, it doesn't deallocate the memory reserved by it, so it's the same memory as if you didn't call clear :)
 » 4 weeks ago, # |   +2 When the solutions will be availible?
 » 4 weeks ago, # | ← Rev. 2 →   +9 When will the tutorial be published?
 » 4 weeks ago, # |   0 DIV1-A / DIV2-D. I know ans is $n * k / gcd(n * k, k * x + c)$, but cannot figure out why $x < n$. Anybody can help? Thanks in advance.
•  » » 4 weeks ago, # ^ |   0 At least in my solution (which es the same formula), x is the amount of restaurants you travel through.
•  » » 4 weeks ago, # ^ |   +1 That's because if $x$ is grater than $n$, then in each jump will be at least $x \cdot k > n \cdot k$, which means that it is more then circle length. And so the place where you will get after the jump is the same as if the jump was $k \cdot (x - n) + c$.
•  » » » 4 weeks ago, # ^ |   0 Wow, I got it, thx a lot.