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

Привет!

Уже завтра, в 25.11.2018 19:35 (Московское время) состоится заключительный раунд Mail.Ru Cup 2018. Задачи были придуманы и подготовлены командой Codeforces — мной, Дмитрием cdkrot Саютиным, Ильдаром 300iq Гайнуллиным и Михаилом MikeMirzayanov Мирзаяновым, а также Максимом Neon Мещеряковым. Спасибо Григорию vintage_Vlad_Makeev Резникову и Kamil Errichto Debowski за тестирование задач!

Этот раунд — заключительный в новом соревновании Mail.Ru Cup, подробнее о котором можно прочитать по ссылке. Раунд будет рейтинговый для всех!

По итогам этого раунда будет ясно, кому достанутся ценные призы:

  • Первое место — Apple MacBook Air
  • Второе и третье место — Apple iPad
  • Четвертое, пятое, шестое места — Samsung Gear S3
  • Традиционно топ-100 участников чемпионата получат классные футболки!

В каждом раунде лучшим 100 участникам начисляются призовые очки в соответствии с таблицей. Итоговый результат участия в чемпионате — сумма двух максимальных результатов из трех раундов. Результаты двух уже прошедших раундов опубликованы здесь. В случае равенства турнирных баллов среди первых шести мест будет учитываться сумма внутрираундовых очков, полученная в соответствующих (лучших для участника) двух раундах.

Вам будут предложены восемь задач и два с половиной часа на их решение.

Удачи!

P. S. MikeMirzayanov приглашает всех в официальный канал Codeforces в Telegram: t.me/codeforces_official.

Раунд завершен, спасибо всем за участие, надеюсь, вам понравились задачи!

Поздравляем победителей третьего раунда Mail.Ru Cup 2018:

  1. Radewoosh
  2. V--o_o--V
  3. ch_egor
  4. ksun48
  5. RAVEman

Общие результаты чемпионата будут опубликованы в ближайшее время.

Разбор раунда тут.

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

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

I hope there isn't much controversy like today's contest.

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

I want to become Cyan :p

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

Число 998244353 простое?

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

There seems to be an unusually large amount of spam in the comments.

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

Can someone help me figure out what is the motive behind the telegram channel? Do we have permission to write our comments there or we can just read?

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

Hello MikeMirzayanov why my comment in this post is removed ?

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

    You have replied to a comment which got a lot of downvotes; such comments are hidden as well as replies to it

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

Two thanks to MikeMirzayanov?? Hope this round goes well. Thanks MikeMirzayanov

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

Don't you want to post anything on that channel??? At least announcing the contests...

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

Is it rated? :D

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

We have all guys from top-10 registered for the contest except only tourist and jqdai0815. Will they join and make competition really high and interesting?

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

tourist hasnt registered yet! i think mnbvmar going to be the first in rating

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

hello i live in a very rural part of yugoslavia and i would like to know if this contest is rated for me too. thank you

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

No contest till 3 weeks! why?

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

    This is codeforces, wait for some days then you can see the list of the contests.

    so please be with codeforces.

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

You should fix the bug on the m1.codeforces.com (and m2,m3) platforms.

I was able to lock problem D and then resubmit it. My second submission must of course be skipped, and the same should happen to all contestants that took advantage of that bug.

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

How to solve B?

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

What is the hack for D?

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

How to solve B ?

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

    If you can count number of numbers with remainder i, it's easy to calculate number of x*x % m = i.

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

    We just have to store the values of (i*i)%m for i=1 to m, the values repeat thereafter.So maintain an array which will store number of values for a particular mod value(0 to m-1). a[(i*i)%m]+=(n/m) for i=1 to m and then compute for remaining values(i=(n/m)*m+1 to n). Then,loop through all values of mod such that mod value k can pair with mod value (m-k).

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

    How to solve D ?

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

      For every node, count the number of leafs in its subtree. Store this number in an array, let's call it numleafs. Then sort numleafs in non-decreasing order (smallest element first). For every k from 1 to n, the answer is numleafs[k-1].

      You can count the number of leafs in a node's subtree with a "simple" dfs.

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

    If we knew the number of elements in range [12, 22, ..., n2] that are divisible by m with remainder i (where, 0 <  = i < m), we can esily count the result, that is, the number of pairs of squares elements that are their sum is divisible by m (without remainder).

    To know that, we should know:

    1) how to find the number of elements in range [1, 2, ..., n] that are divisible by m with remainder i (where, 0 <  = i < m).

    2) how to transform from [1, 2, ..., n] to [12, 22, ..., n2].

    This is my submission for more details.

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

