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

Привет, Codeforces!

В 08.01.2023 17:35 (Московское время) состоится Educational Codeforces Round 141 (Rated for Div. 2).

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

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

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

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

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

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Harbour.Space

Привет, Codeforces!

Мы рады объявить о втором буткемпе по программированию «Hello Muscat 2023», продолжении серии буткемпов «Hello», организованном Harbour.Space University в сотрудничестве с PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club и Codeforces!

Довольно впечатляюще, не так ли? Пришло время глубже погрузиться в мир соревновательного программирования с 8-дневным интенсивом Hello Muscat 2023. Он будет проходить в Маскате, Оман, и онлайн с 8 по 16 марта 2023 года, доступны оба формата участия.

Наш тренерский состав сочетает в себе талант и опыт, в нем участвуют чемпионы мира ICPC, победители и финалисты, а также легендарные имена из области соревновательного программирования: Михаил Мирзаянов MikeMirzayanov, Егор Дубовик 244mhq, Артем Плоткин Rox, Максим Обозный MaksymOboznyi и Николай Будин budalnik.

Буткемп будет разделен на три дивизиона:

  • Дивизион A. станет зеркалом Петрозаводского лагеря программирования. Подходит для команд, которые уже прошли квалификацию на Финал ICPC или стремятся к этому.
  • Дивизион B. Разработан, чтобы помочь командам подготовиться к следующему сезону региональных соревнований ICPC. Подходит в качестве введения для команд и студентов, которые только начинают свой путь в мир ICPC и соревнований по программированию в целом.
  • Дивизион C. Предназначен для новичков в мире соревновательного программирования.

Типы участия: очное и онлайн

Мы считаем, что участие в нашем буткемпе должно быть доступно для всех команд, где бы они ни находились, и именно поэтому мы сделали очную и онлайн-формы участия. Скидка 20% на раннее бронирование предоставляется университетам и участникам, которые зарегистрируются и оплатят до 31 января 2023 года.

  • Очное:

Цена: 1500 € — 1200 €

Что включено: обучение, контесты, доступ к записям лекций, проживание в течение 9 ночей в 4-звездочном отеле Mysk, завтрак и обед, трансфер из гостиницы к месту проведения буткемпа каждый день, развлечения и приветственный подарок.

  • Онлайн

Цена: 100 € — 80 €

Что включено: обучение, контесты и доступ к записям лекций.

Узнать больше о Hello Muscat 2023→

Удачи в раунде,

Harbour.Space University Team

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

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

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

Best of luck everyone.As a participant I am going to give best in this contest.

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

Best of luck everyone . As a participant I am going to give my best in this contest.

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

Good luck everyone. Hope i can solve problem C

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

    I didn't solve the problem C

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

      did you solve b?

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

        Yes! I solved it when there were 5 minutes left before the end of the competition.

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

          B was quite hard for a Div 2 B problem. Man it's really hard to improve in competitive programming, I feel like im stuck. Being stupid also doesn't help.

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

            Only two words: More Practice

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

              Only one word: repeat

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

                Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?

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

              Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?

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

                Idk but one thing I would say Enjoy the process!

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

                This is a good goal. I would also like to go up to 1600 a year. And I understand that this is real if you regularly work and solve problems not only that are easy for you, but also that are higher than your current level, in order to learn how to solve them.

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

Hope to get good rank at contest which I am not able to do so in previous rounds

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

;)

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

I am sure everyone will be successful in this competition. You can! Good luck!

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

    I also wish everyone that no one could hack their solution! I wish everyone +100 or more than 100 to the rating of everyone!

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

      Mathematically its not possible because if you want to get + rating changes some one has to get the negative.

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

i still remember awoo's favourite problem

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

Good luck to everyone!!! (I hope that I can solve at least one problem :>)

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

will try to become specialist.

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

Good luck everyone!

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

Wow, I'm back after a year and comments are as cringe as ever. Joining in.

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

Good luck everyone . Hope I can solve at least one problem.

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

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

good luck have fun

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

Hope to become cyan, and good luck to everyone in this contest.

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

hmm, why I has the conbutrition? can anyone explain??

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

This Contest is very beauty-full

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

me after solving a&b : Your text to link here...

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

me after solving a&b :

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

Classic Mathforces

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

oh yes I saved the previous non-blue profile pic somewhere else and I am getting to use it now

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

    I should find a matching green one aswell, given the amount of times I have dropped right after reaching cyan T-T

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

