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

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

Всем привет!

Скоро, 10 ноября в 21.00 MSK состоится Codeforces Round #210 и его автором буду я.

Это мой первый раунд на Codeforces и я очень надеюсь, что все пройдет хорошо. Спасибо Геральду Агапову (Gerald) и Виталию Аксенову(Aksenov239) за помощь в подготовке раунда.

Удачи!

UPD.

Разбалловка в первом дивизионе: 500-1000-1500-1500-2000.

Разбалловка во втором дивизионе: 500-1000-1500-2000-2500.

UPD.

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

Первый дивизион:

  1. Egor

  2. PavelKunyavskiy

  3. scott_wu

  4. Dmitry_Egorov

  5. mmaxio

  6. enot110

  7. sevenkplus

Второй дивизион:

  1. _ZigZig_

  2. budalnik

  3. Ilya_Yakovlev

  4. Neodym

UPD.

Разбор

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

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

Comments with a lot of positive votes requires a creativity that I don't have. :) So I just wish good luck for you with your first contest! :)

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

Поздравляю с дебютом!

Среди львовских авторов — пополнение) Надеюсь, все пройдет гладко.

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

4 соревнования для div2 почти за неделю — супер! Так держать!

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

новый автор = интересный контест)) ура!!!

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

Glad to see a very full list of contests after a long time!!
4 contests in 9 days! That's the best thing everyone wants!

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

New author — new type of problems!

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

why so many only div2 contests?? Being in div1 seems to be a negative thing nowadays.

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

    You can still participate in Div 2 contests, they just won't affect your rating. It's still good practice though.

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

      u are 100% right that Div-2 contests are good practice, but the thrill that comes with doing a rated contest will not be there, which IMO is the most important thing during the round.

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

Wow, two continuous Div-2 rounds !!! Hip-Hip Hurrey :D best of Luck :)

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

after more than a week, finally a contest! not just one, but this is the first of 4 rounds in 9 days! :)

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

Wow! +180, 30 minutes before the contest! That's awesome!

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

MikeMirzayanov happy birthday to your daughter Tatyana. Hope see had a wonderful day today :)

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

    funny to see lots of people misunderstood that sentence. :D

    "Oh, St. Dijkstra, Tatyana is 2 years old!" ... ;-)

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

    Why almost all of you think that her name is St. Dijkstra?? Dijkstra is a famous researcher in computer science, and his name was mentioned in the sense that he is a 'saint' in our programming world. How couldn't you understand such a simple thing?

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

      Ambiguous sentences invite ambiguous interpretations. In many parts of the world, it makes perfect sense to name one's child in honor of some intellectual hero like Dijkstra. Also, check out this guy named Aristotle Socrates.

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

Offtopic — I wonder what is (p1) at the bottom of the pages of Codeforces... :S

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

This contest is too late for Chinese coder...

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

Что-то мне кажется, что автор немного переборщил со сложностью задач.

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

problem d was dp right?

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

    does the votes mean that problm d from Div 2 was dp?!! cant some one just reply? is it that hard?!!

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

Why the standings are frozen during system test?

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

    That's because during the contest the solutions are tested using only the pretests (which are simpler than the final tests). At the end of the contest, the results are frozen and all the solutions are reevaluated using the final tests.

    It means that you can get accepted during the contest and at the end, if your submission fails on one of the final tests, your points for that problem are taken back.

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

Как решать Д (див. 2)

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

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

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

How to solve Div1 E? The idea is Dijkstra in a layered graph with (k+1)*n nodes?

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

Классный контест, клевые задачи. Понравилась С, жаль, не успел дописать.

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

how to optimize dp in problem C?

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

In C(div2) example 1 input : 4 5

1 2 3 1

2 1 2 8

2 3 4 7

1 1 3 3

2 3 4 8

output: 4 7 4 7

why is a[1] equal to 4? when we know : line 2, a[1] is max 8 line 4, added 3 to a[1] so answer is a[1] = 8 cos we don't know any other change..

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

What are the strings for the first and the second example of Div1 C?

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

    in first example zT where T >= 'a' && T <= 'z'.

    in the second example zy and zz

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

      zz has beauty 0, since there is no i,j such that s[i..j] is strictly larger than t[i..j], because y<z.

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

        Please check the change in the problem statement. It is written in bold.

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

          Well, when this change in the statement has been done? I had no idea about this change until just NOW!

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

