ch_egor's blog

Codeforces Round #751 [Div.1 and Div. 2] (on the problems of Moscow Team Olympiad)
By ch_egor, 3 years ago, translation, In English

Hi everybody,

This Sunday there will be a XIX Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727).

The round will be held at Oct/25/2021 09:35 (Moscow time) and will last for 2 hours. Note the unusual time of the round. Each division will have 6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.

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 Moscow Team Olympiad (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 are prepared by LHiC, cdkrot, isaf27, AlesyaIvanova, Tikhon228, voidmax, fedoseev.timofey, KiKoS, NiceClock, 4eT_llpuyHblJl, vintage_Vlad_Makeev and Daria Krokhina under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to adedalic and KAN for the round coordination and verifying statement of original olympiad, adedalic and GlebsHP for statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Also thanks to napstablook and Anti-Light for providing an additional problems that helped to create (I hope) a balanced problem set for the round

Good luck everybody!

UPD1: Thanks to Um_nik, PurpleCrayon, LHiC, VladaMG98, JovanB, TadijaSebez, AlanSkarica, Markadiusz, actinium16, jurichhh8 for testing.

UPD2: Scoring distribution:

Div.1: 500 — 1250 — 2000 — 2250 — 2250 — 3000

Div.2: 500 — 1000 — 1500 — 2250 — 3000 — 3250

UPD3: Editorial

UPD4: Winners!

Div. 1:

  1. djq_cpp
  2. ksun48
  3. maroonrk
  4. ko_osaga
  5. Radewoosh

Div. 2:

  1. zero4338
  2. C2020jzm
  3. SYDevil
  4. PPL_
  5. just_ice
  • Vote: I like it
  • +267
  • Vote: I do not like it

Comments Comments (86)
| Write comment?
»
3 years ago, # |
  Vote: I like it -23 Vote: I do not like it
T_T
→ Reply
»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Why is it on Monday at 14:35? We're still at school...

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

    In my region the contest is at 1 am. I need to wake up at 6 am to go to school D:

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

    Please consider others. Not everything is for you.

    P.S. I really love this round! Really good pretest. There's even a n=1 pretest so that I would not FST.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -15 Vote: I do not like it

Did this have only 2 comments before? [It says the blog has been posted 2 weeks ago.]

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

    The blog was written 2 weeks ago but published recently.

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

      I thought, I saw this post before and assumed it was republished. But there were no comments. And got confused. thanks for reply :)

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -22 Vote: I do not like it
Spoiler!
→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

i wish contests timings will go back to normal...

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -25 Vote: I do not like it

In problem E in the last sample, why [7 9][7] is impossible?

Thanks.

EDIT: Nevermind. I was too hungry when I read the statement.

EDIT: Looks like I was so hungry that I commented on the newer contest's announcement. Apologizes for spamming.

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

This should be the most unusual time I've ever seen in Cf

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

Bad time

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

I hope there will be more datastructure problems . I like that more than construction problems.

Hope everyone good luck!

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

waiting for aryanc403's pigeonhole comment

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it
lighthearted (redirect)
→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

As a student, who has already participated in this olympiad, I say that problems are good.

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

Oh 22:35, note the usual time!

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

As a tester, the problems are great! Good luck to everyone! :)

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

As a tester, I can confirm that the tasks are very interesting, and the statements are clear and well written. I hope you enjoy the contest. Good luck!

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

If you test a round but don't shamelessly beg for upvotes in the comments, can you really call yourself a tester?

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

I guess orzdevinwang will become LGM after this contest!

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

    sadly the contest contains some unfair problem which is 100% not original and meaningless,we have to wait longer...

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

Waiting for weak pretests.

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

nice contest but still at expert :'(

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

OMG , this contest will give me one of my best rank if there will be no FST , I m so happy

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

