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

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

Привет, Codeforces!

Я рад пригласить всех на Codeforces Round 569 (Div. 1) и Codeforces Round 569 (Div. 2), которые состоится завтра, в пятницу, 21 июня 2019 г. в 19:35. Раунд будет рейтинговым для обоих дивизионов.

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

Свои задачи на раунд предложили Иван ScreaMood Фёдоров, Кирилл kirillbogatiy Бессонов, Мухаммаджон Mr.Hakimov Хакимов, Федор ---------- Ушаков, Фёдор Kuyan Куянов и я, Дмитрий gop2024 Григорьев.

Раунд готовили мы, Дмитрий gop2024 Григорьев, Фёдор ---------- Ушаков, Дмитрий TheWayISteppedOutTheCar Пискалов и Мухаммаджон Mr.Hakimov Хакимов.

Спасибо Ильдару 300iq Гайнуллину за отличное координирование раунда, Sooke Sulfox Gnar, Xiuhan sunset Wang, Ziqian TLE Zhong, Junzhao FizzyDavid Yang, Jiaxuan samjia2000 Gao за тестирование, а также Михаилу MikeMirzayanov Мирзаянову за великолепные платформы Codeforces и Polygon!

В каждом дивизионе будет предложено 5 задач и 2 часа на их решение. На протяжении раунда вы будете помогать ученикам одной обычной московской школы в их обычных повседневных делах. Разбалловка раунда будет традиционно объявлена ближе к раунду.

Прочитайте условия всех задач. Всем удачи и высокого рейтинга!

Ждём вас на контесте!

UPD Разбалловка Div.2 раунда стандартная — 500-1000-1500-2000-2500

Разбалловка Div.1 раунда — 500-1000-1500-1750-2250

UPD2

Вот список победителей:

Div.2

  1. PSMaoTheKingOfAzerbaijan

  2. atacan

  3. Shayan.Kashefi_A

  4. LiPro

  5. BrutBurger

Div.1

  1. Radewoosh

  2. ACRush

  3. ecnerwala

  4. mango_lassi

  5. neal

Наши поздравления победителям!

Разбор задач

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

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

We hope for a good contest.

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

The whole IOI Chinese team tested the round + 300iq coordinated it.

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

Ура, вроде авторы преследовали цель составить нормальный контест, а не ознакомиться с системой Polygon. Завтра убедимся :)

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

The whole IOI Chinese team tested the round!!!**- **

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

Round tested by Chinese.. Hope it will give me an unforgettable experience :)

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

" During the round you will be helping for pupils of one usual Moscow school." What does this mean?

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

Xuihan sunset Wang

I think Xuihan is a typo. You may mean Xiuhan.

(Sorry for my poor English)

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

IOI Chinese testers team lol

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

A 5 problem contest after long days

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

Nearly 12 p.m at my place. But all love for programming, I will try my best.

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

helping kids, noble task.....who's gonna help me help them......lol

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

time to think

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

Best of Luck for your first contest as a problemsetter.

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

Whole people wrote the same comment "ioi Chinese testers team" What is happening!

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

I wish positive rating for every participant :)

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

In fact, Sulfox's name is not Sooke Gnar. However, he loves Gnar —— The Missing Link very much.

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

