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

Добрый день!

23-го декабря в 17:05 по московскому времени состоится Отборочный Раунд 4 олимпиады для школьников Технокубок 2018. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 17:15 до 17:35).

Зарегистрироваться на Отборочный Раунд 4 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

Параллельно с Отборочным Раундом будут проведены открытые раунды для обоих дивизионов, в них могут принять участие все желающие.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Спасибо veschii_nevstrui, adamant и DPR-pavlin за подготовку задач Технокубка. Также спасибо ifsmirnov, Kostroma, winger, AlexFetisov и 300iq за тестирование раунда.

Желаем удачи на олимпиаде,
команда Технокубка.

Поздравляем победителей!

Технокубок:

  1. ---------

  2. I_love_Palindromic_Tree

  3. iakovlev.zakhar

  4. IsmagilS

  5. DCNick3

Div. 1:

  1. jqdai0815

  2. Radewoosh

  3. Swistakk

  4. Um_nik

  5. consecutivelimit

Div. 2:

  1. Kammola

  2. ehnryx

  3. LifeCracker

  4. emoairx

  5. laofudasuanbaofushehui

UPD: Разбор

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

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

Mike during the contest ... "The round is declared semi-rated because no one thanked me for the platforms".

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

Tomorrow we'll have 2 El Clasicos: -> Real Madrid — Barça * -> Codeforces — AtCoder *

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

I'm concerned about one thing... How many problems were made by adamant, you say?

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

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

I'll do it for you. Thanks to MikeMirzayanov for the great Codeforces and Polygon platform.

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

Технокубок от адаманта, да, это будет весело.

Всем удачи!

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

It is rated.

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

Help Post, Why my solution was getting WA? Problem My Solution.

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

Why does the tourist not attend?

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

Hoping short problem statement

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

High ratings to everybody! What a sad story...)

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

the truth is, i'm not getting out neither from the gray zone nor the friend zone -_-

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

Any scoring distribution?

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

The English translation for problem A needs some work.

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

Why so long, man?

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

This round is impossible, I can't understand half of the english.

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

good job author !!!these nerds who are complaining about the tasks are just mad!!!

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

reading the statements I feel like I must work on learning this type of English rather than coding ..really sucks!!

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

RIP for problem statement ____/_____

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

RIP for problem statement __________/_____________

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

In problem 1, the statement is not clear. May be add another example or make the explanation clear. Bad English translation.

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

I never met a contest like this. Such a large code work???

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

Comprehending the questions seems harder than solving them :/

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

After reading problem A's statement, I'm not sure what I've actually learnt in 10+ years studying English...

Can't understand a thing.

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

    Please, clarify major mistakes in English in the problem A.

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

      I believe problem statement is enough clear for A. Though I haven't participated but read out the statement.

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

      I was over-reacting a bit while commenting this. My apology (if it upsets you).

      In general, this problem statement is kind of... confusing.

      At first, as my expectation (like 95% of the Div2A problems I've come across), I go straight into the examples and criteria, and I was like "3 cars? wait then 4 variables... what is the last bear doing?"

      Then I looked up a little bit.

      Masha came to test these cars. She could climb into all cars, but she liked only the smallest car.

      "Alright, so the cars are there in a way that only the smallest one satisfy Masha, others either can't be climbed or Masha doesn't like them..."

      A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It's known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.

      Three similar sentences, consecutively. I don't know what others may think, but its repetitive state made my head almost freeze.

      A few thoughts clouded my head, such as "wait can papa bear climb on mama bear's car?", "can mama bear climb on papa's?", etc.

      This is not what most of us expect in the easiest problem for Div2. I know my point may be biased, but it's mostly intended to be solvable for almost everyone in quick succession, so one should not make the statement open up a whole possibility for confusion and needs for clarification like this.

      Then I made it to the conditions for liking/being able to climb a car:

      It's known that a character with size a can climb into some car with size b if and only if a ≤ b, he or she likes it if and only if he can climb into this car and 2a ≥ b.

      Took me about 3-4 more minutes to understand (at first glance it seemed like the two inequalities contradicted each other).

      To be fair, it was not some critical errors in spelling, or grammar. The problem lies in the expressions — to me (or at least it is me during bad mood, but I won't think other people share this coincidence with me) it is somewhat unnatural and it may jam contestants' comprehending speed.

      Lastly, thanks for directly responding to my comment. I was a bit astonished when seeing the notification.

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

        I also found this problem statement complex, I think many contestant did

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

        I've spent the same amount of time for reading Problem A statement and solving Problem C completely.

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

        I agree. I delayed more than 20 minutes to understand the statement and it is pretty simple. I don't know why exactly but It is made in a way it makes it hard to understand.

        Last week in usaco I didn't solve any problem but read and understand all of them in less than 10-20 minutes that was the time I delayed to read this problem in this case.

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

      Maybe the problem is that it's too clear xD

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

насколько я понимаю из комментариев и турнирной таблицы, знание русского языка — это очень большое преимущество в этом контесте))

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

    А в чем проблема? (это не наезд); у меня таких проблем не было)

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

Third pretest is not correct by the game rules because players cant make such moves (in the middle square) without touching middle positions of all squares, but the output of this pretest shows that the right code doesn't give a f*ck to such errors, so WHAT THIS TASK WANTS?

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

    Read the line about the hare. It doesn't matter if the current structure is possible or not, you just have to tell the next possible move

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