Div.2 D is so hard for me :(

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

FML for never improving my bit manipulation concepts, didn't even get close to solving C.

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

Just for sure, is problem D bfs?

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

    tem_shett thinks that yes!

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

    Kind of... At least in my case, I solved it with a DP + queue, where the DP states are propagated using a queue, sort of like in a BFS fashion

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

    Yes, 0-1 BFS backwards from the top of the well on the state {current position, next event is a slip or jump}.

    Slips (zero cost move) can be easily maintained as an adjacency list and jumps (1 cost move) are just marking all positions where $$$j - a_{j} \leq i$$$ when we are at $$$i$$$. So we can just sort all points by values of $$$j - a_{j}$$$ and process as many unprocessed ones from the start as we can in each step.

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

      I've seen your code but I still don't get how going through the 'order' vector only once is enough. Could you please explain that?

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

Is range addition + range min queries segtree not intended in Div1C or is the TL just really tight?

Had to switch to ints and replace two sets with vector + sort + unique to even go from TL2 to TL13, I half expect replacing the remaining maps in this fashion will fix TLE :/

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

    I've got OK with seg-tree queries that you mentioned. But only after switching from __gnu_pbds::tree to BIT in computation of number of inversions in a[].

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

      I used a BIT from the start, still TLE on 13 :/

      I suspect I'll need to remove the majority if not all the maps in my code to get AC.

      Edit: Yup, removing all maps and using a sort based compression instead was enough to get AC.

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

How to solve div2 C?

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

    check for each bit the frequency among all numbers($$$f_0$$$ ~ $$$f_{29}$$$), find the GCD for the freq among all bits($$$gcd(f_0, f_1, \cdots, f_{29}$$$), the answers are all the factors of the GCD value.

    also, remember to handle the case where all numbers are zero.

    updated: the special case should be all numbers are zero instead of equal

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

      How did you came to this and plz explain why it works.

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

        the idea came to me after I write down the numbers in base-2.

        why it works: for a bit $$$i$$$, let's say it occurs $$$f_i$$$ times, it will be subtracted only when all $$$k$$$ chosen number in that round has that bit, which means that $$$k$$$ has to be a factor of $$$f_i$$$.

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

    Count the setBit of all position from 0 to 30 of all element. Run a loop from 1 to n and check if the mod of i and count of setBit in all position give zero then it is possible to distribute for I

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

Why is Div1C time limit so so tight.

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

    +1. I pass it by using a quicker input ways .

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

    I don't get why authors set problem with complexity O((n+m)*log(n+m)) n,m<=1e6 with non-trivial constant.Even the time taken by the accepted submissions is very high.Is it intended to use getchar while taking input?.Would never have happened if anton coordinate the contest

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

    You can search optimal positions not fair, but with ternary search + checking small neighborhood. Constrains was raised against such solutions.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +7 Vote: I do not like it

      You do realize that because of blocking some weird heuristics many genuine solutions were not allowed?There are 6 pages of TLE in this problem and most accepted submissions are close to tl

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      If very tight tl is intended why not have ai,bi<=1e6 instead of 1e9.

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

Problem 1D/2F is a problem of a private contest in our school.. I'm so amazed..Here is the photo

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

how to solve Div.2 D?

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

"Dp with data structures" round ...

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

Wondering why BFS solution on div2-D got TLE. The complexity would be O(n.log(n)) which is fine!

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

My idea for D was the following:
Since an alpinist $$$j$$$ can come after alpinist $$$i$$$ only if $$$\max(s_i,a_i) \le s_j$$$ so we can first sort the array by $$$s_i$$$ values and say for each index $$$i$$$ the value of max length subsequence ending at this index is $$$DP_i$$$, recurrence would be,

$$$ DP_i=\max_{x \in [0,s_i]}DP_j+1 $$$

And this could be done with a segment tree where after reaching each index we update the $$$\max(s_i,a_i)$$$ index in the segment tree by $$$DP_i$$$ Is this solution anywhere close to the original solution?
EDIT: Okay, I read the editorial and this approach is incorrect:(

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

I really liked problem C. If you construct $$$n \times 30$$$ binary grid of the number's bits, we are essentially taking maximal (vague but it doesn't matter a lot) all one subgrids (in the subseqeunce sense) with column size $$$k$$$ and flipping them to zeroes. This shows that the value of $$$k$$$ should divide all the column sums in all the $$$30$$$ columns. And it's easy to check that it is possible to do the latter when $$$k$$$ does satisfy these conditions.

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

For problem C, is it true that k is in the answer set if and only k divides all count of 1 in 30 bitwise positions? I couldn't prove correctness but passed pretests

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

    Yes and the proof is not hard either.

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

      what is the proof? the condition of k divides is obviously a necessary condition, but how do you prove is it also a sufficient condition?

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

        Consider any divisor $$$k$$$ and a set of numbers such that the count of numbers with the $$$i$$$-th bit on is a multiple of $$$k$$$.

        In each step, choose any set of $$$k$$$ numbers which share at least one same on bit. Clearly this is do-able as long as all the numbers are not zero and the condition that count of numbers with the $$$i$$$-th bit on is a multiple of $$$k$$$ is maintained.

        Now the $$$\textbf{and}$$$ of these numbers will only include bits which are on in all the numbers. So we will reduce the count of numbers with the $$$i$$$-th bit on by $$$0$$$ or $$$k$$$ for each $$$i$$$.

        So the count of numbers with the $$$i$$$-th bit on will remain divisible by $$$k$$$ and we can repeatedly perform this to solve it.

        If you want a more formal proof, you can write a strong induction proof using this fact. The predicate would be something like $$$p(x)$$$ means for any positive integer $$$k$$$ there exists a way to solve an arbitrary set of non-negative numbers with sum $$$x \times k$$$ given that the count of numbers with the $$$i$$$-th bit on is a multiple of $$$k$$$.

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

    every time we want to subtract, we need to subtract k or 0 counts of bitwise pos, so if we want to subtract all elements to zero, the bitwise count in every pos must be divided by k

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

I accidently do my best ever contest in my alt account but not my main account

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

very super legendary strong pretest in B :( Unbelievable :(

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

In problem B (div 2), what is the maximum value of k after which the there is no change? I thought it would be N, but that failed pretests. Running an infinite loop and breaking when the array becomes constant worked.

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

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

    Thanks! Fastest rating updates in recent time

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +101 Vote: I do not like it

About problem D,I submitted a simple code and it passed system test.
Could anybody Hack it or prove that it is right? 

int n,d,ans;
struct P{int s,a;}a[N];
bool cmp(P x,P y){return max(x.s,x.a)==max(y.s,y.a)?x.s<y.s:max(x.s,x.a)<max(y.s,y.a);}
signed main()
{
    rd(n);rd(d);for (int i=1;i<=n;i++) rd(a[i].s),rd(a[i].a);
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++) if (a[i].s>=d) ans++,d=max(d,a[i].a);
    cout<<ans<<"\n";
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    I tried to prove it by swaping adjacent positions.Let's suppose that $$$\max(s1,a1)<\max(s2,a2)$$$ and now we swap them.If $$$a2>\max(s1,a1)$$$,the answer will be obviously smaller.If $$$s2<a1$$$,we can find that $$$a2>a1$$$,so the answer may be smaller,too.

    I haven't found a situation that we can make the answer bigger by swaping adjacent positions,so I guess it is right.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

      But why you explain this to your classmate in English through Codeforces?(I mean that they are classmates and they are both Chinese.It is convenient for them to communicate with each other in private.)

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

I am really surprised to see why div2 winner of this contest having less number of question solved as well as contest also.

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

    Because he has exercised a lot on other websites

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

About E2/C1 problem. Does anyone have the way to construct the final array with A and B elements. Because my only problem is to construct this array.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    For each $$$b_{i}$$$,we use $$$c_{j}=1,0,-1$$$ to denote $$$a_{j}>b_{i},a_{j}=b_{i},a_{j}<b_{i}$$$ respectively,so the cost of inserting $$$b_{i}$$$ is the number of prefix $$$c_{j}=1$$$ and suffix $$$c_{j}=-1$$$,and it's equal to the total number of $$$c_{j}=-1$$$ plus a prefix sum of the sequence $$$c$$$.So we can use the segment tree to solve it.

    → Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

Attention! Your solution 132999485 for the problem 1602C significantly coincides with solutions Scut22/132996768, phantom654/132999485. Such a Enr oxamole do not use ideone.com with the default settings (public access to yOur code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about minutes ago the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790.Such violation of the rules may be the reason for blocking your may be blocked.

I agree the codes are very similar but the logic of the problem was pretty straightforward. Also using variable names like cnt for counting, g for gcd is a quite standard. So I appeal that it was a mere coincidence. Also Scutt22 seems to be from outside India, and I don't know him in any way. Also please note that I submitted the problem during first 30 minutes of the contest. @MikeMirzayanov

→ Reply