Ormlis's blog

Codeforces Round #879 Editorial
By Ormlis, history, 10 months ago, translation, In English

Thank you for participating!

1834A - Unit Array was authored and prepared by Artyom123

1834B - Maximum Strength was authored by jury of the olympiad, and prepared by TheEvilBird

1834C - Game with Reversing was authored and prepared by sevlll777

1834D - Survey in Class was authored by vaaven and Mikhango and prepared by Alexdat2000

1834E - MEX of LCM was authored by TeaTime and prepared by teraqqq

1834F - Typewriter was authored and prepared by Ziware

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +186
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 3   Vote: I like it -25 Vote: I do not like it

[Deleted]

→ Reply
»
10 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Fast editorial!

→ Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Great contest. Good problems!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it 

E is amazing.
→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Fast editorial!

It's a pity that I didn't manage to solve D, by the way.

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

[user:Ormilis] Please add a case with 1e5 elements 2,3,2,3,2,3,...... in problem E. Many solutions are accepted which will run in O(n^2) for this test case since lcm will never exceed its limit and no multiple of lcm is present in this case.

→ Reply
»
10 months ago, # |
  Vote: I like it +48 Vote: I do not like it

I made Video Solutions for A-E.

→ Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This seems to be unintended $$$O(n \log n \log^2 {10}^7)$$$: 210082970

I'm actually surprised there were no strong tests like $$$a_i = 2^{\frac{i}{\tt{const}}}$$$.

→ Reply
»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

For the C solution

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can not understand why the answer of question E is no more than 1e9, any strict proofs?

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    In order to have $$$lcm$$$ be equal to a prime number we must have it in the array. So we only have $$$n$$$ places for prime numbers, that means we cannot ever get $$$n+1$$$ th prime number which is $$$4256249$$$. So we can bound it at that number also.

    Because of the prime fact you can also say that $$$1e9+7$$$ will never be included, because $$$a_i\le1e9$$$ and $$$1e9+7$$$ is prime so you cannot put it into the array.

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can prove it to be 2N+1 at most https://codeforces.com/blog/entry/117339?#comment-1038154

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope source code.

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong in this solution for problem D? 210103552

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your approach it is not necessary that p1 is the interval with minimum right, for example intervals are- (1,10) (1,8) (2,3) here minimum right is (2,3) interval

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell how to efficiently find the segment which has the shortest length and lies completely inside a given segment in problem D.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just find the overall shortest segment and assume it lies inside the segment you are checking -> If not, you will check the outer segments anyway, so it won't change the answer.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I can do it by segment tree?? but is there any other method ??

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        To find the overall shortest segment? It should be just a simple iteration through all segments. Something like the following:

        Code
        → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hope this helps comment-1047413

        → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I have figured it out why simply check the overall shortest segment works:

    Let's pick up a segment A, and find another segment B which shares the shortest common subsegment with A.

    If the shortest segment lies out A, it will share 0 element with A, we can simply choose it, because this will be the optimal choice. When the shortest intersect the beginning or the ending, we can tell that any segment completely lies in A will not product a better answer, because any other segment inside A shares no less than the length of the shortest.

    If the shortest lies completely in A, you should check if there are other better choices by check the segment have the largest ending and the one with smallest beginning.

    So there is need to find such a segment you are looking for.

    → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am a newbie. I just participated and solved problem A and it got an accepted verdict. After solving problem A, I left the contest. I just noticed that I have got a -18 score. Are there cases where even if you solved the problem but you got a negative score? Is it just because I solved it late or because I solved only one problem? How are generally contests assess the solved problems? Thanks for the clarification in advance.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You get score based on your ranking in the contest and your rating. Basically if you perform better than would be expected of someone with your rating, your rating will increase and if you perform worse, your rating will drop

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So scoring does not solely depend on how many problems you solved or when you solved them, right?

      So let's say someone with a rating of 3200 solves problems A and B correctly in division 2 in the early minutes of the contests. Despite that, He/She will get less score or even a negative score. Did I understand it correctly? I appreciated your response.

      → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello everyone In problem 1834B - Maximum Strength i am not able to understand the part where it is written like "Now we can represent the numbers L and R as their longest common prefix" can anybody help me ?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The editorial says that the numbers L (after padding with zeroes) and R can be represented in three parts. The first part is the longest common prefix, the second part is the index where L and R differ for the first time and the third part is the remaining string.

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    If you're given for example

    $$$ L = \color{red}{12345}\color{blue}{6}\color{green}{2718281}, $$$

    and

    $$$ R = \color{red}{12345}\color{blue}{8}\color{green}{0123456}, $$$

    we see that the red part (the longest common prefix) contributes $$$0$$$, the blue part (the first digit where $$$L$$$ and $$$R$$$ differ) contributes at most $$$8-6=2$$$, and for the green part (the rest), we can pick $$$9999999$$$ for $$$L$$$ and $$$0000000$$$ for $$$R$$$ (because whatever you set, the blue part ensures the first number is already smaller than the second). Thus the answer is always

    $$$ \text{difference of blue digit} + 9\times \text{length of green part}. $$$
    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the 4th tc of D wrong, as suppose I ask stud1 ques 2,3,4,5 so his hand is at -4 and I ask stud2 ques 1 so his hand is at -1 and the hand of stud3 is at 0 so the answer should be 4 right??

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're supposed to ask the same questions to all students, so if you ask questions 2,3,4,5.

    Student 1 gets a score -4

    Student 2,3 get a score of -2.

    Hence difference is 2 in this case.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good contest_

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can problem B be solved using digit dp?

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Amazing round! Enjoyed the problems a lot.