один из авторов контеста исчез(((

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

This time is not friendly to Chinese players

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

Time changed from 19:35 UTC to 22:05 UTC.
Time increased = 150 minutes.
May we also get +150 rating today.

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

New Codeforces round, new chance to fall!

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

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

So lucky that the contest starts right before I get home

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

A delayed contest has never been good for my rating.

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

Разбалловка раунда будет традиционно объявлена ближе к раунду. Собственно, где? UPD: во

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

UPS is needed.

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

What is the score distribution?

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

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

Разбалловка?

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

When reading the comment section ends!!!

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

System Test :(

a

->How 30 minutes before contest felt!!

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

Now we have Caseforces!

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

The pretest of problem B is BRILLIANT, because I have just made the first TWO Successful Hacking Attempt in my life !

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

How to solve D?

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

    A 6x6 can be traversed like this, other cases are also analogous. You can easily show that this method does not use the same vector twice.

    1	23	25	36	14	12	
    3	21	27	34	16	10	
    5	19	29	32	18	8	
    7	17	31	30	20	6	
    9	15	33	28	22	4	
    11	13	35	26	24	2
    

    But most probably this is not the only solution. There can be other ways as well.

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

      Is it the only simulation or any proper mathematics.

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

        You could call it intuition.

        First check whether you can always do it for some $$$1$$$x$$$N$$$ grid.

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

        Using that method, it's easy to show that once you take a certain vector, you never use it again. That's because the squares on which you could use that vector have already been visited before.

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

      what if columns are odd sized?

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

      nice!

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

    Starting from (1, 1), move to (n, m), then (1, 2), then (n, m-1), and so on till (n, 1). Then go to (2, 1), then (n-1, m), then (2, 2), then (n-1, m-1), and so on till (n-1, 1). Keep repeating this process. If you reached a row i where row i == n-i+1. Then just from (i, 1) move to (i, m), then (i, 2), and so on till you visit the whole row.

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

    For solving D, i converted it into 1-D array and then using two pointer i solved it . For eg . 2 3 ==> 2*3 = 6 we are firstly in 1,then i will visit 6 then 2, then 5, then 3 and so on .

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

Is div1E an exercise on the proportional cake-cutting + optimizations to pass $$$O(n^2\cdot\log{n})$$$ queries?

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

What is in pretest 9 of problem B Nick and Array?

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

    I got stuck on the same pretest :(

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

    Try 2 3 4. Answer should be -3 -4 4

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

      how did you solve B?

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

        The only way to increase product is by increasing |a| for each a in array. Only positive numbers can be increased in magnitude by the given method i.e. 4 becomes -5 so |-5| > |4|.

        So first change all positive numbers like this including 0 to -1. Now all are negative. If even sized array, we cant do better. If odd sized change the largest negative number like -100 to 99. This makes product positive

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

          what is the logic behind taking the largest negative number in magnitude instead of smallest negative number in magnitude

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

            When you change an element with value -x from negative to positive it becomes x-1. This multiplies the magnitude of the product by (x-1)/x. You want this to be as large as possible, and it gets larger as x gets larger.

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

      No I don't think so . My answer is -3 -4 4 according to 2 3 4. I think it is 9 -4 -5. the answer should be 9 -4 -5 .

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

    take the biggest negative number instead of least.

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

      I was making this mistake, can you prove your greedy approach ?

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

        if you are multiplying 2 numbers x and y, such that |x| > |y| then you can visualize it in 2 ways, first adding y x times and second adding x y times. Now if you decrease x then you are just removing 1 y and if you decrease y then you are just removing 1 x. Now you can see which one is optimal.

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

please help me to identify my mistake in problem B https://mirror.codeforces.com/contest/1180/submission/55894819

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

.

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

shit that m1 range i took it int got wrong

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

I hope to finally become a candidate master :).

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

I'm just gonna skip B in future rounds, C is almost always easier for some reason.

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

    The logic I used for b was much simpler than c imo, (convert all to negative and then convert the least to positive if n%2==1).

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

Very nice and enjoyable problems!

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

What concept was involved in Div1C ?

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

    Hint: imagine it as brackets

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

    Consider suffixes of cummulative frequency of both dishes and people.

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

    Can you please expand a bit on your solution, because I couldn't think of something with these hints. Thanks!

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

      Let $$$fstudents(i)$$$ be the frequency of students with money equal to $$$i$$$.
      Let $$$fdishes(i)$$$ be the frequency of dishes that cost $$$i$$$ money.

      We are looking for the greatest j such that $$$\sum_{k = j}^{1000000} fdishes(k) > \sum_{k = j}^{1000000} fstudents(k)$$$.

      We can consider $$$dif(i) = fdishes(i)-fstudents(i)$$$. We want to find the rightmost index $$$i$$$ such $$$\sum_{k=i}^{1000000}dif(k) > 0$$$.

      We can have a segment tree that stores the value of maximum suffix sum of $$$dif$$$ in range. The updates are just adding and substracting 1 from leaves of the tree. We can answer queries in $$$ O(Qlog^210^6) $$$ by binary searching to find the first $$$i$$$ such that the maximum suffix sum is greater than 0. We can do this faster, in $$$O(Qlog10^6)$$$ by the method of descending the tree. I hope i explained it clearly.

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

        Thanks Charis02

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

        Hey, I think I’m missing something simple. Why is it sum(dif(k)) > 0 instead of sum(dif(k)) < 0? If the sum is positive for some i, doesn’t that mean that we have more students than dishes for that i, not that there’s a dish we can take.

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

          Yes you are right, sorry. I meant to write $$$dif(i)=fdishes(i)-fstudents(i)$$$ . Thanks,I'll correct it.

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

        Hey, one doubt. If you just update the leaves in the seg tree will it be suffice ? Dont we need to update all suffixes of greater length than this ? I.e lazy prop. Bcoz if you just update one suffix then the suffix greater than this length won't have updated value and will have one student or dish less ?

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

          No, because by updating the leave you update all ranges containing it (standard segment tree update). You don't need lazy prop because you update only one leaf not a range of them.

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

          code_kit

          By every node $$$nd$$$ storing the maximum suffix sum of $$$dif$$$ in range, Charis02 means suffix with respect to $$$nd$$$, not the whole array.

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

Can we actually solve D like this or is it just luck?

55894627

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

Why is there a hacking phase? I suppose only Educational rounds have that phase.

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

Delay in System tests?

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

Один из худших раундов за последнее время

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

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

Сколько элементарных операций в секунду могут выполнять сервера на cf?

Квадратичное решение 55897039 к задаче 1180C - Валера и дек на max-тесте при попытке взлома отработало за 3244 мс. Я, конечно, понимаю, что TL в задаче 6 секунд, но все равно неожиданно.

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

Is there a hacking phase? I suppose only Educational rounds have hacking phase.

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

It happened to me for the first time, My solution was hacked midway between the contest, I tried to figure out the mistake but was sure it was correct. After some time I got a notification that my solution was correct :D

Link : https://mirror.codeforces.com/contest/1180/submission/55886651

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

It is really a good contest.

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

It happened to me for the first time. My solution was hacked midway between the contest but after a while I got a notification that my solution was correct.

Link : https://mirror.codeforces.com/contest/1180/submission/55886651

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

    I hacked you during the contest with the test case:

    3
    0 -1 -1
    

    After pressing the hack button, I found that it should be an unsuccessful hacking attempt but it turned out to be a successful one

    I thought it's quite strange and I've reported this to problem setters during the contest Few minutes later they replied "under investigation", and your code is Accepted, my hack became an "ignored"

    Actually I'm not sure what's going on lol

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

      Thanks a lot buddy, You sacrificed 50(150) points just for honesty. Cheers.

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

      But the setters might be having similar system tests as well, so setters please be careful of your system tests for Div2 B

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

      We had a little bug in our checker and it didn`t work correctly when the answer is $$$0$$$ and the jury answer is different from the participant answer as a multiset. We are sorry for the mistake.

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

      Hello there.

      Sorry, that was definitely my fault, because as a coordinator I missed this case with $$$0$$$ in the checker. There were no similar tests in other hacks or in systests, so everything should be fine.

      My apologies to shpvb, who suffered from my mistake.

      I will be more attentive to these kind of things next time, sorry again.

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

      Also, thank you for your honesty! Without you, we wouldn't notice this bug.

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

I think this works for E, but I wrote too many bugs so couldn't get it to work in time :(

Edit: 55909022. Turns out some constant optimization was required too, so I wasn't that close

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

I think can't pass D because of lines:

if (n > m) {
swap(n, m);
}

I did not find the anti test. Please count my solution as correct if this is the case :(

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

    gop2024 please look this. I know it looks stupid but I don't want to lose points because of this.

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

    Give me more minuses. My logic was correct. If it was n <= m code will passed. You are ratists even did'nt read what I wrote. I wish your solutions failed due to checker get Compilation Error on test 99 and etc.

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

      Lol. If you swap lines, you swap coordinates. So you should also swap coordinates in your algorithm

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

Why the system test still pending?

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

everyone should be given positive bonus rating because of unexpected power cut occurred before start of exam ..... it mentally affected many people ,hence not giving their best output in exam.....

note: if some one don't like it ,kindly don't down vote it as i already have negative contribution, just ignore this comment and move on.

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

Any hints for Div1 D?

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

How to solve DIV2 E ?

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

When your rate reach the buttom look at the bright side there's one way to go (me trying to motivate myself after my stupidity streak this month)

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

Div2B have bad pretests.

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

    And a lot of people had wrong solutions, FeelsBadMan

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

    Strangely enough, almost always in Div. 2 problem B has the worst [pretests passed / accepted] ratio. Not sure about the reason for this phenomenon.

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

    It's a comparative thing. Before system test, my standing was 618, after system test, it's 557. So if you avoid all pitfall but others not, you can have a better standing. The contestants who found the pitfall and avoided it should have an advantage over those don't.

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

Good old five-problem contest. Skill over speed. Thank you.

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

    I like this grand old way of 5 problems. I personally don't enjoy subtasks and contests which has very large problems like 7 — 8+. less and good questions are good to stay you focus during the contest, rather than moving here and there to solve subtasks.

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

    I doubt it's possible to make skill over speed contest if it lasts less than, at least, 2h30m. When contest lasts a bit longer even if it has more problems in it, there's much more bigger probability that you will reach problems you can't solve because of your skill and not speed before the contest time ends.

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

Hackforces

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

Please make pretests not so strong next time :)

It seems like there are no fails on systests at all

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

    Are you really suggesting they should intentionally make pretests weaker?

    Imagine failing to system tests because the specific corner case your code didn't handle was removed from the pretests, while others fail pretests and can fix their code. Yeah, no thanks, more rounds like this please.

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

      I suggest that pretests shouldn't cover, like, everything.

      So it's more about they shouldn't make them intentionally strong.

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

    If you are bored with nothing to do, I wouldn't mind knowing what's wrong with my D. :)

    EDIT: I just mean I want someone to debug my code :)

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

      Well, it clearly says that.

      wrong answer 1st numbers differ — expected: '204997350968', found: '204998250971'

      You output incorrect number.

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

        Brilliant explanation on how the WA verdict works! You should totally write a blog on that.

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

      Your code only computes the correct answer for paths through the first centroid found. This seems to suffice for almost all cases (as Radewoosh mentioned), but not always when the tree has two centroids (which test case 103 satisfies). Try comparing my getAns function with your get_subtree function.

      EDIT: As saketh mentioned, there are also counterexamples where the tree has only one centroid.

      (mine) 55894131

      (yours) 55893926

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

        Can you please tell if my solution for D is correct?
        The final structure will look like a cycle with branches coming out of the nodes which are a part of the cycle. Let there be 'x' nodes in the cycle and size of the subtree going out of these x nodes be a_1,a_2,...,a_x. So now there will be an extra path from any node in one subtree to other subtree. Thus there will be a_1*(a_2+a_3+...+a_x) + a_2*(a_3+a_4+...a_x) +...+ a_x-1*(a_x) extra paths. This can be written as: ((a_1+a_2+...+a_x)^2 — (a_1^2+a_2^2+...+a_x^2))/2 . First term is equal to n^2. So we need to minimize 2nd term.
        So now choose arbitrary root. Let there be a node 'u' with 2 of its children u_1,v_1. let say we want to connect u_1 , v_1 then 2nd term of above equation will become u_1^2+v_1^2+(n-u_1-v_1)^2 . Similarly if want to connect a child of u_1 say u_2 to v_1 then the 2nd term will become u_2^2+(u_1-u_2)^2+(n-u_1-v_1)^2. This expression is less than that if we connected u_1,v_1. So we can say by induction that for any node 'u' we will want to connect 2 of its leaves such that their lca is 'u'. Now if sizes of subtree of node 'i' is denoted by s_i then we can define 2 values for each node: d_i=min(d_i,d_child+(s_i-s_child)^2) and f_i=d_i+(s_i)^2-2*n*s_i. We can show that the second term of above equation can be written as:
        if a node 'u' has only one child: n^2+f_child.
        if a node 'u' has more than one child: n^2+ f_child1 + f_child2 +2*(s_child1)*(s_child2).
        Now our equation was telling us number of extra paths on adding an edge, so it must be positive and for any node 'u' if we subtract the second term from first we get -(f_child) or -(f_child1 + f_child2 +2*(s_child1)*(s_child2)) respectively which means that f_i will be negative. So for any node if we choose 2 of its children such that their f_i are smallest among all children we can get the max number of extra paths added. So we find this for all nodes and find their max.

        My solution:55909246

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

    Better call GreenGrape

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

Nice round. I liked it.

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

I have only looked at problem C so far, but it is already enough for me to conclude that it was a brilliant round. Thanks guys!!!!!!!!!!!!

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

Wasn't Div2-C easier than Div2-B ?

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

System testing completed good rate for everyon.

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

pctr

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

I've never waited so long for systest/rating changes!! Good round tho :-)

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

Can someone help me in Div2 problem B.

I am getting wrong answer for test_case#60.

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

Кто-то еще сочувствующе посмеялся с начала задачи B? :)
"На свой 5 день рождения Коля получил от мамы в подарок новенький массив.."

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

11 and counting :P

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

can someone help me in Div2 problem B.

I am getting wrong answer in test_case #60.

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

Any hints for div2C? Thanks :)

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

Is this true that in d1d optimal path will contain the centroid of the tree? Does anybody have a proof/a counterexample?

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

    What do you mean by optimal path? Could you share some hints about how to solve the problem?

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

      By optimal path I mean the path between vertices which will be connected with an additional edge. The hint is that if we group the vertices by the vertex on the path which is closest to them, only the sizes of the groups matter somehow (you have to minimize the sum of squares of these sizes).

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

    Hmm, don't know about centroids, but there always is an optimal path which connects two leafs.

    (Guess it's obvious though)

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

    It's false. This type of graph produces a counter-example:

    There are $$$N = W + 2T + 2$$$ nodes. When $$$2(W + 1) > N$$$, $$$C$$$ is the unique centroid.

    The orange edge produces an optimal path going through $$$C$$$. The number of simple paths when adding it is $$$2 { N \choose 2 } - { T + 1 \choose 2 } - { W \choose 2 }$$$.

    The blue edge produces $$$2 { N \choose 2 } - { W + 2 \choose 2 }$$$ simple paths. Any choice of $$$W$$$ and $$$L$$$ such that $$$C$$$ is the unique centroid and $$${ W + 2 \choose 2 } < { W \choose 2 } + { T + 1 \choose 2 }$$$ produces a counter-example.

    $$$W = 17$$$, $$$T = 8$$$ is one such choice.

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

    After reading socketnaut's comment, I wondered that what is the minimum case which all of optimal path does not contain any of the centroid of the tree.

    I wrote a brute-force code, and proved that there is no such case which is $$$N=3,4,5,6,7,8,9,10$$$ and $$$11$$$. Seems like socketnaut's counter-example ($$$N=35$$$) could be the minimum.

    Source Code of Brute Force: Link

    UPD: Finally I realized that socketnaut's second comment means my user photo :)))))))

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

      :) "Who is this man and why is he trying to sell me this graph."

      I have some intuition for why this form might produce the smallest possible. Adding leaves to $$$C$$$ is the best way to make it be the centroid without incentivizing the best path to go through $$$C$$$. Or to put it a different way, if the best path doesn't pass through $$$C$$$, we can reformat all of the subtrees that are below $$$C$$$ and away from the best path into leaves attached directly to $$$C$$$. Such a change doesn't worsen the best path and doesn't improve the paths going through $$$C$$$.

      Going to the best path, suppose that the blue edge connects some vertices $$$u$$$ and $$$v$$$, and $$$\ell$$$ is their LCA when the tree is rooted at the centroid. If either $$$u$$$ or $$$v$$$ has a "worse" path coming down from $$$\ell$$$, the orange edge can always connect the centroid to the one that is better. So, we need them to be symmetric. Minimizing the path between $$$C$$$ and $$$\ell$$$ and making the trees from $$$\ell$$$ down to $$$u$$$ and $$$v$$$ linear gives the best configuration.

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

My solution to Div. 2 D TLEed on TC74 when compiled with MSVC++ while the same exact solution ran in 280ms when compiled with G++. A custom test shows that my solution ran in 1029ms when compiled with MSVC++. Is MSVC++ really that much slower than G++?

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

    Ah that's sad. Probably the constraints were too tight. Even I got TLE & afterwards got an AC just by replacing all cout's with printf.

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

      Agreed. I was only able to get AC using VS by using printf, not even cout with ios_base::sync_with_stdio(false) ran in time, which I previously thought was only slightly slower than printf. I can't think of why the constraints need to be this tight, since as far as I can tell there isn't an easier solution that needs to be prevented from passing.

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

I am not sure if this is a right place to put my idea/complaint . I am from Beijing,Chine, and in the contest last night , I refresh codeforces.com and m2.codeforces.com for 25 minutes only to find a series of "This site can’t be reached". And this situation is common before. According the comments following the blog of Round569 , people out of China didn't encounter this annoying process. So , I write this wanting you to know what happens in China and hoping for a response. Maybe you buddies can help me to let worker in codeforces know the situation? :)

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

I should try this round because I think I can solve all problems in div.2 , but I am afraid that I will get lower rating. Maybe I should be braver.

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

    In the short run, your rating may fluctuate. But in the long run, your rating converges to your skill. Participating and practicing more improves skill. So just calm down and focus on the long term performance. That's how I convince myself to not afraid of a drop in rating and participate as many as possible. Hope that helps.

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

Hi. So I was wondering about my submission for Problem B here.

The verdict says 'wrong answer multiply isn`t maximal possible', but not something like 'expected X but found Y'.

So, I just want to know whether there is some issue here? I don't see where my submission is wrong

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

    I have also done the same mistake , that you dont have to choose only positive max element. but negative max element (in absolute value) can be better choice .

    Eg -5 2 3 Here answer will be 4 -3 -4

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

      Oh no! I messed up the compare function. Should have payed more attention while coding it.

      UPD: Changing compare function still doesn't work sadly :(

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

Again Editorials are late.

This is actually becoming very common these days. Earlier the editorials were published right after the system tests, but now they come really late.

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

the editorial flies away~~  pigeon is walking~~~

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

So where is the Editorial

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

So where is the Editorial

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

if my submission got hacked, then how to know for which test case the submission is wrong??

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

How to solve Div 2(Problem E)??? Anyone..thankyou

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

Problem D: I submitted Submission 1 but it was showing 'TLE'. But then I again submitted by just changing 'endl' to '/n' and it got submitted. Accepted Submission. Please explain why this happened?

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

    endl always causes a flush oepration, "\n" does not!Thats why endl is slower.

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

How to solve Valeriy and Deque? I have used this code (python) but I am getting TLE in case 4 ~~~~~ n, q = map(int, input().split()) s = list(map(int, input().split())) query = [] for _ in range(q): query.append(int(input()))

if  q > 0:
    for i in range(1,query[-1] + 1):
        if i in query:
            print(s[0], s[1])

        if s[0] > s[1]:
            temp = s.pop(1)
            s.append(temp)
        else:
            temp = s.pop(0)
            s.append(temp)

~~~~~ Please any help will be appreciated

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

    Queries can be up to 10**18. Don't you think it is kinda big number, u know?

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

      Yeah. Could you suggest a better solution? I saw various accepted solutions but its hard to understand the logic of whats happening there

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

        After make the biggest number in the first place... Guess what will happen then.

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

          After making the biggest element first all the element in the second place will move to the last position. And that would be a cycle. I under stand the part when the query is smaller than the position of biggest number in the list. But when the query is bigger than that no matter what the first number will be the biggest number but I do not understand a way to figure out second position number.

          I have seen the editorial and don't understand how they got the index position of the second position number.

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

Can someone prove the correctness of 55895158 (Div.1 D)? I calculated the answer using a method similar to the tree diameter. I just guessed it but don't know how to prove it.

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

May I get the editorial for this contest? gop2024 for Contest #569 (Div.2)

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

Can someone help me understand div1 D? I can't see why in the first sample case the answer is 2. Won't he just add an edge between both nodes, then there can only be one simple path containing both edges that goes to both nodes? Otherwise it would break the rule "we consider only simple paths of length at least two".

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

    Ok, after examining the second sample case I get the idea that "length two" means two nodes and not two edges, is this proper? And I assume "loop" refers to self-loop?

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

Can we get Editorial for Contest, please? Thank you.

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

Can someone help explain their thought process for Div 2 D?

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

All the questions were long,except problem a.

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

is there a solution for problem C ?