Автор errorgorn, 6 дней назад, перевод, По-русски

Привет, Codeforces!

Присоединяйтесь к объединенному Div1 и Div2 раунду Codeforces Raif Round 1 (Div. 1 + Div. 2), который будет проходить при поддержке Райффайзенбанка и начнётся в 17.10.2020 16:05 (Московское время). Он будет рейтинговым и открытым для обоих дивизионов. Обратите внимание на нестандартное время начала раунда.

Все задачи были придуманы и подготовлены bensonlzl, oolimry, errorgorn, dvdg6566, shenxy13.

Спасибо:

Вам будет дано 8 задач, одна из которых будет разделена на простую и сложную версии, и 150 минут на их решение.

Мы надеемся что для вас условия покажутся короткими, задачи интересными и претесты будут сильными. Всем успешного раунда и повышения в рейтинге!

Разбалловка будет объявлена ближе к началу раунда.

Спасибо компании Райффайзенбанк за подарки участникам:

Призы для победителей:

  • 1-3 место = Беспроводная колонка

  • 4-10 место = Поясная Сумка

  • 11-20 место = Power bank

3HCumg.md.png

Случайные 50 участников, не вошедшие в топ-20, но решившие хотя бы одну задачу, получат:

  • Термокружки

  • Футболки от Райффайзенбанка

Несколько слов от команды алготрейдинга Райффайзенбанка:

Наша команда разрабатывает ультрасовременную HFT-платформу для торговли на валютном, срочном и фондовом рынках, основанную на математических, статистических моделях и машинном обучении, с высокими требованиями к latency и производительности.

Вы сможете:

  • поработать с задачами в таких областях как JIT-компиляция, устройство современных CPU;

  • поучаствовать в разработке высоконагруженных распределённых систем;

  • оптимизировать скорость исполнения кода и архитектуру платформы;

  • реализовывать низкоуровневые структуры данных и алгоритмы.

Если вам интересно пообщаться с рекрутерами и командой алготрейдинга Райффайзенбанка, заполните короткую анкету и расскажите о себе.

Заполните форму →

UPD: Разбалловка: 500 — 1000 — 1000 — 1500 — 1750 — 1750 — (2250+750) — 4000

UPD: Разбор!

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

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

As a tester, make sure to stay hydrated!

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

Absolutely strange prizes distribution, but ok. Waiting for nice contest!

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

score distribution?

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

All the author are from Singapore zoo. Why zoo?

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


But unfortunately it will reward us a big negative delta :'(

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

Ok it's not funny my bad

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

Because of prize there might be a DDOS. I Noticed many times, whenever there are prizes in CF round there happened a DDOS for sure.

Hope things will be fine this time. :)

Thank You

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

I just want T-shirt

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

Guys, list of participants looks weird.. There are lots of unrated users with the strange handles..

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

None of the japanese coders here have noticed the Arigato pun in the statement :(

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

CF has really given us a variety of rounds this year :o

We've had a polish round, indian round, russian round, chinese round, japanese round and now we're being blessed with a singapore round followed by a romanian round.

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

Nice timing for Indians, will have dinner on time which is unusual...

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

Hope none of the duplicate account get prizes.. Not because I am envious it's just that it would be undeserving... (And now don't downvote me from your duplicate account else I will understand this world is doomed).

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

Note that the start time is unusual.

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

Just curious about the facts on score distribution, I don't know--- what is the basis of scoring distribution? Why is scoring distribution announced before the round, and not before that? Also, do the rounds get tested without scoring distribution?

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

    We haven't announced scoring distribution because we're still discussing it :) I'm not sure about other round authors. Usually scoring will have some basis in difficulty, since we want to make sure that solves are rewarded fairly. As a result, obviously rounds must be tested without scoring distribution, since we get difficulty feedback (and thus basis for scoring) from testers.

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

It clashes with COCI can you delay the contest?

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

    These weekends: Codeforces Raif Round 1, SRM, COCI, AGC, Kickstart, CF Div2, Cook Off. Pls tell how to fit everything without intersections.

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

      Sounds like a problem statement

      There are multiple number of rounds these weekends, and coordinator antontrygubO_o needs to schedule the contests so that there will be no intersections! Please help poor antontrygubO_o figure out how to reschedule the contests! The first line contains N, the number of contests. For the next N lines, two inputs A and B, respectively the starting and end time of the contests will be given. Print the optimal number of...

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

      I think you missed today's ABC xD

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

