grphil's blog

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

  5. 2qbingxuan

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

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

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

I hope the problem statements are short as the announcement

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

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

Wishing everyone a wonderful contest after almost a week!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Yeay! My first Div 1!

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

Round delayed by 5 min ":(

»
4 weeks ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it
  • »
    »
    4 weeks 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

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

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

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

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

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

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

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

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

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

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

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

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

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

      I think the contest should get unrated

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

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

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

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

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

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

    .

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

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

      I named this solution as the solution with dp))

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

    Just precalc)

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

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

        Yes. Precalc took 2 minutes.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

What is was testcase 14 in problem D?

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

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

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

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

How to solve Div2 C?

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

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

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

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

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

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

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

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

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

      Maybe too many variables to remember

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

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

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

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

How to solve Div1.D? Thanks in advance.

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

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

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

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

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

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

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

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

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

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

FALLLLINNG DOWN!!!!

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

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

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

Waiting for rating!~

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

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

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

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

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

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

    You were pretty adamant in doing contests.

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

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

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

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

2nd question of div2 was easily googlable!!

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

How to solve div2 B? thanks in advance.

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

    Precalc or dp. Precalc: link

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

    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, # |
  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

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

please upload the editorial of this contest...

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

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

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

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

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

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

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

seems like problemsetters are jojo fans)

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

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

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

When the solutions will be availible?

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

When will the tutorial be published?

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

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

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