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

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

Привет всем!

Это 139 раунд на Codeforces специально для 2го дивизиона. Участники из 1го дивизиона могут принять в нем участие вне конкурса.

Раунд готовили Ripatti , Gerald , Delinur.

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

Удачи!

UPD. По техническим причинам контест откладывается на 15 минут.

UPD2. Тестирование завершено. Победители:
1. wccy
2. ttl
3. shubhanshu
4. Atarashi_Ako
5. dvylfz921

2 участника решили все предложенные задачи.

Разбор.

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

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

Ура! динамическая стоимость! :) Всем удачи!

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

    О нет, динамическая стоимость. Но все равно всем удачи.

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

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

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

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

    В том что стандартная разбалловка не всегда объективная.

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

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

    MikeMirzayanov:На практике все не так просто. Иногда оказывается, что авторы и тестеры не угадывают сложность задачи с точки зрения массового участника.

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

Time for the contest is 23:30 in China. It's toooo late

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

Опять перенесли. Ну офигеть теперь.

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

Начало соревнования сдвинуто на 15 мин. Это уже норма

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

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

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

Ну, сука, охуеть теперь

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

    как грубо!)

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

    дааа... быстро тут у вас минусуют

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

      Ну а ты как думал? Сейчас 2к человек практически нечем заняться — а ты беспокоишься что 15 человек заминусовало

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

Дают людям лишние 10 мин для регистрации.

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

    даа, дают 10 минут... может просто нагрузки не выдержал?

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

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

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

    сейчас по классике жанра тебя заминусуют эти люди)

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

    и еще раз Опять перенесли. Ну офигеть теперь. why +15 min??? what is problem It is shit. Usual CF problem, overload. Начало соревнования сдвинуто на 15 мин. Это уже норма зачем настолько много переносить, неужели минут 5 не хватило бы?

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

    Ну надо же чем-то заняться в ожидании раунда)

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

У меня чуть epicfail не случился только что))) Сижу жду контест, и в последний момент осознаю, что не зарегистрировался). С максимальной скоростью жму регистрация, и когда на таймере 0.00 жму зарегистрироваться)). Хром выдает баг, что было слишком много переадресаций -> думал все минус контест))) И тут — открывают регистрацию, начало сдвинуто на 15 мин. Вывод: Спасибо вам, технические причины!!!

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

    а кто-то этому рад)

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

    регистрация за 5 минут закрывается. Зря проявлял скорость и суету)

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

      Всмысле за 0.00 до закрытия регистрации))) Не зря ведь. Я зашел и перепроверил потом.

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

Зачем переносить когда контест только начинается? Можно до минуты хотя бы.

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

    Я думаю его переносят в тот момент, когда что-то падает на сервере, что контролировать явно никак нельзя со 100% уверенностью, а не просто так, хотя как знать)

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

      это коварный план администраторов

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

Хорошо, что раунд перенесли на 15 мин. у меня перед самым началом, инет на 10 минут упал).

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

Песец! И это задачи 2го дивизиона???

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

Missed the registration. Didn't know contest was today. Quite quick back to back to contests.

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

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

но всё же — это точно для второго дивизиона? ибо реально и честно я могу решить только первую.

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

    Вникай в динамическое программирование и в жадность => будет тебе счастье ! :)

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

Классные задачи, но сложноватые для див 2.. Но все равно спасибо.

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

Это ощущение, когда сдал задачу D на "Претесты пройдены" и понимаешь, что решил не правильно...

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

Задача E полное и большое Г. Видимо мне не суждено понять зачем нужно давать на контест такие задачи :-(

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

    как это Г решать, собственно?

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

      Пишем перебор. Замечаем что ответ 2 в степени что-то -1. Гуглим это что-то, дальше вроде бы понятно.

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

        ну первые два пункта я сделал... третий просто шикарен

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

      Перебираешь x, y <= 10000 кладешь их в bitset<100000000> теперь идешь по нему и видишь что первые числа равны: 1, 3, 15, 63, 4095, 65535 и понимаешь что последовательность такая 1 2 4 6 12 16. Вбиваешь их в в берешь второй вариант как наиболее подходящий нажимаешь на ссылку и видишь первые 39!!! а не 40 ответов. Вбиваешь шлешь видишь что ты угадал последовательность правильно остается только 40й ответ узнать. Начинаешь гуглить выяняется что эта хрень называется числа Мерсенна. Ищешь 40е число Мерсенна в гугле находишь и самое сложное в этой задаче (тут то я и набажил) вычитаешь 1.

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

        будет забавно, если авторское решение такое же)

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

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

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

            А может, там не числа Мерсенна.

            UPD: да, они, уже прошло такое решение.

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

        О, вы опередили мой вопрос. Спасибо за информацию. Жаль, что мощности моего компьютера не хватило на то, чтобы за адекватное время получить 6е число, не подвешивая остальные процессы...

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

          Вы наверное совсем не оптимально это делали, я без особых проблем отыскал 7 чисел.

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

        А я даже следующее найти смог, только выбрал не ту последовательность на oeis.org.

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

      ответ [M_n/2],где M_n — n-е число Мерсенна

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