Just like last week, I will go live just after the round ends to discuss my solutions https://www.twitch.tv/errichto

Also, that's the ugliest bluetooth speaker I've ever seen.

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

Google Translate told me that swag means goods that be stolen. How funny it is :)

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

Hope this contest will be a good contest UwU

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

Hey, I'm flattered! Can't skip this one now

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

[memem.jpg

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

Is contest rated ?

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

Let's start an errorgorn orz chain! errorgorn orz

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

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

    Codeforces ain't perfect, but when you compare it to other sites like codechef, it's considerably better imo.

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

    Is this supposed to mean that Mike does a bad job?

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

      I suppose not

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

      Do you believe world's best boss was bad at his work? That's offensive.

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

        i guess you got it wrong. my context was, after getting the same compliment for so many time, that will be Mike's reaction if this handshake happen in real right now

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

      I don't think being imperfect means you are doing a bad job. Every system will always have its faults, but codeforces is comparatively far better than anything else that is available.

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

        You went philosophical there. I'm just asking about the meaning of this meme. Michael in pic doesn't seem to know what he's doing.

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

nice

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

Are there remote jobs at Raiffeisenbank?

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

Ok. Finally, I have a chance to get a prize. Although it depends o my luck.

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

Will try for the random 50 as a noob :D

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

Another global round!!

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

I hope to solve all of problems

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

[Deleted]

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

I remember I read short statements XD

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

How to hack a problem i locked?

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

    Go to room tab at the top. Click on some submission. Read his/her code. If you believe you have a counter case, click on the Hack! button below.

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

      But why submissions is unclickable?

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

        maybe you are trying hack submissions of people not in your room, click on room on the dashboard and then try clicking on submissions of the people in there

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

    All dont works,ok?

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

Is there a way to delete an accepted submission? I got C accepted at 00:24, and then I thought I would test another solution, and it turns out the system only counts the last submission even if all of them are accepted. Please tell me why this is a thing, so annoying going down 2k places for something that doesn't make any sense

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

    Passing pretests during the contest does not mean it is correct. Therefore, sometimes a contestant may want to resubmit their solution which the pretests may not have caught their bug. This is why the rules are designed this way.

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

I am eagerly waiting to see the test case no:2 of problem "B".

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

Did I choose wrong problem?

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

Good contest!!

Amazing problem D!

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

    What was amazing about D? Seemed like mindless implementation to me. Unless there is some elegant way of solving it?

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

      Of course there is a elegant way!

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

What is test 4 in D ??

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

    well you can send your code to figure out where is your problem : ) (and dont send your submission link because ig seeing others code is unavailable rn)

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

      also, I think my code isn't clear enough to read :) so this is my solution

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

        well you can match the number 3 with 3 type of things. 1) the ones who is not match with any 2(free one). 2) all of the columns with number 2 -> just put a higher mark on top of the last one and another one with the same height. 3) with another 3.

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

        You can match a 3 with a 2.

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

    probably
    3
    3 2 1

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

what the fuck is pretest 3 of E

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

How to solve G?

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

How to do E?

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

    Let's consider you converted the first part into x1 part, the second one into the x2 part ...

    find out how much you can reduce from the final answer if you cut the i_th part another time(convert it from x_i part to x_i + 1 part)

    put the values inside a priority queue and do the best option each time

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

how to do b?

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

    Let's first iterate over the string and check if we have any cw or acw paths. Now, everytime we encounter an off path, we can mark it as a good path. If we encounter a cw path, we need to make sure that there are no other acw paths and vice versa. Also, another case is when the previous or the next path (leading to and from a node/snake) is off, we can mark this node as good.

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