Any proof for B?

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

    Pretty straightforward after trying to solve for a 1d array instead of matrix

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

    There are $$$n^2-1$$$ possible differences $$$(1\dots n^2-1)$$$. And the chain $$$1, n^2, 2, n^2-1, \dots, \left\lfloor\dfrac{n^2}{2}\right\rfloor, \left\lfloor\dfrac{n^2}{2}\right\rfloor+1$$$ (chain ending correct modulo parity), contains all differences and has $$$n^2$$$ terms, for $$$n^2-1$$$ differences.

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

    I code brute force as the max difference can be (n*n-1). Try to create all differences from (n*n-1) to 1.

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

    If I have understood it correctly, the proof is:

    Let's solve this problem for a 1D case, then we will extend it to 2D. Say, n = 3. So, the values are: 1, 2, 3, 4, 5, 6, 7, 8, 9 (from 1 to n*n) Here, the minimum value is 1 and the maximum value is 9, so, no matter what, the absolute difference will be at most 8 (when |9-1|) and the minimum absolute difference will be 1 (when |9-8|), and the other values will be in between. Our target is to maximize the total various types of such absolute differences. If we order the numbers in the following way: 9, 1, 8, 2, 7, 3, 6, 4, 5 then the target can be maximized. As in this case we are getting these all kinds of absolute differences we could ever get from them taking side-adjacent values. That are: 8 (i.e, |9-1|), 7 (i.e, |8-1|), 6 (i.e, |8-2|), ..., 1 (i.e, |5-4|)

    Two numbers in an array are side-adjacent when they are positioned one after another either in the same row or in the same column. For example, for a 5x5 matrix, the indices are as follows:

    (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) 
    (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) 
    (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) 
    (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) 
    (5, 1) (5, 2) (5, 3) (5, 4) (5, 5)
    

    So, the side adjacent to position (3, 3) are (3, 2), (3, 4), (2, 3), and (4, 3) positions. We have to find all possible side-adjacent positions for each position and take absolute differences of corresponding values and count how many unique absolute difference values we get. And obviously, we have to find an arrangement in such a way, that the number of possible such values maximizes.

    Going back to 3x3 cases (for better manageability), a deterministic solution is to arrange the 1D array (which maximizes the result in 1D case, i.e: 9, 1, 8, 2, 7, 3, 6, 4, 5), in a zig-zag fashion. So, the solution is:

    9, 1, 8
    3, 7, 2
    6, 4, 5
    

    which follows the following pattern:

    --->----
           |
           v
    ---<----
    |
    v
    ---->---
    

    This will work because the zig-zag pattern is nothing but the same 1D array (just in an entangled fashion). But the values which were side-adjacent in 1D cases are still side adjacent in 2D cases (if we just follow this path). Obviously, as it is now in 2D, there will be more side-adjacent pairs that are not shown in the path (each position can have at most 4 side-adjacent positions, namely: left, right, up and down position), but we simply don't care for them, as we already have maximized the result and the other side-adjacent values will just create duplicate absolute difference values which we already found while traversing the path.

    Solution: https://codeforces.com/contest/1783/submission/190766740

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

seriously, what is the point of problems like B, where you have to find some stupid pattern on a grid?

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

    I wasted time thinking that question is asking for only border elements.

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

    Why do you think that is a silly thing to do? It trains observational skills.

    Regardless, its not like patterns in grids of numbers are a meaningless or trivial thing to study. There are a ton of problems that can be represented as patterns in grids of numbers.. Doing regression in data analysis for example.

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

    its not stupid instead you can find the logic behind the pattern. though i wasn't able to solve the problem i found its quite intuitive after contest... since there will be in total 2*(n*(n-1)) adjacency relationship and also maximum diff between any two adjacent could be n*n-1 < 2*(n*(n-1)), we can always generate pattern such that from 1 to n*n-1 all diff got generated. now take the maximum diff i.e., n*n-1 we cannot make it a adjacent diff between two big values so adjacent relationship can be between big and small values, like n*n and 1, 1 and n*n-1 like that. If we solve that for 1D array of length n^2 we have total n^2-1 adjacency relation so just making a spiral out of it to make the n^2 length array to a n x n matrix would suffice.

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

    Yes i did it using Spiral Traversal :)

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

Too much penalty >:( and I thought the condition in problem B is $$$a_i + a_j$$$ instead of $$$|a_i - a_j|$$$.

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

    how did you solved B?

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

      There's at most

      Unable to parse markup [type=CF_MATHJAX]

      distinct value so we started from

      Unable to parse markup [type=CF_MATHJAX]

      and apply it to a zig zag path on the matrix.
»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

so my approach for problem C was since the nth player can at max have n wins . so a win against him would increase my chances of having a lesser rank . i tried defeating maximum players from the end. and then sort the number of wins for each player in decreasing order and decide my rank why wouldn't this logic work ?

here's my submission https://codeforces.com/contest/1783/submission/188487469

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

    See this testcase:

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

    Even i tried a similar approach. 1. Try defeating players from last. 2. Sort and try to defeat as many as possible. Then print the minimum of the two ranks. But it failed on TC 2.

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

    I was also thinking the same but this will not work because we are concerned more about the total number of wins by "me".

    even if we win against last person but our time left is 0, our total win is only 1 so players before last one (like p=2 or 3) can win and our rank will fall.

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

People asked for binary search, dp, segment tree problems aand... here we ended up

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

    I think C was a beautiful problem , though B was little annoying to me

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

      I didn't mean that, C, D, E are very much algorithmic problems, but many of my friends complained about them being too hard ( I think they are easy)

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

      You need some testers for educational round too lol. There are so many ups (and lots of downs) in the quality of these contests

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

      how to solve c?

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

      i tried binary search But not Know how to write function correctly Plzz share some hint

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

    Most of the good contests I participated in had at least one of them

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

How to solve B?

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

Problem B was annoying :(

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

How to solve B?

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

    some pattern based try for n = 4 it will be like

    1->16->2->15

    13->4->14->3

    5->12->6->11

    9->8->10->7

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

      how to solve c?

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

        You can solve C by sorting the array and finding the maximum number of people you can defeat with the given m, let's denote it by wins.

        1) if wins = 0 or wins = n , then your position will be n-wins + 1 (last or first).

        2) If wins >=1 and wins <= n-1, if you could defeat person with a [wins] index (his total wins are equal to wins or wins+1), your position would become one better, so the answer would be n-wins, otherwise n-wins+1. (You could go 1 position higher by having total wins equal to that person.) 188489483

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

      Thanks I overcomplicated it too much

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

      how did you come up with the pattern?

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