I think test cases maybe weak for problem $$$E$$$, I have two almost identical solutions where one is getting AC in ~0.7s and the other is getting AC in ~1.5s

My solution is the same as the editorial but I perform the actions in a slower (dumber) way. My algorithm is as follows:

  • Set $$$lim = 10^7$$$ as the upper bound and ignore all LCMs greater than this.
  • I make a segment tree on the array with LCM as combine operation.
  • Iterate over $$$r$$$ and find all the first $$$l$$$'s such that $$$LCM(A[l..r])$$$ is unique.
  • To do this we first set $$$l=r$$$ and find the minimum $$$l'$$$ value such that $$$LCM(A[l..r]) \neq LCM(A[l'..r])$$$ using the segment tree trick.
  • Set $$$l = l'$$$ and repeat above until we cannot find $$$l'$$$ for a particular $$$l$$$.
  • Add all these values to a set and find mex.

I think time complexity is $$$O(N \log N \log 10^7)$$$

The other nearly identical solution that is slow is, Instead of iterating over $$$r$$$, I iterate over $$$l$$$ and perform the equivalent actions.

without #define int long long
Soln1 submission: 210273930 AC with 0.7s
Soln2 submission: 210273834 AC with 1.5s

with #define int long long
Soln1 submission: 210271657 AC with 1.6s (hackable)
Soln2 submission: 210271736 TLE

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B

Let's say L = 68 and R = 72 according to the editorial ans = abs(6 -7) + 9 = 10 But is 10 possible?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Choose 69 and 70 from that range. First digits differ by 1, second digits by 9.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone managed to solve E with sparse table?

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Me 210335889 although it is possible this can be hacked.

    Edit: Shaved 600ms off that with 210346369, although again I wouldn't be surprised if this could also be hacked

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, would we also need to consider an extra O(log(M)) complexity for lcm operation?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C was a nice problem indeed, and its explanation in the editorial is great as well. good job Authors!!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My $$$O(nlog^2a_ilogn)$$$ for problem E passed. 232426932

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there was a typo in problem E's editorial: $$$n^2 \ge x^2 \ge 2^{k - 1}$$$ which is actually: $$$n^2 \ge x \ge 2^{k - 1}$$$.

→ Reply