Isn't E just about always taking the maximum number m and separating it into p = m / 2 and q = m - p for all maximums, which can be implemented by priority queue? If not, could someone explain why?

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

    1 3 8 you way : 4 2 2 the better answer : 3 3 2

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

      Hi my logic gives correct answer for this case...but i got WA on test 4.

      Submission

      My logic : https://codeforces.com/blog/entry/83730?#comment-710946

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

        n = 2, k = 2, array = {1, 9}, your answer : 50, the real answer 82.

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

    4 8
    2 4 5 8

    You algo give answer 49 (2, 2 2, 2 3, 2 2 4)
    But correct answer is 47 (2, 2 2, 2 3, 2 3 3)

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

    It isn't always an optimal option. For example for input $$$[2, 4, 10, 5]$$$ your algorithm would divide $$$[10, 5]$$$ into $$$[2, 3, 5, 5]$$$ while an optimal division would be $$$[3, 3, 4, 5]$$$.

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

      Ah, crap, I didn't realise we were allowed to do that. RIP my problem reading skills. I'll leave trying to become better at problem solving and go and start learning primary school english.

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

For E, to generate k carrots with minimum eating time, I derived that the $$$a[i]$$$ carrot should be split into $$$\frac{a[i]}{\sum_ia[i]} * k$$$ parts. But since each carrot should contribute to atleast 1 piece, I could not incorporate this fact into that. Can anyone provide insight on this?-

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

    Any final split is equivalent to splitting $$$a_i$$$ into $$$j$$$ pieces, which can be optimally solved by for any $$$j$$$. The final answer will be the smallest that has a total of $$$K$$$ times. The function for the difference between $$$j$$$ and $$$j+1$$$ is nondecreasing, so it's optimal to maintain the sorted list of current changes for each $$$i$$$ using a priorityqueue/set.

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

    Hi i was following a similiar approach can you have a look at my comment just below? https://codeforces.com/blog/entry/83730?#comment-710946

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

one stupid bug made me submit WA on E if my solution is correct I'll throw myself from the window

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

So,fast tutorial!!!Thank you.

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

I got an idea for E : Was trying to make all k numbers as close as possible to give the minimum sum of squares. This follows directly from the well known QM>=AM>=GM>=HM inequalities.

Take QM>=AM Here QM is sqrt((L1^2 + L2^2 + ...... + LK^2)/K) WHERE Li is the length of carrot we give to ith rabbit.

Also AM is = (L1+L2+L3+....LK)/K.

Now L1+L2+.......+LK is equal to sum of lengths of all carrots.

From here we can see the minimum value is [(sum of all carrots)/k].

I was trying to implement a similiar approach on these lines but got WA on pretest 4 what am I missing ? Also I saw Errichto solve it in the first 15 minutes after (in addition to solving A,B,C obviously) and knew it was some clever problem.

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

    We cannot combine the lengths of 2 carrots.. hence i guess your approach is wrong.

    CASE:

    4 4

    1 1 1 9

    The answer is 84

    but you will print 36

    which is wrong. I hope i have not read the question wrong xD

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

      Oh damn..I see...you right we cant combine...I knew we cant combine but still combined them idk.

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

Lol, F is a "segment-tree-beats" problem. https://codeforces.com/blog/entry/57319

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

I spent most of my time trying to solve D. I thought my construction was perfect, however, the judge didn't think so. T_T

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

Hey, is there anyway to solve Problem 'E' using Binary Search ? I tried to solve 'E' using Binary Search, but could not pass pretest 3 link to my code : https://codeforces.com/contest/1428/submission/95803093

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

I passed pretests for Problem C. But forgot to lock it. Does that count?

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

fastest editorial I've ever seen

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

    we've had fast editorials in most recent contests. It's a great improvement for codeforces i think!

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

I wish i could know what is the test case 4 of problem E....

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

It was a nice contest! Interesting Cool Problem Ststements!!!

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

I am so sad that my solution to problem D was wrong just because the grid numbering started from top. Couldn't change it as it was in last minutes of the contest.

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