As always Educational rounds are worst.

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

    The whole point of them is to learn (standard) algorithms, not to solve interesting tasks. And I think that $$$A$$$, $$$B$$$, $$$F$$$ and $$$G$$$ are great for that ( educational ) matter.

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

      what does one learn from B?

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

        What Wind_Eagle has said before, how to prove theorems in mathematics. Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proof. And I think it is an okay problem, requiring some basic implementation which is, in fact, useful. I understand that many find it annoying though, which doesn't necessarily make it bad.

        • »
          »
          »
          »
          »
          4 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proof

          Infact the reverse is the case, it is very easy to guess the pattern for problems like this without knowing the proof.

          I'm pretty sure for this problem, people just randomly guessed patterns that gave $$$n^2 - 1$$$ as difference, and only a few actually proved the patterns or derived it mathematically.

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

is problem c Segtree or vector of priority queues since ai<=1000 or I completely overcomplicated ?

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

    It has to be on Binary Search but this mf B wasted an hour and my mind went blank coz of that so couldn't even think properly about C

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

    Key observation is because each player plays each other the other players will have 1, 2, 3, 4... wins... If you can beat the player with exactly 1 more win than you while still maintaining the optimal number of wins than your place is (n-wins+2), else it is n-wins+1

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

GOODBYE EXPERT!! These hit and trial B's are the worst

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

Rounds like these make me wish there was an un-register button on Codeforces just like on Atcoder. Wtf was problem B???

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

How to solve D? Spent most of my remaining time trying to solve it...

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

    Try thinking about $$$dp_{i,s} := \textrm{the number of possible suffixes of the array starting at } i\textrm{ having } a_{i+1} \textrm{ equal to } s$$$.

    The transition will be something like $$$dp_{i,s} = dp_{i+1,a_{i+1}+s} + dp_{i+1, a_{i+1}-s}$$$ depending on whether $$$s = 0$$$.

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

      are we trying to find how many different types of sum are possible at end position after applying all operations. eg. if array is a1,a2,a3,a4, at max answer can 4 with 4 different sum a4+a3+a2,a4+a3-a2,a4-a3+a2,a4-a3-a2 possible at the last position?

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

      Bro I did same as yours appraoch but getting TLE on test 18, can you please see and help me how to avoid it. Link to solution : Solution

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

Can we solve C using Binary search?

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

    I too want to know this, I got an intuition but couldn't mold it in any kind of solution.

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

    I did it using binary search on the number of people we rank at least as low as. So to beat $$$k$$$ people, I pick the $$$k$$$ weakest opponents (in terms of $$$a_i$$$), if their sum of $$$a_i$$$ is less than $$$m$$$, we can rank $$$n-k+1$$$, there's also another small detail but this is mostly the idea.

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

    Yes, we can binary search answer. When we check mid, we know that we can't lost the n — mid + 1 opponent. Let t = n — mid + 1. So we do it greedily to beat as many opponent as possible. Now there are 2 case : If the number we can beat >= t, we always win because player t can win at most t games. Else(number we can beat = t — 1) if we can beat player t, we can win too because now t win t — 1 games. 188457382

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

    Yes.You can see my submission.

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

how to solve c

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

Did we have to check only from prefixes and suffixes in the C problem? Like we try to win against only suffixes or only prefixes or some prefixes and suffixes combined? (for the sorted array)

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

Is D even DP ? 💀

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

A: If min==max no solution, else {min, max, (anything)} is a solution.

B:[1, n^2, 2, n^2-1, 3, n^2-2...] arranged along any path of the matrix

C:Sort the array and you will get an almost-best solution. But it needs an extra check to get the best solution. When you've checked first k opponents with least time to prepare, look for whether you've prepared for the opponent with index k+1. If not, check whether you can remove a prepartion and prepare for (k+1)th opponent.

