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

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

Приглашаю Вас поучаствовать в рейтинговом Codeforces Round #518. Дата и время проведения раунда: среда, 24 октября 2018 г. в 19:35. Раунд был перенесен с 23 октября на 24 в связи с проведением в это же время ICPC Indian Online Qualifier.

Это первое соревнование, предложенное мной. Надеюсь, что оно вам понравится.

На раунде будет 6 задач для второго дивизиона и 5 задач для первого (3 задачи общие). Контест будет длиться 2 часа.

Задачи для вас составляли Алексей kristevalex Кристев и Алексей Um_nik Данилюк. Также большое спасибо:

Николаю KAN Калинину и Ильдару 300iq Гайнуллинину за помощь в подготовке задач; Ивану isaf27 Сафонову и Олегу Merkurev Меркурьеву за тестирование раунда; Михаилу MikeMirzayanov Мирзаянову за платформы Codeforces и Polygon.

Хочется выразить отдельную благодарность Um_nik за помощь на протяжении всего процесса подготовки раунда, а также терпимость к моим глупым вопросам.

небольшое лирическое отступление

Как вы заметили, этот раунд проводится в честь компании Mail.Ru, значительно поддержавшей Codeforces по случаю 8-летия платформы. Вот несколько слов от MikeMirzayanov:

Большое спасибо Mail.Ru за поддержку Codeforces! Мы являемся партнёрами уже много лет, и было особенно приятно получить поздравления от старых друзей. Мне кажется, Mail.Ru — чемпион мира среди компаний по организации различных интересных соревнований для любителей программирования. Вот список (уверен, неполный) активностей Mail.Ru, которые могут быть интересны аудитории Codeforces:

  • Mail.Ru Cup — новое соревнование по спортивному программированию (совместно с Codeforces!), открытое как для студентов, так и для профессиональных разработчиков;
  • Технокубок — олимпиада по программированию для учеников 8-11 классов из России и стран СНГ (совместно с Codeforces!);
  • Russian AI Cup (RAIC) — открытое соревнование по программированию искусственного интеллекта игровых стратегий (совместно с Codeforces!);
  • Mini AI Cups (Mini AIC) — мини-клон чемпионата Russian AI Cup, площадка соревнований по искусственному интеллекту, связанных с написанием ботов для игр;
  • Machine Learning Boot Camp (ML Boot Camp) — онлайн-чемпионат по машинному обучению и анализу данных;
  • HighLoad Cup (HLC) — соревнование разработчиков высоконагруженных систем.

Кроме этого Mail.Ru запустило большое количество образовательных инициатив, я сам неоднократно смотрел записи лекций на YouTube с занятий Техносферы и других проектов.

Еще раз спасибо за поздравление. Надеюсь на долгосрочное и плодотворное сотрудничество!

Разбалловка будет объявлена ближе к началу контеста. Желаю высокого рейтинга и жду вас на соревновании!

Я буду на Codeforces Discord server в течение некоторого времени после раунда для обсуждения задач.

UPD: разбалловка div1: 500 1000 1750 2250 2500 div2: 500 1250 1500 2250 2750 3500

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

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

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

Codeforces is the best platform :) We are proud to work together!

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

I've noticed that 300iq is still unchanged to his real form. The legend will be mad.

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

If Um_nik didn't told you to stop creating problems, then I guess it will be a great round.

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

    Participate and find out for yourself :)

    I think that kristevalex really is a talented problemsetter. Of course he need more experience both in preparing and solving problems but his ideas are sometimes brilliant. Or maybe that was one time and will never happen again. Who knows.

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

    Dude that doesn't even have anything to do with this round's setter, seems your so salty have to put your issues on random blogposts ._.

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

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

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

.

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

Is it rated?

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

6 consecutive hidden comments, ridiculous.

UPD: 7 comments.

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

FST forces!

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

The time page gives 404 error, please fix it.

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

hhey is it rated or i dont partisipate

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

Why so many downvotes?

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

I don't mind my comment to be harmonious with the others (since it doesn't mean that I was wrong to comment).

The time link still gives 404 Error.

I can know when the contest will begin from the timer of Codeforces, but I want to be sure, because the difference between our country's time and previous blogs' time was zero, and now it is one hour and a half.

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set

Seriously, another problem with a bad statement, time to leave.

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

    Totally agree you cannot use a word to define it's self "Let's call the set of rooks ... with rooks from this set" , it like saying a ball is a round-shaped ball, it doesn't make sense.

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

      While I agree that the line (and problem statement as a whole) could have been phrased better, I'd also like to point out that what is being defined here is 'connected', so using 'set of rooks' in the definition isn't leading to circular definitions.

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

    Yeah, I kept on staring this line without any clue for quite some time. Glad that I was not the only one.

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