Is anyone else finding the problem statements hell lot confusing more than normal CF rounds? :(

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

Is anyone else finding the problem statements a hell lot more confusing than normal CF rounds? :( :(

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

worst contest ever -_-

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

Please tutorial good some provide links to lean English :/

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

worst contest ever

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

This contest should at least be semi-rated. RIP English!

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

My first Div.1 contest!

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

Couldn't even solve A :(

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

This problem from a Korean judge seems quite similar to Div2F/Div1D, but the value of modulo in this problem is at most 106.

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

Неправильная разбалловка для D1B, D1C...

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

How to solve C?

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

    dp[mask] = minimum number of steps to get clique consisting of vertices in mask.

    Now iterate through each member of mask (provided mask is reachable state) and try to get him to the next step. It is profitable only if vertex has some neighbour outside of mask — it also means that he could have not been selected yet.

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

      I had the same idea, but how to prove it's always optimal to chose an adjacent vertex of the clique at each step?

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

        You choose any of the vertices already in mask and you compare dp[mask + neighbours] with dp[mask]+1.

        In every optimal solution for mask, one of it's vertices had to have been chosen as the last one. We take the optimal vertex and it's neighbours out and the state for the remaining subset is already optimal.

        Edit: You can't select a vertex wchich have set of neighbours (and itself) disjoint with the rest, as it could not construct a clique. dp[mask] is the minimum number of steps to make masks a clique. If you select some 2 disjoint sets there is no way of connecting them, so mask will not be a clique, hence you always have to choose a vertex which is part of the existing clique.

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

    C can be solved in O(2n * n) with brute force. There is no need for DP. We can use the following observations to test whether a subset S of chosen vertices is valid:

    • The order of choosing vertices in S doesn't matter.
    • S is valid iff for every pair (u, v) there is a path from u to v that uses only vertices in S as intermediate vertices.
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Didn't notice that the order doesn't matter. Thanks.

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

      How to verify that path requirement in O(n)?

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

        I used BFS. Start from any vertex in S and only push new edges to the queue if the current vertex is in S. Then check if every vertex was visited.

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

          What if every person is friend to every other person ( Like when m = n * (n - 1) / 2 ) Then the answer is 0 and S will be empty.

          And can you please elaborate your algorithm? How will it run on graph like this : N = 5, M = 4

          Edges :

          1 — 2

          2 — 3

          3 — 4

          4 — 5

          Thanks.

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

            I had a separate check at the beginning of the program

            if(n==0 || m == (n*(n-1))/2) {
                cout << 0 << endl; return 0;
            }
            

            For the your example case, it would look something like this:
            - While trying all subsets, we currently have S = {2, 3, 4}
            - Start BFS from 2, add 1 and 3 to queue
            - Visit 1
            - Visit 3, add 4 to queue (not 2 as it's already visited)
            - Visit 4, add 5 to queue
            - Visit 5
            - Now that the BFS is finished, check that all vertices are visited. They are, so update the best subset to be S.

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

              What if S = {2, 4}?

              Then you will be visiting all the nodes although 1 and 5 cannot be friends.

              Correct me if I have mistaken something.

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

                Steps would be as shown:
                - Visit 2, push 1 and 3
                - Visit 1, nothing pushed as it's not in S
                - Visit 3, nothing pushed as it's not in S
                Queue is now empty and not all nodes have been visited

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

          Why is it linear in nodes, not edges?

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

            Yes, BFS runs in O(V+E) == O(E), however this is still fits quite comfortably into the time limit, with my solution running in ~300ms. 33578496

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

    it's so hard to see ur color...how did ppl make out u were askin div1/2 :P

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

I quit

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

Seriously, what in the world is pretest #7 for C? I can't think of any corner cases...

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

    Did you unmark letters on ? operation?

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

      If I currently don't know the letter, and it gives me "? x", How will I know if he is shocked or not? I decided to make it the former and only then it passed pretests but I am not convinced that this is right.

      Lot's of ambiguity in this round.

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

        Statement said he only say correct letter at the end. So other '?' are shocked

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

        Because you're guaranteed to know the answer at the end only. It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action.

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

    if something like this occurs

    ". 25 unique characters"

    then you can find the required character.

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

    If the query is of third type and it is not the last one, then the guess is wrong.
    So we need to eliminate that character too from the set of possible characters.

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

      I also considered that case :\ Maybe my implementation went wrong somewhere. Thanks.

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

      WTF like seriously he always guesses wrong -_-

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

        yes, until the last query.

        It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action.

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

        It's not that he always guesses wrong. It is only that if he guesses right, the game is over. So every guess before the last one will be wrong

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

    27 . a . b . c . d ... . y ! z ? z

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

    there is no edge case in it . just make two set one of which contain all the character that can't be hidden character and another contain all the possible values of hidden character.and at any time if size of possible values set become 1 or size of impossible set become 25 , then we can uniquely determine the hidden character.

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

      I was using two boolean arrays and simulating something like that, but perhaps it didn't work like I thought it did.

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

    some n

    . b

    ! ab

    .... ?a

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

    Did you initially believed all characters to be a possible special character candidates. Only those mentioned in the strings are possible candidates.

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

      yes initially i considered all char possible then at each time when a string comes with '!' then i remove all the char which are in only one of them (string and possible set ) and put them in impossible.

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

    I think it was when wrong letters are repeated in a word, or at least that was my case!

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

How to solve B? (And if possible, please tell me how did you find that solution).

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

    I thought about looking at all permutations O(n!) for small values.
    For bigger tables there should be some way to distribute values that always works.

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

    I used chess coloring, then put all the white numbers to the left part of the table, and black to the right. Numbers with the same color obviosly aren't neighbors, so we just have to find n pairs of numbers with the different color, which aren't neighbors. For m > 4 that is easy ( for example, choose white numbers with j = 1 or 2, and black with j = m or m — 1). For m <= 4... some hardcoding.

    So, the point is, if I see problem about cells that aren't neighbors, I use chess coloring.

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

      Yup, I did the same thing, but I failed to account for the case of a tall and skinny matrix, because I was initially doing it row-by-row.

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

      From what I understand, suppose n =5 , m =5 ;

      so, white cells = {1, 3, 5, 7, 9, ...., 25}, and black cells = {2, 4, 6, ... , 24} ;

      Putting the white numbers to the left part of the table means, filling the matrix column by column, i.e. filling in this order -> {a[1][1] ,a[2][1],... , a[5][1], a[2][1], a[2][2],...), until we have exhausted all the whites.

      Have I understood it correctly?

      Where are you filling the black cells? Do you just fill them right where the white cells end? Also, what do you mean by this -> "so we just have to find n pairs of numbers with the different color, which aren't neighbors" ?

      Thanks.

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

        Yeap, i fill them right where the white cells end. But there is a problem: in a new table there is n neighbors (or n+1, depending on n and m) of numbers with the different color, so they could be neighbors in the first table, so we have to fill these cells so this numbers won't be neighbors in the first table.

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

          Got it. So, basically, when you were saying that we have to check n pairs of numbers, you were talking about the worst case scenario. Isn't it?

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

          One other doubt. Why do we need to hard code the solution for lower values of m and n.

          if (n *m == 1) { return "NO"; }

          else {

          We will do what you said above. If it is not possible to fill the array(i.e. we run out of possible black values to fill in the current matrix cell), we shall declare that there is no solution. Else, we have a solution.

          }

          Correct me, if I am wrong here.

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

    if n < 4 or m < 4, Just checked for 1000 random permutations, if the answer existed or not .

    For all other cases the answer will exist :

    I found the smallest prime which did not divide m(which will be among the first 10 primes) and started placing the numbers at this gap.

    Solution

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

      Any proof/intuition why that works?

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

        The intuition behind this was that if I am placing numbers at the gap which is a prime factor of m, I will get a smaller number around a smaller number. But I want it to be the other way round.

        Suppose n = 4 m = 6 Placing at gap 2 — >

        1.2.3.

        4.5.6.

        Placing at gap 3 — >

        1..2..

        3..4..

        As you can see, that numbers are appearing below each other. To avoid this the gap shouldn't be a factor of m.

        gap 5 — >

        1....2

        ....3.

        ...4..

        As you can see Numbers are not appearing below each other. But there's another case in which the gap may be a factor of n which is pointed below by Omar_Elawady. So we will place the number at a gap of the first prime which does not divide n*m.

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

      Fot the test "5 36", Your code prints 1 next to 37!

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

        Yes, you are right. I didn't think that through. The case you pointed out was that I haven't excluded the prime factors of n. In this case I am placing a numbers at a gap of 5, which is a prime factor of n.

        So instead of placing numbers at the gap of first prime which does not divide m, we will have to place the numbers at the the gap of the first prime which does not divide n*m.

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

what is problem A mean?

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

Does randomize algorithm work in problem B (and maybe C)?

And what are the deterministic solutions for these problems?

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

    I got pretest passed with a random solution on problem B, but I do have a lot of pragmas. Without them it took at least 6 seconds in some cases. I tried to submit C but I had a bug in the implementation.

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

    I came up with the following deterministic solution: for n & m less than 3, the answers are hard coded, otherwise;

    - for general case, initialize the original grid then rotate even rows 2 positions to the right and even columns 1 position to the bottom.
    - Else if m <= 3, then rotate the even columns 2 positions to the bottom, and the even rows 1 position to the right.
    - For cases where m = 1 or n = 1, I did a special handling by rotating each 3 consecutive elements, with step = 2

    Unfortunately, I couldn't get it AC during contest, and this is harder than the randomized one.
    http://codeforces.net/contest/907/submission/33573025

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

The gaming experience is very disappointing.

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

I've decided to capture this historic moment. Never been so high in my life :)

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

    All the best for the sys tests :)

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

    What's your solution to E btw?

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

      I've greedily added new vertices. If the vertex v introduces 10 new edges and vertex u introduces 9 new edges, I choose the vertex v instead of u.

      This solution doesn't work by the way ;)
      33565564

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

        oh wow! A greedy passed all pretests. Very weak pretests.

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

        I wrote a dp solution but unnecessarily resubmit. I had the following error — I initialized my dp state to be 1 for the mask consisting of the vertex and all of its neighbours.

        It is incorrect in case of isolated vertex and vertex with 1 neighbour — it should be 0 in this case as we don't add any new edges when we select such guy to the next step.

        However the case with 1 isolated vertex or an edge are special cases handled by if and the rest of dp seems to ignore such states in an optimal solution. Is there a test, where initialising such values to 1 instead of 0 could provide WA?

        Here is accepted submission.

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

    yeah ... at least you got the chance to get a AC on E pretests . good for you !! and keep it up

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

      Actually, I feel good about this systest failure, because there was nothing clever in my solution and it was just a leap of faith :)
      I'd have been sceptical about my rating otherwise ))

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

Worst contest I have ever had :(

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

Did anyone solve div1B/div2D using random? I was thinkin about it but didn't dare to code it.

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

    I submitted solution that uses random, but I had a bug in my code and got hacked. I think it should work.

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

    I generated solutions for n<=8&m<=8 using random, and solved for other cases :)

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

    I did it without any if's

    repeat 10000 times:
      for every cell of the grid:
         choose a random not yet used number for this cell. If it can't be neighbours with number from cell above or on the left, choose a different number, and so on at most 10 times. If succeeded, move to the next cell. If not, try from the very beginning.
    
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Horrible problem statements. The worst contest ever. I wonder how some people understood Div 2 A correctly and got it accepted in first attempt.

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

    the statement was correct, that's why.

    I believe almost noone likes problems like this but it is good to get people who do not read the statement properly and assume things just to be some minutes ahead (this works lots of times for div2A)

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

I didn't get AC but my idea for div2 E was something like binary search on the ans, generate all combinations of size mid and check.

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

    My idea was to use bitmask of friends.

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

    Nice idea!

    Although this approach is correct but it should TLE in my opinion ( however, it does not ). I am quite skeptical about the time complexity of the approach. According to me, it should be O(2n * n2 * log(22)) where n2 is for checking if the generated subset is feasible and the log factor is obviously from binary search.

    Here is the AC code : http://codeforces.net/contest/907/submission/33579509

    Have I done anything wrong in my estimation of time complexity?

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

      The number of subsets of size k is not 2n, but . So even if you generated these subsets for all the possible sizes, your amortized time-complexity would still be . And because of the binary search, it becomes faster.

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

For D, key idea is query(l, r) = query(l, min(l + magic, r)).

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

D is bullshit

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

Problem A's english was very unclear. Masha needs to be able to ride all three cars but she has to dislike the first 2 cars and like the smallest car.

Problem B's english was awful. Though they gave me some clarifications in the end, but it was too late for me. After the clarification, I was like "This problem is nothing but the english killed it". This ain't the first time in CF that english has caused major upset in the contest. Please after this, let some normal (knows basic english) people view the statements before posting it for a live contest.

Sorry, but this contest sucked only because of poor english.

I found problem C interesting and passed the pretests but problem B made me suffer and could not complete it in time.

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

    Don't know the situation with problem B, but I have no idea what is it that everyone dislikes about A. To me it seems like the problem is not English, but the fact that it requires a bit more thinking than the usual div2 A. In fact, English in this problem is absolutely fine.

    Let's take a look at your complaint.

    Here's your wording: "Masha needs to be able to ride all three cars but she has to dislike the first 2 cars and like the smallest car."

    Here's problem statement: "She could climb into all cars, but she liked only the smallest car."

    What new information does your wording provide? Why is it better?

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

      Your problem statement says that Masha may not dislike those 2 cars. She does not like it and she does not dislike it. Yes, in some senses, you can say she likes only the smallest car which means she hates/dislikes rest of them. But it is not true always. It could be that she likes the smallest car and she doesn't like the rest ( not necessarily dislike those). This caused the ambiguity. If you ask other people they will say that they made their solution thinking that Masha has to like the smallest car and for the rest she may or may not like it. "She has to dislike the two big ones" is not mentioned explicitly.

      did you get it?

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

        "he or she likes it if and only if he can climb into this car and 2a ≥ b."

        Pay attention to "if and only if" here. This means that when 2a >= b and a <= b, then she has to like it. And since it is written that she liked only the smallest one, it follows that the rest do not satisfy these constraints.

        If it's any consolation to you, the Russian statement uses exactly the same wording.

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

      I would rearrange the problem statement in the following way.

      First, define "climbing" and "liking" as in the problem, in order to give the problem statement a more logical ordering. (This isn't an English exclusive issue, this is an issue in the structure of the writing)

      Then, explain problem statement with first and second paragraphs.

      Second paragraph being in the past tense is very confusing, especially since what came before is in the present (Father bear can..., Mother bear can...).

      Rephrase it as: "Misha needs to be able to climb into all cars, but only like the smallest car. Given sizes of the bear and Misha, determine if finding a set of car sizes is possible. If it is, print them."

      I don't think the error in this problem was that it was intentionally misleading (certain problems do this very well). The problem statement was not misleading, but it was structured in such an illogical way that made it really confusing and tricky to understand.

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

How to solve Div1D?

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

Сегодня в маршрутке девчушка лет 4-х спросила маму: «А если всем попросить Бога, он выключит систесты?». С мамой плакала половина маршрутки… Боже, выключи систесты!!!

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

Time limit for Div.1 C was pretty good, really fast n^2*2^n(just the OR(|) operations) did not pass. How to solve it in n*2^n?

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

    O(n) to check if each integer(representing each friend) has value 1<<n — 1. I think the order of making friends do not matter.

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

      yeah but to simulate new friendships you need to do M operation for each case. That's (n^2)*(2^n)

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

        I just ORed the current friend with all friends. That's the O(n). I mean... If the current friend is 2, and he's friends with 3,4,5 then OR 2's friendships on top of 3,4,5 person's friendships

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

    I had 2^n*n^2 lol. Try using bitset.

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

Большое спасибо организаторам за интересные задачи!

У меня вопрос по правилам форматирования выводам и взломам. В правилах вывода в условии задачи Б сказано:

Если же она существует, то в первой строке выведите «YES» (без кавычек), а в следующих n строках выведите по m целых чисел — искомую таблицу.

Я заметил что участник выводит в некоторых случаях матрицу в транспонированном виде, что противоречит условию о n строках и m столбцах, но взлом не прошел. Жюри ответило, что формат вывода не важен:

Можно ли узнать подробнее, в каких случаях не важен формат вывода? Хотелось бы больше не попадаться и оградить себя от подобных потерь очков на взломах :)

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

    Обычно игнорируются пробельные символы, ведущие нули и различия вроде 1.05 и 105e-2 в вещественных числах. Иногда игнорируется регистр букв.

    То есть чекер вряд ли проверил и такую матрицу, и транспонированную. Он просто прочитал nm чисел из входа, как если бы они были выведены с правильными переводами, и расставил. Если бы тест был посложнее, вполне возможно, что участник бы получил с точки зрения чекера совсем не тот ответ.

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

I don't think those problem should appear in codeforces round(And problem A,B,C are all horrible problem statements), because we have only 2 hours to solve them.

Practice our idea instead of Reading comprehension plz.

Too large statement just make us feel awful.

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

I think problem A div2 needs to highlight some points, such as how Masha dislikes the first 2 cars.

Of course it was my fault for not reading the statements clearly, but it should give more of a "competitive programming" rather than "competitive problem reading".

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

How to avoid MLE in E? I took a matrix of size int[1<<22][22].

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

Worst descriptions ever; Ambiguity everywhere.

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

Was there a way to solve div1B without case bashing? There seemed to be so many cases I needed to take into account (1,1), (3,3), (N, M <= 3), (N=2,M>3), (M=2,N>3), (N=2, M=3), (N=3, M=2), (N,M >= 3)

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

How to solve Div2/A :c

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

вот у меня в городе если вы знакомы, то это не значит, что вы друзья

это по условию, а по задаче: как решать div1C?

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

I have no interest in solving these problems.

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

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

    If you don't have good idea then solving this problem is an ugly process, but once you realize that it can be done by random then it is completely fine.

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

      I didn't know there is a random solution, all the ones I've seen are case bashes :P. While it's much better, it's still pretty ugly. What's the point of a problem where the solution is just hoping that random passes and implementing?

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

        It's not that simple here. You need to have a good understanding whether random can pass or not. Here if I'm not mistaken probability that random permutation is fine is something like which is too small and trying random permutations will not give you AC. However number of bad pairs will be very small (~8), so you can get those bad guys and put them in random place and this process should end very quickly. In my opinion that's an interesting solution far from "let's write naive random and hope it passes".

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

          Yeah that's a very nice solution, thanks for explaining it :D

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

          Could you explain how to calculate these probability?

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

            There are ~m2n2 / 2 pairs of people in total and ~2mn are neighbours in every arrangement. For a particular pair of neighbours in new arrangement prob that they were not neighbours in previous arrangement is ~. Of course these events are not independent, but their independence is so little that prob that new arrangement is fine can be estimated as roughly

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

      It was a huge hint to see first two ACed solutions both working in 1.9 seconds :)

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

    You are a funny guy!

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

    Being libertarian? :D

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

    You only need to handle 3 case:

    • m > 4
    • n > 4
    • m, n ≤ 4

    The first two has deterministic solution, the last one can be done using randomization.

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

I think this round is Reading comprehension-Dead do(loop without any algorithms)

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

for problem A, i wanted to hack this solution 33555103, but i could not because contest ended. i think this solution will get TLE on this test case: 100 49 20 5, ironically it got AC on system test ???

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

Shiiit this B and A

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

Thanks, for the fastest system test.

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

    there weren't that much of solutions to test and that is why it was fast,so you should thank for the shitty problems set

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

I kindly recommend that you should rename Codeforces "Readforces."

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

This guy used multiple accounts. { ethereum, yerkimbekov }

Have a look MikeMirzayanov

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

Помогите, пожалуйста!

Я не могу понять, что не так с моей программой?

Похоже, на 2 тесте происходит только ввод N, функция Evolution() не запускается...

Помогите, пожалуйста, выяснить, что не так. 33571490

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

In Div2 Question A In 6th pretest i.e [v1 v2 v3 v4]=[100 99 98 100] why is the answer -1 ? and why is [200,198,100] wrong answer?

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

    Well, it's wrong answer because Masha can't get into the son bear's car.

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

      But, the size of masha is 100, it can easily get into son bear's car according to the question. As, 100<=100

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

        Ohh...Sorry...

        Maybe, the answer is wrong because Masha likes not only the smallest car?

        100 * 2 >= 198.

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

          Yeah, you are right,

          The thing is masha only likes the smallest car.

          But, here it likes the second car and the first one too.

          Thank you for this.

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

    This is wrong because masha liked only the smallest car. But in your case, she also likes the medium and large car.

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

    Because the max size of mama bear's car is 198 and hence Masha will like mama bear's car. However, Masha can only like son bear's car. So answer is -1

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

    Masha also likes the cars of father and mother bear as 200<=200 and 198<=200. He only has to like the son's car.

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

    Oh My bad did not see only in the question.Thanks Guys

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

Help me, please!

I really can't understand, what's wrong with my program.

It seems like only getting N is happening in test 2, Evolution() is doing nothing...

Help me, please, to find out what's wrong. 33571490

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

    Привет, Всеволод)

    NumbHits++ нужно делать не всегда, а только если он уже мог угадать

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

      Рад тебя видеть!

      Но... Я ведь вывожу не NumbHits, a NumbHits — NumbNeed. Как только в массиве Litter[] остаётся ровно одна буква, я кладу NumbHits в NumbNeed и больше не меняю...

      Тут в другом проблема...Функция Evolution() на тесте 2 вообще не запускается. Если добавить вывод в её начало, на экране ничего не появляется.

      И массив себя на тесте 1 странно ведёт... В нём либо все ноли, либо все единицы.

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

        Функция evolution() во втором тесте запускается прекрасно, но есть пара недочётов. Первый баг, который я поправил, чтобы пройти второй тест, состоит в том, что, когда чувак неправильно угадывает букву, ты просто увеличиваешь количество ударов, а надо этот символ прочитать (без сина идёт дальнейший сбой) и в массиве Litter обнулить. Сравни свою посылку и мою 33576279

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

        Если тебе интересно, то вот 33576931 полностью исправленное решение

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

