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

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

Всем привет!

Совсем скоро, 26 ноября в 19:30 MSK состоится Codeforces Round #215, автором которого являюсь я. Это мой девятый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald), Диме Березину (Berezin), Виталику Аксенову(Aksenov239), Михаилу Мирзаянову (MikeMirzayanov) и Максиму Бевзе(Cenadar) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Разбалловка див1: 500-1000-1500-2000-2000
Разбалловка див2: 500-1000-1500-2000-2500

Gl & hf ! :)

Раунд завершен, спасибо за участие. Извиняюсь за ошибку в задаче A. Надеюсь, что задачи Вам понравились, а нестабильность сегодняшнего соревнования не испортила Вам настроение.
Всем хорошего вечера :)

Так же давайте поздравим rng_58 с достижением 3010 очков рейтинга!

Разбор тут.

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

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

This Contest and previous one from the same street as Berezin said :)

When I read the previous round post I say to myself yea no recommendation for reading all problems But I found this statement

Sergii sends greetings and strongly recommend to read ALL tasks. :)

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

Странно, что пока никто не выложил известное фото автора.

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

Why another round for Div1 takes place at Tuesday? Sadly I'm not able to take part in any round at Tuesday, I prefer Saturdays/Sundays and I think I'm not alone with that opinion.

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

Although I hate the time (19:30 MSK, means 23:30 Peking time) because it means I cannot go to bed until nearly 2:30 am, I still like taking part in the contest.... I hope more contest starting earlier...How about at noon in MSK?

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

    I think this time is chosen by considering most places in the world.

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

      But 19:30 MSK is not rational enough, because most coders don't like contests between 00:00 am and 13:00 pm, but not just between 00:00 am and 8:00 am.

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

      right. for this is a russian website actually. thought that if the round can start a little earlier, only 30min is ok...perhaps i'm a little selfish.having contest after having supper isn't a nice thing, right?

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

Most probably last round before Dhaka site regional ... :)

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

I really like your contests than others, thanks a lot.

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

Project presentation tomorrow ... but sereja's rounds have so interesting questions that I can' leave it :)

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

    I have my last presentation for university :3! In 4 hours... Ahh Codeforces habe become a vicious fot me last week xD!

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

Ого разбалловка уже определена,РЕДКОСТЬ!!!!

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

GooD Luck!!!!!

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

Damn!! Cannot participate cause of overtime at work.. Anyway, all the very best to everyone.

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

Wow! almost 3 people participated per second! (in the last 3 minutes before end of registration)

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

GLGL! c:

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

Каким образом в пятой задаче решение мождно найти в массиве длиной 1 если по условию задачи в массиве должна быть пара чисел x и y x ≠ y?

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

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

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

      Я не нашёл как задать вопрос жюри, да и времени особо искать сейчас нету — соревнование идёт :)

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

        Прям на главной странице контеста — большая кнопка "задать вопрос"

        P.S. А открыть пост и написать коммент время нашлось? :)

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

        Посмотри, внизу есть "Вопросы жюри". Там рядом есть кнопка "Задать вопрос".

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

Hey! Your not using PHP 5.4 as you state in FAQ. Array short syntax [] causes compilation error. Update PHP or your docs.

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

"К сожалению, его реализация алгоритма работает слишком долго, поэтому Сережа обратился к вам за помощью." и сразу появилась легкая неуверенность))

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

Какие вырожденные случаи существуют в задаче С 2-го дивизиона?

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