How to prove gcd(i, i+1) =1?

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

    There are 2 cases : 1)if i is even, the i + 1 is odd, 2) if i is odd , then i + 1 is even gcd(even,odd) = 1

    incorrect,sorry)

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

    пусть i делится на какое-то простое p, тогда i+1 имеет остаток 1 по модулю p, и так для всех простых для обоих чисел => взаимно просты

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

    because of 1*(i+1) — 1*i = 1

    Note: a and b are co-prime if there exists x and y such as a*x+b*y = 1

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

    According to property of GCD: gcd(a+mb,b)=gcd(a,b)

    Let a=1, b=i, m=1, you can get: gcd(1+i,i)=gcd(1,i)=1

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

    Each second number is divisible by 2 Each third number is divisible by 3 ...

    So the two consecutive numbers can not be the same divisor Sorry for my english

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

Снова скоростное тестирование! Спасибо.

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

    И на удивление быстрое обновление рейтинга :)

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

I don't understand test cases in problem C. With input:

2 2 yz

We need strings t with beauty 2. These are ya,yb,...,yy (25 in total) plus az,bz,...,xz (24 in total). Thus, the answer should be 49 but the expected answer is 26. ???

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

    in first example zT where T >= 'a' && T <= 'z'.

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

    notice that only za...zz has beauty 2 lexicographical larger: the first compared char must be strictly larger than the other.

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

    t is larger than s. See the change in the problem statement in bold.

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

      Well, when this change in the statement has been done? I had no idea about this change until just NOW!

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

Can anyone give me a hint about how to approach problem C in Div2 please?

I would like to attempt to upsolve it, but, I'm totally out of ideas...

Best,

Bruno

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

Ahhh, Loved it !! #Needed some out-of-box thinking, throughout. #looking Forward.

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

really fast system testing..:)

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

Really interesting problems. I expect more contests from you RomaWhite :)

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

Обидно одним из первых решить А и завалить время на В. :(

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

    Аналогично. На первой минуте сдал А и пока возился над всеми задачами по очереди, вернулся к В на 55-ой минуте и за 25 минут решил.

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

Never Do this mistake! Never do! NeveR! [A div 1, segment tree instead of FORs]

P.S: i'm so Idiot!

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

Не в моем случае жаловаться конечно, но diff WA10 на контесте и OK в дорешке вызывает прилипание руки к лицу.

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

Can someone tell me how they solved Div2, A?

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

Прочитал в B "сумма" вместо "максимум", весь контест решал не ту задачу. И даже почти решил.

Все-таки три контеста в день -- это слишком.

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

    Аналогично. Только после прочтение этого комента это заметил(

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

Ребят, после решения задачи А (DIV 2), стало интересно,

Дано число n и k

Нужно вывести любую последовательность из n чисел, что бы их сумма была равна k

Например:

n = 7; k = 10;

1 + 0 + 2 + 1 + 1 + 3 + 2 = 10

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

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

    ах да, забыл добавить, что цифру 0, можно использовать только 1 раз.

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

      Заметим, что минимальное число, которое мы можем получить из n слагаемых равно

      0 + 1 + 1 + ... + 1 = 0 + 1 * (n-1) = n-1

      тогда, если k < n-1, то решений нет, иначе построим ответ так:

      0 + 1 + 1 + ... + 1 + (k-(n-2)) = n-2 + k-n + 2 = k

      Слагаемые: [0, 1, 1, 1, ..., k-n + 2]

      Еще, наверное, надо рассмотреть отдельно случай n = 1

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

Может кто-то объяснить С(Div2)? Как её решать не за n*m?(без деревьев)

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

How to solve problem DIV2 D / DIV1 B ??

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

How to solve problem DIV2 D / DIV1 B ??

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

    Plz anyone explain the process how can i solve it with binary search and the logic behind it.

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

      Imagine we have a function f (returning true/false) that tells us whether it's possible to reach some c by changing at most k numbers (that means that after this change, the difference between every two consecutive elements is less than or equal to c). Obviously, when f is true for some c, it's also true for every c2>=c. That means, that we can use binary search to find the "cut-off", the first c for which f is true (which is what we are asked for).

      So the last remaining step is to program such function f. We can use dynamic programming — denote dp[i] as the minimal number of changes in elements 0..i so that the difference of every two consecutive elements in range 0..i is at most c AND the last element remains unchanged.

      We can calculate dp[i] as a minimum of i (that means we change every value before the currently considered element to the same value) and dp[j]+(i-j-1) for each j smaller than i with the condition that abs(a[j]-a[i]) <= c*(i-j) — that corresponds to remaining the j-th element unchanged and changing every single element in between of i, j.

      Then we can determine the minimal number of elements that we need to change as min(dp[i]+(n-i-1)) for each i (we take i-th element as the last that remains unchanged, so we need to change the rest).

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

Can you tell me how to solve div2-D problem????

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

Please, could anyone write a brief editorial of the contest, I could only solve problem A div1, I am trying to upsolve the other problems and I think many other coders too. thanks in advance.

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

With a little bit of delay — screencast