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

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

Всем привет!

Очень скоро, 19 мая в 17:00 MSK, состоится очередной Codeforces Round #184 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Игнатьев Александр (aiMR). Это наш второй раунд, и мы надеемся, что не последний. Выражаем благодарность Геральду Агапову(Gerald) за помощь в подготовке задач, Михаилу Мирзаянову(MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой(Delinur) за перевод задач на английский язык.

Мы надеемся, что Вам понравятся наши задачи, и вы получите удовольствие от их решения.

Настоятельно рекомендую Вам прочесть условия всех задач!

Всем удачи и высокого рейтинга!

UPD1: Распределение баллов будет стандартным: 500, 1000, 1500, 2000, 2500.

UPD2: Разбор задач

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

  1. SillyHook06
  2. hyplymac
  3. HAPKOMAH
  • Проголосовать: нравится
  • +147
  • Проголосовать: не нравится

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

I like the previous contest of gridnevvvit. i hope this contest is similar to previous.

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

I think it will be interesting. :)

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

I hope that contest would be easier than last time(181 round)

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

"Настоятельно рекомендую Вам прочесть условия всех задач!" плагит взятый в Sereja :)

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

    Во-первых, Sereja пишет Настоятельно рекомендую прочитать условия ВСЕХ задач, что всё-таки отличается от призыва в этом анонсе. Во-вторых, подобные призывы встречались и до того, как Сергей начал проводить контесты. Например, здесь.

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

Даешь динамическую оценку и расположение задач не в порядке возрастания сложности!!!

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

two successive rounds that starts at 17:00(MSK) I hope this starting time keeps on.

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

ухты! Неожиданно!)))

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

    Это уже с Testing Round 6

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

    Ну вот зачем такие огромные скрины делать, растягивая страницу и залазя на прямой эфир? Уменьшил бы в размерах хоть...

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

      Наверно лучше сделать это автоматически, с возможностью увеличивать по клику?

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

"pretest 3" what a pretest!

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

    Problem A ?... i can't imagine what is wrong in my code :(

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

      in problem A,

       Vasya can only sum pairs of integers (a, b), such that for 
      any decimal place at least one number has digit 0 in this place
      

      it means you cant get sum of (10, 20) but you can get sum of(1,0), (100, 11), ... Maybe it's the 3th test

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

        it says at least so I assumed that if both numbers had a digit that was 0 we could add them.

        also what exactly does this refer to?

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

          For each digit p in number a and number b, at least one of a_p and b_p has to be 0.

          e.g.: a = a_2 a_1, b = b_2 b_1 => a and b can be added if a_1 equals 0 or b_1 equals 0 (or both) AND [same condition for a_2, b_2] (=> a and b both have 2 digits, so a_2 and b_2 are non-zero => they can not be added)

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

      In problem A, the maximum number of the chosen integers is between 0 & 4. Because if you choose a 2 digit integer, you cant get another one( If you choose another 2 digit number, the first digit of both of them is !0 & you cant sum that pair). And you cant choose more than one of 1 or 3 digit numbers with same reason. So in maximum case, Vasya can choose 4 numbers a,_b_,_c_,_d_, a=="0", b = a one digit integer, c = a 2 digit integer, d = a 3 digit integer & d = "100" Sorry for my terrible English!

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

        this is not always true. what about the input 1 0 0 0? he can choose all the 4 integers!

        UPD: just re-read the problem statement. the input i mentioned is invalid, because all the integers must be distinct! sorry about that!

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

I_Love_WJMZBMR

This handle made my day.

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

I do not understand problem A's statement!!! Can Anybody explain to me what problem A means? Thanks in advance.

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

    Problem A is weird.

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

      Can you please explain this test case:

      3
      2 70 3

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

      Can you explain with an example?

      I thought that having two numbers A and B, then if and only if either of those numbers has at least one digit that is equal to 0, then the two numbers can be added.

      So for example 90 18 can be added, 11 99 can not be added and 10 100 can be added.

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

        actually 90 and 18 cannot be added because at 10's place there are 9 and 1 and none of them is 0.

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

      Yeah, this was my worst contest ever, A problem was very strange

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

    It seems like I will never understand what the author wants to get in Problem A. Problem Statement: "...pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place ..." Step 2 of tutorial: "If we got number greater than 0 and less than 10, we take it." I really do not understand then test case 2.

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