Am I the only one who found problem statement of Div.2 A to be tremendously hard to understand?

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

This contest is plain garbage.

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

    Contest was really nice. If you found contest easy try D,E,F, if tough then A,B were really easy. I liked 2A. In 2B, we just have to count the number of divisors of b.

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

nice contest

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

Problem A Div.1 Sample is useless.

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

Hack for D1B?

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

    I hacked 1 solution with:

    21 2
    3 1
    4 1
    5 1
    6 2
    7 2
    8 2
    1 2
    9 1
    9 10
    9 11
    9 12
    10 13
    10 14
    10 15
    11 16
    11 17
    11 18
    12 19
    12 20
    12 21
    

    Maybe some solutions could get hacked by changing k from 2 to 3.

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

GreenGrape, your rounds are perfect

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

E: link. Nice problem!

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

    I used the same :D

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

    So, how to solve it based on this fact? My thought was like consider every edge separately, use something like tree dynamic programming to compute the probability for it to be the matching edge. But I'm not quite sure if this would work.

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

      There is a greedy algorithm to find maximum matching in a tree. So, I have DP[n][2] — vertex and "Would this vertex be already matched in greedy algorithm?". When I consider some unmatched vertex with its unmatched child — I must match them (like I would do in greedy algorithm). Each DP[v][i] is a pair of integers — how many subsets of edges in this subtree would lead to this state and what is the sum of results in these situations.

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

        Aha!Got it,thx. Just a slightly change of the algorithm of finding the maximum matching in a tree.

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

      You can use standard dp. dpv, 0 is max matching in subtree if we didn't take v, dpv, 1 is max matching if we took v. Every time we connect v and u which were not taken, we should add edge (v, u) to matching.

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

      Tree DP is right. Count the number of max. matchings and the sum of their sizes, where the top of a subtree can be unmatched / has to be matched. When processing a vertex's sons, you can use an intermediate state "has this vertex been matched with some son?". There are some annoying long formulas, but that's basically it.

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

I alone do not understand this part of the condition of problem C: "Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal."? After all, this means that the rook can make a move only in the next cell, where there is another rook (which does not correspond to test 1). Or how then to understand it?

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

Thought I had something for C, but I guess I was wrong! Kept getting WA pretest 3. Anyone want to share solution?

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

How to solve A?

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

    i change long long to double long and i get ac

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

    My solution is dp[i][number on position i][is a[i — 1] >= a[i]], to calculate it use prefix sums.

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

    I think for Div2C, you have to construct a zig-zag like pattern. Messed up my implementation though!

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

    let dpi, j, 0 / 1 denote for the first i elements, with the last value j, and the last dimension stands for is it needed that the next element is greater than/equal to the last element. Naively doing it would result in O(2002 × n), With prefix sum optimization, it can be reduced to O(200 × n).

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

    Div1A/Div2D is DP[10^5][200][2] , but I can't implement it ).

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