For E is there a fault in logic if I try to binary search for the max height of the carrot such that the total number of carrots is K. then evenly divide the carrot heights and find the answer??

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

    Can you have a look at my submission and logic? https://codeforces.com/blog/entry/83730?#comment-710946

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

    Yes. Consider the case where you cannot actually evenly divide things, for eg

    4 5 100 100 10 1

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

    Yes, the optimum set of lengths might not be the one with the minimum maximum length. Consider the case n = 2 k = 5 and initial lengths 235683 and 675850 (sorry for the big numbers).

    The optimum lengths are 235683, 168962, 168962, 168963, 168963.

    However it is possible to get to 117842, 117841, 225284, 225283, 225283. And the maximum value of this sequence is smaller than the optimum one.

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

      Yes totally makes sense.. I know the other solution using priority_queue (didn't click during contest tho) but i couldn't find why this wouldn't work... bad dayyyy.. But good round!! Thanks for the help!! :D

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

Sample test cases in E were literally useless

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

    I think the samples were fine. They should just be there to make sure that you understand the problem properly. Creating your own nontrivial samples to test on and see if your algorithm works is something that's important and should be done by the contestant.

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

https://www.youtube.com/watch?v=g22-5e5xAGA

Watch Video Editorial of all problems

Also do watch , cp experiences of IIT Madras students

https://www.youtube.com/watch?v=8n12sCm0VUI

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

Great round!!! Fun Fun Fun!

P.S. Problem D 122+ system tests? O_o

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

why kosaraju algorithm gave TLE on the 2nd question????????

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

wrong answer on pretest 2

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

https://www.youtube.com/watch?v=VI5bL7Csc7w

Video Editorial of all Problems

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

Thanks for the contest. :)

I really liked problem D!

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

errorgorn, will there be a list of t-shirt recipients?

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

When your last attempt of saving your rating in last 10 seconds of contest got rejected by a semicolon

(It got accepted after fixing the semicolon)

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

Was log^2 with segtree intended to pass in F? I got TLE on recursive version and accepted (<500ms) on iterative one. If log^2 complexity can easily pass why not set the limit to 4s?

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

where we can know who is winner ?

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

As a human, I'm going to die without becoming a Grandmaster :"

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

Enjoyed This Round clear problems statements !!

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

Here's my solution to H:

Firstly for each ring choose a random number from $$$[-20, 20]$$$ and move it by such shift to make sure that nothing very bad will happen.

Now consider the rings in random order. Let's take some ring $$$i$$$. Move it clockwise and stop and the moment when the result decreases for the first time. After this, shift this ring counter-clockwise by one.

After such a phase all arcs are grouped. By grouped I mean that every two arcs either share their exact position or don't touch each other at all and the size of each group is at least $$$2$$$.

The number of groups is ofc $$$\leq 50$$$, but it'll be a bit less in average. Now it'd be nice to discover how the indexes are grouped. To do this, initialize a set of groups, initialy empty and consider all the rings (again in random order). When we consider ring $$$i$$$, then move it by one clockwise. Nextly, loop over all the existing groups, and for each of them take its representative and move it once clockwise and once counter-clockwise. It's possible to know to which group ring $$$i$$$ belongs (or if it's in a new group). Then shift ring $$$i$$$ counter-clockwise by one to fix the situation.

So we know how the rings are grouped, but we need to know their order (and distances). Take one group and it's representative. Let's move it clockwise and stop when it bumps into another group. In this moment iterate over all other groups, for each of them take one representative, move it once counter-clockwise and once clockwise. It's possible to know if we bumped into this group (and ofc we know the travelled distance). Then move the ring back to its group.

After this we know everything.

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

    fun fact: When code forces ran your solution during contests on systests, it gave "runtime error on test case 21" from too many queries.

    In the end, it ended with 14848/15000 queries, what a clutch rng!

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

    Why does the random shifting in the first step stop very bad things from happening WHP?

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

      Imagine having the results $$$0$$$ at the beginning. Wouldn't we need $$$O(n \cdot m \cdot \log(n))$$$ moves to move the arcs to the groups (even with an optimal order)?

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

        Not sure what you're asking. There's a one-parameter family of test cases of the form 0 (k times), 20 (k times), 40 (k times), ..., 20*ceil(100/k) (100%k times), and variants with distributions more skewed to the one end than the other.

        You're randomising the order in your "move clockwise until gap" phase to avoid a quadratic blowup when k is small. When k=1, for instance, each iteration of "move clockwise until gap" creates a new gap, giving you an expected O(mn log(mn)) moves or so. When k >= 2, though, the new gaps take a while to form. In particular, the first sqrt(n)-ish iterations won't create a new gap.

        Numerically, when k=2, I get a mean of 13060 steps and a standard deviation of 2500 steps just in the "move clockwise until gap" phase.

        I can imagine a tight arithmetic progression being bad too. Intuitively, random jitter shouldn't change the nature of an arithmetic progression instance too much. Why does the initial randomisation step help with this dynamic?

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

