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

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

Всем привет!

Скоро (9 августа, 19:30 MSK) состоится очередной Codeforces Round #195 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Автором раунда являюсь я. Выражаю благодарность Геральду Агапову (Gerald) за помощь в подготовке задач, Евгению Соболеву (Seyaua), Виталию Аксёнову (Aksenov239) и Сергею Сухову (Serega) за тестирование задач, Александру Игнатьеву (aiMR) за тестирование задач и перевод разбора на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой (Delinur) за перевод задач на английский язык.

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

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

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

  1. Triolossus_3
  2. WHITE2302
  3. PM2.5

Отдельно хочется поздравить Егора Куликова (Egor) — единственного человека, который сдал все задачи!

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

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

Надеюсь задачи будут не как в прошлый раз, что никакой красный не смог решить все, это же Div2 контест.

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

    Не дождешься... :) В этот раз красные, наверное, решат, но Div2 — вряд ли

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

      Про множественное число в слове "красные" не угадал.

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

        Да жесть вообще. А Egor поздравляем с победой :)

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

    Сегодня только один красный все решил.

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

      Растем. Еще несколько сотен раундов от этого автора и тогда простые смертные смогут решить 4-5 задач.

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

Здравствуйте! Хочу спросить совета: я в олимпиадном программировании новичок, задачки получается решать плохо, алгоритмы знаю только сортировок. Ну немного ещё понял идею динамических и жадных алгоритмов. Ну так вот, в чём вопрос... стоит ли участвовать в подобных раундах, или сначала нужно выучить все базовые алгоритмы (ну или хотя бы дочитать Лезерсона? :))

P.S. Если вопрос глупый, прошу тухлыми помидорами не кидать.

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

    Я советую порешать задачки из архива из прошлых Div-2 раундов (преимущественно A,B) и на основе этого принять решение.

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

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

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

    Конечно, стоит! Это же весело! Я, когда написал свой первый контест, из сортировок знал только выбором)

    P.S. Что за Лезерсон? Яндекс находит только повара(

    P.P.S. Может имелся ввиду Лейзерсон?

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

      Угум, именно он)

      P.S. Спасибо за совет, буду участвовать.

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

    Удивительно книгу "Алгоритмы. Построение и анализ" называть Лейзерсоном, а не Корменом :)

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

how and when can I be sure that I am registered for the contest ??

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

    about 18 hours before the round , you can find the registration link , in contest page.

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

    Hi . first login then Go to the hereand see your name and all registerant or goto the here see your name and friend name if your name is be there your register . Excuse me for my bad writing .

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

The Div.1 participants will be rated???

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

i think this contest should be "Eid Special" :)

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

I hope a non-russian-speaking person had the chance to proofread the problem statements

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

Ans scoring system ???

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

Scoring system will be announced later

Later means after the contest ?

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

edited

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

The website is too busy... terrible T T

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

boring problem set, specially problem B :-| Really miss interesting problems on CF

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

For some reason when we have only div2 rounds they are much harder than when we have both div1 and div2 rounds.

I wonder why this is the case.

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

