ch_egor's blog

By ch_egor, 2 months 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, algorithm16, 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. CQBZ_PPL
  5. just_ice
 
 
 
 
  • Vote: I like it
  • +267
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it
T_T
»
6 weeks 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...

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

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

»
6 weeks 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.]

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

    The blog was written 2 weeks ago but published recently.

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

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

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

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

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

»
6 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

Bad time

»
6 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

https://codeforces.com/blog/SD_1_2

Any one pls solve the above question in link

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

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

waiting for aryanc403's pigeonhole comment

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it
»
6 weeks 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.

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

Oh 22:35, note the usual time!

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

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

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

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

    I like clear topics very much,thank you

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

»
6 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

For Chinese players, this competition time may appear in class. I am

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

I guess orzdevinwang will become LGM after this contest!

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

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

Waiting for weak pretests.

»
6 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it
Spoiler
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :D start contest in online class :D but time, I don't think it :(((((((((((

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

The contests for Russian High School students always gives me prejitters.

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

From score distribution it looks like to be a speedforces

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

nice contest but still at expert :'(

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

»
6 weeks ago, # |
  Vote: I like it -71 Vote: I do not like it

Div.2 D is so hard for me :(

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

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

Just for sure, is problem D bfs?

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

    shart23 thinks that yes!

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

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

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

»
6 weeks 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 :/

  • »
    »
    6 weeks 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[].

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

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

How to solve div2 C?

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

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

      can you explain why it this valid ?

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

      Can you explain why you do that?

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

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

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

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

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

    Just check if the total set bits in the jth bit is divisible by k or not j(0,31) and if not then that k is not valid else valid.

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

Why is Div1C time limit so so tight.

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

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

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

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

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

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

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

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

how to solve Div.2 D?

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

"Dp with data structures" round ...

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

»
6 weeks 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:(

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

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

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

    Yes and the proof is not hard either.

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

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

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

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

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

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

»
6 weeks ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

.

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

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

Does everyone have access to the editorial? I am getting 'You are not allowed to view the requested page'.

»
6 weeks 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, MikeMirzayanov will remove cheaters and update the ratings again!

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

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

    Thanks! Fastest rating updates in recent time

»
6 weeks 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";
}
  • »
    »
    6 weeks 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.

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

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

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

    Because he has exercised a lot on other websites

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

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

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

Can anyone please advise why this submission for Div2D gets WA6? I tried to implement what is written in editorial, and was hoping to get a TL so that I can do further optimisations (just wanted to make sure that I got the idea right). Thank you!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Attention!

Your solution 133020424 for the problem 1602B significantly coincides with solutions Vivek_Kolhe/133020424, shishisuiliu/133031726. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, 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 the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

So, This round was my first rated contest and I received this today like an hour ago. I'm not even sure if this is the right place to post this but I'm posting it anyway. I'm just here to clarify that my solution was submitted to contest before the other solution (My solution was submitted at 13:47 (+5.5GMT) and the other solution of some random guy was submitted at 14:02 (+5.5GMT) to be precise.). And I admit I must have posted my solution to my repository right away to review it later unknowingly and I'm ready to face any consequences, if there are any.

»
5 weeks 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.com/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