D:Consider for every possible value of sum(ai*sign_i), where sign_i = 1 or -1. There are at most 180000 different values, and run dp for an O(n*A^2) solution.

E:Seemingly easy inequality problem, but naive implementation will get TLE. For certain k, if all multiples of k are not in any range [bi,ai-1], then k is good. We need a segment tree to check all values of [1,n] in O(n*log(n)).

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

    [E] You don't need a segment tree. Just do range sum using prefix arrays and iterate over all multiples of k for every k.

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

      Ohhhhh I missed it

      I just thought about "How to set a range in O(log(n))" and implemented with segment tree

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

    Do I check whether I can prepare for the k+1th opponent in the sorted array or in the orignal array?

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

      Original

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

        Please correct me if I am wrong.

        The logic is: If I can beat any k opponents it means I will rank alongside the k+1th person in the rankings right? So I check if I can add a preparation for the next highest opponent which I have not prepared for and remove prep for the lowest index which I have prepared for so as to beat k+1th opponent right? Such that my number of preparations always remain the same so I beat the opponent removed on total number of wins anyway.

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

          If you don't prepare at all, the wins of each other player is their index (1-indexed).

          In fact, if the number of preparations is fixed at k, you win k matches, and for each other players with index i, their number of wins will be i-1 (you prepared for it) or i (otherwise). Notice that if i < k+1, then i<=k and i-1<=k, which means whether you prepare or not, the number of wins of i-th player cannot be larger than you. It's similar for i>k+1 (their number of wins will be always larger). So only i=k+1 will matter.

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

Worst contest for me!

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

Through this edu round,I know a fact that I'm a totally trash.Maybe I can never be an expert.

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

Very surprised by number of B and and C solves, B confused me while C seemed like a trivial sorting problem

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

Worst B ever. Period.

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

    I didn't solve B, but I liked it. It tests one's observation ($$$n^2-1$$$ upper bound) and simplification (solve it for 1d array first) skills.

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

    That is because you didn't find a key idea of it,so your code was very long.If you found that $$$1 \sim n^2-1$$$ must be able to express,you could know that $$$n^2$$$ must be adjacent to $$$1$$$,easily we could expand it into an easy solution.

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

