Блог пользователя ruzana.miniakhmetova

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

Всем привет!

Друзья, напоминаем, что сегодня в 18 часов состоится второй дивизион ABBYY Cup 2.0!

Всех участников ждет подарок: помимо задачек от Умного Бобра будет специальная задача от проекта Codeforces!

Длительность контеста не изменилась, за четыре часа участникам предстоит решить 7 задач. Тесты разбиты на две группы стоимостью в 30 и 70 баллов соответственно. Засчитывается только полное прохождение группы тестов. При равенстве баллов штрафное время учитывается по правилам ACM. Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время.

Ну и как писал MikeMirzayanov:

Простой контест будет рейтинговым для участников из Див 2 (независимо от того студенты они или нет). То есть рейтинг будет пересчитан для всех официальных участников простого контеста + участников из Див 2, кто вне конкурса.

Не забудьте, что легкий дивизион ABBYY Cup 2.0 предназначен, главным образом, для ребят из Див 2 Codeforces и тех, кто имеет небольшой опыт спортивного программирования. Ребята из первого дивизиона Codeforces могут участвовать во втором дивизионе вне конкурса.

Желаем всем весеннего настроения и бодрого духа! Отдельно хочется пожелать удачи всем, кто будет участвовать в контесте в первый раз в жизни! А таких, судя по зарегистрированным, будет немало. С дебютом, друзья :)

Всем удачи!

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

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • Попытки сдачи бывают по задаче или по группе тестов?
  • Что за неверные попытки? Что за ресабмиты?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

7 задач по 30 баллов = казалось бы 3 задачи по 70, но получается у первого штрафа сильно больше только засчет того, что его много раз посчитают. При этом 5x30+70 >> 3x70

В целом для этого контеста не очень актуально, а вот во втором будет какое-то мясо, учитывая, что (20+30)*2 = (20+30+50)

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

    Ну это мне кажется нормально. Круче тот, кто решил 3 сложные задачи, а не 7 легких.

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

А по какому признаку некоторые из див2 участников зарегистрированы вне конкурса?

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

    Видимо они не регистрировались на ABBYY Cup.

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

      Я зарегистрировался но меня всё равно записало вне конкурса. почему?

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

        Официально мероприятие студенческое, а вы — школьник.

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

    Участник должен быть зарегистрирован на сайте ABBYY Cup 2.0 как студент и быть из второго дивизиона.

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

      Похоже, сейчас это действует как "и быть из второго дивизиона на момент регистрации на сайте ABBYY Cup" нет, достоверно это сказать не могу

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

      В посте указана ваша цитата: "Простой контест будет рейтинговым для участников из Див 2 (**независимо от того студенты они или нет**)."

      Я не студент, регистрация предлагается только вне конкурса. Как быть?

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

        Там же написано, что контест будет рейтинговым для всех участников из Див. 2.

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

Just a bit of translation ,although its obvious->"ABBYY CUP 2.0 -Second Division! "

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

