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

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

Всем привет!

Вот и опять пришло время раунда, в этот раз это Codeforces Beta Round #91! Автором задач являюсь я, Герасимов Виталий (witua). Большое спасибо Артему Рахову (RAD) за помощь в подготовке раунда и Марии Беловой за перевод условий. Надеюсь задачи всем понравятся.

Приятного раунда!

Спасибо всем за участие! А вот и победители:

Дивизион 1:

  1. tourist
  2. 2222
  3. PavelKunyavskiy
  4. Petr
  5. vepifanov
  6. dzhulgakov
  7. e-maxx
Дивизион 2:
  • Проголосовать: нравится
  • +125
  • Проголосовать: не нравится

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

Тег 77+7+7 говорит о том, что нас опять ждет встреча со счастливыми числами. Я угадал? :)

Удачи всем; и после опыта нескольких последних матчей - пожелаю, чтобы матч был рейтинговым, а так же чтобы автору не пришлось прямо во время матча исправлять какие-то проблемы или баги.



13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Подозреваю, что контест с номером 77+7+7+7 уже зарезервирован? :)
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Looking forward to it. Nice tag :) 
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
как-то неожиданно заблаговременно создана тема очередного кф... или в последнее время я что-то пропустил и всегда уже так...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не всегда. Действительно неожиданно. При чем приятно неожиданно =)
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
I suggest to name this contest after John McCarthy's 91 function.
13 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится
why your tag is 77+7+7 just write  91  to help us when we search by tag :) :)
btw,nice tag :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Maybe it's a hint for a problem in the contest. :P
    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Or just show that 91 is also a lucky number :-)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        It is not lucky number. It's only almost lucky number :)
        However, there are 4 7s in 77 + 7 + 7 which make 91 seems luckier than many other real lucky numbers. Nice one.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
по-мойму создавать тег с пробелом безсмысленно... все равно по нему не ищет.... хотя если надеется на светлое будущее...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я, например, не знал что по тегу с пробелом не ищет.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    А по тэгам без пробела тоже почти никто не ищет, я думаю. Легче использовать гугл указав в запросе site:codeforces.ru...

    Все эти тэги смахивают на некую временную меру которую прикрутили при разработке сайта, надеясь в будущем нормальный поиск добавить... Ну и подзабыли... ;-)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      мне кажется теги очень удобны, но без стандартизации никуда не годятся (например поиск по тегам trains и neerc не находит все блоги с тренировками итмо)
13 лет назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

Помню, что, помимо семерок, автор любит еще и четверки, есть еще такое представление:

7*4 + 4*7 + 4*7 + 7
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Short statements, hands-on!
13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

I hope I will increase my rating as well by positive "lucky" number.

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

bug comment

