Zlobober's blog

By Zlobober, 5 weeks ago, translation, In English,

Hi everybody,

Lasts Sunday there was a 15th 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 Megapolises Olympiad (rounds 327, 342, 345, 376, 401, 433).

Round will be held at 11:05 UTC on Monday and will last for 2 hours. Each division will consist of 6 problems.

Problems are prepared Andreikkaa, sender, Flyrise, -__-, kraskevich, wilwell under supervision of your humble servant with great help of GlebsHP, _meshanya_, Endagorion and Helen Andreeva.

Discussing problems with anybody who was a participant of Moscow Team Olympiad is strictly prohibited and may be a reason for disqualification.

Good luck everybody!

UPD: Thanks everybody for participation, congratulations to round winner!

Div1 winners:

  1. fateice
  2. simonlindholm
  3. Haghani
  4. yjq_naive
  5. Petr

Div2 winners:

  1. Cypi
  2. Nu11
  3. ZJT_IOI_2020_AK
  4. guoxingzhuo
  5. Senji

Editorial will be published today after a while.

UPD2: Editorial!

 
 
 
 
  • Vote: I like it  
  • +240
  • Vote: I do not like it  

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

Is it rated?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -47 Vote: I do not like it
    Is it rated?
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      Every time when I wrote a comment "Is it rated?".. there is always someone to reply ""Every time I see comment "Is it rated?". Yes, it is."" :D

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it -39 Vote: I do not like it

        Every time when I wrote a comment "Every time I see comment ""Is it Rated?"" " there is always a reply "Every time when I wrote a comment "Is it rated?".. there is always someone to reply ""Every time I see comment "Is it rated?". Yes, it is."" :D"

        Is it rated?
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -52 Vote: I do not like it

    yAs iT iS rAtEd

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

    Old way to get downvotes man be creative like me! I'm the master of downvotes in CF you can see my blogs or my comments to learn more about downvotes

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

      :D what differ to me if I get downvote or not.. Actually I never care about to be down voted..

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

      Arabs don't have short.

»
5 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Recent contests were nice for me because I'm in UTC+8. Another great rated round is coming, good luck to all of you.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

212 = 441

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

I had just done a contest yesterday xD

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Yap, two Consecutive contests in two Consecutive days. It's really amazing. :)

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

    That too with two Div1 contests in two days. I was sad that I was unable to give yesterday's round, but seems fine now.

»
5 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

Heylooo guyzzz .... is it RatEd ??????????

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Great!

»
5 weeks ago, # |
  Vote: I like it -59 Vote: I do not like it

The timing could have been better, as Indian college students mostly have classes till 5 PM .

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Good luck to all the participants

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

A great time for chinese students again!

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Let us hope for too much hacks :)

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

GL & HF

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope the problem statement will be short like yesterday round...

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Scoring distribution?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    Their history also shows that no scoring has been ever announced.

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

WTF!! Can't see the problems

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

will my rating change if I have one WA and Tle in the contest but no correct submission?

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

:)

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

I don't know Russian but i want to know the puns!

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

    You are still waiting for somebody to explain you the puns? You could have already started learning Russian!

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Why there are only Div2 and Div3 contest?

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

What surprised me first was that “Why is the name list so LONG?"

»
5 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

Click Here

And the go to profile/submissions ;) you will magic!

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

A query regarding the judge..

The output was 0, I displayed 00. Wrong answer.. why? aren't they the same thing..

If I have calculated my output and there is still some input left which can be taken, is it possible I don't take it and directly display my result. (it is a normal take an array and do something question, not 't' times one.)

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

What is pretest 9 in E?

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