Sometimes poor problem statement, sometimes bad problem-set, sometimes not maintaining expected difficulty of certain problems, sometimes 20 minutes long queue, unrated, semi-rated contests — Codeforces is frequently failing to maintain its quality contests.

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

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

rated . ?

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

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

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

Why my output is wrong? (Div2A)

input: 99 50 25 49

My Output: 99 99 49

Judge Output: 100 99 49

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

Want to see some cheaters? Here are they: Edgration. and Anoxiacxy. Submissions for Div2 D: xlj's:33566367 and Zero_cxy's: 33564264. You can see that xlj replaced some parts of Zero_cxy like dfs -> asfkolasnhf, mt -> map_asfknas..., and Zero_cxy added a tree struct at the beginning but didn't use it to cheat. Those guys should be disquallified from this contest.

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

I think Codeforces server is having a few issues.

I've just received this announcement recently (one of my friends received it about 5 minutes before me).

In my opinion, this announcement must be presented long before, but for some reasons it won't pop-up in some users' browsers. Perhaps you should have a look.

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

div2e

I don't understand why this output -testcase 1- is wrong?!

2 2 4

after 2 introduces all of his friends to each other, all of 1 , 2 , 3 , 5 become friends. Then choose node 4 so all nodes are friends. Someone help me understand this please.

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

    This is the initial graph (ignore the numbers outside of the circles, they were my drafts actually xD) After you choose guest 2, the link between 1 and 5 will be made. The similar applies to 3 and 5. (as 1, 3, 5 are guest 2's friends).

    When you choose guest 4 afterwards, since he only has 3 and 5 as his friends, and they are friended already, no more links will be made.

    2 and 4 are still not friended yet, so your solution is wrong.

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

I was screwed up at the testcase n=1,m=1 (Div.2 D)

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

Worst Contest ever!

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

Как можно было дать такую ущербную таску А дать??? (Див 2)

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

now due to problem E, am trying to learn bm + dp. How to start it. i.e as of normal dp is concerned, first thing a brute force solution and then memoize it. But as for bm + dp, i looked into TSP. But there the brute force way is just factorial and it has nothing to do with the subset construction. I also looked into tutorials of hackerrank (Assignment problem). But i could not understand it. So can someone give a detailed explanation of how to approach bm+dp and how to solve it? TIA

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

My rating has been 1900.. I do not know should I be sad or happy :-)(

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

In problem A

TEST Case : 100 99 98 100 Output should be : 200 198 196

Because They can climb 100 < 200 AND 99 < 198 ANS 100 < 196

They can like also 100*2 >= 200 true 99*2 >= 198 true 98*2 >= 196 true

Masha can clim all of them and he can like the smallest one 100*2 >= 196 true

So why the system give WA and give -1 instead of this solution ?

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

AshishYadav are true now :)

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