ну блин хоккей же в это время(( хнык

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

I registered for the ABBYY Cup 2.0 but forgot to register the contest until now......

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

Почему я вне конкурса? Я зарегистрировался на ABBYY Cup как студент, и мне пришло письмо-подтверждение.

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

    В базе регистрации стоит отметка, что вы выбрали "выпускник". В любом случае, изменю тип регистрации вручную.

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

I've registered for the ABBYY Cup 2.0, but forgot to register for the contest until 4 minutes before it starts......

What a tragedy......

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

Как же так??? Я регался на чемпионат на сайте ABBYY, а сейчас мне пишут, что я не зарегистрирован на соревнование и регистрация закрыта! А я вечер уже запланировал под это. Обидно.

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

    Некрасиво ругаетесь. Ну вы же не первый раз участвуете, знаете что на контест всегда отдельная регистрация. Она была открыта сегодня весь день (на самом деле с 2х ночи). Время ее окончания было опубликовано все это время. В любом случае, так как правила контеста позволяют — продлили и оставили открытой вплоть до конца соревнования.

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

      Приношу свои извинения, как всегда, погорячился. Но почему сразу не открывать регистрацию до конца соревнования — люди могут не рассчитать, немного опоздать и т.д.? Тем более, что технически это, видимо, несложно. В данном же случае некоторые участники просто не подумали, что на соревнование, фактически, нужно регистрироваться 2 раза. Это выбивается из здравой логики.

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

        Обычно это делается, чтобы сразу распределить по комнатам.

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

присоединяюсь к тем кто зарегистрировался, но не зарегистрирован:)

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

Не сразу допер, что надо за 30 баллов и за 70 отдельно отправлять решение. Обидно, потерял время :(

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

    Когда пишешь комменты во время соревнования, теряешь еще больше времени:)

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

will solution be re-evaluated after the contest?

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

will solution be re-evaluated after the contest?

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

Переключатель дивизионов в результатах не работает.

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

there was no pretest. so how is that it's pending for system test?!

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

Каким образом в задаче про перелёты значение X могло быть выбрано произвольным образом?

Разве это не значит, что на каждой планете мы могли пробыть как минимум бесконечное количество дней отдавая сколько угодно сувениров в день, что вроде как не во всех случаях даст общее нужное время путешествия?

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

    PS : не так понял вопрос.

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

    во второй группе a[i] = 0 => если с = 1 то х — любое

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

    Тест
    2 2
    0 1
    0 1
    Любое х подходит.

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

    f(x) возрастает не монотонно, но возрастает, поэтому пересекать константу С сможет только в одном отрезке, ну или в точке.

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

    Возьмём тест

    1 1
    0 1
    

    , тогда, чему бы ни равнялся x, мы пробудем на первой планете ровно один день.

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

Кто ждет системного тестирования, отзовитесь!

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

Какое еще "Ожидается системное тестирование", включите дорешку уже ^_^

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

"Сценаристы не хотят выбирать набор максимальной ценности — это сделало бы сюжет слишком предсказуемым"

Очень плохие сценаристы =| Загубили контест XD

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

Слабые тесты это хорошо, но когда на них заходят решения абсолютно не верные и ловят WA на сильных, а не TL немного расстраивает, а так контест шикарен!

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

Very enjoyable contest for me :)

Just one question: Was my idea for Space Voyage correct? What I did was perform a binary search for the lower and upper bounds of X (of course, only if it was confirmed that there weren't infinite solutions). My rightmost bound for the BS was c * MAX(b[i]), and I got WA on test ~ 23 or so.

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

    Yes, that's a correct solution. It's very easy to overflow though (the problem statement even hints at this).

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

Кто что в D2 писал?

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

    Для каждого a[i] посчитаем отрезок b с какого по какой элемент по нему пройдет. Потом просто a[i]=(a[i]+s[r]-s[l-1])%c. Где s — массив сумм на префиксах

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

      Я догадался, но написать не успел :(

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

      Упал под стол — не додумался до префиксов написал дерево отрезков :)

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

        Ололо, знать надо — элементы не изменяются, значит префиксы, изменяются — значит дерево. Причем желательно фенвика)

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

          Да я то новичек(относительно) :)

          Вообще я начал писать кумулятивные суммы, но почему-то решил, что это неверно :D

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

          не туда коммент

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

      даже так (i<=n-m+1)?(l=1):(l=i-(n-m+1);

      r=min(m,i);

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

Как решалась G на 100 баллов? Очевидно, что можно построить Ахо-Корасика с 10^5 состояний, но как сделать по нему столько итераций? Нужно искать цикл?

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

"Ожидается системное тестирование" эмммм... А зачем, если задачи полностью сходу проверялись? Может, это баг КФ?)

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

Не знаю, обсуждалось ли это где-нибудь ранее, но идею разбития тестов на группы можно было бы использовать в некоторых обычных раундах Codeforces. Например, если решение проходит претесты и никем не взломано, то даже в случае ошибки на основных тестах можно было бы давать немного рейтинга. Простите, неправильно высказался. Я имел в виду начисление баллов именно при time limit или memory limit, а не wrong answer или наподобие.

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

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

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

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

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

