Ormlis's blog

Codeforces Round #879 (Div. 2, based on All-Russian olympiad in the name of Keldysh) [Rated]
By Ormlis, history, 17 months ago, translation, In English

Hi!

This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students, Moscow Open Olympiad in Informatics (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829, 852, 857).

We are happy to announce Codeforces Round 879 (Div. 2) based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Jun/18/2023 11:05 (Moscow time). Please notice the unusual time. You will have 6 problems and 2 hours to solve them.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of All-Russian olympiad in the name of Keldysh (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Problems of this competition were prepared by grphil, Mangooste, sevlll777, Siberian, TeaTime, teraqqq, Ziware, TheEvilBird, Ormlis, Alexdat2000, vaaven, Mikhango, Artyom123 guided by Ormlis, grphil and Helen Andreeva.

Thanks to Artyom123 for the round coordination, and also thanks to MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Great thanks to the testers of the round: PurpleCrayon, He_Ren, feecIe6418, penguinhacker, ix35, Dominater069, MagicalFlower, tzc_wk, gyh20, ezraft, Kieray, AquaMoon, satori_____, njupt_lyy, Mike4235, ak2006, Lavine, Ritwin, xiaossr, turmax, fastmath, Kapt, Kirill22, Be_dos, Olerinskiy, gmusya, blyat, vsinitsynav, orz, TheGoodest, playerr17, lesssia.

UPD1: Scoring distribution:

500 – 1000 – 1250 – 1750 — 2500 – 3000

Good luck everybody!

UPD2: Editorial

UPD3: Winners!

Official:

  1. Final_Brave_Niuniu
  2. tzc___________________wk
  3. MoFalkmusic
  4. do_while_not_not_true
  5. Cherrt

Unofficial:

  1. hank55663
  2. stkwill
  3. jiangly
  4. Sugar_fan
  5. Brovko
  • Vote: I like it
  • +463
  • Vote: I do not like it

Comments Comments (145)
| Write comment?
»
17 months ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

Hoping this time, the contest to be balanced with better pretests, unlike the previous few editions :)

All the best everyone!

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

Sorry if this is a stupid question but what does it mean that the round is based on the russian olympiad? I read something like that on codeforces sometimes, also in other posts. Can somebody explain?

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

    It means that there is an on-site olympiad contest in Russia which has the same problems as this Codeforces round. The problems were originally prepared for the olympiad, and they just reuse the problems here on codeforces.

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

Good luck everyone! wish I turn purple!

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

When will scoring distribution come out?

edit: got it.

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

I hope the round will be better than the previous one and I will become a master!

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

Can you make the pretests stronger?

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

Will this be rated?

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

    Yes. But you could've just read the title.

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

Two contests in one day, cool!

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

I'm confused why comments like "Good luck" sometimes get downvotes but sometimes get upvotes

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

two rounds in one day??

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

confused..which one to attend , 879 or 880

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

is it ununsual to have 2 rounds happening so close to each other? never in the Codeforces have i ever seen this coming

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

    Because these to rounds are not "regular", they are based on two olympiads (Russian and Polish), which are at the same time. A funniest joke it that there is Atcoder Regular contest between two CF rounds:)

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

    it is unusual, but it has happened, in fact, round #829 and #830 had only a 15 minute break between them!

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

Super Sunday tomorrow! CF 879 > ARC 162 > CF 880

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

I have a question. How manage Codeforces rating changes if I participate in both rounds? My new rating will be calculated using my rating before compete in the first round or after my first contest rating changes? I ask that because I wanna do both contest :).

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

    Rating for first round will get updated before second one.

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

      not really , last time two back to back contests happens in one day , and both rating updates happens after end of both rounds accordingly

      → Reply
»
17 months ago, # |
  Vote: I like it +11 Vote: I do not like it
This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh

Who is Keldysh?

+

It's great to see AquaMoon as tester

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

    Thanks for your support! Tasks are nice and wish you good luck (〃'▽'〃)o

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

Be ready with Math Problems :)

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

Russian kids eat div.2 problems for lunch （￣︶￣）↗　

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

I hope there's no DDOS,I just have a bad ABC.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