Div2A: For input 100, 99, 98, 100 can someone tell me why 200, 198, 196 is not a correct answer?

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

DIV2 people(Pupil) who don't understand problem A and getting low rating :p Your text to link here...

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

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

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

Can anyone explain why the following formula is true, and how to use it to solve D?

when b > phi(m)

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

    Is that (mod m) over the whole power or on just b?

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

    Assumption, m = p * q, Where p is as large as possible such that gcd(a, p) = 1. Applying Euler's theorem for modulo p. For modulo q, because b > φ(m) so the remainder always is 0. That is the purpose of plusing φ(m) in φ(m) + b mod φ(m),

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

      For modulo q, because b > φ(m) so the remainder always is 0

      Can you elaborate on this? What remainder that is "always 0"?

      PS: Got it. Since a is divisible by all the prime factor of b, ax will be divisible by b when x is large enough. (φ(m) is just a possible lower-bound, the actual lower-bound can be lower). Is that correct?

      PS2: Also, how to prove that if and , then ?

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

        The rest is quite clear. ab ≡ aφ(m) + b%φ(m) modulo p, q. Because gcd(p, q) = 1) so done?

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

          Got it. Turned out the last piece of proof that I'm missing is Chinese Remainder Theorem.

          Thanks for your help. (I spent the entire morning just trying to prove this formula)

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

    Only one clarification, when b>phi(m) may be exchanged for when b>log(m) I have an empirical not bounded proof, means that I can only prove that in some point that formula works. I unable to give a full proof of one of the two lower bounds, but the boths works nicely.

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

    This solution doesn't seem to be using the property you mention but still gets AC. :/

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

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

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