I wonder what is the solution of E. Anybody write in short please.

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

I finished Div.2 C problem just 5s late... Bad luck...

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

Прекрасный контест, очень интересные задачи. Из последних -- совершенно точно один из лучших для большинства участников.

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

сбалансированый интересный контест, но Е (точнее ее решение) — это бомба

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

Спасибо, pva701 за помощь.

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

Задача E — боян. И зачем такое вообще давать на контесты?

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

    Последнее число — 225964951−1 — было найдено 18 февраля 2005 года, оно состоит из 7816230 десятичных цифр, тот же, кто найдёт простое число более чем из 10 миллионов цифр, получит приз в $100000. Эти деньги можете выиграть и Вы, если присоединитесь к проекту.

    может поэтому?

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

Зато теперь мы знаем, кто умеет гуглить.

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

А разбор будет?

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

Я один заметил, что tourist писал на С++?

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

[CENSORED] ну и задачи!

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

как я люблю Ripatti

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

"It started like a Cheetah , but now is as slow as a snail "- yes , the system testing

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

Solutions to A and E of wccy and wzc1995 are ditto same.

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

в этот раз видимо тестируют вручную

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

Учитывая проблемы в начале контеста и скорость системного тестирования, хочется передать админмистрации привет :)

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

    супер, на самом-то деле.

    всем Лига Чемпионов)

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

So slow.. =/

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

Довольно странно, мое решение задачи D на тесте (в правке 2) в запуске потребляет 289736 KB, но все равно проходит.

Offtopic: и почему-то постоянно стало переключать сайт на английский язык.

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

deleted

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

Although my program of problem C is passed by the system test, my total scores in the scoreboard does NOT add the score of the problem C as well as my new rating. Please recalculate my score and new rating.

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

I have a problem with B: why i WA at test6:

4 3 Output 3 2 1 1 Answer 2 4 0 "If there are several possible answers, print any of them." ???

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

For this 139 competition, I receive notification on E-mail 4 hour after contest!

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

А это у всех перестало показывать номер реального теста на котором выполняется решение в статусе?

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

а мне одному уведомление о начале этого раунда пришло на почту сегодня в полвторого?

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

225D - Snake In the problem was said that the snake's head is "1", the second segment is "2", and so on to k. But in the sixth test the snake starts from 5 to 9. Where is the first part from 1 to 4?

I saw it — http://codeforces.com/blog/entry/5322#comment-105121

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

Что случилось с рейтингом? У меня после этого соревнования отняли 5 рейтинга, а сейчас еще единица убавилась=)

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

I'm having some troubles generating the K-bonacci numbers on problem B. I tried to just implement the recurrences describe in the problem statement, but I suppose I have a bug somewhere. Can anyone help? Thanks.

typedef long long i64;
i64 K;
i64 S;

i64 F(i64 n) {
  if (n >=1 && n < K)
    return 0;
  if (n==K)
    return 1;
  i64 ans = 0;
  while(n > K) {
    ans += F(n-1);
    --n;
  }
  return ans;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("139_B.in","r", stdin);
#endif

  cin>>S>>K;
  for(int i = 1; i <= 15; ++i) {
    cout<<F(i)<<endl;
  }

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

    while(n > K) is wrong. You should add every F(x) for x in [n — K — 1, n — 1].

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

      Thank you for the help. I changed the loop to be like this, but I never get 3 as one of the K-bonacci numbers when using K=2. However, according to example 1, 3 is supposed to be one of the numbers.

        FOR(x,n-K-1,n-1) {
          if (x < 0)
            break;
          ans += F(x);
        }
      

      At any rate, I don't want to waste anyone's time here, so I will try to study some other solutions to see if I can use them as a reference. Thanks very much again for your help, I really appreciate it.

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

Извините, не к тому контесту комментарий.

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

Can anyone tell me what is the relation between Mersenne primes and the answer of Problem E???? I mean what is the proof that (2^(Mp-1)-1) don't have an answer to the equation??? I will appreciate a proof or a reference to be read! ;)