Div2A statement is bad :(

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

When Um_nik criticize misof for TCO and then, interestingly, leads a contest which consists of extremely bad statements... Just saying...

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

    Really activates my almonds.

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

      hahaha what does that even

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

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

          wait wtf is a homemade coconut? I never knew food science was advanced enough that we were doing this

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

            lmao dude have you even used a crafting table before?

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

              I see what you did there. You are trying to paint me as a man of no culture (because I don't play minecraft)

              Unfortunately, I'm always munching on cultured vegetables. Goes well with my alkalized water.

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

                Can you really talk about culture when you aren't drinking 1000 liters of milk in 3 gulps though

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

                  Dairy is bad. Instead I drink coconut kefir (from my own lab grown coconut) with some activated almonds

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

        Pete Evans describes "activating almonds" as putting them in water for 12 hours.

        I guess normal almonds haven't even achieved their final form

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

    I'd say "extremely bad" are a kind words for it.

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

    90% of questions we get were caused by participants not able to read statements and understand basic mathematical constructions.

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

      Instead, it would be better for a legend to reconsider his self-esteem.

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

        It would be good, but not instead. I can't really do anything about people who either don't know mathematical notation or don't spend time reading statements.

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

          Um_nik Hope you already know that, reading statements and understanding them are not same. And I think it's not you who will decide whether the statements were good or bad to understand. It's us, the contestants will do.
          Do you think contestants complain about problems in every contest? No. If something really went wrong, they complain about it.
          And only then you should say "I can't really do anything", when you know people hates you, so they started complaining about problems.

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

      Problem A had poor statement as well as weak pretests. :(

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

      Yeahh, right, maybe not able to guess what you hid in there. GUESSINGFORCES it was, how you like it ??

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

      No matter the quality of problems, I agree with Um_nik that there are so many stupid questions asked. It happens every contest, even if people don't complain later in the comments.

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

How to solve div2E?

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

    I didn't solve it, but here is my idea

    Cut all the vertexes with degree 1, repeat it until one is left : the root Then simply check if all vertex's child degree is not less than 3

    *Is it right?

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

    This is what passed pretests for me:

    A k-hedgehog has  ≥ 3k leaves. Since n ≤ 105 this bounds k by 11 or so.

    Now, perform k steps. At each step, remove all leaves from the graph, and decrease the degree of their parent by 1. Make sure that any non-leaf node either sees no change in degree, or their degree changes by >= 3. After this, update the graph so that you get a new set of leaf nodes, and do this again. After k steps, you should be left with exactly 1 node at the end. Any other case is a "No".

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

    Div1C solution is just a cross:

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

    After contest, I solved it after drawing some examples on paper and noticing the symmetry the hedgehog type of tree has, which turned out to be solution 2 from editorial.

    My solution:

    The natural solution I saw to the problem was to identify the "center" of the tree (which, must exist if it is a hedgehog) and then, from there do DFS/BFS to check if the given tree satisfies the properties given in the statement. The problem is, we need to identify the center quickly. How do we do that? If the tree is a hedgehog, every longest path must pass through the center node, which is number k, zero indexed (one can notice this by carefully reading how the hedgehog type of tree is created). So we find a longest path, and check if the length of it is > k. If it is not, then it is not a hedgehog. Else, we take the center node of the path and run BFS/DFS to check the properties, which are:

    • The center node must have degree equal or larger than 3.
    • All nodes that are not leaves (are at a depth < k from the center) must have degree >= 3 without counting its parent.
    • All leaves (are at depth k from the center) must only have degree 1.

    If all these are satisfied, we print "Yes", else, the given tree is not a hedgehog.

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

Does having two rows of white squares (0, 0), (2, 0), (4, 0), etc and then (0, 3), (2, 3), (4, 3), etc work???

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

Shit. I just found an asymptotically sufficient assignment for div1C:

  • a row of knights in the middle
  • 2 columns in the middle
  • out of these two columns, remove most of the top half of one and most of the bottom half of the other

Also, Um_nik, if div1E reduces to div1A-B after an easy to find observation, it shouldn't be in an online contest!

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

    Easy to find you mean online? I didn't succeed, but I'm not good at googling. I'm sorry for that, you are right about problem being only about this observation.

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

      "adjacency matrix" rank tree: gives SE as the second link, the first answer mentions something 2x size of matching

      "adjacency matrix" rank tree matching: gives the answer for a tree directly, generalising this to a forest is easy

      Not completely easy to find, but easy enough.

      My story: I looked at the scoreboard immediately after submitting B, saw that someone solved it already and decided to work with the assumption that the solution is online. I read the statement, decided that if something is online, then it's the rank of an adjacency matrix, found something (including the first link), read the statement again and realised — I missed that the input is a tree, made the two queries, mentally checked that the first sample fits, so I haven't found something irrelevant, and started thinking about a solution.

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

The descriptions were not clear at least for me. Didn't like this contest.. AWFUL

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

Deleted

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

problem C statement was really bad .. ofcourse so many solved it but you should consider not everyone has shakespear english level and give the beginners who hasn't read alot alot of problems a chance to solve it

I was going to try it but i was like if i need so much time to understand it then when I'm going to think how to solve it

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

Any idea why this submission would get WA on test 3 while this one passes pretests?

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

Being in #1 for almost all the time, then got punished by a hack on 2A :D At that moment, I realised the statements were bad enough for me to deny reading them in the 10 last minutes :D

Btw, anyone can provide me a hack for 2A? :D

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

    Could be overflow, numbers go up to 10^18

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

      Not with mine. My solution consists of at most 1 addition, and no multiplication, the other operations possible were division only...

      My hacked solution: 44781223 (not sure if accessible now)

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

    10 6 3 4

    many programmers checked only if m>n or (l+k)>n, then print -1 else printed ans=(l+k)/m + bool((l+k)%m), they never checked if ans*m is exceeding n or not and hence got hacked.

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

    Both statement and pretest for Problem A were too poor. I will also fail system test! :(

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

Pretest 3 of div1A?

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

Is DearMargaret going to have a bad rating change for first time?

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

How to solve Div2.C ? I'm really confused by the statement, thus cant solve it ://

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

    Same here, examples didn't make sense for me.

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

    for every edge x1-x2 put rook of color x1 to (x1, y) and of color x2 to (x2, y). make 'y' value unique for every edge and check condition that all colors should be on chessboard

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

      There could be n * (n — 1) / 2 edges, which is 100 * 99 / 2 = 4950 for 100 colors. Your solutions places 2 rooks for every edge, resulting in 9900 rooks on the board. This is a violation of: "Total number of rooks must not exceed 5000."

      There is accepted solutions with this algorithm. Could anyone please explain where my thoughts are wrong? Are they?

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

Am I the only one who passed the pretests of problem A Div.1 using a Top Down approach?

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

    deleted

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

    I did, but I had to resubmit at the end of the contest to reduce memory usage :( Recursion uses memory too, so having array size within the limits is not enough.

    I tried this test in Custom Invocation and got MLE: -1 200 -1 200 ....

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

Does anyone have a correct solution for Div. 2 F/ Div. 1 C? I found something that gave but I couldn't improve it further.

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

How to solve Div1C:

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

    How do you generalize the answer from this? It's just 5 guys chilling in a row with 2 in front of them

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

      In one column you have a knight at y=0, in the next one at y=0 and y=3 and that pattern repeats. It seemed quite obvious to me.

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

EDIT : Didn't see that the editorial is already published.

EDIT: Most probably, it fails because I am assuming the CHT implementation to be min-oriented but it actually is max-oriented.

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

    Idk, seems reasonable to me. But I also observed that the optimal i for each t would be the same, i.e. we just spam some i until one upgrade is available. So no need to use CHT here.

    EDIT: Same as jtnydv25 and realized the editorial doesn't do what I did :s

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

      Do you mean for each t > 1? (otherwise the statement is definitely wrong), and how do you prove it even for t > 1 ?

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

        Wow, right when I tried to write my proof I realized it was completely wrong :o

        How it was not caught in the pretests is beyond my knowledge though.

        Anw there goes my red xD was fun bragging around

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

Please someone tell me, why do I get TLE in this: http://codeforces.me/contest/1068/submission/44804608 This is Div2B

Please tell me, it won't take a minute for you to read my code.

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

Div1C
Is this the way to place the knights?

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

Dear kristevalex and Um_nik, please stop making problems.

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

What's wrong with vintage_Vlad_Makeev? Was he hacked or just rofl?

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

English statements are not too good, especially problem Div2C. Still, it was a fun competition, thanks for the effort.

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

The problems were nice, but the contest was bad. Here are the reasons:

  • A is much harder than B. So a lot of guys decided to not participate when they haven't solved A in 10-15 min. So A+B guys with bad time will be severly punished for participating in ranking. While A+B fast will be ~60th place.
  • E after googling is on the same level as A, still harder than B.
  • in C you can submit anything, get the authors output and generlize...
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    All of that are valid points, thanks.

    • That's kinda my fault, but I still think that A is easier. A is standard DP and B needs some observations. Also I don't think that authors should be thinking about strats like 'couldn't solve A in 10 minutes — leave'.
    • Nothing to add here
    • I didn't know about that feature of CF. We changed outputs for samples and thought that was enough.
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Output of C provides almost no information. I don't think there is any mistake here. Out of 3 people who said "easy to generalize" only 1 guy actually did it.

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

      which observations does B need? it was obvious from the picture how to solve it

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

div1 B test case "1 1" is not in the pretest...

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

Why was Div2B given a max score of 1250 instead of the usual 1000? Did you think Div2B was closer to Div2C than Div2A? I read Div2B 4 times because of your decision to give it 1250 points. Guess I should have done that for Div2A instead as it had such a good corner case. I read similar complaints about Div1A and Div1B as well. Points distribution was not good.

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

After this round, i am demotivated for sure.

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

    Participant's output -501767591

    So it seems that you have overflow. Checking the code you declared int bs() instead of ll bs(). I didn't test it but it seems that is the problem.

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

Started after 10 minutes, misunderstood B, got WA, then solved A, panicked with B, pretests passed E, panicked with B again then finally understood(felt so stupid at that time), couldn't submit C with 2 seconds in hand! :(

Watched the status board with heart in my mouth whether E will pass the system test or not. It passed :D Submitted C after contest, AC in one go. -_-

Mixed feelings, A very eventful contest indeed!

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

Very nice problem !

And I finally got the Expert Title during this contest!

I wait for this blue name for a YEAR and I finally got that!

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

Является ли раунд рейтинговым для 2 дивизиона?

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

Интересно, а в задаче Bdiv1 тесты 120+, принесшие большую часть реджектов -- это добавленные взломы?

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

Unfortunately the system tests on today's Div 1 problem D were quite weak. I wrote up an explanation here: https://codeforces.me/blog/entry/62692. Make sure to take a look if you are trying to solve problem D in practice mode (or just interested in the problem).