WHAT IS DIV1D PRETEST 10 AHHH

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

    Make sure you are not overcounting the subarrays. Try this test case: n = 3, a = [2, 4, 4].

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

      answer is 2?

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

        Yes.

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

          I see that you had WA10 in contest but you managed to fix it. Is there any other case that you had to fix before getting AC?

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

            Maybe overflow? I had only this issue with my code fixing which got me AC. I hope this won't fail the systest. :P

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve F?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +34 Vote: I do not like it

    First, convert princes to nodes, and princesses to edges. You can show if the set of edges is a valid solution if and only if it is a psuedoforest (https://en.wikipedia.org/wiki/Pseudoforest ). So, it suffices to find the max weight pseudoforest.

    It turns out this is a matroid, so adding edges greedily works. All we need is an efficient way to check that each connected component has at most one cycle.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Apparently my first submission tried to do this but I used = instead of |= in dsu. I think replacing it will make it correct. Have to wait after systest to submit it though.

      UPD : It got accepted.

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

    lewin is absolutely correct, though this approach may be described from a different point of view without matroid theory.

    Consider a princess that is the best match for both of her princes. In an optimal solution this princess should be covered with an edge (otherwise we may force one of her princes to marry her and it will be at least the same profitable).

    It turns out that we may remove such princess from a graph (adding her value to the answer) and contract two her princes into a single super-prince having the union of edges of the original princes. It's easy to prove that it is an equivalent transformation.

    It leads to exactly the same solution that uses DSU to keep contracted princes.

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

How to DIV2C?

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

    Hint : What is the number with maximum sum of digits?

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

    Note that numbers up to 10^9 have at most 9 digits. So the maximum we can add to a number is 9x9 = 81 (putting 9 in every digit).

    Therefore we can just bruteforce 100 numbers (just to be safe) from n-100 to n checking if each one of them + the sum of the digits equals n.

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

      that's exactly what i did..... first time solved div2 C..... hurraayy! But B not solved xD

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

      Yep exactly what I did. Arbitrarily put an lower limit of n-100. Although if there is a proper solution or a proof for it I would like to know.

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

    My incredibly overcomplicated approach is this:

    We can represent any number x as a0 + 10a1 + 102a2 + ... + 10nan. If we add a number's digits to itself, we will obtain a number k = 2a0 + 11a1 + ... + (10n + 1)an.
    Let's fix a0, a1, a2, a3, a4 = 0, and try all possible combinations of (a5, a6, a7, a8), generating all 104 integers k = (105 + 1)a5 + (106 + 1)a6 + (107 + 1)a7 + (108 + 1)a8 and storing them in a map. Then, we can fix a5, a6, a7, a8 = 0, then try all combinations of (a0, a1, a2, a3, a4) in the same way. For every integer k generated in this step, we can just check if n - k exists in the map we created before.
    Complexity: O(105log(105)).

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

      Hi I was trying something similar. But why do you fix First five numbers?

      My submission

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

        We should minimize 10x + 10y, subject to x + y = 9. (10x = number of integers generated in the first step, 10y = number of integers generated in the second step.)

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

      I tried exactly the same, it's like a diophantine equation. But, i didn't know how to solve it whitout bruteforce all the combinations, O(109) in the worst case.

      Why check n-k?

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

    Let consider sum(x), sum(x) is the sum of the digits of the number x

    x + sum(x) = n

    x = n - sum(x)

    it's mean that you can just do bruteforce by the sum of the digits.

    Let maintain current sum as cursum, if sum(n - cursum) = cursum, we add n - cursum to our answer

    Complexity O(log(n) * maxsum)

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Am i the only one who solved the first task using dp???

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

Best contest ever. :)) I have never passed D. :))

»
5 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

clicked the submit button 7secs before end of the contest, but it was not submitted. Now this thing has happened to me twice on cf.Just a suggestion, but maybe cf should consider accepting submissions for 10 extra seconds after the contest? As server is usually slow at the end of contest, this should not benefit people submitting just after contest.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve DIV2 E?

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

What was the hack for Div 1 C?

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

    I was hacked on the case when I tried to set to some letter that it should be capitalized don't paying attention that this letter can be already marked as a letter that cannot be capitalized.

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

    I failed in test case 62 31410790

    4 5
    2 1 5
    2 1 4
    2 2 3
    2 2 5
    

    I reduced 5 to satisfy 5->4 but did not reduce 3 so 3->5 became unsorted. My solution got accepted by running the recursion twice 31414586.

    I think the accepted solution is still incorrect. If there are three items I need to be reduced instead of two then I need to run the recursion 3 times. I guess there are no test case of such scenarios.

»
5 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

How can Div1.F be solved in 9 minutes?

I think more difficult problems are better.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +54 Vote: I do not like it

    Maybe the author just wants to see if there is anyone doesn't see the f problem from beginning to end

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