А за взлом жюри +100 не дают, да?

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

    Тогда +300, у нас было 3 решения, все упали.

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

    Ага. Картина маслом: у меня -2 по задаче, у тебя -1, у Petr -1, у Dmitry_Egorov -1. Что нужно делать в такой ситуации? Правильно, такого не бывает, жюри где-то лажануло, надо идти решать другие задачи.

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

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

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

        Я сделал так же, но жюри мне ответило "нет, у нас нет такой баги" (ну либо я его не понял), поэтому пришлось дальше баги у себя искать :(

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

          Извиняюсь, просто я был уверен, что если 3 решения верны и обсуждены, то все будет хорошо. Не все так хорошо... :(

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

            Можно было написать совершенно тупой брут, который делает то, что описано в условии (;

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

            Ясно. Мне кажется стоит на первые несколько бревен по любой задаче смотреть глазами, благо задач всего 5 в контесте :)

            Спасибо за раунд!

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

    +100 к рейтингу:)

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

    а в чем у жюри ошибка была?

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

I spent lots of time trying to use method mentioned here to hack submission 5246996, but failed to generate the anti-hash sequence in time.

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

Whats wrong with my code (5256546) for 367A - Sereja and Algorithm ? I'counting 10e5 steps, but still get time limit exceeded?

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

    Maybe it's because you used "cout" and "scanf". I think I have read one time that "cout and cin" and "printf and scanf" can have problems when used together...

    I tried with only cin and cout, and it is accepted: http://mirror.codeforces.com/contest/367/submission/5259184

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

    Actually, its because your solution is O(n^2) and not O(n) as it looks. That's because you're calling strlen(s) in the for loop, for each iteration, which is itself O(n). Call strlen once, keep its value in a variable and use it in the for loop.

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

А на чем B так активно ломали? Неужели антихештест?

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

    Егор у нас ломал, видимо, на этом:

    lastIndex = i + (p — 1) * m; // overflow

    if (lastIndex >= n) ...

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

      Да, все 3 взлома таким тестом

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

      Блин. На том же упало.

      long long index = i + (p-1) * m;

      Не до конца подумал, что там лонг лонги.

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

    http://pastebin.com/S4zNh4Em

    Некоторые зачем-то перемножали p и m. И иногда получался бред.

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

    У меня в комнате было несколько неправильных, которые не проверяли, что q  +  (m  -  1)·p  ≤  n и из-за этого слишком часто добавляли в свою структуру элементы массива b, что приводило к TL на тестах с большими m и p.

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

Сломал восемь решений разными тестами вида:

n, m, p = 100000, 100000, ...
print(n, m, p)
L = ' '.join(map(str, [i % 4243 + 1 for i in range(n)]))
print(L)
print(L)

где вместо ... подставляются числа 90000, 80000, 70000 и 60000, чтобы добиться разных видов переполнения выражений вида (m - 1) * p. А кто C на чём ломал?

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

    С ломали на неправильных формулах.

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

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

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

    Девять на этом же =) n = 110000.

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

I can not even imagine how author come up these ideas for problems? Sereja Can you please give us some idea about how did you think about setting about these problems, so that it might be good for upcoming setters ??

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

Если я правильно понял условие, задачу 367D - Сережа и множества мы с vysheng давали уже почти семь лет назад с ограничением m ≤ 26 (задача G). Широко известным бояном она, видимо, не стала.

Интересно, удалось ли мне её после этого сдать :) .

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

Задача С очень похожа на А из этой интернет-олимпиады. Правда, там был цикл, а здесь массив, но это мало что меняет.

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

    Тут уж куда сложнее. В моей задаче всего то нужно просто заметить эйлеров граф. Тут же огромнейшая куча гемора, учитывая условие "равные рядом не стоят".

    Тем более тут еще и цикл)

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

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

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

Кажется, настало время выполнять обещания =(

Кстати, кто-нибудь может сказать решение В и, по возможности, объяснить, почему следующая стратегия ведёт к ВА 3: Разобьём a на двумерный массив moduls[i][j], где moduls[i][j]=a[p*i+j], а затем отдельно рассмотрим все строки такого массива и найдём все подстроки оных, которые совпадают с b.

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

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

    UPD: и полные тесты тоже

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

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

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

    ВА3 — это не сортишь ответ

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

It seems that many people got tricked when solving Problem A,Div.2.I got tricked,too.Although I found it in the last few minutes,I still lost a lot of score.I think it's a good lesson for us who want to solve the easy problems as fast as possible.Nice job,Sereja.

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

Как решить "B" (div 2) ?

Я решил таким образом: pastebin.com/LvYPHfQm

Но у меня превышен time limit на 11 претесте.

Скажите пожалуйста, в чем у меня ошибка?

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

    TL ты поймал из-за того, что для каждого запроса пересчитываешь ответ. Асимптотика решения получается O(n^2). Можно и нужно её улучшить :)

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

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

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

        или как это делается?

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

          Нужно было предпосчитать ответ для каждого i=1..n,чтобы потом отвечать на запросы за O(1); Предпосчитать можно за линию несколькими способами.

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

          Допустим, у нас есть задача, где мы должны быстро отвечать на запросы о сумме на отрезке от l до r. Возьмем наш изначальный массив и на основе него посчитаем новый массив(этот трюк называется префикс — суммы). Пусть этот массив называется sum, а изначальный массив — a. Тогда i-тый элемент в массиве sum равен сумме первых i элементов в массиве a. Обратите внимание, что массив a[] у нас в 0-индексации, а массив сумм в 1-индексации.

          sum[0] = 0;
          
          for(int i = 1; i <= n; i++) {
              sum[i] = sum[i - 1] + a[i - 1];
          }
          

          Замечательно, sum[1] = a[0], sum[2] = a[0] + a[1], sum[n] = a[0] + a[1] ... + a[n — 1]. Что это нам дает? Пусть нам поступил запрос найти сумму от l до r, тогда ответ — (сумма от 1 до r — сумма до 1 до l — 1).

          result = sum[r] - sum[l - 1];
          

          Теперь подумай, как на основе этого давать ответы на запросы, которые в задаче В.

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