How to approach problems like B? I solved it by randomly guessing stuff.

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

    Have you ever solved tasks from mathematical olympiads?

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

      No. How would that be useful to tackle such problems?

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

        These problems aren't random guessing, it's just math.

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

          how exactly do you approach B mathematically?

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

            This is the type of question like "how mathematicans prove theorems" or even "how tourist solve CP tasks".

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

              just noticed your round is the next cf round, rofl. with this type of shitty opinions of yours, I pity whoever participates in that round.

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

                True, He better not include these kind of problems. B pissed me off and I left contest within 20 minutes to play CSGO

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

            The process "find the strictest lower/upper bound for the answer and then show that it's reachable" is common in math competitions (not only that, it also frequently appears in algorithm correctness proofs). This is the first step to the solution: it's quite easy to see that the answer is bounded by $$$n^2-1$$$ (all differences are positive, and the maximum difference cannot be greater than $$$n^2-1$$$).

            Then, to actually find the way to reach this bound, you need to try some common techniques to solve problems. You can take a look at MikeMirzayanov's post on these techniques. From these, we have already used "Bold Hypothesis". The "From Specific to General" (with a twist, since we actually change the problem partially instead of just simplifying it) may help us as well: 2D sounds too complex, what if the problem is in 1D instead? This case sounds way stricter: we have only $$$n-1$$$ adjacent pairs, and all of them should be distinct. Believe it or not, but having stricter constraints actually makes the solution easier, inventing a construction on one-dimensional array is not that hard.

            Spoiler

            All that's left is to convert the 1D solution to 2D, which means that we should go through the matrix visiting all its cells, which is a common math/programming problem.

            Spoiler

            Note that our process of solving the problem used something like "try to apply a concept and then see if it works" multiple times, and this is very common in both math problems and harder programming problems. So getting familiar with these concepts and methods will not only help you solve some constructive and/or ad-hoc problems, but also the more difficult ones, where you have to mix it with some standard data structures and algorithms.

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

              Want to add something: some hard tasks require to try a dozen of different approaches before solving the task. This is common not only for constructive and maths, but for interactive problems, graphs or even data structures.

              And solving those "just guess" tasks improve your thinking skills and allow you to recognize some patterns in future tasks.

              So, dear contestants! Instead of just "problem was too bad", answer the question: was it hard or just difficult? Many people claim that the task is "bad" if they weren't able to solve it in time and got negative delta.

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

                I had to tinker around with some randomly put together constructions till I came across the solution.
                Proving it seemed easy once it was clear.
                Definitely not appropriate for problem B, but it's an edu round and technically the order doesn't matter, so whatever, ig.

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

              My opinion on the quality of Problem B has changed after reading this comment

              Thanks

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

          what's math in that?

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

            Well it was not total math problem, but yes there was a quite neet observation, that is the maximum ans is always n^2 — 1, from there you can make the matrix multiple ways.

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

              I got that observation but still it felt like massive hit and trial to me

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

          But I think, here intended solution was random guessing!:(

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

    Thats how you solve it, xD

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

After failing to submit E in the last 10 seconds the last time(Jan 6), this time I found the solution of E in the last 5 minutes and got AC just 5 minutes after the contest ended... [Sad]

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

B spoily my mood and I gave up after 20 minutes

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

Hi there! I try to help people by upsolving contest problems and post them after the contest on my channel — https://www.youtube.com/@grindcoding . I have been trying hard to help people by solving daily challenges across platforms and also the contest problems. Please provide me suggestions on what I can improve. Have uploaded problem C of this round already and would upload others as required by anyone of you. Any advice is appreciated :).

P.S. not the channel who promote leaking solutions during live contests. I know it provides better growth with the huge amount of cheaters, but I understand it's detrimental and against the overall spirit :) happy coding :) Soon would be making a good data structures and algorithms course to help beginners (though not a pro myself but want to contribute as I grow).

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

Here is the intuition I used to solve problem B:

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

A tough contest to me :(((

problem B needs a lot of observation :((((

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

Any hints to approach problem 'C'?

Really reject stopping solving problems regularly T_T

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

    Hint 1: Without considering your training, each other player has a unique amount of wins

    Hint 2: What 1 other player's ranking can you affect that could also improve your ranking?

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

    Hi! yes! there's one case you need to consider, can you defeat the person who has wins==wins_you_have+1, I have uploaded a editorial video on my channel you can check this here- https://www.youtube.com/@grindcoding

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

    Let's say I want to reach a specific position Xth, what's needed? Once you've figured that,

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

got stuck with b and no time left to think about c .. uff time to go back to green

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

Participate in post contest discussion

www.peer2peer.social

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

Wow, I really enjoyed the problemset! Problem F is just otherworldly *_*

Huge thanks to the developers of the contest! <3

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

Nowadays the problems in the contest are not properly sorted in the order of their difficulty. Sometimes the problem B is made very hard, whereas sometimes it is made as easy as A, and in this case the C problem is made very very Hard.

It would be nice if the difficulty order would be made moderately increasing.

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

Welp this was a waste of time.

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

Problem B was horrible and problem D was harder then E.

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

was anyone able to get the solution to E with $$$n√n$$$ time complexity?

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

It was a worst contest I have ever written. My problems never been hacked by some random pupil ranked participant.

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

Tips for Python

In Python, you can put negative indices in a list (A[-1] means A[len(A)-1]). This makes it easy to implement dynamic programming with negative indices. When the index can take values from -L to L, prepare a dp array of length at least 2*L+1. In this array, information on positive indices can be placed in the first half of the list, and negative indices in the second half ([0, 1, 2, 3, ..., L, ... , -L, ..., -3,-2,-1]).

Source Code for D:

mod = 998244353

n = int(input())
a = list(map(int, input().split()))
dp = [0] * 2 * 10**5
dp[a[1]] = 1

for i in range(2, n):
    ndp = [0] * 2 * 10**5
    for j in range(-90010, 90010):
        ndp[j + a[i]] += dp[j]
        if j != 0:
            ndp[j - a[i]] += dp[j]
    dp = [j % mod for j in ndp]

print(sum(dp) % mod)
»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone tell me a test where my code fails?

https://codeforces.com/contest/1783/submission/188507888

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

188508171 Please show me a case where my submission for problem C get the wrong answer :((((

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

The hack channel for problem C is ridiculous. If I set t to 1 and n to 500000, it will show generator crashed, which means it is hard to hack it tle!!!!!!!!!!!!!!!

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

Quite an ambiguous definition+example of the side adjacency for problem B. In the 2x2 example almost any nonsense one may come up with yelds same answer. For example if you define side adjacent elements as "elements on the same matrix edge". After the clarification it gets better, but still there's a chance you keep solving the wrong task on impulse.

Any ideas how this "insanely misinterpreted" problem can be solved by the way?

Once again. Same task: find the most beautiful matrix, but the adjacency definition is:

Two different matrix elements $$$a[i_1][j_1]$$$ and $$$a[i_2][j_2]$$$ are adjacent iff ($$$i_1 = i_2 = 1$$$ or $$$i_1 = i_2 = n$$$ or $$$j_1 = j_2 = 1$$$ or $$$j_1 = j_2 = n$$$) ?

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

    1 n 2 (n-1) 3 (n-2) 4 (n-3)

    Look at this like and all will be clear(first row of matrix)

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

      Thanks, but that's the solution to the original problem, but doesn't seem like a solution to the problem I mention.

      I'm interested in filling these so that the size of the set made of absolute difference of any two elements from first row or last row or last column or first column has max size.

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

can anyone tell me how to solve E?I Just know that for every a[i]>b[i],then check k is ok if and only if (a[i]+k-1)/k==(b[i]+k-1)/k (i.e. ceil(a[i]/k)==ceil(b[i]/k)). but this get TLE as expected. how to get a faster solution? i cant understand the solution in the front row

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

can anyone tell me how to solve E?I Just know that for every a[i]>b[i],then check k is ok if and only if (a[i]+k-1)/k==(b[i]+k-1)/k (i.e. ceil(a[i]/k)==ceil(b[i]/k)). but this get TLE as expected. how to get a faster solution? i cant understand the solution in the front row

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

    $$$\left \lceil{a[i]/k}\right \rceil \neq \left \lceil{b[i]/k}\right \rceil $$$ if and only if there exists a number divisible by $$$k$$$ in range $$$[b_{i}, a_{i}-1]$$$.

    Therefore, we can mark all numbers in this range (for example, by using a segtree) and for each $$$k$$$, check if there is a marked number divisible by $$$k$$$.

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

In problem C, does NlogN pass? I didn't want to take a risk and made an O(n+maxA) solution.

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

can anyone help me understand in problem C if the test is 8 6 2 2 2 2 2 2 2 2 so if I win against the 8 and 6 and 4 so 1 1 win 2 2 win 3 3 win 4 3 win 5 5 win 6 5 win 7 7 win 8 7 win I 3 win so I should rank 3 why is the answer 5 I don't understand I got stuck in this problem for that

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

    just because there are 4 people whose win count strictly larger than you (i.e.5,6,7,8),let the count called k. and the answer is k+1. I guess you misunderstood the computing method of the rank within this question.

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

      Ty I think so the solution is much easier than i think ಥ⁠‿⁠ಥ

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

      Brooooooooo, will re-read question 10 times now while solving.

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

    Because rank is the no. of people with more wins than you + 1. Your win count is $$$3$$$ but $$$8$$$ and $$$7$$$ both have won $$$7$$$ and $$$6$$$ and $$$5$$$ both have won $$$4$$$, hence the no. of people with more wins than you is $$$4$$$. Therefore, your rank is $$$5$$$

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

      Yeah i understand that they group people with the same win so that i should minimize the number of group

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

    It's optimal to beat the any 2 players and the 4th player which results in 3 wins.

    Bracketed players are the ones we beat.

    So 2 2 2 [2] 2 2 [2 2]
    

    And then if we count the number of wins and also consider the players we lose to we get our answer.

    1st player will have 0+1 wins
    2nd player will have 1+1 wins
    3rd player will have 2+1 wins...
    4th player will have 3 wins
    5th player will have 4+1 wins
    6th player will have 5+1 wins...
    7th player will have 6 wins
    8th player will have 7 wins...
    

    We ourselves have 3 wins. Order looks something like this then

    P(i) = 1 2 3 4 Us  5 6 7 8
    Wins:  1 2 3 3 [3] 5 6 6 7
    

    Our rank is 5.

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

BledDest Can anyone explain problem C?

For this test case

4 4

1 2 2 1

Since we have 4 minutes I can defeat Opponent 1,2. But why in the explanation it is mentioned we can win against only opponent 1 and we have no time to prepare

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

    That's the 5th test case.

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

    If $$$m = 4$$$ and we prepare and win against opponents 2 and 3 and lose against 1 and 4. Don't we get 2nd place? As our opponent 4 has $$$3 + 1 = 4$$$ wins against our 2 wins. I must be missing something obvious.

    Edit: ok my confusion was to fail to understand that "min place" actually means best ranking and not worst ranking.

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

      We can pick the following opponents. (Bracketed means picked)

      [1] 2 [2] [1]
      

      Which gives us 3 wins. Opponents will be ranked as follows:

      P(i) = 1 2 3 4 Us
      Wins:  0 2 2 3 [3]
      

      This results in first place.

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

I almost spent the same amount of time on B as I did on C and D combined.
Seemed like I was solving some weird newspaper puzzle.

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

    How is B an 'edu' problem?

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

      I start to think that "edu" is not about learning, "edu" is about Harbour space, like , there are Pinely rounds, Polynomial Round, CodeTON Round etc.

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

      It is rarely a difference between EDU and classic rounds. EDU were immature rounds initially, with no score distributions and possibilities for hacking, but later classic rounds overcome simplification and become similar to EDU, without hacking almost, but still with different costs of problems (except newer Div.>2, which are simplified further and have no difference with EDU).

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

      It's not a random guessing problem. Notice that the difference is between 1 and $$$n^2-1$$$, so naturally we first try to get them all. For $$$n^2-1$$$, $$$n^2$$$ and 1 need to be adjacent, then for $$$n^2-2$$$, either $$$n^2$$$ and $$$2$$$ or $$$n^2-1$$$ and $$$1$$$ need to be adjacent, .... It's quite easy to achieve that. If you know gray code, Z-order, or something like those, easier.

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

Solution of D(with explaination please)?

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

This was a perfectly good round, without any major errors. Why all the downvotes?

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

Though the binary search solution greatly simplified the task, was it actually required in C?
I mean, apart from the edge case of losing to the winner and changing the required score, it was all greedy and sequential, right?

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

There is interesting solution of E with Eratosphens sieve: It's a fact that upper bound of a[i] / k must be <= upper bound of b[i] / k for all i. So we need to check only pairs where a[i] > b[i]. You can increase every a[i] position by any big number (1e7 + 1 in my case) and decrease every b[i] position by 1. Then we get prefix sum of this array and iterate like in sieve. If any sum on prefix with length which divides k doesn't divide 1e7, it means that we found some b[i] with b[i] / k > a[i] / k. That's it: 188522674

UPD: nevermind lol, it's basic solution

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

For problem D, I submitted these 2 solutions after the contest:

Submission 1 gives a Wrong Answer verdict. 188541769

But when I submitted a new solution taking the answer modulo, I got a TLE verdict. 188542103

I don't think I changed much of my code. Does anyone know what the heck is going on?

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

    Modular operations are expensive. And even if they weren't, the first solution already took nearly 2s and adding more operations there inside the loop would yield TLE.

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

    If a,b are in [0,mod-1], you can use

    ans=a+b;
    if(ans>=mod) ans-=mod;
    

    instead of

    ans=(a+b)%mod;
    
  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Also you should check if(a[1]!=0) instead of if(a[2]!=0). Because of this mistake your answer will be hacked by some tests with a[2]==0, even if don't get TLE.

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

problems are good , but the implementation part is a bit complicated.

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

For D problem,can we use dfs and work it out?

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

    Use DFS with memorization,in fact it is nearly the same with DP solution.

    My good friend wrote it,though his code was not very easy to read.

    188473734

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

        As I said,you didn't use DFS with memorization.In other words,you could find that there will be many repeated search with the same $$$(i,ai)$$$.So you could record the answer of dfs(i,ai).It will cut lots of unnecessary search.

        Your TLE code is a $$$O(2^n)$$$ solution.If you use memorization,it will be $$$O(n^3)$$$ because you will find $$$|ai|$$$ will not exceed $$$90000$$$.

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

        hey, why are you returning 2 here?

        if(i==n-1) { if(ai==0)return 1; else return 2; }

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

          Because if i==n-2,there are two operations you can make:a[i+1]+a[i] or a[i+1]-a[i].But if,a[i]=0,then a[i+1]+0=a[i+1]-0,these two ways are the same way,we can just calculate 1

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

      There's a line of code that needs to be modularized. I think my time complexity may be the same to your friend's,why mine cannot pass through?Can you help me slightly modify it and make it work?

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

        I fixed your solution

        188553247

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

          I racked my brains last night, but I couldn't figure out how to cut the branches. It turns out that you can use space to exchange time and it increases my knowledge. Thank you very much!

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

          So it is Mnemonic search? It turns out that I can really use some simple knowledge that I am good at to pass this topic! Because the code of my friends around me is complicated, I hope my code can be changed and pass. It really turned out to be okay.

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

Apparently I crashed codeforces because of a hack submission I made. I don't even remember the testcase I did, but it was supposed to bug a code that was using random generator for the answer. Anyway, thought I would leave that here so someone would look through it and see why it's still waiting for about 10 hours now!!

Here is the link to the hack: https://codeforces.com/contest/1783/hacks?verdictName=TESTING&chosenProblemIndex=A

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

    I subitted my hack for someone's D problem last night,and it showed "generator crashed",which made me amazed,too.

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

      No that's normal. That happens when the code you made to generate the testcase had some bugs in it.

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

        Aha?It shows that: The hack uses generator Generator is not determinate [the verification run produces different output, cmd =cvp], [389171 bytes, '1

        100000 5731847

        175 801 492 274 740 3 22 624 98...850 521 474 390 847 127 534 896 874 535 704 834', sha1=0cc6f6ae5c8479c995b9dec28fcd7dc48de6b3fe] vs. [388952 bytes, '1

        100000 5731847

        181 530 685 865 602 856 479 769... 803 621 675 483 837 275 74 663 223 426 353 310', sha1=911ae7fb5a320770e460a2a3d1a2c49baa34c4c6]. My hack submission includes randmized integers,so I think it's naturally that the generator is not determinate. I've tried to submit code that generates random numbers before, but I've always succeeded before, but I don't know why I didn't succeed this time. I tried to write test to a file to make the value certain, but it said the file was too big and had too much text. So I think this is a bug in the cf mechanism.

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

Will we see rating update and tutorial before next contest begins?

Why does "Educational round" mean slow rating update and slow tutorial?

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

How to solve G ? Seems that the tutorial won't be soon :(

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

Wait for D's solution.DP is my weakness...

And there is still no tutorial yet?

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

    Small hint to you:

    • In any time,$$$|a_i| \le s$$$,where $$$s$$$ is the sum of the given array.

    • When you are going to operate $$$i$$$,you only care the value of $$$a_i$$$ now.Try to empress the dp state as $$$f(i,now(a_i))$$$.

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

I dont understand why this contest was downvoted, I felt like problems were good, specially C.

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

This round was really boring.

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

I'm wondering how 300*2*300*300 solutions were accepted for D. Thats like (10^8)/2. Aren't 10^8 solutions supposed to TLE?

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

    It is very easy to pass in codeforces.In fact,many $$$10^9$$$ level codes could pass in 1 or 2 seconds in codeforces with their small constant.

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

      Interesting, thanks. Wasn't really aware of it. It was a pretty straightforward dp question in that case. Will remember it for next time.

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

        It's like the worst case scenario strategy, because none of the authors consider 10^9 solutions

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

    176169324

    Such as this code,it was a $$$O(n^3)$$$ solution and $$$n \le 1000$$$,but it was very fast,with a $$$\frac{1}{6}$$$ constant.

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

B is worst problem fck

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

This Bootcamp, is it meant only for students? Or can I join at the ripe age of 33?

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

Has anyone tried to submit B using simulated annealing? I tried but it gets WA: 188572639

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

Rating??

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

When is system testing going to happen?

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

Trush round!A is not perfect.Problem B is the worst problem I have ever seen.I wasted an hour on it.But C is very interesting.Hope more questions like C will appear in cf.

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

Why it's taking time to get the rating updated for this contest?

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

Where the rating updates at?

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

any tutorial?

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

When will the tutorial will be published ?

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

has this contest been declared unrated or what? why rating is not updated yet?

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

    It takes so long in Educational Rounds

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

      Yes, and 4 hacks are not tested yet. All that hacks are on this solution, it has random and easily gets TL. I dont know why testing solutions on hacks dont break after TL...

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

        But in fact this code is expectly $$$O(Tn^2)$$$ in the worst cases,which is easy to pass.I didn't understand why it can be hacked(I submitted a same one and was hacked),could someone tell me?

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

          I don't know about TLE, but does random give 100% correct answers?

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

            If it was checked that the array was not correct,it will repeat the random algorithm till it find a correct answer.

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

          If you have array [1, 1, 1, 1, ... , 2] you have 2 correct answers — [1, 2, 1, 1, ..., 1] or [2, 1, 1, 1, 1, ..., 1]. In this case you have n possible permutations of array, so in each random shuffle you have only 2 correct answers from n, where maximal n = 50.

          if you do K random shuffles, probability of your win would be correct positions / all positions. All positions = n ^ k, correct positions = all positions — bad positions = n^k — (n-2) ^ k. So if you do K random shuffles probability of finding correct answer is

          P = (n^k — (n-2)^k) / n^k.

          For n = 50:

          • if k = 5, P = 0.1846273024

          • if k = 10, P = 0.33516736

          • if k = 100, P = 0.98312968

          So on this testcase it does 100 shuffles for finding answer. So your code does t * n * K = 2000 * 50 * 100 = 1e8 operations, and you choosing random number 1e8 times for shuffling array, and this can take long time and maybe TL.

          If you would find testcase where is only one correct permutation:

          P = ((n^k) — (n-1)^ k) / (n^k)

          • if k = 5, P = 0.096079

          • if k = 10, P = 0.182927

          • if k = 50, P = 0.635830

          • if k = 100, P = 0.867380

          • if k = 200, P = 0.982412

          In this case your code does t * n * K = 2000 * 50 * 200 = 2e8 operations

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

            Yeah I thought just like you,but I tried to use $$$2000,50,1 1 1\cdots 2$$$ to hack it,but it ran very fast,just used 93ms!

            link

            And I just found the all the data hacked my submissions satisfied that $$$n$$$ is small(In fact,$$$n=4$$$). I'm a bit confused about it.

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

            I just wrote a random algorithm as it.

            188610805

            I guess that randomize in the hacked code is the murderer of it.

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

              Yes, randomize function is bad and slow.

              When you tried to hack his solution it's not guaranteed that his random would use 100 operations — maybe if he would lucky he can find correct answer in 5 or 10 attempts.

              About test that hacked your code, i dont really understand why it failed, because for n = 4 and k = 5, P = 0.96, so you need on the average 5 attempts for shuffle, so I dont know why it got TL...

              I will try your solution in locale on testcase which hacked your solution, if I would find something interesting I will write you in messages.

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

          It was me who hacked it. Sorry xD

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

            I didn't care about it(And it wasn't my code in contest),I just wanted to know why it got TLE(And now I get it).And my submission above with shuffle seems to be correct.

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

              Yeah some types of shuffle will work. I saw someone use random_shuffle and when I looked at it in the documentry it looked like a very good way of shuffling, and a fast way too. It just two successive elements, which is really all what you might need for the answer

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

The contest is supposed to be rated right?

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

IMO Editorial should be provided shortly after the hacking phase finished.It's too long.

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

Can anyone explain how to solve problem F?

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