Div1 A is exactly same problem to Atcoder Regular Contest 034 B (http://arc034.contest.atcoder.jp/tasks/arc034_2 [old Atcoder contest, Japanese]), so I managed to solve in 2 mins.
I think even copy-pasting the submission of this problem can lead to AC of today's Div1 A.

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

    Unrated contest :P ?

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

      But I think the effect is very small, so it will be rated.

      • This problem statement is in Japanese, so it seems >95% people didn't see this problem in participants of this contest.
      • In addition, it seems >95% people who saw this problem didn't realize the problem, which this problem is already published in 3-years-ago AtCoder problem.
»
5 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Is there anyone who understood Div1B?

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

    It took me hours to understand D , I thought I am not understanding it because I am a newbie.

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

Why after adding sort(a+1,a+n+1) to my submission it fails on test#1 on TLE

TLE#7 31410864

TLE#1 31411210

UPD : Already found

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

So to me, the key was understanding problem statement. I almost failed at Div2 D(Div1 B) but somehow managed to guess what authors meant. However, I completely failed at understanding Div2 E(Div1 C). Redefined 'Lexicographical order' was way too difficult and confusing.

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

div1b, div1c, div1d = [div1c, div1d, div1b]

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

    div1b was pretty easy . maybe like div2b

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

      Div2B is usually a task that could be submitted by average expert/candidate master in something like 10 minutes. Maybe I'm dumb but I didn't manage to find solution in ~30min while contest and ~30mins after.

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

Am I the only one who used segtree + binary search on div2 D?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I too used a SegTree. Not Binary seaching though. Was really blown when I saw the actual solution!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    why binary search? I maintained the rightmost position of zero in one segment tree and count of ones in an interval in another segment tree. So, the answer is just 1 plus count of number of ones present before the rightmost position of zero.

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

    I used BIT+binary search

    I thought it would fail as number of iterations were > 1e8,but it still passed in 218 ms :D :D

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

      xD mine passed in 608 ms

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

      I thought i was the only person used O(nlog^2n) algorithm in the world...XD Luckily, it didnt FST....

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

      Am I the only one how solved it with Disjoint Set Union :)

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

        Can you explain how you did it with dsu??

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

    I just keep tracking on the rightmost consecutive X's and my solution passed in 156ms :)

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve div2 E ?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it

    Build a graph on letters which should be updated together. If the strings are different, there is only one pair of letters, which decides that the previous string is lex smaller than the next one.

    123

    124

    Add edge 4->3 to the graph, which means, that if you capitalize 4, you have to capitalize 3 too.

    125

    124

    You must capitalize 5 and you can't capitalize 4.

    In the end run dfs from every letter you must capitalize. Check that the letter which can't be capitalized, was not capitalized.

    I also checked special case

    1245

    124

    Which gives no immediatelly.

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

    2-sat.

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

      I do not remember 2 sat solution exactly but I know that strongly connected components were involved. For this problem, we have DAG (edges are from higher letters to lower).

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

nice contest but really d was translated soooo bad

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

It seems like there are a lot of people failed the first system testcase of Div1C (including me T_T).

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Unlocking new bandage: FST Master.

»
5 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

It's friendly to Chinese

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

WoW!So many guys solve all the problems,You are so great The solution size of F seems so short,amazing!

»
5 weeks ago, # |
Rev. 4   Vote: I like it +46 Vote: I do not like it

Problem almost the same as F was used in this contest in Petrozavodsk as problem A in 2012.

Surpisingly, team Moscow SU T@pirenock: Evstropov, Ivlev, Pyaderkin was 12th in that contest, having two incorrect attempts at problem A :)

This is the link to its statement.

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

    access denied, fix pls

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +142 Vote: I do not like it

    Can't tell for Gleb and Michael, nontheless, I should have participated in that contest as a training around 2013. Of course I didn't remember this problem until this moment, otherwise we wouldn't have taken it in Codeforces round :)

    Almost 6 years is a long time period. Not sure if it is possible to remember all problems since you have started participanting in a programming contest. This problem in particular was suggested for a contest as an easier version of wilwell course work.

    PS so to me seems like a notorious coincidence.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Where is div2 rating update?

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

In div2 B, why we don't need to calculate the difference between elements of multiset, just calculate the number%m and push it in vector array or map to count it's size?

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

    because (a — b) % m = (a % m) — (b % m) (and + m if it is negative). We save numbers (a, b) which have same remainder (x). a % m = x and b % m = x => (a — b) % m = x — x = 0 (that's we need). And it works for all pairs {a, b} if they have same remainder.

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

Can someone please elaborate how to solve Div.1 F? Thanks!

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

How to solve Div1D or Div2F ??

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

    start placing the numbers in decreasing order on the array now for each number that you put find out how many new intervals you can choose which contains this number . now its obvious that these intervals cannot include any of the already placed numbers (you can find the bound easily by std::set) now for each j that the current number & pow(2 , j) = 0 find the first place after and before the current place that number y & pow(2 , j) = 1 . now you have two intervals . just some conditions and AC

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

      Thanks a lot ...

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

      I think my solution is basically the same thing as what you described. Is Nlog^2N supposed to pass, or is there a more optimal solution?

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

        Mine was pure

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

          It can be optimized to n log max easily with a pre calculation that for each bit and place we store the next and previous 1

»
5 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Am I the only one who doesn't like large problem statements.

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

I still didn't get the problem Div2D? :(

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

Still no tutorial yet...

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

For DIV2 D,it's more hard to read than write.

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

life sucks