How much time does it take to update ratings?

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

    generally it take 3/4 hour in div1/2 contest... but in recent contest it's happening in short time. btw the rating has updated already.

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

Congratulations to prize winners!

Bluetooth speaker:

List place Contest Rank Name
1 1428 1 Radewoosh
2 1428 2 Um_nik
3 1428 3 kczno1

Bumbag:

List place Contest Rank Name
4 1428 4 ecnerwala
5 1428 5 littlelittlehorse
6 1428 6 300iq
7 1428 7 DmitryGrigorev
8 1428 8 ksun48
9 1428 9 neal
10 1428 10 maroonrk

Power Bank:

List place Contest Rank Name
11 1428 11 Benq
12 1428 12 Endagorion
13 1428 13 Errichto
14 1428 14 yosupo
15 1428 15 zeronumber
16 1428 16 Medeowex
17 1428 17 Muffinhead
18 1428 18 kefaa2
19 1428 19 gs18115
20 1428 20 tfg

Thermos Mugs & Raiffeisenbank t-shirt:

List place Contest Rank Name
57 1428 57 UnstoppableChillMachine
184 1428 184 Yousef_Salama
305 1428 305 LJC00118
526 1428 525 yuusanlondon
747 1428 746 reiracofage
804 1428 804 VivekUchiha
1126 1428 1126 siddhant1
1654 1428 1654 sh_mug
1841 1428 1838 sahilshelangia
1934 1428 1934 sojisan
1967 1428 1962 snowcubes
2107 1428 2105 kansal_2106
2625 1428 2625 Igorbunov
2762 1428 2757 sandeepkumar
2885 1428 2876 aniket.nsit.2000
3063 1428 3058 ab_dtu
3165 1428 3164 the_traveler_
3424 1428 3416 akash_garg
3735 1428 3732 gxy001
3894 1428 3893 adimiclaus15
4225 1428 4224 rsgt24
4226 1428 4226 agarwala2512
4418 1428 4418 Joe_Goldberg
4532 1428 4532 hritik_456
4549 1428 4548 aky121
4761 1428 4760 suresh_babu
5010 1428 5010 joker2
5176 1428 5175 avinashrao
5241 1428 5240 sauraviiitp
5311 1428 5311 pako1609
5321 1428 5321 coder_rohit_r
5431 1428 5430 FatemaKapadia
5459 1428 5459 Vishwa_02
5589 1428 5586 evilbegin
5795 1428 5794 Mohamed_El-sayed
6020 1428 6018 Park_Min_Young
6866 1428 6866 KaoYanGou007
7055 1428 7055 Moaaz-Mahmoud
7104 1428 7104 youcef
7216 1428 7216 viven0525
7410 1428 7402 1600-1700
7644 1428 7595 brytnispiers
7861 1428 7861 B1GGersnow
7898 1428 7861 Palak_8840
8055 1428 8050 Naheed28
8131 1428 8112 biswa_990
8475 1428 8466 srinidhi21
8551 1428 8533 mr.saylander
8813 1428 8813 phoenix_1402
9351 1428 9340 Liniou

Note that it is possible that some cheaters will be removed, but we will not recompute prizes unless one of them is a cheater.

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

Nice Job ! =)))))))

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

Why does this get WA in E ?

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

nice contest

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

I thought for a long time the problem B was a strong coupling component :v

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

Does someone know how to download full test cases for a problem? My C attempt gave WA at the second test set's case #92, but couldn't see what it is.

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

    nope..no way bro

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

      Ah that's sad.

      Essentially I tried to find a counterexample for my WA attempt, in which I consider the input string as "(some_number_of_B)(start with A and end with B)(some_number_of_A)". The middle part (start with A and end with B) is then reduced to contain only As or Bs, so the string is further reduced to (some_number_of_B)(some_number_of_A). I know the editorial solution is correct and simpler but struggled to find the counterexample for the idea above.

      Any suggestion is really appreciated!

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

        if there is any 'A' before 'B' that is the only time you need to reduce 'A'. on your example you not need to reduce the last (some_number_of_A). Because that is after (some_number_of_B). You can easily check it by bruteforce.:)

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

        You can create a brute-force solution and Random test generate. Then you can try to give the same input for both and check their output.

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