The Round #184 is displayed "finished" here. What happen?

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

The Round #184 is displayed "finished" here. What happen?

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

what was the pretest 3 in problem A?

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

Horrible !!!!

What a case is pretest 3 !!!! :/

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

Очень, очень крутой проблемсет. Давно не получал такого удовольствия от Div. 2 контеста.

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

В задаче 3 во вкладке "ЗАДАЧИ" контеста отображается TL 0 sec и ML 0 mb **UPD: **уже исправлено

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

This was a hard contest.

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

Что интересно. Задача B опять заходила на питоне с минимальными усилиями. В комнате у себя видел такое.

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

worst contest ever for me.... :(

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

I can't connect to "yandex.st" website. This issue increases time of loading each page to 4-5 minutes for me. I should have waited a long time for reading problems or to see the result of my submitted code during contest. Anybody else having the same problem? Can the moderators fix this?

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

http://saveimg.ru/show-image.php?id=31a2f20b88c0b681a46d99ce0314ec9a Что это за баг по задаче С по времени и памяти???

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

ideas for solving C ??

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

    Think of the binary representation of the sum and the binary representation of a 2^v -1 decimal number.

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

    2^V-1=2^0+2^1+2^2+...+2^v-1 if array consist of distinict elements ans=MAX(a1,a2,...an)+1-n; there is only one problem if you have same powers in array.In this situation you need to transform your powers in such way that get distinict powers, for example: if you have 2^8,2^8,2^8 you can tranform it and get 10^8,10^9 if you have 2^4,2^4 you can tranform it and get 2^5

    sorry for my poor english

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

    2^0 + 2^1 + . . . + 2^n = (2^(n+1)) — 1 Your task was just to find the biggest power of 2 and count how many of the powers from 0 to the biggest are not shown in the sequence. but dont forget to change two a s to one a + 1 for example : 2^3 + 2^3 = 2^4...

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

During system testing it showed that my C got accepted. Now, it shows that it failed on test case 26. What happened?

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

Dynamic scoring would work better!

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

How to use long arithmetic in this solution?

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

    Don't think you eally need it. What about d=gcd(p,q); p=p/d;q=q/d? :)

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

      WA43. I think that we need long arithmetic because of p = big prime number and q = big prime number => their gcd equal to 1 and it doesn't change our p and q.

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

        I am not talking about overflow. For example you have p=100, q=50. And your algo will find Pn=2 and Qn=1 which is quite the same.

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

      And another question. Why thistakes AC and WA43? What is the difference?

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

Can someone please explain this testcase for problem A: Input: 2 1 2 Output: 1 1

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

    consider answers: (0), (1 1), (1, 2), if you can choose (0), you can choose(1 1), in both answers you couldn't choose two numbers that can add together.

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

Could someone, please, help me? I can't find mistake in my solution for C problem. Here is my code.

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

cool bug in the codeforces! http://nic.p.ht/up/c70903297fe1.png

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

Conteste fogholade chert!! Maskhare bud...

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

Kudos to problemsetter for D. A really nice problem, in how a lengthy statement with many conditions can be visualized in a way that leads to a simple solution (although with several special cases to be checked).

To explain what I mean, my solution:

  • it's clear that the original graph, as well as any target graph, must be a DAG without multiple edges

  • the first condition for the target graph means that it contains a directed path through vertices 1->2->3->...->N; then, the 4th condition means that between any 2 corresponding vertices, there is no other (shorter) path, so "any edge from vertex i must lead to vertex i+1 or at least i+K+1"

  • the 5th condition boosts this to "any edge from vertex i must lead to vertex i+1 or exactly i+K+1"; you may view the graph as an incomplete cycle with additional "bowstring" edges

  • the 5th condition also implies that if there's a vertex i (with the smallest possible i) in any target graph that there's a bowstring edge from i to i+K+1, then all other bowstring edges may only lead from vertices i+1..i+K to the corresponding +K+1 vertices (if these exist); these conditions are also sufficient for any target graph

  • so if the input graph contains an edge from i to neither i+1 nor i+K+1, the answer is 0; similarly if there're 2 bowstrings i->i+K+1 and j->j+K+1 such that j >= i+K+1

  • if those conditions aren't satisfied, we must add all edges i->i+1 and then we can choose a suitable first bowstring edge (if the first bowstring in the original graph is a->a+K+1 and the last one is b->b+K+1, then the chosen first one must start at vertex at least b-K and at most a, inclusive, but also at vertex at least 1 and at most N-K-1, obviously); iterate over all those possibilities, or over all vertices from 1 to N-K-1 if there's no bowstring in the original graph

  • if we've chosen the first bowstring from i to i+K+1, the answer is 2^(maximum number of bowstrings we can add-number of bowstrings already starting at vertices between i+1 and i+K in the initial graph); the second part of the exponent is fixed due to all bowstrings having to start at vertices i+1..i+K, and the first is simple min(K,N-K-1-i) when indexing vertices from 1

  • precompute powers of 2 up to 2^K; then simply iterate over all possibilities and add them to get the answer

Details are skipped, feel free to ask if you find something lacking. Code: 3746010

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

    Thanks. I am a setter of this problem, but there was another statement. There were no initial edges in graph. But Gerald gived idea to add initial edges in graph

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

Не совсем понятное условие в задаче А.

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

for problem a test 3, the array of my output is :

[70, 40, 30, 100, 50, 60, 0, 16]

why it's get WA, if we sum from 70 until 0, the total is 350, and 350 + 16 is valid operation, i think...

thx

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

    30, 40, 50, 60 and 70 can't be in the same output. Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place

    In the second decimal place, none of them has 0

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

    You cannot sum 40 and 30, for example

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

      why ? isn't one of them has digit 0 ?

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

        "Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place."

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

          oohhh, took so long to understand that important sentence,

          at first glance what crossed in my mind is, vasya can sum pair of integer (a,b) if a has at least one 0 or b has at least one 0

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

            I made the same mistake and got two wrong answers. Two of my friends also misunderstood the statement. I think it would be better if there were more clear examples or sample tests

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

I wonder why updating ratings takes a lot of time!

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

    Checking solutions is a way easier problem than updating the ratings I guess

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

      You know, they have to change colors of nicknames at every single subdirectory. Manually. It takes time.

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

In Problem A. How can a single number form a pair?

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

    We're looking for such numbers that if we choose any pair, their addition is allowed. But if there's just 1 number, there are no pairs, so we never get a situation which is not allowed, so 1 number is a valid output :D

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

      Vasya wants to choose some integers from this set so that he could sum any two chosen numbers.

      But the set dosn't contain two numbers! So the output cannot be a single number i guess.

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

        Read "so that he can sum any 2 chosen numbers" as "there are no 2 chosen numbers that he can't sum". 1 number satisfies that.

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

          I think sometimes CF expects us to read the mind of the problem setter. :/ no more arguing.

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

            Sorry, but that's the standard convention in mathematics. I've encountered it several times (once with the warning that the problem statement uses strict mathematical logic :D).

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

            hang yourself

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

taking long time to update ratings!!!

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

Rating?

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

The contest time is too early for me! It's better if the contest starts two or three hours later.

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

Пора ввести регистрацию с прикреплением номера мобильного телефона к аккаунту, надоели эти бесконечные черные с одинаковыми никами.

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

The best contest ever... Problem C was easier than A!

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

Дорогие организаторы! Обратите внимание, что в задаче А было написано, что все числа разные, но были успешные взломы используя такие тесты. 3 0 100 100. Решите эту проблему. Спасибо!