Что за прикол с победителем отбора?

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

Actually, Problem A refers to the famous Russian folk tale about Masha and three Bears, that's why we have such a long statement. So, by solving this problem you can look at the part of out culture. Here is the original text:

Once upon a time, there was a little girl named Masha. Onу day she went for a walk in the forest. Pretty soon, she came upon a house.  She knocked and, when no one answered, she decided to walk right in.
At the table in the kitchen, there were three bowls of porridge. She tasted the porridge from the first bowl.
“This porridge is too hot!” she said. So, she tasted the porridge from the second bowl.
“This porridge is too cold,” she said. So, she tasted the last bowl of porridge.
“Ahhh, this porridge is just right”.
After the meal Masha decided to have some rest and went into the living room. There she saw the three chairs: large, smaller and the smallest. Masha sat in the first chair and fell from it.
“This chair is too big!” she exclaimed. So she sat in the second chair.
“This chair is too big, too!” So she tried the smallest chair.
“Ahh, this chair is just right,” she said.  But just as she said this, the chair broke!

Then Masha decided to take a nap and went to the bedroom.  She lay down in the first bed, but it was too hard.  Then she lay in the second bed, but it was too soft. Then she lay down in the third bed and it was just right.  Masha fell asleep.
As she was sleeping, the three bears came home.
“Someone’s been eating my porridge”, – growled the Papa bear.
“Someone’s been eating my porridge”, – said the Mama bear.
“Someone’s been eating my porridge and they ate it all up!” – cried the Baby bear.
“Someone’s been sitting in my chair”, – growled the Papa bear.
“Someone’s been sitting in my chair”, – said the Mama bear.
“Someone’s been sitting in my chair and they’ve broken it”. – cried the Baby bear.

