grphil's blog

By grphil, 5 years ago, translation, In English

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

  1. Um_nik

  2. LaiMeiyun

  3. Benq

  4. dotorya

  5. ilyakor

Div2

  1. Infleaking

  2. lamejeck

  3. ZeroTwo

  4. Amtek

  5. 2qbingxuan

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

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I hope the problem statements are short as the announcement

»
5 years ago, # |
  Vote: I like it -87 Vote: I do not like it

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.

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

Wishing everyone a great contest after almost a week!

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

Just wondering, how many weeks do you waited for proposal queue to organize this round in Codeforces?

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

    We waited around 6 weeks before our problems were first reviewed, but after that we haven't waited much for everything else

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

      Do they announced or told that you are going to wait even more after you waited for 2 weeks?

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

Screenshot-from-2019-03-29-17-33-07

»
5 years ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

This time is not friendly to Chinese people.>_<

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

    The last div1 round was at a time that was much friendlier to Chinese, but not to me. Fair turnaround, I guess.

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

    What are you talking about, you can see problem statements 12 hours ahead of us.

»
5 years ago, # |
  Vote: I like it -33 Vote: I do not like it

can you make it at 20:20 every contest i can't participate because the bad time

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

10:00 on a Saturday morning! California thanks the round setters!

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

Div2 round is rated for non-rated user? (for me)

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

    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.

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

Sounds good...hope the problem statement will be also great like this announcement.

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

Yeay! My first Div 1!

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

Round delayed by 5 min ":(

»
5 years ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I'm not an ICPC finalist, but I will happily receive a hat if you want xD

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

I gave up the div1 contest because the description of problem A was too difficult to understand, and even did not give the picture.

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

I get the error ~~~~~ You have submitted exactly the same code before ~~~~~ even though i haven't submitted anything yet. Anyone knows why?

»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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...

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

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.

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

Cheating notice: rusau and King_01 submissions on problem B are same

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

I was stuck on pretest 4 of div. 1 B. any help?

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

    My code that failed pretest 4 broke with this:

    3 4 1

    1 2 3

    1 2 2 3

    1 4

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

      Hmm, that didn't break mine. Guess I'll just wait for sys tests to finish.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Sorry, my bad. I offered the problem, and it coincides.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -86 Vote: I do not like it

      I think the contest should get unrated

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      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.

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

      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.

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

        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".

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

Div2 B is just B. Does anybody know a solution without dp?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -14 Vote: I do not like it

    .

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

    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)*9

    like if n=1099 they are 1099,1089,099 or if n=100000 they are 100000,99999

    i didn't know how to explain better https://codeforces.com/contest/1143/submission/52059415

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

      I named this solution as the solution with dp))

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

    Just precalc)

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

      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?

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

        Yes. Precalc took 2 minutes.

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

    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

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

Any idea how to solve div.2 E,F ?

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

    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)

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

What was the intended solution for Div2E/Div1B? My solution seemed ridiculously complicated, and I imagine there was a simpler way to solve it.

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

    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.

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

      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?

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

        Yeah, binary lifting is probably what it's called.

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

    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.

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

    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.

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

      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

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

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/gcd

UPD: And now it turns out I actually could have hacked people, just not on this...

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

    Why is NK / gcd wrong?

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

      It's right, that's the problem. I couldn't hack anyone because of that.

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

      NK/gcd is right, but what he wrote can overflow

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

How can I solve problem D?.. T^T. I just read and read D for 1 hour... OMG..

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

Any idea of what test case 4 for div2 E(div1 B) is?

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

What is was testcase 14 in problem D?

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

    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.

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

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...)

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

    It definitely wasn't clear to me as well and lost some time because of this.

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

How to solve Div2 C?

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

    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

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

      Can you please prove if this would give the correct result?

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

        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 things

        1) 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.

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

      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.

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

I lost interest while reading DIV2D. Can someone say the technique to patiently read such problems?

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

    What's the problem with this statement? It is relatively short.

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

      Maybe too many variables to remember

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

        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.

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

          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.

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

            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.

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

How to solve Div1.D? Thanks in advance.

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

    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.

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

    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 11

    Moreover 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.

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

      I think these kinds of problems are pretty "cancer".

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

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.

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

Can anybody look at my problem C code and tell me where am I going wrong
https://codeforces.com/contest/1143/submission/52037703

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

    You don't have to remove the root. Since it doesn't have a parent it cannot disrespect its ancestors.

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

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...

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

    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.

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

FALLLLINNG DOWN!!!!

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

Does anybody have an idea for n =10^5 nodes recursion is giving runtime error in python even after using setrecursionlimit()

My submission

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

    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)

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

Waiting for rating!~

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

RIP to those submissions which initialized minimum as 1e9 in DIV2 D. TC #33 .

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

https://codeforces.com/contest/1143/submission/52055235 I'm getting WA in pretest 8. Why is it not 888999999? please help!

»
5 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

I will never forget this contest because of the problem D! It's a sad story about inf!!!!!!

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

Quick instruction for those wondering:

  1. Don't give a fuck about any kind of training, virtual participation or upsolving whatsoever
  2. Participate in every CF round you may for 7 years (219 so far)
  3. ??????
  4. Wait for another color revolution or black day for CF database to wipe out every trace of you ever being red

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

    Congratulations on making it to the Red level! I've noticed you've been an active member since quite a time. You deserved it.

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

    You were pretty adamant in doing contests.

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

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

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

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)?

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

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 !

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

How to solve div2 B? thanks in advance.

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

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

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

please upload the editorial of this contest...

»
5 years ago, # |
Rev. 63   Vote: I like it +10 Vote: I do not like it

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.

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

    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.

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

      Thanks for detailed explanation. I got accepted using different approach for $$$\text{next}_{n-1\text{th}}$$$.

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

What's the approach for Div2D(Div1A) please ?

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

    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$$$.

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

seems like problemsetters are jojo fans)

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

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

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

    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 :)

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

When the solutions will be availible?

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

When will the tutorial be published?

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

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.

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

    At least in my solution (which es the same formula), x is the amount of restaurants you travel through.

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

    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$$$.