The contest was very well prepared and I actually had fun competing, so thanks to the organizer. But I have a doubt.

I am not sure this kind of contests should be rated for "strong contestants" (let's say IGM). Problems E and F were quite standard, and also G was just a variation on the knapsack-problem (it was not easy to understand the details of the associated knapsack-problem, but it was pretty clear that it shall be stated as a knapsack). I think this kind of problems are a bit too standard to play a role in the rating of high-rated contestants. Once again, I am not saying that this contest was not good, I am sure it was interesting and pleasant for 99,9% of the participants and therefore it was a very good contest (clear statements, nice problems, good pretests and good tests... high-quality overall). I am wondering whether it would be better to make it clear in some way (before the round) how original the problems are (adjusting accordingly the rating range).

I am implicitly suggesting that a system similar to the AtCoder one (only AGCs are rated for strong contestants) might be beneficial also for Codeforces. In general, I feel that what I consider interesting is quite different from what a contestant with rating 1910 considers interesting (and I guess that this difference is even bigger for contestants stronger than me) so it is strange that we have exactly the same set of rated contests. The main reason is that there are many nice problems (for example E and F of this round) that are incredibly cool for a candidate master but quite standard for an IGM (in the same way that sorting an array in $$$O(n\log(n))$$$ is incredibly cool for a novice, but standard for anyone who knows a bit of stuff).

I would like to hear the opinion of some strong contestants... maybe I am the only one with this opinion (and maybe noone will ever read this late comment).

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

    Hi, thanks for the feedback!

    I'm not exactly a strong contestant but I do agree largely with your comments. I'd say the problems E and F are kind of classic at higher levels, and that the contest is easier than what you'd expect from a normal div1.

    About problem G, I didn't think that it was that standard when I set it. That's probably because I found the observation about 0,3,6,9 the hardest part of the question. So while the knapsack part is classic, I found the hardest part of the question the ad hoc observation at the start. Also interestingly no tester solved G during contest time (although some almost solved it).

    About differentiating "original" and "classic" contests, I think it'll be a good idea. However, I'm not sure about the feasibility since usually problem setters don't have much flexibility in choosing the type of problems since we don't have enough good problems to play around with the style of the contest.

    An idea is to look at the problems after they're proposed and then decide which category it falls under? Random thought I had: what if combined rounds are more of the classic type and have a rating cap. Rounds which are div1 + div2 (5/6 problems each) be more of the original type (at least for div1), and possibly harder now.

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

      I agree that problem G was less standard than E, F; I mentioned it because if G had been very original it would have made the whole contest original. Regarding "no tester solved G during contest time". I am not claiming that G is easy, in fact it is not. But originality and difficulty are almost orthogonal properties.

      Regarding your proposals and comments on how to solve the issue... I simply have no opinion. I don't know whether combined rounds should be capped, or if separated rounds should be capped (or if the capping should be independent of the type of round) or if the threshold for div1 should be raised.

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

Is anybody able to access the editorial right now? It was available an hour ago but now when I click on the link to editorial, it says "You are not allowed to view the requested page" and redirects me to the last opened page on codeforces. Please confirm if you are facing the same problem.

Upd: Fixed Now, Thanks

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

errorgorn I guess there is a glitch with the editorial, It says the editorial is not accessable. Please check once

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

Help wanted :
For problem E, I binary searched on the length and found out the maximum possible length in which the carrots may be divided. It'll be great if someone can explain me why its wrong.

https://codeforces.com/contest/1428/submission/95793574

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

    Who's this cutie pie muah muah

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

    Consider splitting 100 into three slices.

    When you take a cut of size 33, you split it into 3 '33' length cuts and 1 length '1' cut.

    33 33 33 1, and hence you say this is suboptimal and you proceed to 34, which results in this splitting: 34 34 32 which you falsely claim optimal. (Your answer will print sigma square of this array)

    However, you could have split it as 33 33 34, which is a case your code doesn't test. (Turns out this is the most optimal split)

    i.e it is not optimal to always take arr[i]/mid portions along with arr[i]%mid extra. sometimes merging arr[i]%mid with another is more optimal.

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

    ..