They decided to go to the bedroom. Papa bear growled: “Someone’s been sleeping in my bed”.
“Someone’s been sleeping in my bed, too”, – said the Mama bear.
“Someone’s been sleeping in my bed and she’s still there!” – exclaimed Baby bear.
Masha woke up and saw the three bears. She jumped out of the window and ran away.
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Div2 B, the problem statement says '.' will be found where there is no 'x' or 'o' but if you check your submission you can see they are passing underscore '_' instead of a period. To find this go to your submissions and click on this problem. Anybody face the same problem?

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

Сколько человек из основного раунда проходят в финал?

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

Ну блин. Валялся аккаунт полтора года, никого не трогал, решил поучаствовать в одном-единственном контесте — и вот те на. Как поменять хэндл? Я не антисемит, просто "GasTheKikes" — это первое, что мне в голову пришло, когда я ник придумывал.

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

Thanks to MikeMirzayanov for such a great platform and all the red coders who create such nice problems which i feel are great to improve not only our basic and fundamental skills of core CS but also thinking skills to great extent. but it seems that quality of the problems is decreasing now-a-days .

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

is there any editorial?

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

Is there any editorial?

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

What's wrong with codeforces again? Why nobody is on first place?

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

Why did you disqualify GasTheKikes?

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

Why did you remove GasTheKikes , the winner?

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

    Look up "kikes" on urban dictionary. And if you still not understand it, read about WW2 and the holocaust.

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