Can anybody please tell me how he solved problem C div 1? I tried to count what's the minimum required N to use K different values, so I tried to find the maximum K <= M such that the found N is less than or equal to the given N and pick the largest K costs from input, but I couldn't pass pretests.

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

    The idea is just like that ... Seems you have got the implementation wrong.

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

    F(K) is the minimum required N to use K different values. If k%2=1 => f[k]=k*(k-1)/2 + 1. If k%2=0 => f[k]=k*(k-1)/2 + k/2.

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

      What's the proof?

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

        It's about Euler path in Complete Graph. There are K vertices and a edge is a condition, you want to go through all edges. If k%2=1 => k vertices with even degree. If k%2=0 => k vertices with odd degree. You can think about it that way.

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

          During the contest it looked like a Chinese Postman problem in complete graph to me. In Euler Path edges can't be visited more than once, aren't we allowed to do that here (even in optimal solution) ?

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

            If k%2=1, all vertices have even degree so we can go through all edges and finish in start vertice. That's why f[k]=number of edge + 1 in this case. If k%2=0, we have k vertices with odd degree, so just add an edge between 2 vertices have odd degree, we add in total k/2 new edges. After that we can go through all edge but not finish in start vertice (be cause the last edge is the added edge and we already go through the original edge).So F[k]=total number of edge (new edges and original edges) for this case.

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

What's the source of the problem with problem div1-A? How is it even possible to have the judge solution for the first problem in the contest fail pretests? Have you tested the problemset at all?

I only saw the announcement around ~30 minutes into the contest (since the popup opens in a random open window of CodeForces, not necessarily the one you're looking at), and spent the whole time "debugging" my A. Then at the end I missed the chance to submit D by seconds :(

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

    We had 3 solutions. All of them were wrong :( Sorry for such situation.

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

    Whole time "debugging" your A ???
    you submit it after 12 minute :) :)

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

      Yes, and it was correct, but it got WA on pretest 3 then. 3-7 minutes later, the judge solution was corrected, but I only saw the announcement about this (and that my solution now has pretests-passed) 18 minutes later.

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

why are most of the nowadays contests in Sundays or in Tuesdays? I count and find that there are about five contests in this month that they were in Sunday or Tuesday. Unfortunately I have a class these days and I lost these contests. Is it fair? I wish next contest will not be in Sunday or in Tuesday. I wish ...:) (I want to write this comment before the contest but I arrive home now!)

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

Problem B in Div 2: The question defines the sequence as "li, li + 1, ..., ln" but shouldn't this be "li, li + 1, ..., n" according to the second explanation which says "a(li), a(li + 1), ..., an" I got a WA because of this since I assumed it was "li, li+1 , ..., ln"...

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

what a good contest! :D really cool, good problems

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

Wow, the system judged very fast today.

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

Ого, обновление рейтинга просто-таки молниеносное.

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

Integer overflow on Problem B again ARGHHHHH

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

Finally 3000! :)

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

Как решалась C (Div2)/A (Div1)?

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

    Предподсчитаем количество букв (суммарное).

    Далее, если r-l < 2, то ответ YES, иначе смотрим на кол-во букв на отрезке (разность предподсчета), если разница максимального и минимального больше 1, то NO, иначе YES

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

Почему строка yyx это YES?

Задача С div2. Тест 3. Строка 2.

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

What a good problem A! 7 successful hacks!

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

witua: 2293 -> 2191 (-102), 278 место.

I_love_Tanya_Romanova: 2291 -> 2189 (-102), 479 место.

Как-то мне оно кажется странным. Или так должно быть?

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

    Похоже на искусственное ограничение. Еще пример: poopi: 2217 -> 2115 (-102), 448 место.

    Но готов поспорить, что все равно формул нам никто не скажет.

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

    Мне кажется, или имеет место неправильное вычитание? ;)

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

Very interesting round, waiting for the tutorial..

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

Удивлён, что раунд rated — вроде же аж 15 минут было неправильное решение жюри?..

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

    К сожалению, в последнее время требования к раунду для признания его рейтинговым сильно упали. Постоянно падающий сайт, 15-минутная очередь тестирования, или, как сейчас, неправильное решение жюри одной из задач (а 15 минут — это очень много для старта контеста) уже давно перестали быть поводом для анрейта. Да и TC в последнее время этим периодически грешит.

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

