Ormlis's blog

Codeforces Round #879 Editorial
By Ormlis, history, 3 years 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

Comments Comments (36)
| Write comment?
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it -25 Vote: I do not like it

[Deleted]

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -26 Vote: I do not like it

Fast editorial!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Great contest. Good problems!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 

E is amazing.
→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +48 Vote: I do not like it

I made Video Solutions for A-E.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope source code.

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        hope this helps comment-1047413

        → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can problem B be solved using digit dp?

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

anyone managed to solve E with sparse table?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
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
»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi! Could you please tell me why my submission 355175302 for Problem A doesnt work?

→ Reply