For Div2 E (or Div1 C) "Party", is there anyone that has passed it by using the following algorithm?

Lemma: A group of guests is available iff I. their friends cover all people II. without other people, they are still connected

So just use a bit-dp, generating all states and check that if each of them satisfies the lemma above, and choose one with the minimum number of people.

Total Complexity is O(2^n*n)

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

    Of course one can do some pruning in the dp-process, and it'll be much quicker.

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

    In particular, for each state(that is a bit-representation of people) I, maintain 2 data, one is whether it is connected (a bool), the other is their friend (using a int to represent it by bit-representation)

    and just check every friend J of them who is not among them, and update the state I|(1<<J), set its "connected" to true, and set its "friend" to (friend of I)|(friend of 1<<J)

    and when a state K, its friend covers all, then it is an available group of people, and one should use it to update the answer.

    and it can be proven that the answer will have nothing to do with the order of the guests.

    So it's O(2^n*n) in total.

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

      Is it easy to prove the order is not important?

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

        I think it's pretty easy though, don't know how is it to other people.

        consider 2 series, representing the same people but in different orders, let's call it A and B,obviously A and B are permutations to each other.

        consider an operation in a series, which is swapping 2 neighbouring person, and we can do some finite steps of such operations to transform series A into series B(like bubble sort).

        so we just have to prove that in one such operation, their is no difference between the final outcome, and then, because A can transform to B by some finite steps of those operations, and in each steps, the outcome won't change, so in the end, A and B are equivalent in outcome.

        and I'll prove that such operation won't make difference to the outcome. consider two series, satisfying series 2 is transformed by series 1 after doing one such operation. they'll have the formations as below: series 1: ab..zXYa'b'...z' series 2: ab..zYXa'b'...z' (swapping X,Y) when we have performed the common prefix ab..z, their outcomes are same. when a person P have introduced all of his friends to each other, the friends of only P's friend maybe changed, but the friends of any person who's not P's friend will stay unchanged. so if X and Y aren't connected currently, performing X will not change Y's friend, and what Y do next will be have no difference, so as performing Y first and X next,so there's no difference between ab..zXY and ab..zYX and if X and Y are connected currently, performing X will let all X's friends know each other including Y, and then performing Y will let all Y's new friends(from X) and Y's old friends(not from X) and X and Y, all know each other, the outcome is all of X or Y's friends including themselves knowing each other, and the friends of people who aren't X or Y's friends stay unchanged, so if we performing Y first and X next, it's the same outcome. so no matter whether X and Y is connected currenty, performing X then Y, is equivalent to performing Y then X, so ab..zXY is the same to ab..zYX after doing the common suffix a'b'..z', ab..zXYa'b'..z' is equivalent to ab..zYXa'b'..z' so it's proved that such operation won't make difference to the outcome.

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

    A group of guests is available

    Could you, please, elaborate what do you mean by available?

    their friends cover all people

    And this.

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

      I think he means that if you use that group then all people will be connected

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

      a group guests that satisfied the constraints: after one by one they come to introduce their friends to each other, all people will be familiar with each other.

      that's what I mean.

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

    I've used google translation to translate the Russian version of editorial, and found the idea for this problem is just the same as I posted.

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

      Where can i find the editorial?

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

        enter the contest interface, and the link "Tutorial" is at the right-bottom corner.

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

          When i click tutorial, it says "You are not allowed to view the requested page" What can I do?

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

            oh I've just found what you said. the link is available earlier when I enter from it.

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

