Блог пользователя Zlobober

Автор Zlobober, 7 лет назад, По-русски

Всем привет!

В воскресенье в Москве прошла пятнадцатая Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433).

Раунд состоится в 14:05 16 числа и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи соревнования подготовлены Andreikkaa, Sender, Flyrise, mingaleg, kraskevich, wilwell под руководством вашего покорного слуги, а также GlebsHP, meshanya, Endagorion и Андреевой Е. В.

Если вы участвовали в МКОШП, участвовать в раунде строго запрещено. Не обсуждайте, пожалуйста, задачи и их решения с участниками раунда до его окончания, это является поводом для дисквалификации.

Всем удачи!

UPD: Всем спасибо за участие, поздравляем победителей раунда!

В Div1 ими стали:

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

В Div2 ими стали:

  1. Cypi
  2. Nu11
  3. zjt_is_our_red_sun
  4. GXZlegend
  5. Senji

Разбор появится сегодня несколько позднее.

UPD2: Разбор!

  • Проголосовать: нравится
  • +240
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится -71 Проголосовать: не нравится

Is it rated?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -47 Проголосовать: не нравится
    Is it rated?
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -33 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится -39 Проголосовать: не нравится

        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?
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -52 Проголосовать: не нравится

    yAs iT iS rAtEd

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -25 Проголосовать: не нравится

Крутой контест)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

212 = 441

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I had just done a contest yesterday xD

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Насколько это надежно участвовать в раунде, в котором могут принимать участие люди, которые в свою очередь ознакомлены с заданиями? Стоит ли пропустить?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    Можешь смело участвовать. Живым после этого раунда точно останешься.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      То что я останусь живым это конечно радует, но все же как то это странно... ведь кроме того что люди могут сами писать этот контест еще и могут другим рассказать что да как решается)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    В смысле надежно? Задачи от этого хуже не становятся :)

    Вообще это довольно частая ситуация с раундами по мотивам школьных мероприятий.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится

      Задачи я уверен будут интересные и сложные)) Но вот рейтинг сильно зависит от количество человек набравших большое количество баллов... Я не знаю насколько много человек из Москвы участвовало в МКОШП и сколько у них друзей которым они поведают решение)) Может ли их большое количество сильно повлиять на распределение рейтинга?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

        зависит чисто от того, насколько ты нарешаешь, несмотря на других

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +7 Проголосовать: не нравится

          мда, поколение пошло... изменение рейтинга зависит от места в таблице относительно других участников

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +42 Проголосовать: не нравится

            Я бы сказал, что почти для любого участника, отличного от Гены, средний разброс места на контесте сильно превышает количество людей, которые могут его обогнать нечестным образом. Но это моё личное непрофессиональное мнение.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится -6 Проголосовать: не нравится

            и к чему ваш комментарий, если он является логическим следствием из моего... мда, ну и поколение прошло...

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

Yes, it is rated.

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Great!

»
7 лет назад, # |
  Проголосовать: нравится -59 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Good luck to all the participants

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A great time for chinese students again!

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

GL & HF

»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Scoring distribution?

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

R.I.P English

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Орнул с условия Div2F

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    Посылайте лучи плюсов в сторону mingaleg, самый орный автор задач московских олимпиад

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Когда заблокировал задачу, понял, что решил ее неправильно и ждешь, пока она упадет

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Why there are only Div2 and Div3 contest?

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

What is pretest 9 in E?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WHAT IS DIV1D PRETEST 10 AHHH

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve F?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to DIV2C?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      My submission

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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)

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve DIV2 E?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the hack for Div 1 C?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

How can Div1.F be solved in 9 minutes?

I think more difficult problems are better.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +54 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -62 Проголосовать: не нравится

    Unrated contest :P ?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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.
»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Is there anyone who understood Div1B?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    div1b was pretty easy . maybe like div2b

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

How to solve div2 E ?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    2-sat.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

nice contest but really d was translated soooo bad

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Unlocking new bandage: FST Master.

»
7 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

It's friendly to Chinese

»
7 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +46 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    access denied, fix pls

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +142 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Where is div2 rating update?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div1D or Div2F ??

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it in almost the same manner as from the recent 1418G - Три вхождения. My code here : 95019408

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Still no tutorial yet...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

life sucks