I was wrong :3

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

Is this round rated?

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

Bob's goal is to maximize the duration of the game

Sure, Bob, whatcha gonna do about it?

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

Nice contest. First time to solve only A & D.

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

    how did you solved D.

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

      For every i-th segment I found the segment that difference with i-th segment maximum possible. Let x be the r_i — l_i + 1, y be number of common points. Difference will be 2 * (x — y)

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

        Yes I know this..but how to find that segment with the maximum difference or minimum overlap

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

          There are only three cases, Compare with 1) segment with largest l 2) smallest r 3) smallest size

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

            can you explain it's proof.

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

            for the 3rd one, you need it to be included in the ith segment. How to do that efficiently?

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

              Not really. If the smallest interval is not included, the height difference only gets better and you would have covered it in cases 1) or 2).

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

          For i-th segment if there is a segment that doesn't have common points you must choose it and difference is 2 * x. Otherwise you must check with segments which have minimum length, wich have minimum r[j] that l[i] <= r[j], which have maximum l[k] that l[k] <= r[i]. NOTE: I used set for finding r[j] & l[k]

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

      To get the max difference of heights, there should exist a pair of segments such that one gets +1 increments and other gets -1. Iterate on all increment segments and find the best decrement segment to maximize the ans, there will be 3 cases:
      1. consider the segment with rightmost start.
      2. consider the segment with leftmost end.
      3. consider the segment fully overlapping with least length.

      1 and 2 are easy to achieve by sorting, for 3rd case iterate on segments in increasing order of start points and maintain a multiset of segments sorted by lengths that have start points greater than or equal to current segment

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

        For 3rd case we can sort according to ending point and keep track for minimum length segment. You can Check my submission 210074389

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

I submitted my code for D 2 times out of FST paranoia and approximately lost 100 points on the second submission. Is this intended? I thought that only the first accepted counted for scoring.

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

    This is how it is intended to be, it's not a bug. In Div.1 or Div.2, if you submit multiple times with "pretests passed" to a single problem, only the last submission will count and all previous ones will be regarded the same as previous incorrect submissions.

    In other words, you get -50 for each previous submission, and you get time penalty according to the last "pretests passed" submission. I actually don't know if submitting a "wrong answer" submission after "pretests passed" gives any penalty, though.

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

Problem E is so nice. The answer cannot exceed $$$max(a_{i})+n^2$$$, so $$$ans \leq 10^{10}$$$. Now imagine function $$$nxt(i, x)$$$ which tells you the smallest index $$$j>i$$$ such that $$$a[j] \nmid x$$$. Then, to find MEX, we can just use the $$$nxt(i, x)$$$ atmost $$$log_2(max(a_{i})+n^2)$$$ starting from each $$$i$$$!

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

    Was being braindead sorry.

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

    There are $$$O(n)$$$ prime numbers in range $$$[1,n \cdot logn]$$$. So you can consider your upper bound of answer to be around $$$n \cdot logn$$$.

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

    We can show that the answer doesn't exceed $$$10^7$$$.

    Consider the subarrays $$$[i;i], [i;i+1], \dots, [i;n]$$$ (i.e. subarrays with a fixed left point) and their LCM's. If we go through these in order from left to right, the next segment's LCM must be a multiple of the previous one. This means that if the value changes, it must at least double. This means that within these segments starting at $$$i$$$, there can only be $$$\left\lceil\log_2 10^7\right\rceil = 24$$$ different values $$$\le 10^7$$$. This means that within all subarrays over all leftpoints $$$i$$$, there can be at most $$$n \cdot \left\lceil\log_2 10^7\right\rceil = 3 \cdot 10^5 \cdot 24 = 7.2 \cdot 10^6$$$ distinct values $$$\le 10^7$$$. Since this number is less than $$$10^7$$$, some values $$$\le 10^7$$$ must be missing, and the answer is thus $$$\le 10^7$$$.

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