Почему задача"Б" такая тяжелая ? Объясните , как ее решать (после окончания раунда ).

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

    Особенно интересно, что за 3 претест :(

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

    Ну поймём для начала, что мухи будут бегать из каждой нижней в каждую верхнюю.

    Далее решим за О(1) для каждой нижней. ЧТобы сходить прямо вверх нужно 2*r, чтобы в соседнюю — (2 + sqrt(2))*r, дальше (2 * k + 2sqrt(2))*r. Используем формулу суммы арифм.прогрессии.

    Код

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

any further explanation for problem C ?? .. i think it's not clear atleast for me :D

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

dirty problemset :| [kaCf]

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

Is anyone else having problems with problem b? It says my answer for the second pretest is wrong, but it gives the answer for the second example (I guess that's also the second pretest?) as 5.4142135624 and mine is 5.41421356237, which is less than the 10^-6 error they allow, but is still graded wrong

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

I enjoyed this problemset, though most people probably don't like tricky cases.

Edit : Express your opinion and get downvoted. Communism for the win.

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

Problems was bad! But Thanks for fast system testing!

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

    Your avarar shows typical Div2 participant's face after this round ended I guess :) Cool problems, but a bit harder, than Div2 used to be

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

Что означает wrong output format Unexpected end of file — int32 expected?

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

How fast the system testing!!

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

What's the solution for problem C? Thanks.

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

    for every bit position (0 to 32), consider numbers in the array that have this bit set (= 1). Take bitwise and of all these numbers for each position i in [0,32), this takes O(32*n) time. Note that AND has "the more, the better" scenario, ie, for a particular v let set S be solution; if (v+1)th bit is set for a number N, then N \union S will also be a set with solution v. Using this, calculate above array. Now find maximum i 0<=i<32 such that the "bitwise and" calculated above has all bits 0 to i-1 unset (=0). This is the solution

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

    Make 30 buckets (vectors) and if a number from array has i-th bit turned on (0 <= i < 30) put the number in i-th bucket.

    After that for each bucket calculate the bit-wise and of all the numbers in that bucket and if that sum is divisible by 2^i output all the numbers in that bucket and the size of the bucket, of course choose i to be as high as possible.

    Edit: got ninja'd by the user above me :D

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

    same as c0d3junki3, but i use a builtin function named __builtin_ctz . It returns the number of trailing 0-bits in x, starting at the least significant bit position.(I think it's faster than %)

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

Wow system test is so fast now...I like it. Problems are great, a little bit too much math though. Have enjoyed it. Thanks to authors!

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

Кто-нибудь знает почему попытка может быть проигнорирована, если я решение повторно не посылал?

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

why this submission skipped???it's correct![submission:4249620] please help!

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

I think there is something wrong in the description of the problem C. I wonder how to understand this sentence in problem C: "If such number v doesn't exist (that is, for any non-negative integer v, number b1 and b2 and ... and bk is divisible by 2v without a remainder), " if v doesn't exit,number b1 and b2...and bk is divisible by 2^v should with a remainder,am I right?

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

    meaning if bitwise and is zero, then v can be as large as you want. In this case, answer is -1

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

    if b1&b2&...&bk == 0 it divides to all 2^v, and we don't have maximum v

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

    Really, all this sentence is saying is that the number (b1 and b2 and ... and bk) should not be 0. If it was 0, it would be divisibly by 2v for any non-negative integer v.

    It was hard to understand though. I wish they just said "(b1 and b2 and ... and bk) should not be 0".

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

Может кто-то объяснить почему для теста 3 1 ответ 3,25?

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

    Та же самая просьба !

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

    Присоединяюсь. Я уверен, где-то очень туплю но у меня выходит 3,387.

    Пересчитывал руками, вроде бы так-же. Для крайних выходит (2 + (2+sqrt(2)) + (2+sqrt(2)+2)) (учитываем дважды) Для центральной (2+(2+sqrt(2))+(2+sqrt(2))) И того 22+6*sqrt(2) Делим на 9 получаем 3,387

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

    Вот здесь зеленый путь короче.

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

why not make a scoring board for Div.2 only without the out of competition participants ? To know your real ranking during the contest

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

Is there a problem with the contest list? round 196(div 1) is 4 days later than round 196(div 2)!

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

For problem A, if you see sample test 1, input: 10 5 output : 0 15 15 0 But how about 0 9 23 0 ? The conditions are still held, moreover its area is smaller. What would you say?

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

    Oh, it's my bad. I thought "isosceles" is right angle because it was written as "isosceles(<ABC is right)". Should have looked up.

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

    The triangle must be isosceles which means that the two sides are equal in length.

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

why this submission skipped???it's correct![submission:4249620] please help!during the contest this submission had accept!why now is skipped??:(

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

неужели координаторы задач не видят, что этот раунд сложнее обычного див2? неужели так сложно было в этом случае сделать динамическую разбаловку, раз уж задачи такие получились?

неужели в задаче Д было сложно сделать в примерах тест, когда n != m???

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

    500 3000 3000 3000 3000

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

    Мне раунд тоже не очень понравился. По-моему, у этого автора вечно что-то нужно посчитать, типа ДП или комбы какой-то. Я с конца в этот раз начал читать задачи. После того как видел "выведите количество вариантов по модулю 1000000007" у двух последних задач, дальше и не читал даже. Кому-то такие задачи нравятся, а кому-то наоборот нет. Мне кажется, что нужно придерживаться определенного баланса в этом смысле.

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

Whats wrong with this solution? C WA6

http://codeforces.me/contest/336/submission/4257324

actually my beauty is 29 :|

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

    I've got the same question. My solution write beauty 29 too.

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

    The beauty of your answer is 21 not 29, the remainder with 2^29 is not 0.

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

    Note that if you claim the beauty to be 29, then the AND of all numbers you pick must be divisible by 229. In your case, the AND of all numbers you pick is actually 229 + 221, which means it's not evenly divisible by 229. (The actual beauty in this case is 21; 229 + 221 is divisible by 221 (giving a quotient of 28 + 20 = 257).)

    I suppose you misunderstand the problem.

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

    Did you find out what's wrong with that ur approach? Now even i'm curious..

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

If I registered and didn't attempt any problem, will my rating be calculated.??

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

ABCE's name is "Vasily the Bear .."
and D's name is "Bear Vasily"

What's the point?

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

    The problem title might be limited at either 35 or 36 characters; "Vasily the Bear" for D causes the problem title to go to 37 characters. (The next longest is E at 35 characters.)

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

      I'm not sure about what you say! For example problem 319C's name is "Kalila and Dimna in the Logging Industry" which has a length of 40!

      "Bear Vasily and Beautiful Strings" can change to "Vasily the Bear and Beautiful Strings" which has a length of 37. (37 < 40) ! Maybe it has another reason!

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

Can anyone tell me, why was this round JUST AND JUST geometry?!

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

Quick question...

On 336b, the one with the circles and the ant, I am getting a different answer when I run my code than what the tester is getting. I'm using python 2.7, and when I enter 2 2 for the second test, I get 5.41421356237 in my python interpreter, but the tester is getting 7.41421356237 when it runs my code. Does anyone know why this is happening? I did not import any external libraries and all my code is pretty standard...

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

    Even when computing manually (by hand, not by an interpreter), I got 7.414 as your output. Are you sure you didn't misread 5 as 7?

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

почему раунд 196 для див1 и для див2 будет проходить в разные дни? автор подготовил 10 задач?(уже исправили)

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

Why the rating not change?

sorry for my bad English

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

deleted. was about repeated topic

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

when will rating change?

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

codeforces is not bad

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

I think gridnevvvit doesn't want to write the editorial of this contest!

P.S: Ratings changed!!!

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

Можно поинтересоваться почему во второй задаче ответ: 5,41421356237309 считается неверным, при том что верный:5.4142135624

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

    Дело в другом, 5,41421356237309 -> 5.41421356237309

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

      Не понял, честно сказать.. 1..6 знаки правильные

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

        wrong output format Expected double, but "5,41421356237309" found

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

          В условии об этом не сказано. Сказано только о погрешности..

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

            Дело не в погрешности, а в том, что у Вас число неправильно написано, после целой части должна идти точка, а затем дробная часть. А у Вас стоит запятая вместо точки.

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

Может я туплю : но мне одному кажется что это один и тот же код просто на разных языках ?) 4254254 4255478

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

Problem D is quite nice.

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

Classic Contest

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

Почему не Медведь Дима?

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

how to prove problem A in simple out 1 I think (0,10),(20,0) is more small than (0,15),(15,0)

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

My first time facing a floating point problem on codeforces. The custom test case was outputting -0.0000 for all my answers on g++ 4.7 using printf. What is the reason for this ?

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

solve problem a in a few minutes, and try to understand other problems for about 2h...

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

Sorry but I really can't hold it anymore. With all respect the way the problems are written is not clear at all. Well not all of them but some.

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

Дорогие организаторы! Это div-2 контест! Пожалуйста, не забудьте это!

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

    До контеста еще -3 дня, не надо паниковать, не забудут