13 лет назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится
наверное, мне одному не нравится, что раунд сегодня... по мне, лучше бы он прошел так, как и было изначально задумано: в пятницу
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
I'm sorry for the off topic question, but I could not find any other place to ask. Is there any tool, that is capable of generating the problem skeletons with a stub for the implementation method and test cases? Something similar to CodeProcessor on topcoder?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    If you use IDEA for Java, plugin from Egor can help you
    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Thanks, but unfortunately I do not use IDEA (I write in cpp).
      Is there any place here, where noobs can ask stupid questions?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        Unfortunatelly, no.
        May be your blog is a such place, but if care about your "contribution" you'd better to ask Google first :)
        What IDE/OS do you use?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится
          I don't really care about the contribution in particular, because I do not know what is it good for, which is in turn due to the fact, that there's no description of any sort on this matter :)

          I am using Visual Studio on Windows. It would be fun to write such a tool, I am up to it, unless it is not implemented yet (which would surprise me actually).
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            I haven't heard anything about such plugin.
            You're welcome to implement and share it :)
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
thanks for your problems in advance :D
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Последний тег радует)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Удачи всем!
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
Website response seems slow to me. Are you feeling same? :(
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
I loved your previous contest :D Hoping to feel the same today :D
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решается С(div - 1)?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Не на своих местах будут не более 13 последних чисел. Перестановку их можно сгенерировать и честно посмотреть, а меньшие счастливые подойдут все.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    Заметим, что в перестановке с номером 109 переставляется от силы 15 последних элементов. Тогда найдем кол-во переставленных элементов, сгенерируем их k-ую перестановку и проверим в лоб условие. Так как большой префикс не менялся просто переберем все счастливые числа до n-длина_измененной_части и добавим их кол-во к ответу.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Составляется перестановка каких-то 13-ти последних чисел и смотреть по ним напрямую.
    + общее кол-во счастливых до начала переставлений.

    П.С. правда я не успел это написать
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
thanks

this problems are easy and good!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Div 2 задачи отличные, особенно D понравилась.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Непривычно легко. Особенно D, даже легче чем С
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Однако я ухитрился допустить в D глупейшую ошибку, вообще очень странно что она не всплыла в претестах.

      Как же меня подводит невнимательность :(
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        У меня в первоначальном решении в D был объявлен масссив на 1 элемент меньше чем надо, благо претест-10 проверял n=100000
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Отличный контест.

Немного резкий переход между "простыми" и "сложными" задачами, ну и многовато пользователей, которые решили все. Хотя последнее, думаю, поправят систесты:)

Зато удобные понятные короткие условия, отсутствие лагов, понятные сэмплы, ну и + за тему счастливых чисел!

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Ну и я бы сказал, что не правильно поставлены D и E. Хотя это ощущение тоже могут поправить систесты.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Как С решается в div-2 подскажите, пожалуйста?
  • 13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Вобщем как-то так.
    Сгенерируешь перестановки для 4 и 7 размером <=9
    После чего находишь наиближайшие индексы к значениям для left и right.
    Потом в цикле подсчитываешь все суммы (happy[i+1]-happ[i])*happy[i+1].
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ответ помещается в стандартный тип?..... написал почти такое же решение, протестил, вроде выходит за пределы int64 при худших данных... там нужна была длинка?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        Думаю, автора бы убили, если бы там нужна была длинка.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Даже если для всех 10^9 чисел взять минимальное возможное счастливое число из 10 знаков (оно равно 4444444444), то ответ получится 4444444444000000000, то есть примерно 5*10^18 < 9*10^18, так что умещается в long long.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Надо делать перестановки для 4 и 7 размером <=10. 
      Когда r=109 тогда next(r)=4444444444.
      На тест l=109 и r=109 нужно выводит десять четвёрки.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Cгенерируем все счастливые числа и посортим.
    Далее, пусть у нас есть i-тое и (i + 1)-число.  Заметим, что LUCKY[i + 1] будет next(x) для всех x от LUCKY[i] + 1 до LUCKY[i + 1] включительно.
    Найдем сумму всех next(x) для x от 1 до N.
    Найдем первое счастливое число не меньше, чем N, пусть у него индекс k.
    Тогда, прибавим к ответу (N - lucky[k - 1]) * lucky[k], а для всех предыдущих счастливых прибавим lucky[i] * (lucky[i] - lucky[i - 1]).
    Тогда, ответ sum(r) - sum(l - 1).
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

На А надо было ставить TLE = 0.5.
Или ограничения до 10^12.
А то люди пишут за O(10^9) и...
01:18:36  A  Неудачная попытка взлома участником atetubou
01:26:09  A  Неудачная попытка взлома участником dalex
01:28:57  A  Неудачная попытка взлома участником hogeover30
01:40:22  A  Неудачная попытка взлома участником flowlight

А в остальном очень хороший контест!
13 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Why are digits 4 and 7 considered lucky? Is it a Russian tradition?

Partly because I'm very sleepy, I don't like those `lucky number' problems, by the way.  I shouldn't have participated :-(
  • 13 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    It's witua's tradition, not Russian :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    No, such problems are often apears on TopCoder too.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    I bet, such tradition appeared after one of TC contests (403 or 404, can't remember, maybe even earlier).
    And after that many liked that idea and so on...

    This time there wasn't any special properties of such combination, so them could be almost any different pair as well. But why one should break such a good tradition? :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      I didn't know that.  It seems I need more SRM practice ...

      The idea of four being a lucky number sounds a bit odd to me, because where I live the number four (in fact even numbers in general) is considered to be very unlucky.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    This is tradition from Lviv, Ukraine.

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

So many lucky number contests, almost bored of lucky numbers.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мне интересно, сколько людей на С(div2)/A(div1) делали прекалк?=)
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Nice problemsets again, thanks witua!

BTW, what's the corner case of DIV2 A? So many people got hacked.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I used 222. It is divisible by 74.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    Many people think that lucky number just 4 and 7. in fact there's a lot lucky number under 1000 = 44, 47, 74, 77 ect. . . And I got hack because of that T_T
    • 13 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится
      Even don't think about this. After I found A was a source of fierce hacking, I thought probably no wrong solution would be lucky enough to survive, so I did't attempt to hack.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Интересно, пройдет ли по E O(M*sqrt(N)*30).

upd:

806940 27.10.2011 20:46:48 1010011010 E - Счастливый массив Delphi Полное решение 2450 мс 23908 КБ

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

    о_О оптимистично... Я хоть и знаю, что сервак быстрый, но M*sqrt(N)*С отбросил сразу...

    А действительно, может пройти?

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это вообще много. У меня N*log(N)*30+Mlog(N), и я, если честно, не уверен.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Расскажи решение E, пожалуйста.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Не знаю как с TL, но вроде N*log(N)*30. 
        1) Сгенили все хорошие до 10000
        2) Будет дерево отрезков на массиве величин Xi - ai, где Xi - минимальное хорошее не меньшее ai
        3) Считаем в нем две величины - максимум и количество максимумов.
        4) Когда поступил запрос add добавили и все - все равно мы пока ничего не смотрим.
        5) Когда надо посмотреть, понятно как обработать запрос. Но надо еще исправить то что мы нагадили при add-ах. Ну исправляем, пока максимум в дереве положительный увеличиваем значение Xi, вычитая что-то из соотв. числа. Всего таких событий не очень много.

        • 13 лет назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится
          У меня по E решение за 109 прошло. Т.е. добавление делаем просто проходом по массиву, ответы на запросы - деревом Фенвика. Интересно, предполагалось такое решение? :)
          • 13 лет назад, # ^ |
              Проголосовать: нравится -12 Проголосовать: не нравится
            меня одного это бесит? пока кто то думает, извращается, придумывает решения которые будут <109, кто то берет и просто сдает за 109... не в упрек natalia будет сказано
          • 13 лет назад, # ^ |
              Проголосовать: нравится -13 Проголосовать: не нравится
            Да и работает оно быстро.... не то что 30*sqrt(N)*M
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Прочитал комментарий ниже - вопрос отменяется.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У меня отработало на тестах жюри за 1910 ms почти в лоб решение.
        После исправления бага — хранения ответа в short :Z. Ну это надо было умудриться.

        Заметим, что суммарно добавлений не более 109. Поэтому втупую реализованная операция add работает довольно быстро (а после loop unrolling-а руками — ещё чуть быстрее).

        Напротив, count может в сумме пройти по 1010 элементам. Чтобы с этим бороться, кэшируем последние 128 запросов на count. При запросе add инвалидируем все закэшированные запросы, с которыми этот add имеет общие точки. При очередном запросе среди всех валидных закэшированных запросов выбираем тот, от которого быстрее всего считать до нового (оценка — сумма модулей разностей левых и правых границ отрезка). Если нашли, считаем от него. Если не нашли, считаем просто в лоб.

        Решение вот. Свалить его, вероятно, можно тестом, который поочерёдно делает add точкам вблизи середины и count на почти всём отрезке.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Мне тоже, на моем компе решение с такой асимптотикой в худшем случае работало ~3.3 секунды. Надеюсь, зайдет.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня O((T + N)log2NC) локально работает 2.7. Вряд ли пройдет, но уже очень мало времени до конца оставалось
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ох и жесть я написал в D, только не успел отправить. Дерево Фенвика с Бигинтами даже есть :) Посмотрю, пройдет ли после систеста.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А два указателя, с утверждением, что уже не круто?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если честно, я не понял смысл этой надписи. :)
      Я решал следующим образом.
      Сгенерил все счастливые числа, отсортил. Далее перебираю самое левое счастливое число и бинпоиском ищу правое. А затем в этот получившийся отрезок подгоняю входные отрезки. За O(1) не придумал как подгонять. Придумал за logN с суммой левых границ, но 10^18*10^5 в худшем случае в long не помещается, поэтому пришлось использовать Бигинты.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Смоделируем руками бесконечность. Если произведение или слишком большое, то оно равно бесконечности. На этом обламывается фенвик, потому что надо вычитать, а вычитать бесконечности можно только если очень хочется и не всегда правильно. Поэтому пойдем двумя указателями и надо только прибавлять, а прибавлять бесконечность это просто,
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня решение 2мя указателями, но при проходе надо было считать величину вида X*C-Sum (right_endpoints) чтобы посчитать, сколько необходимо действий, чтобы покрыть данную точку. И тут величины до 10^23 и с парой длинных пришлось все равно морочиться. Вам удалось как-то это обойти?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да. Можно просто прибавлять изменение. Если оно большое, то оно бесконечность. Но конечных больших чисел в середине не возникает.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А еще можно считать примерно в даблах + точно в лонгах по модулю 264
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Заменил бинпоиск на второй указатель, зашло и с Фенвиком и с Бигинтами :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Good problem set. 
13 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Ну почему никто не поломал мой шедевр в C?
if (n <= 3) {
        out.println(0);
        return;
}

Исправил и получил Accepted :(

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А мог бы...
    И у себя проглядел - упало на тесте "1 2"
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Я получил на претестах WA 6, исправил про -1 в основной проге, а в этом if-е забыл. Не всегда их полезно писать...
      Кстати, даже фиолетовым не стал. Все-таки сложно вылететь из Div-1, надо штук 5 подряд контестов сливать.

      Ну вот, наконец, и в B дурацкий баг нашел. Как так можно писать...

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

задача B.НЕНАВИСТЬ

P.S. а в целом задачи отличные

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задачи очень понравились, спасибо автору.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ждём разбор D и E. В коментах непонятно.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Стыдно быть красным, но оставаться жёлтым по уровню. Типа, с суконным рылом да в калашный ряд)
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Товарищи, я что-то не пойму, что с задачей E. Написал решение, которое при add влоб обновляет массив (если число стало "хорошим" или перестало быть им, делает апдейт фенвика). На макс. тесте такое должно работать что-то типа O(10^5 * 10^4 + 30 * 10^5 * log(10^5)). Локально на макс. тесте давало 8 секунд. После систеста пишет, что решение зашло за ~900. Как так? o_o

P.S. послал просто так, "на шару".
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    мне вот интересно, почему каждый раз после раунда выясняется, что тесты хероватые?... или это стало традицией кф?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну я "куски" тестов глянул. Макс. тесты вроде бы есть. В любой случае тест, на котором у меня локально падало по TL, на поверхности. Это не какой-то хитрый случай. Странно, если его в наборе нету. Может тестирующий сервер ооооочень быстрый? =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Похоже, что в этот раз не тесты хероватые, а сервера слишком хорошие :)

      P.S. Будущее наступило - решения с асимптотикой 10^9 работают меньше секунды :)
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
This is the first time I'm in the DIV1.But I am so nervous that I made many silly mistakes.To sum up, I learn a lot.Thanks the author!
13 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

а я так надеялся, что Гена отловит все мои тупые баги...

P.S. видимо, в этот раз ему было лень ломать )

13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Ааааа, до чего же глупый баг допустил в C. Забыл отсортить полученные счастливые числа...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я круче, в В сначала ищу последнее вхождение тройки, которая зацикливает, а после этого использую его, как первое.

    -25, снова в оранжевые, вместо плюсика...

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    а я в А их сортил, но забыл, что сортил, и пересдал
    ну не смейтесь!! :D
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да блин, у вас по одному багу, это не страшно. Вот у меня их целых два, и я сижу с одной задачей и неудачным взломом, потому что 10^9 заходит в A
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      дак у меня, кроме плохого времени по А, С не зашла, потому что я тупой психопад!
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Can someone give me the logic to solve problem D.looked into the accepted solutions but unable to get the logic behind the code.Thanks in advance:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You basically loop through the array once and perform the described actions until you either reach the end of the array or run out of moves.

    The case to look for though is when you reach a part of the array that looks as follows: a[i-1] = '4', a[i] = '4', a[i+1] = '7', and i is even. In this case this part of the array will switch between 447 and 477 for eternity :) So if you have an odd number of moves left it will end at 477, otherwise 447, and this uses up all your remaining moves.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Search for 4-7's from starting. Now There are 2 crucial observations:

    1. When you find the a 4-7 in a odd position
            >>If there is only one 7 in front of it than just replace the 7 with 4 and continue searching.
           >> If there are more than one 7 like(124777) you'll stuck in a loop(124777-->124477-->124777)

    2. When you find the a 4-7 in a even position
             >>If there is a 4 behind the 47(like 6447) you'll stuck in a loop.(6447-->6477->6447)
             >>other wise you can just replace and continue searching.

    in case of  "replace and continue" i increment "step" by 1. When i stuck in a loop i just check how many steps left and determine the final string from it. The complexity is just o(n).
    Hope this helps.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I assume you mean div 2 problem D. The idea is, that once you encounter the string "447", where the second 4 is at an even position it will keep looping with 447 -> 477 -> 447.

    If a such string is not present the amount of operations that can be done is O(n).

    You thus run through the string and when encountering a 47 you check if it's in odd or even spot. If it's in an even spot you check for the terminal condition (above). If this isn't a terminal 47 we can just do the operation and either move one step forward or one step backwards depending on odd/even.

13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Очень обидно что решение по Е на FPC получило ТЛЕ, а на делфи зашло :(
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А бывало и наоборот. На Делфи - TL, на FPC - Accepted. Раз на раз не приходится.

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Nice contest,div 1B/div 2D was really an interesting  problem. Hope editorial will be available soon.  I now have experience of getting +0 point both in tc and cf.

Can anyone share idea of div1 C?

  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    You must know how much last elements, lets say x, you have to swap. It will be at most 13, because 13! > 10^9. If x > n you print -1. Otherwise you get k-th permutation and you set last x elements according to this permutation. Then you check for each element if this element and it's position are both lucky numbers.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    It's well known, that number of permutations of first N numbers is equal to N!. Therefore, we can say when we shall print "-1"  - if N! < K. Of course, we shall check this only for N <= 12 as 13! >= 1000000000.
    Let's assume SIZE as the biggest integer for which equality SIZE! >= K holds. Now we can definitely say that changes are made only to last SIZE numbers- they are N - SIZE + 1.... N. 
    Now we simply generate K-th permutation for SIZE numbers ( we can do this using O(SIZE) memory and O(SIZE * SIZE) time). 
    Let's generate all lucky numbers up to 1000000000. Each number less or equal to N - SIZE stays on position that is equal to this number. As we have no more than 511 numbers, we simply iterate over them and count them. The last thing to do  is to work with our generated permutation. If position (N - SIZE + i) is lucky and (N - SIZE + perm[i]) is lucky we increase the answer.
    Here you can see my code. Please, feel free to ask questions if any.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain how do you generate the k-th permutation of SIZE numbers using  O(SIZE) memory and O(SIZE * SIZE) time? 

      Thanks.


      EDIT: I found it.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    Notice that 10^9-th permutation can shift no more than 13 last numbers.

    First, count number of happy numbers that could not be shifted - they all stay on their places, happy places.

    After that, generate K-th permutation, apply this permutation to last numbers and find indices of happy numbers among last numbers.

    upd: so many replies)

13 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
This is one of the best problem-sets I've ever seen in Codeforces. Thanks!
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Задачи хороши, не знал что можно придумать столько задач на тему счастливых чисел)), но хочется пожелать автору в следующий раз уделять больше внимания оценки TL и генерации тестов против переборных решений.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Nice problemset!

But what's the point of having hacks if there are trick/corner cases on pretests?

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

    Not only on pretests but also on the examples. However it depends on the author which corner cases he decides to reveal. Sometimes the difficulty of the problem can vary a lot depending on the pretests and the examples.

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

UNFORTUNATELY , i had a stupid mistake and got wrong answer on 30th test . I have never written any contest with no silly mistakes  thats why i am in 2nd division again :(((

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Задачи отличные, да.
Правда, оранжевый цвет мне нравился больше :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    i don't know how to change the colour :)
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

      Это очень просто
      1) Регистрируемся на любой контест
      2) На первой минуте сабмитим int main(){} на любую задачу
      3) Достаем пиво и два часа наслаждаемся монитором на контесте
      4) ?????? system tests
      5) PROFIT

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        При желании можно пункты 2 и 3 заменить на сдаем халяву и пытаемся всех сломать на семпле. 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Надо всего лишь взять велосипед. Ну вы поняли.
13 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Impossibly weak tests for DIV 1 E!

I saw at least two accepted solutions that don't pass basic max test like one generated by code below.

#include <cstdio>

int main() {
  int n = 100000;
  int m = 9999;
  printf("%d %d\n", n, 2*m);
  for(int i=0; i<n; ++i) printf("1 "); printf("\n");
  for(int i=0; i<m; ++i) {
    printf("add %d %d %d\n", 1+i, n-i, 1);
    printf("count %d %d\n", 1, n);
  }
  return 0;
}
13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

The complexity of block-array solution seems to be O(m*sqrt(n)*log(sqrt(n)*2^10)? I don't know whether it can solve this problem without enumerate every lucky number

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

Отличные задачи :)

С интересом решал.

Можно глупый вопрос? Как вы генерировали последовательности счастливых чисел? Мне ничего умного в голову не пришло :(

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Можно генерировать рекурсивно, например, так:

    vector<int> lucky;

    void gen(int num, int l) {
    if (l > 0)
    lucky.push_back(num);
    if (l < 9) {
    gen(num * 10 + 4, l + 1);
    gen(num * 10 + 7, l + 1);
    }
    }
     
     
    Запустить надо от параметров (0, 0), результатом будут все счастливые числа длиной не более 9 цифр.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится
    ArrayList<Long> list = new ArrayList<Long>();

    void gen() {
        for (int len = 1; len <= 10; len++) {
            for (int mask = 0; mask < (1 << len); mask++) {
                long res = 0;
                for (int i = 0; i < len; i++) {
                    if (((1 << i) & mask) != 0) {
                        res = 10 * res + 4;
                    } else {
                        res = 10 * res + 7;
                    }
                }
                list.add(res);
            }
        }
        Collections.sort(list);
    }

    Подсветка синтаксиса тупит и вставляет лишние переводы строк
13 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
Even the numbers of winners in both divisions are lucky numbers (7 and 4). It was odd to me that the number of winners in div 1 is different from div 2. Now I know why. lol
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is 799 almost lucky? (122A)