Can someone explain problems D and E to me? I solved problem ABC quickly, but I couldn't solve any of the others.

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

    D: Just take every pair. now you will to call all from x[i] to y[i]. then if you find a r> y[i] || l<x[i] then current contribution is (y[i]-x[i]+1)*2. If not then check with the minimum length segment.. the last check is check is intersected pair with ith pair.. find the max l[i] as l[i]<=r also find lowest r[i] as if r[i]>=x[i].

    link

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

    I might have overcomplicated myself but notice that there are only three possible candidates for the range $$$[l_i, r_i]$$$:

    1. The range $$$[l_j, r_j]$$$ with the minimum $$$r_j$$$.

    2. The range $$$[l_j, r_j]$$$ with the maximum $$$l_j$$$.

    3. The range $$$[l_j, r_j]$$$ with the minimum length such that $$$l_i <= l_j, r_j <= r_i$$$.

    Case 3 can easily be checked with a dynamic segment tree.

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

      Actually, for the third case, a segment tree is not needed. Consider the minimum overlap for Cases 1 and 2 as X;

      Then iterate through an array sorted based on the lengths of the segments until the current subsegment length exceeds X.

      My submission.

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

Any hints for solving problem C ?

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

    Think of parity of the operations bob can make

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

    Calculate the cost of making S == T and S == Rev(T)

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

      min of them is answer ?

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

        Yes, since Alice wants to minimize the duration of the game.

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

          i missed the exception when alice does not need to make any meaningful move and just wait for string to get reversed .

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

            Oh yeah, that's an annoying edge case

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

              ikr , thanks though . tryna upsolve d before next round

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

              Luckily the edge case was present in the sample test case. It was a good edge case.

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

        You should also consider Bob's movements. If you make 17 Alice movements, to make S == T then after 17 movements Bob reversed T and S and you should add 1 more Bob's (for example)

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

    main hints is if bob reverse the S or T affect are same.

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

Could you please put a link to the contest in the announcement?

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

Anyone else so dumb that they confused statement of B like this:

Find a number X in [L, R] such that the strength of X and R is maximum. I wasted an hour just to realize the correct statement, and then it was just a matter of a couple of minutes.

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

    How did you solve B? I'm gonna lose 150 rank in this contest because of that stupid problem aaaaaaaaaaaaaaaaaaaaaaaaaaaaaah

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

      It's simple once you read it correctly. First, make them equal by padding 0s. Then, find the first index from the left where digits differ. Let's say x in L and y in R.

      Now, we can construct two numbers like,

      .......y00....00
      .......x99....99

      It can be proved this is optimal.

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

Amazing Contest! Can anyone tell the difficulty rating of A,B,C please? Also how to solve D?

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

    The difficulties probably are 800,1000,1200

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

    For D, my main observation is that we can always get the answer by choosing two segments and calling all the numbers in the larger one. This will give us a maximum difference of $$$2$$$ times the length of the larger segment minus $$$2$$$ times the intersection length. Now if we can come up with a way to choose the best segment to pair a given segment with, we can iterate over all segments and take the maximum answer we get.

    what I did was to keep track of the shortest leftmost segment, shortest rightmost segment, and the shortest segment overall. Let those be $$$[l_l, r_l], [l_r, r_r]$$$ and $$$[l_s, r_s]$$$ respectively. Now for each other segment, if $$$l_i > r_l$$$ or $$$r_i < l_r$$$, we choose this segment and that boundary segment which doesn't intersect it. If the current segment intersects both boundary segments, we have 3 choices:

    • We consider the current segment and the left boundary

    • We consider the current segment and the right boundary

    • We consider the current segment and the shortest segment overall

    We can simply check what we get for all these choices and update the answer as we go. Finally, we have to check what answer we can get if we choose the right and left boundary segments themselves.

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

      What does the 'shortest leftmost segment' mean? on what basis did you sort them?

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

        I primarily sorted to minimize the $$$r_i$$$ (thus 'leftmost') and secondarily to maximize $$$l_i$$$(giving the 'shortest' part).

        Similarly for the rightmost shortest segment I primarily sorted to maximize $$$l_i$$$ and secondarily to minimize $$$r_i$$$.

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

      Do you sort the $$$[l_i, r_i]$$$ first on the basis of length and then run this algo? I mean how are you handling the case when the current segment is contained in any of the segments which have been already processed? I'm talking about the case when any of the processed segment could contain whole of the current segment.

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

        No, I process the ranges in the same order given. However I find the overall shortest, leftmost and rightmost ranges before processing. I don't understand what you mean by the processed segment containing the whole of the current segment.

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

    For problem D, a naive solution is to iterate over all pairs of students, then try to raise the first one's hand as high as possible and the second's hand as low as possible. Using greedy algorithm can easily determine the best strategy to ask the topics and update the answer. The time complexity is $$$O(n^2)$$$.

    A key observation is: let i, j, k be the students with the smallest r, the one with the biggest l and the one with the smallest r-l, respectively. We can make the second student be either i, j or k, which can be proved right with simple caseworks.

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

    video editorial for D survey in class

    @Astroflexx

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