Is the editorial up?

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

System test for problem B (div 1) is too weak. For example, 33583372 this code will surely get TLE with 3 33333, in custom test it ran for ~6s.

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

А почему у топ 1 нету хэндла?

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

Good contest, the problemset was perfect, We want more contests like this. but please use better problem statements.

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

Why everyone always complaint about Codeforces. But it is not only happening with you others are also facing it. I think it is due to you are not able to perform well in the contest and same is happening with me but complaining according to me will not solve that problem. Try to perform well in the contest. See people like KAN and other more who are red and even purple also. The difference b/w them and us is that they try to not commit the mistakes that they have committed earlier. I hope my message is clear to all and if u don't wanna give a shit to this then u are different :(

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

vintage_Vlad_Makeev Please upload the editorial.

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

div2e My approach is greedily pick the node that can create as many as possible edges among friends. Got Wrong answer on test 51 :'( Code: http://codeforces.net/contest/907/submission/33589732

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

    a concise counter-example to the greedy algorithm you said above is like this: 9 13 7 8 8 9 9 7 7 1 7 2 7 3 9 4 9 5 9 6 8 2 8 3 8 4 8 5

    (the answer will be: 2 7 9 ) that's because of the person 1 and 6, the person 1 just know 7 in the beginning, and 6 just know 9, so (7 or 1) and (6 or 9) must be chosen, and if you just choose 7 and 9, they will be an answer to problem, without 8(although initially he knows the most number of people comparing to 7 or 9)

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

When will we get the editorial ?

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

Where can I find the editorial of this contest?

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

Any plans of publishing the editorial in near future? :)

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

In div2 E what if m=0 then even if do operations in any order then also we can't make all of them know each other??

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

    It's guaranteed that each pair of friends is described not more than once and the graph of friendship is connected.

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

please upload the editorial :/

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

For question 1 of div. 2 test 4 is input "99 50 25 49" my output is 99 50 25

which I think is correct because mama bear fits and likes her car, just like papa bear and Masha can fit into son bear's car because son bear's car-size limit is 50, and Masha is size 49.

The correct output is apparently 100 99 49 which is also correct as all bears and people can fit into their cars, but this is not the only solution and in the question, it is stated that "multiple answers are allowed" if you want the source code for my solution the link is https://pastebin.com/AK8yXQPN . Thank you for posting any solutions/ answers to my question.

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

    Think about it: the problem asks you to output the size of the cars of the three bears. The condition is that Masha should be able to fit into all three cars (which means that Masha's size should be <= all three bears sizes), but only like the small car (which means that Masha's size *2 >= only the small bear's car's size). In your output, neither condition is met, since Masha (size 49) cannot fit into the small car (size 25) and Masha likes both the small car and mother bear's car (since 49*2=98 which is >= both the small and medium car)

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

      Where exactly did the problem state that Masha should fit into all cars? It is implied that Masha HAS TO fit into all cars larger than her (including mama and papa's) and she does like the son's car.

      Overall the question was very confusing in both languages (I read it in Russian and it made no sense at all) and it was the reason I was stuck on this one question for the whole round.

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

        The same issue all of us are complaining about: badly written statements. I read the problem in English and it stated in the problem description.

        "Masha came to test these cars. She could climb into all cars, but she liked only the smallest car"

        I also got stuck in this one for the first 50 minutes of the contest.

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

so...random_shuffle works for D-Seating of Students, this is interesting.

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

    Just random_shuffle doesnt work as I explained above and indeed I tried it after contest and it is too slow, as expected.

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

I have a question.

I send this 33572495 for problem A dive2 in problemset and got AC.

and output for this testcase is:

input : 100 10 9 15

output : 200 10 15

but answer is -1.

why this code got AC! :)

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

What is the answer to this test case of DIV 2 C

6

! codeforces

! hello

? e

! e

? o

? e

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

Шото сложна

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

i think you should never publish an editorial if you want to keep this contest as the worst contest ever !!

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

I cannot wait to see the editorial!
Hope it will be published soon.

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

Can you Please publish the editorials?

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

Came for the tutorial again. Found nothing again.

Please upload the tutorial :( Thanks a lot

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

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