Автор awoo, история, 3 года назад, По-русски

Привет, Codeforces!

В 22.11.2021 12:35 (Московское время) состоится Educational Codeforces Round 117 (рейтинговый для Div. 2).

Раунд пройдет по задачам Чемпионата Юга и Поволжья России 2021, который является региональным соревнованием ICPC. Если вы участвовали в нем или планируете виртуальное участие, то, пожалуйста, воздержитесь от участия в Educational раунде.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

UPD: Разбор опубликован.

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

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

NOTE THE UNUSUAL TIMING

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

eagerly waiting for the contest.

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

Why Unusual timing again? :(

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

Finally a cf contest after so long .....All the best to the fellow programmers !!

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

contest after long time in unusual time , why in the last period the contests in unusual time :(

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

On behalf of all Russian schoolers, I protest against the unusual timings on weekdays.

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

On behalf of myself I strongly support the unusual timing, it gives an opportunity for competitors around the world to participate :)

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

Will try to perform better this time. let's hope for the best. Good luck everyone!

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

Good luck everyone!

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

Last week one contest this week five contest I am not complaining, but it would have been better if contests evenly spaced them in these two weeks. Lately, there has been a lot of inconsistency in contests either there are very few, or there is a lot in a 7 to 10 days period. Anyway, today is contest day, so best of luck to everyone.

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

Can you change the timing i have meeting from 4:00 to 4:30 pm , please

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

Will the problems be arranged in the correct difficulty order? Or will it be shuffled as we see in icpc?

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

Mathforces

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

How to solve D?

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

How to solve E?

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

best contest i've ever done!

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

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

Does anyone know the proof for why it's never optimal to select more than 20 pins in 1612E - Messages??

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

    If $$$s_i$$$ is the sum of all $$$k_i$$$ with $$$m_i = i$$$, then the expected return you get from including $$$i$$$ is equal to $$$\frac{s_i}{t}$$$ if $$$t \geq 20$$$. Note that you greedily want to select the largest $$$t$$$ values of this for the messages, and you can show that this value is greatest when $$$t = 20$$$ (since averages decrease since you're taking lower and lower sums).

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

    If you take 20 best messages out of $$$m$$$ taken in terms of expected value contribution and leave just them, their expected value will increase proportionally to $$$\frac{m}{20}$$$. But since they were maximal total EV will not decrease.

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

    Suppose we have selected the $$$y$$$ messages with the max $$$x$$$, where $$$y$$$ $$$\geq$$$ $$$20$$$, and $$$\sum{k_i}$$$ $$$=$$$ $$$x$$$ for all $$$i$$$ where $$$i$$$ is one of the chosen messages. If we select the $$$(y+1)_{th}$$$ message $$$msg$$$ where $$$\sum{k_j}$$$ $$$=$$$ $$$z$$$ for all $$$j$$$ where $$$m_j$$$ = $$$msg$$$, the first $$$y$$$ messages are still the best, and their total expected value decreased from $$$\frac{x}{y}$$$ to $$$\frac{x}{y+1}$$$, that is, decreased by $$$\frac{x/y}{y+1}$$$. However, $$$msg$$$ only introduced $$$\frac{z}{y+1}$$$, and $$$z$$$ $$$\leq$$$ $$$\frac{x}{y}$$$, otherwise it would be one of the best $$$y$$$ messages.

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

idk how many guys pass G, I want to say that F is much easier than G

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

    When I began solving G, it had 17 solves while F had like 3.

    Most people who reached F/G didn't have time to solve both, so it was probably just an observer effect here.

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

    Hi, can you please give some hints on how to solve F? For me G seemed easier than F.

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

      You can just optimize bfs.

      The queue contains tuples $$$(a, b, d)$$$ ($$$d$$$ is the number of moves to reach $$$(a, b)$$$). Let $$$(a, b, d)$$$ be a useless tuple if there exists a tuple $$$(a', b', d)$$$ in the queue, with $$$a' > a$$$ and $$$b' > b$$$. If you remove useless tuples from the queue (e.g. by rebuilding the whole queue if its size is $$$> 2 \cdot 10^5$$$), the bfs is fast enough.

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

How to solve D ? I called gcd(difference, maximum number % difference), but if the difference is larger, then it gets executed huge number of times...

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

    Basically, the numbers you can reach are everything reached by the Euclidean algorithm for a and b.

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

    I guess resultant number was eventually max-min*k such that max-min*k>=min after that max and min will change so you just have to check whether x%min==max%min otherwise pass for min,max%min

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

Hmm... I think G is easier than E. E was difficult to translate.

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

I dont know how total accepted submissions of problem D went from around 1200 to 1700 in last 20 minutes ;_;

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

traditional -100 for me kekw

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

EDIT: ok i got the mistake.

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

i should've been prepared more before joining this round

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

Can Anyone provide the intuition behind D, it ate up my whole hour, still couldn't find a logic.

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

Should E really pass in $$$O(nlogn*20)$$$? I did write a solution which passes but with a high execution time. Can someone hack it?

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

Did anyone observed precision handling error in python in question 3

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

    Yes — do use from decimal import Decimal to handle floating point numbers with higher precision in Python.

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

What's the approach for E?

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

    Observation 1: if you're going to pick X messages, it's obviously optimal to choose the mi such that sum(min(ki,X)) is maximised (why? consider how you would write the expectation calculation as an equation). So the first thing we want to do is sort the messages by the sum of ki values assigned to that value of mi.

    Observation 2: it's never optimal to go beyond 20 messages (or, more specifically, max(ki) messages). Why? Suppose we have exactly max(ki) messages. Then our expected value is E20 = sum(ki)/20 for the users whose messages are in this set of 20. If we add another message, the expected value E21 = sum(ki_prev)/21 + sum(ki_21)/21 = E20*(20/21) + sum(ki_21)/21. Suppose E21 > E20. Then we have sum(ki_21)/21 > E20*(1/21) = sum(ki_prev)/(20*21), and hence sum(ki_21) > sum(ki_prev)/20. This means that the 21st message has a greater sum of ki values than the mean of the first 20. But this is impossible because the 21st message has a sum of ki values less than or equal to the first 20 values.

    So it's proven we will never go beyond 20 messages. Now we just try all possible values from 1 to 20, and find which gives the greatest expectation. There's a tricky nuance (which I believe I got wrong in contest) where you have to sort each time according to sum(min(ki,X)), rather than just sorting according to sum(ki).

    Code

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

      And you don't even have to make the second observation, I, for one, completely missed it. You can just sort all E20 highest to lowest and check all prefixes of this order.

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

      I Was looking for this proof precisely, Thank You for the clear explanation !

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

How to solve C?

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

Regarding this submission: https://codeforces.net/contest/1612/submission/136484148

If I'm not wrong, it's complexity is clearly $$$O(t * 10^6)$$$ for cases which results in -1 -1. So, it must exceed the given time limit easily (as $$$t \leq 3000$$$), but on Custom Invocation I have tried and it runs in $$$\sim 1500$$$ ms.

Can anyone kindly explain me why it is so?

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

How to solve F?

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

Can someone explain their approach to Problem D

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

What's the hack case on E?

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

Here are the video Solutions to the first 5 Problems In case you are interested.

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

Thanks for the good sample tests to avoid overflow in problem C.

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

Here's a heuristic solution for problem F: https://codeforces.net/contest/1612/submission/136557294

The idea is that it's generally much better to replace the smaller number to increase our power quickly (which greatly overpowers any gain from synergies), but for small values this might not be the best option. We take all possible choices for the first 6 moves, and then apply the following:

  • If $$$x$$$ or $$$y$$$ is already maximized, then replace the other.
  • If one of $$$x$$$ or $$$y$$$ can be maximized on the next move, then do that.
  • Otherwise, do whatever will increase power the most.

This passes all test cases but I highly doubt it is correct, and would welcome a valid hack.

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

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

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

I panicked in this contest and lost a bunch of ratings. My biggest drop yet (-100). I couldn't even solve A. Is there anything I can do to get a better grip of my nerves in a contest and not panic when I see an implementation heavy or math problem in the contest?

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

164 pretests in E and still they do not have tc that fails the most obvious wrong solution)

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

What kind of time of sending tutorial is normal? Looking forward to the solution.QWQ

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

I received a System mail saying that my solution 136459207 matches with idkmyname_ submission 136471505. I believe this is because we both have used nor's publically available BigInt library
I had also put this link as a comment in my code, as one should do while copying third-party code. MikeMirzayanov please look into this

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

I got this email from Codeforces which says that my solution for problem C coincides with too many people.

It goes like- Attention!

Your solution 136470651 for the problem 1612C significantly coincides with solutions bihari_bandar/136430343, greyman/136431111, going-too-far/136431248, SnigdhaReddy27/136438434, Jee_none/136440961, loser53/136448455, Pratyush_tripathi/136449209, manishchembeti/136452512, yash112124/136453654, misra99/136456090, ashutoshtr/136458047, TheThinker_08/136458129, venom0912/136460586, Secret_Superstar12/136461961, pratik2912/136462123, shivam.yadav98939294/136462732, Karan10100/136462833, 123Alpha/136465897, crosscheck371/136466967, darkcoder_347/136470103, codeprakhar/136470651, ramanand_rv/136470925, noob_tusharb/136471502. 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.net/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.

Now, I don't understand how my solution can so perfectly coincide with so many people even when I don't know who they are! I even have never used Ideone.com.

I was previously trying to solve this question using simple maths(quadratic equation solution) but that didn't work so I thought of another method that involved simple binary search. It worked.

I understand that the code of binary search is freely available at almost any programming website which leads to this coincidence.

Codeforces community... How can I get this fixed?

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

MikeMirzayanov I got an email from the system that one of my solutions for this round coincides with many others. Although I still can't understand why it happened;

The main concern is that All the problems for this contest were skipped from evaluation but still, my rating went down by -108. If the contest was skipped; shouldn't the rating neither increase nor decrease?

Please look into it and return my rating like before this contest. Thank You

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

I want to ask question F, if I just think about q=0, does it have the same number of answers as it has the right answer? How long does it take for the Fibonacci number to form Max of m,n