problem D is nice!

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

I think tests were very weak

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

problem B

accepted code give output 29 for this input.( 88 2588) but i guess this should be 28. please make me understand.

upd: ok understood

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

    0999 2000 gives 29 (:

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

    whenever you encounter a digit in string b that is bigger than a, you don't have to check the rest as you can force them to be 0 and 9 , so the ans here is 2+9*3 which is 29

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

    0999 2000 it will give 29

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

I threw hard this contest and didn't solve C in contest. I solved it after tho with a somewhat unique idea. I simulated the optimal strategy for Bob to make the game last as long as possible. In order to keep it relatively fast, I also kept a reverse of the string so that I wouldn't have to keep reversing it after Bob's move. 210083837

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

Solved ABC in 30 minutes and then struggled with D. Interesting task, I was quickly able to reduce the problem to finding two segments with the largest exclusive area and was trying to transform it in a useful way but failed. Waiting for the editorial

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

Question about problem B: seems like for a following test

1
11 11299

according to the correct solution the answer is 37, but isn't it only 36, because in the best case we can get these two numbers: 99 and 9900 (I dont see how it is possible to get a sum any higher than this).

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

cool contest, problems D and E require at most 30 lines of code if you got the right idea

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

Any kind of proof for the upper bound of LCM in E?

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

    I commented this already elsewhere, just copied from there:

    We can show that the answer doesn't exceed $$$10^7$$$.

    Consider the subarrays $$$[i;i], [i;i+1], \dots, [i;n]$$$ (i.e. subarrays with a fixed left point) and their LCM's. If we go through these in order from left to right, the next segment's LCM must be a multiple of the previous one. This means that if the value changes, it must at least double. This means that within these segments starting at $$$i$$$, there can only be $$$\left\lceil\log_2 10^7\right\rceil = 24$$$ different values $$$\le 10^7$$$. This means that within all subarrays over all leftpoints $$$i$$$, there can be at most $$$n \cdot \left\lceil\log_2 10^7\right\rceil = 3 \cdot 10^5 \cdot 24 = 7.2 \cdot 10^6$$$ distinct values $$$\le 10^7$$$. Since this number is less than $$$10^7$$$, some values $$$\le 10^7$$$ must be missing, and the answer is thus $$$\le 10^7$$$.

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

      I was kind of looking for a tighter limit $$$10^6$$$ works for me and I don't think the answer would exceed that number.

      Also, I think the actual limit is smaller think about it this way you need a position for each power of a prime plus you need to kind of have some weird configuration of the array to get all values.

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

    For each i there's at most one value of lcm in a range [L, i] for each [2^j, 2^(j+1)). Let's take x being the minimum integer such that 2^x > N. Then in the range [2^x, 2^(x+1)) there's at most N values that appear as lcm of subranges, but since the range has size greater than N there must be a missing value. This proves a bound of 3 * N + 1.

    Edit: even stronger is realizing that we can generalize the observation from [2^j, 2^(j+1)) to [X, 2X). Then, for the range [N+1, 2(N+1)) there are at most N values that appear, so there's one missing and it can be at most 2N+1.

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

      Oh, this is really nice, thanks.

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

      Can you please label what does i, j, L indicate in accordance to the array?

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

        Fixing a position i in the array, considering every value of lcms of values in ranges [L, i] of the array that end at position i, there's at most one unique value of lcm that has value in range [X, 2X) for any positive X.

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

    It's obvious that the answer doesn't exceed $$$10^9 + 7$$$, as this number never occurs. So, we don't care about LCMs greater than this number.

    Let's choose three indices

    $$$1 \leq l \leq a < b \leq n$$$

    if $$$LCM(l, a) \neq LCM(l, b)$$$ then $$$LCM(l, a) \cdot 2 \leq LCM(l, b)$$$

    So, for a fixed leftpoint, the number of different LCMs doesn't exceed $$$\log(1e9 + 7)$$$

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

    We can say that 5e6 is an upper bound since there are at least 3e5 prime numbers less than 5e6

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

Such a fast rating update.

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

    probably because there's another contest today

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

what is the idea of B ?

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

    Brute force on prefix where you place all 9s in a number and 0s in another number

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

Could you explain me idea of problem D?

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

problem E has really weak system tests.
Just hacked an accepted solution with this test:
1
100000
6 8 6 8 ... 6 8
https://mirror.codeforces.com/contest/1834/submission/210074338

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

A: The number of occurences of -1 should be even and not greater than n/2.

B: From the first different digit of L and R from the highest digit. Let L=a1*10^m+a2 and R=b1*10^m+b2 where a2,b2<10^m, we can let 0-th to (m-1)-th digits of L become 9, and corresponding digits of R become 0. Then the answer will be at least abs(a1-b1)+9*m. We can see this is also the upperbound of the answer.

C: We can see that for Bob, reversing S and reversing T are equivalent, so Alice only need to make S==T or S==reverse(T). If Alice make k changes to transform S into T, the game will end at (2*k-1+(k+1)%2)-th turn, and if Alice make k changes to transform S into reverse(T), the game will end at (2*k-(k+1)%2)-th turn — but there's a special case: if k==0 the game will end at 2nd turn.

D: Define f(i,j) be the size of [l[i], r[i]][l[j], r[j]] (which denotes the set of numbers contained in [l[i], r[i]] but not in [l[j], r[j]]), then for any two students i, j, the difference of there height will be not greater than 2*max(f(i, j), f(j, i)). Therefore, we need to calculate max(f(i, j)) over all pairs of (i, j). We need to consider 2 cases: range i is contained inside range j, and otherwise. For the first case, we need to sort all ranges by their left-end, and for 1<=i<=n checking max(r[j]-l[j]) where l[j]<=l[i], and calculate (r[j]-l[j])-(r[i]-l[i]). For the second case, we need to check min(r[j]) where r[j]<=r[i], and calculate r[i]-max(l[i]-1, r[j]).

E: Note if p is a prime number or 1, and p is in the set of lcm, p must occur in a[i], so the answer will be at most p[n] (the n-th prime number). And for each i, the number of different values of lcm(a[j], a[j+1], ..., a[i]) below p[n] is at most log(p[n]), so we can check these values by maintaining the set L[i]={lcm(a[j], a[j+1], ..., a[i]) : 1<=j<i} in O(p[n]+n*(log(p[n]))^2) for checking n*log(p[n]) values and calculating lcm in O(log(p[n])).

F: The answer of a single query is the number of indexes i such that p[i]<i. Since there are at most 2*n different status of the array (n shifts of a[i] and n shifts of reverse(a[i])), we can pre-calculate all of them using fenwick tree.

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

A: Many straightforward approaches. What I did was count the number of +1s and the number of -1s. Make the number of -1s even (making a change if needed). After that, you can only change two -1s at a time to preserve parity, resulting in a +4 difference, so the final answer is $$$2 \left\lceil \frac{\max (0, minus - plus)}{4}\right\rceil + (minus \% 2)$$$

B: Find the first digit position in which $$$L$$$ and $$$R$$$ differ. Change all digits after this point to 9 for $$$L$$$ and 0 for $$$R$$$, resulting in a total strength of (difference at first change) + 9 * (number of digits after the first change)

C: It makes no difference whether Bob reverses $$$S$$$ or $$$T$$$, so Alice simply needs to make sure either $$$S == T$$$ or $$$S == rev (T)$$$. Count how many operations Alice needs for each of them, and pick the smaller, then count how many total operations are needed (including whether it ends on Alice's turn or Bob's "turn"). The problemsetter was very kind to place the edge-cases of $$$S == T$$$ and $$$S == rev (T)$$$ in the sample input (I legit missed both of them when I first thought I completed my code).

D: We only care about the highest hand and the lowest hand, so we basically need to find the maximum pairwise set difference between all intervals. My observation was the student with the lowest hand would have to be either: (a) the student whose interval ends the earliest, and if there are any ties, then this student has the shortest interval among them, (b) starts the latest, with shorter interval breaking ties, (c) shortest interval, with early end breaking ties, (d) shortest interval, with latest start breaking ties.

Proof Sketch: consider all cases how lowest hand interacts with highest hand: either they overlap on the left, or they overlap on the right, or the former is a subset of the latter, and in all three cases, we can see that violating all four conditions guarantees the existence of another student that would achieve a lower or equal hand (for the same choice of highest hand).

Once I found these four students, I checked all $$$n$$$ students as candidates for highest hand against each of these four students, and picked the one with the largest set difference. I'm not even sure if it's necessary to check all four, but I couldn't complete the proof for fewer than 4 low-hand candidates, so I stuck with the safe choice of checking all four.

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

Please any hint for problem D

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

During the contest, I misread the statement of problem C and thought that In turn, Alice chooses an integer i between 1 to n one of the strings S or T and any lower-case Latin letter c and replaces all occurrences of the i -th symbol in the chosen string with the character c. If so, how can this problem be solved? I've tried a lot but haven't found the answer, I'm stuck and can't generate a solution, so any help would be greatly appreciated!

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

    You could make a graph on letters where an edge between x and y means that all occurences letters x and y must become the same letter.

    This means that for each string, the answer would be (total number of characters — number of connected components). There also might be an edge case where there are no characters that are in both strings from current component so you would have to add 1 for each of these.

    Rest is the same as C, solve for odd/even separately

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

I became Master in this round!

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

https://www.youtube.com/watch?v=qq1D83Mj4TY My solution for D

I fixed the 'ith' student to be one of the maximum/minima. and then checked for 4 cases

  1. the other student is disjoint with the ith student. In that case, the answer is the max(2*size(i),2*size(k)) for all 'k' segments disjoint with i. (which can be found using binary search and maintaining suffix maximum)

  2. the other student partially overlaps, in this case, we will take the student with the farthest start point out of all the overlapping segments ( we assume that the other student is the minima)

  3. the other student partially overlaps, and is the maximum, in this case, we take the student with the farthest endpoint.

  4. the other student is fully overlapped by the ith range, for that we will take (size(i) — minimum size of any segment which is partially/fully overlapping with the ith segment)

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

What is the meaning of statement "Your solution ... have been uphacked". Is it means that my solution was hacked?

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

    It means that someone hacked your solution after contest. But notice that this a div.2 contest, which does not have an open hacking phase after the contest (you can only hack during the contest in your room for score). Since the hacking was done after the contest, you don't lose score. But this shows that systests were not strong enough to catch all wrong solutions.

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

@Ormlis, I got this mail today morning. Your solution 210063237 for the problem 1834C significantly coincides with solutions sanjaydwk/210063237, tandj_24/210066622.

But there was no such submission by tandj_24. In fact, I saw his/her profile and he/she have not solved any question in this contest. Please look into this matter asap.

Thank You!

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

Today I received a message saying that my solution for problem B and C of Codeforces Round #884 coincides with the solution of a codeforces user named AbdulRahman_Salah. [cut] I was really confused why this has happened. But then I saw that a particular design is present in both of our codes.

Problem B -

Mine || AbdulRahman_Salah

Problem C -

Mine || AbdulRahman_Salah

I've been using this template for so many previous contests and I've no idea why this has happened. Moreover, I have given around 26 contests and I have a very clean record. I am not a cheater.

I would request MikeMirzayanov to look into this matter as clearly there is no fault of mine in all this. Please help me. Codeforces, please look into this matter. I don't want to lose my expert tag. I've got it after so much hard-work.

Moreover, see this blog for more.

→ Reply