Подскажите, пожалуйста, как C и D по нормальному решались

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

    C — Находим все компоненты связности и удаляем те в которых есть враждующие вершины. Выводим размер самой большой оставшейся ( ну или 0 если их нет ).

    D — Найдем какие элементы добавятся к A[i], а именно B[l,r] где l = max(0,i-(n-m)),а r = min(m-1,i) Ну и выведем (A[i]+B[l,r])%c

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

      В смвсле удаляем? Вот, навпример тест: 3 2 1 2 2 3 1 1 3 Компонента связности одна, удалив ее удалим все. Но ведь можно пригласить двух людей так, чтобы они не враждовали. Или я задачу не так понял?

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

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

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

          Блиин, тогда все понятно :-D

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

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

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

        Я вот тоже затупил с ней — там если зовут кого-то, то обязаны придти все его друзья, иначе он не пойдет.

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

Strange! my rank is 65th and if unofficials are included rank is 226. But in rating chart its showing 163!!! Whats the reason??

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

    The second division (easy) contest will be a rated event for Div. 2 Codeforces users, so it will be rated for official participants and those unofficials who is from the Codeforces Div. 2.
    Again :
    It will be rated for official participants and those unofficials who is from the Codeforces Div. 2.
    One more:
    And those unofficials who is from the Codeforces Div. 2.

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

    cose in table showed div2 and div1 + unofficial members

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

    The standings include results from both divisions where as the contest results only consider Div-2 contestants.

    To see the results for a single division (and therefore the results for the Div-2 contest) you can select Div-2 from the top-right pulldown menu.

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

    Unofficials include Div1 contestants, but rating change only in Div2.

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

В дорешке нет ни одного теста по задачам ><

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

    Это из-за необычных тестсетов. Пока эти задачи убраны из дорешивания.

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

All tasks were enjoyable, one of the best competitions recently. :)

The solution for task G must be ingenious because of the constraints. Any ideas?

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

what's happening?! all solutions are accepted without any check! i've sent my A question answer for C by mistake and my solution was Accepted !!!!! :D:D

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

    These problems are not supported in practice correctly for now. I've temporary removed them from the problem archive. Sorry.

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

To Mike: My rank in Abbyy Easy is 80 and I solved 4 questions correctly. But my rating change -10 and my rank is 199 in the contests page of my user. If I tick the show unofficial my rank is 269, too. WHY?????

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

    As mentioned in earlier comments: select "Div-2" in the top-right pulldown menu. Overall results include Div-1 as well. As for your rating change: consult the FAQ.

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

сокращу, чтобы пост много места не занимал.

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

    Официальное оно только для тех, кто зарегистрировался на сайте ABBYY как студент. Рейтинговое для всех из div 2.

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

    спасибо, понял.

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

Что надо было писать в Е на полные баллы?

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

    Два бинпоиска.

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

      Значения подходящих X идут подряд? И бинпоисками ищем минимальное и максимальное подходящее?

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

      Можно заметить, что достаточно одного поиска. Хватает найти одно подходящее значение x: из него для каждой планеты можно узнать количество дней (для всех подходящих x они будут неизменными). Тогда для планеты i интервал подходящих x-ов [minX; maxX], можно вычислить вот так:

      ci = (x*a[i])/b[i];
      minT = b[i] * ci;
      maxT = minT + b[i]-1;
      minX = (minT+a[i]-1)/a[i];
      maxX = maxT/a[i];
      
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Any tutorials coming?

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

Why I can't practice this contest?

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

Why I can't practice this contest?

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

Как и где мне дорешать эти задачки?

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

А дорешивание включите? UPD. Не видел что уже спрашивали.

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

Как решать задачу G2 c этого контеста?(http://codeforces.net/contest/177/problem/G2)

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

    Данная строка формируется таким образом, что префикс у неё остаётся неизменным, а суффиксы чередуются в зависимости от чётности. Видимо, решение заключается в том, чтобы узнать, сколько новых вхождений появляется при переходе от чётного номера к нечётному и от нечётного к чётному (сделать это можно втупую, сгенерировав 2-3 первые строки Фибоначчи, которые по длине превышают строку-запрос), а затем с помощью возведения матрицы в степень получить итоговый ответ.

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

Can anyone explain me, how to solve problem G2?