Wth is pretest 5 in B

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

Can anyone provide test 7 for E? Got runtime error :(

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

I can't wait till the system testing finishes. Has anybody an idea what is pretest 17 of problem E??

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

What's pretest 2 in F?

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

    Probably some random test case, but looks like I can only pass by switching to using binary search / ternary search instead of analytic solutions.

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

      I switched to ternary search as well but no luck.

      My solution was to find with DP the minimum of achievable for a fixed k and total number of points P. Then we can minimize and check whether it fits under time.

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

        I have the same one! And I don't have any reasons why my solution doesn't work.

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

          I passed pretest 2 when realized that t must be non-negative. So I took t = 0 if f(t) is minimum at negative t (but I got wa56 then and I have to clue about it)

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

        I did the same thing and failed to the same test :(

        This is one thing I hate about math problems: The idea is often trivial but in the implementation you have to do so much math that it's inevitable you'll get bug :/

        EDIT: my bugs were the following:

        1. I calculated the optimal x (time spent training) as x = max((ld)0, -b/2*a), when it should be (2*a)

        2. Knapsack looped from bottom to top, allowing the same item to be used twice

        ... how this even passed the first test, I'm not sure

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

        Okay I had a major fuck-up which didn't trigger samples (never does): applied rearrangement inequality in reverse direction. Sorting the array in reverse direction worked.

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

        I think the problem with analytic solutions might be that the value of t which minimizes the function comes to be negative. That seems to be the only thing I missed in my solution.

        EDIT : Yes, that was the only fault in my solution.

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

        Look at mine: 46228777

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

      I also lost about 50 minutes due to the same issue , but I've no idea WTH is wrong with it. Does anyone knows why this happens?

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

        What did you change?

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

          I changed the O(1) formula to find the maximum value in a concave function to a O(log(T)) ternary search and passed the pretests.

          By the way if anyone is interested , here's a counter test :

          1

          4

          1.000 11.112

          4 9

          12 3

          1 3

          1 5

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

            I had that as well but it was because the formula gave me a negative value for t. It worked when I maxed it with 0.

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

Please guide for B and D

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

This was my first time solving D but I failed to solve B >:(

Can someone please tel me how to solve B?

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

    How to solve D?

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

    ((i*i) + (j*j))%k can be written as ((i%k*i%k)%k + (j%k*j%k)%k)%k. Keep count of number of i's such that (i%k) = j for all j from 0 to (k-1). Similarly using this count array, construct (i*i)%k mapping to j, let this be arr. Now for every i,j such that 0<=i<k and 0<=j<k if (i*i + j*j)%k == 0 add the value of arr[i]*arr[j].

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

      Thanks! Simplifying the problem using modular arithmetic was really smart.

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

    Instead of thinking of the coordinates as numbers from 1 to n, think of it as several consecutive periods of numbers from 1 to m.

    Traverse an integer i from 1 to m. With each value, calculate two value:

    • cnt: number of periods that contains i within range [1, n].
    • r: the remainder of i2 when divided by m.

    Make an array RemCnt[], and with each i, add cnt to RemCnt[r].

    After this, we can safely do a O(m2) traverse to find out the number of pairs (i, j) such as i + j is divisible by m.

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

Problem B was a fantastic problem.

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

In problem D hack attempt: input: n = 1, giving status: invalid_input, I think it is a valid case 1 <= N <= 100000 .

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

whats the test case 7 in C ??

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

Tfw you're worried AF about system tests in E because you used a single and standard hash :(

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

    Haha, May the force be with us all :P

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

    No reason to be afraid of system tests if you survived hacking phase, I didn't have that luck ;_;

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

    I'm using an insanely weird modular number, yet the "single" property still makes me worried as hell, especially seeing Swistakk got hacked...

    What I've used
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Can you explain your solution for E?

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

      Loop length of the string replacing zeroes, calculate length of string replacing ones, and check if this configuration works with hashes. Complexity is O(n log n) since you do n + n/2 + ... + n/n = O(n log n) work.

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

Guys, what is the tricky part in problem C, i get wrong answer on test 7. :(

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

    Probably the query you are accidentally printing is the value of the player itself and not the index. I got a WA on test case 7 for that one.

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

    I think for optimal solution you have to take special pairs of heroes first. I also got WA on test 7..... I fix this and pretest passed.

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

    Simply you were getting the strategy wrong.

    If you have a turn and not being obliged by anything, you can choose one pair of special heroes, pick the stronger one, therefore forcing your opponent to pick the weak one, and give you back your turn again. It's a clear win-win, so whenever you have a chance to freely choose heroes, repeat that process until there's no special heroes' pairs left unchosen.

    After that being done, we return to the normal, maximum-prioritized strategy.

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

In problem D,Sample test 2

At k = 4 why is the node 3 happy? considering that subtree of node 3 consists of (3,4,5) we only colored (4,5) what about 3(it can't be colored) but shouldn't be counted as colored?

A happy junction is such a junction t that all light bulbs in the subtree of t have different colors.

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

what is the hack for D ?

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

fast system testing running...

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

Задача E была несколько лет назад на SN*S(а значит Снарк взял её из еще более раннего контеста).

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

why can't you fcking include n = 1 in pretests?

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

    Because it is corner case and it should be quite obvious to check before submitting solution. So if you didn't that — it's your fcking problem.

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

    Depending on how you implemented it, n=1 is not even a corner case; it can be handled by the general case. If you consider the sole node in n=1 to be a leaf and begin processing nodes at the leaves, you shouldn't run into an error with n=1, and you don't need a special case for it either.

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

This has to be the Fastest System Test ever.

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

Thanks for fast system testing!

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

Thanks for fast system testing!

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

codeforces system testing rocks...

fastest ever.

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

No n = 1 in pretests for D? Are you kidding me!?!?!?!?!

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

Open it for practice please

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

Open it for practice please Edit: Its open now, wonder why the delay.

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

How long after the contest is over can we submit our solutions again?

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

Was that the fastest System testing in Codeforces history :D

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

How long after the contest can we submit solutions again?

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

mnbvmar gonna win Apple MacBook Air.

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

Very bad problemset for div.2. >5k registered users, >3k users participated (made submissions), about 1.3k participants solved A. And only 1.7k solved more than A (or at least B or C). So if you were participant of div.2 level, you probably read problems' A statement, almost immediately submitted an answer, and then you could leave contest, and your place will be determined only by comparing submission speed (and speed of overcoming of starting 502 Bad gateway) of problem A comparing with thousand other same level participants. I want to emphasize that there were no announcement about difficulty of the problemset, only it was said that this round is for all (so it means for div.1 + div.2 + div.3). And there were "АЖ" 8 problems. 7 of them were for 2/3 participants. In my opinion, better were to offer for all participants: about 2 problems of div.3 level, about 2 problems of div.2 B-C level, and about 4 more difficult problems.

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

    The only thing you should do is to stop complaining and improve yourself, and you will find out that pB is trivial enough.

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

    rsFalse has a point here. B, C, D felt of the same difficulty, which isn't good already. For div. 1 guys they all felt easy, and for div. 2 guys they were all medium. Making B easier and D harder would've been appreciated by more people as then B would've been solvable by more div. 2 and div. 3 people, while D would've been more interesting for div. 1 participants. Problems of the same difficulty really create issues, but this is difficult to avoid when preparing a contest.

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

How to solve B ??

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

    For a given n and m you have to count how many i, j are there where (i^2 + j^2) = 0 (mod m). You can easily see that i^2 mod m and j^2 mod m ( i, j from 1,..., n) forms a cycle.So, ans will be equal cnt[i^2 mod m] * cnt[m — ( i^2 mod m)]. Check my submission 46215431

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

By the way, why is the next competition three weeks away?

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

    Maybe they are just taking care of new problems/competitions before posting them.

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

congratulation to yashChandnani to become a red coder.

such an inspiring rating graph.

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

Is there a reason for the tight time limit on problem H of 1 second, when n is 300000 and the intended solution is O(n sqrt(n))? Were there any unintended solutions you wanted to keep out with this time limit?

EDIT: sorry, I referred to the wrong problem

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

46235526 Problem A TEST 10. My answer is correct and the test result is incorrect. How can I pass the test?

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

    You answer is incorrect since you have 64.

    Notice the first numbers from 2nd line and so on indicate the number of stops in that line and it is not a stop itself.