Thanks Sereja! It's a nice round: Solutions are short and clear. And the overall difficulty is not too low as I thought (Because it has some tricks in implementation, I failed 2 tasks by it.).

Maybe we can have more rounds like this, do you think so?

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

In problem Sereja and Algorithm, here the constrain is "string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2." But when I see the testcase then I'm confused, because answer is "YES" when q contains such substring like "zyx", "xzy", "yxz". Why? My code is AC after the contest because in contest time I was confused.

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

А разбор по ссылке найден. Или это только у меня?

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

Div1-pB is almost as same as IIUPC 2013 pH which occured on contest of UVa Online Judge today!

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

I got AC on Sereja ans Anagrams with this code: 5261631. Yet, I am getting WA with this 5261332. This two codes are virtually same except for in one I am using

(WA) if ( good == mp.size() ) // Here mp is a map < long long, int > mp
(AC) if ( good == dif ) // Here dif = mp.size() right after inserting things in map.

The reason I am getting WA is because the size of mp changes at the end of the process. But it shouldn't since I am not inserting anything after the beginning. Can somebody explain this bizarre situation? It would suck if I ever have to face such situation during contest time!

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

    When you use map[num], it will add new element in map if num isn't already in it (example). So, if array A has some elements that B dosen't have, size of map will be changed.

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

    Run this code. May b this might help you. int main() { map<int,int>M; int sz=M.size(); cout << sz << " " << M.size() << endl; if(M[5]==1)cout << "i m not gonna print" << endl; sz=M.size(); cout << sz << " " << M.size() << endl; return 0; }

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

This is my submission of Problems B. Div 2

http://mirror.codeforces.com/contest/368/submission/5266990

I confused why the output of test 2 was different from it was on my computer and Ideone.com. Any body can help me ? Tks for all :)

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

    I test your code for test 2 it's WA your program give me 3 2 1 also it's basically seem WA can you explain your solution ?

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

      For each l[i], I put a[l[i]] into a Set in C++, and the set only holds distinct numbers, so I simply print the size of this set

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

        In your solution you're only counting the number of different integers amongst alm, alm - 1, ..., al1. Instead, the problem asks you to find the number of distinct numbers amongst ali, ali + 1, ..., an, for each of li.

        On a side note, I would discourage the use of preprocessor directives like these:

        #define FOR(i, a, b) for(int i = a; i <= b; ++i)
        #define FRD(i, a, b) for(int i = a; i >= b; --i)
        

        Essentially, the main goal for the majority of participants here is to improve their problem solving skills. Even if less typing saves an extra 3 minutes per match for you or me, it is somewhat unlikely to make any difference. Rather than that, it's all about learning to find the solutions for increasingly harder problems in increasingly smaller amount of time. And especially if you're only beginning to practice solving programming contests, writing a clear code (without macros) will only help you to maintain a better clarity of mind.

        But that's just my own opinion. I realize some people will disagree, and at some skill level this coding "style" may become more useful.

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

          I like these macros and would recommend them. I think the code is much clearer (for the given participant, at least). Also, you'll never make a mistake like:

          for (int i = 0; i < n; ++i) {
              for (int j = 0; j < n; ++i) {
                  // ...
              }
          }
          

          which is really hard to find (at least, just by looking at the code).

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

Hi everybody, sorry to bother, but I don't understand why I get different outputs between the online judge and my computer

http://mirror.codeforces.com/contest/368/submission/5275044

That's my solution, and it works fine when I try it... but it doesn't seem to work in the online judge... Any ideas? :(

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

    Aren't you going out of bounds with this line, when your loop enters for the 1st time?

    arri[i] = arri[i + 1] + 1;

    so arri[i + 1] will have some random value in the memory, since you declared the array localy?

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

I think Problem C from Div2 Has some problems to be fixed ! Or changes which were made during contest are not being reflected in the practice session !!

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

I think there is some problem with Problem C in DIV2 to be fixed or the changes which were made during contest are not being reflected in here !!

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

    Everything is good with the problem. Just be more careful while reading as statement can be a bit difficult to understand at first. Cost me 5 WAs before finally getting it AC. Hats off to Sereja for the problems though.

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

I am confused about a testcase given for Div2-C: Sereja and Algorithm.

q=zyxxxxxxyyz (input string) s=zyxx (query substring)

The explanation for the says — "...you can get string "xzyx" on which the algorithm will terminate" However, the problem states that 'zyx' should not be present in the query string.

In fact, the permutation 'zxyx' would be allowed, but not 'xzyx'.

Am I missing something?

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

    Yes, you're making up additional constraints. There is nothing in the problem statement saying that there can't be 'zyx' present in the input string. It only states that 'zyx' won't be rearranged.