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

Автор Seyaua, 13 лет назад, перевод, По-русски
Привет всем из солнечного Петрозаводска!

Сегодня я и мой брат sdya подготовили для вас несколько интересных задач. Из-за плотного графика на петрозаводских сборах, особенно из-за рафтинга и просмотра аниме ночами напролет, у нас было немного времени на написание длинных условий задач. Так что наслаждайтесь короткими условиями и изобретайте легенды на ваше усмотрение :)

Удачи всем!

Контест завершен! Поздравляю победителей!

Division 1:
  1. dolphinigle
  2. ilyakor
  3. marek.cygan
Division 2:
  1. wuzhengkai
  2. jayi
  3. superpear
Опубликован разбор.

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ого, какая заблаговременность.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
короткие условия это хорошо, а то последнее время, особенно на топкодере больше времени уходит на чтение задач чем на их же решение... короче спасибо)

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
thanks Seyaua &  sdya for preparing and creating problems.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Второй раз ваш контест не удается написать, обидно:(

P.S. Удачного всем и во всех смыслах контеста!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Sounds like a pretty awesome training camp.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Just a little mistake "invent some legends for them on you own." Must be "invent some legends for them on your own."
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Seyaua & sdya, you guys look exactly the same in the pictures ;-)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks to problemset I hope enjoy the problems.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему у вас одинаковая ава?))
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
which anime you guys finished recently ?
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Странно, мой гугл календарь показывал, что контест вчера должен был быть.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не знаю точно куда написать.

У меня пропала кнопка отмены регистрации. Зарегистрировался на сегодняшний раунд и только потом вспомнил что на это время назначены важные дела.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так просто не решайте. От того, что Вы зарегистрировались, Ваш рейтинг не упадет.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо, я в курсе =)

      Просто когда участвую не нравится что половина комнаты забила, не хочу быть одним из таких участников.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Короткие условия это хорошо, и рафтинг это тоже круто=)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Man I love these training camps you guys get to attend. I wish I could, but none happens in my part of the world. :( Hopefully some day I'll conduct one, when I am RED. ;)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за чушь?

Почему нет тестирования?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is the judge dead?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
what happened with the judge?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
very slow testing
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The requested URL /contest/111/customtest was not found on this server. Это меня печалит, поскольку RE#1
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How can I lock my solution?
The "lock" icon disappeared.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I like statements :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
unrate this round, please...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Огорчён тормознутостью системы...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как вторую делать?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если пройдет:
    Для каждого x находить все делители. смотреть когда каждый делитель появлялся последний раз. Если попадает в диапазон , то +1 к ответу, потом обновить для делителя время когда на него что-то делилось в последовательности.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
nice problems :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Шикарный раунд. Если бы ещё нормально работала очередь (на неё, в принципе, пофиг) и вкладка "запуск" (а вот её отсутствие печалит).

Из первых четырёх задач дольше всего думал над B, которую и написал последней. Есть решение проще, чем для каждого делителя построить список чисел, его содержащих, и потом разбираться с каждым делителем в отдельности?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно хранить когда последний раз встретился каждый делитель. И делать все онлайн
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Для каждого числа тупо построить список его делителей иподдерживать массив когда мы последний раз его видели
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Блин, очевидное же решение. У меня в общем, то же самое, только в оффлайне.
      И почему я это придумывал минут двадцать реального времени?)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        а почему я час писал какое-то г**но по ней вместо того, чтобы думать над нормальным решением?

        P.S. столь же риторично, да
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я так понимаю, что B(Div 1) == D (Div 2).

    Я для каждого делителя хранил индекс последнего числа, которое кратно ему (числа из массива X). Ну и в итоге асимптотика O(N * sqrt(N)).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите идею решения 3-й задачи во втором дивизионе, пожалуйста.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Берем a[1]=y-n+1, a[2..n]=1. Проверяем и выводим, доказать, что это оптимально, несложно.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хана обидно.Написал это, но не отправлял(.А как если не секрет доказать что это оптимально?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        (A+B)^2>A^2+B^2. Аналогично для любого N.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если a >= b, то (a + 1)^2 + (b - 1)^2 >= a^2 + b^2
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        а какой смысл не отправлять  решенную (пусть даже мб и не правильно) задачу?
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          оказывается если бы я ее здал то меня б взломали на n>y)
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            вы бы ничего не потеряли(кроме интернет траффика(: )
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      у меня именно такое решение и мне очень интересно как меня сломали
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто какие хитрые тесты знает к C (div1)? Я написал жадность, поэтому хотелось бы ее потестить...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
good short mathematical questions.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На чем ломали A(Div 1) / C(Div 2)?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I wanted to use custom test feature, but it was disabled. :(
Anyway, thanks for the good problems.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In problem B i know the size 2n*2n but i didn't notice he give me the input 2n not n
i solved the problem as the input=n so i didn't divide by 2
so just n/2 ----> passed  :( :( :( :(

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I love these short and challengeable problems.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Petya and divisors .... Nice problem  . But unfortunately i wasn't able to solve it. :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Looks like I am not getting the statement right :-

    For the case 18 4.

    Why is 6 not a solution, it does not divide any of 14,15,16,17 . Or did I miss something miniscule.

    Thanks.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      The 4 in "18 4" refers to the four lines above,
      4 0
      3 1
      5 2
      6 2
      

      18 has 6 divisors: 1,2,3,6,9,18, and only two of them do not divide 4,3,5,6.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Нельзя писать такие решения, которое я написал по задаче B. Хранить все числа, делителем которых является данное число. Счастье, что оно зашло.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Почему нет? Это nlogn в сумме по всем числам.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      вроде n^4/3 же?
      но все равно нормально, да
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        n^(4/3) push_back() мне по времени казалось многовато.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          да казалось бы не многовато, даже если 2*n^4/3, то получается около 10^7. При том, что ТЛ 5 секунд
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Разве оценка количества делителей - логарифм? 
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        2 кубических корня.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну вот.
          Да и в любом случае, было глупо не придумать решение за O(n) по памяти. Тем более что я использовал в решении тот факт что нам интересно только последнее число которое делит данный делитель. Будь ограничения чуть покруче, я бы пролетел. 
          • 13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Нет, но .

            UPD: +O(1) тоже умножено на n.
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Да. Там при суммировании n*log(n).Не успел поправить - CF отрубился.
              Upd: Правда ваша формула справедлива для одного конкретного n. Но ведь у числа n не может быть n*log(n) делителей.Я имел ввиду оценку в конце это статьи
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              нет, вот пример: 100000 раз во входных условиях число 83160. У него 128 делителей. В итоге я храню 12800000 элементов-для каждого делителя я храню номера всех чисел, которые его делят. Это больше, чем logn*n 
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Но тем не менее у первых n чисел O(nlogn) делителей. Доказать несложно, взяв сумму n + n / 2 + n / 3 + ...
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              числа там попарно неравные разве были?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Нет, какие угодно. Но можно было воспользоваться этим фактом и найти все делители чисел в отрезке [1, 105] и потом ими пользоваться. Это давало выигрыш по памяти от до O(n· ln(n)) и по времени от до
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А вот мне раунд не особо понравился. Скучная 4-я задача
+ в третьей совершенно незаметное условие m*n <= 40, в результате чего я начал искать конструктив
+ в пятой не особо заметное условие что ячейки не в одном столбце и не в одной строке.

НО: хотелось бы отметить, что задачи B и E мне понравились. С нетерпением жду разбора Е, очень удивлюсь, если окажется, что для нее есть верный полиномиальный алгоритм.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anybody tell me how testing is done when there are multiple solution for test case, like in todays div2 Problem C.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It checks to see if your solution satisfies the constraints...
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Algorithm for checker.

    If solution prints anything and it is correct- AC (it is easy to check 2 conditions)
    If solution prints anything but not correct - WA
    If solution prints -1, and jury prints -1 AC
    If solution prints -1, but jury have answer WA
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Testing procedure is not always exactly full comparing of your answer and jury answer.
    Usually authors write special program - checker, that checks your answer, using input and jury output for this test. Moreover, sometimes checker program can be much more difficult then solution.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I made a funny mistake, failed my C because I thought that 1<<6 is less than 40 :-)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что-то я совсем разучился думать. Написал в B sqrt-декомпозицию...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если не секрет, как?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Разбил все n чисел на sqrt(n) групп. В каждой группе хранил булевский массив чисел, которые являются делителем хотя бы одного числа из данной группы. А дальше для каждого делителя каждого числа находил за sqrt(n) будет ли он входить в ответ или нет.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Так все-таки, будет раунд рейтинговым или нет?
UPD вопрос снят
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите как решать задачу E(Div2)/C(Div1).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Лично я перебирал по точкам, в которых останутся пауки, и для каждой позиции проверял, есть ли рядом с ней выбранная точка. Это 2^(N*M) * (N*M). Но я перебирал маски в порядке увеличения количества битов (т.е. первая годящаяся и есть ответ), и ещё несколько оптимизаций.
    Думать дальше мне было лень, но это уже походило на что-то выполнимое по времени, поэтому я запустил это на своём компе, и минут через 10-15 получил ответы для всех возможных тестов, ведь их не так и много.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня Дп по 2м маскам:
    очевидно что нас в текущий момент интересует только последний и предпоследний столбец.
    Я хранил две маски: то, с каких клеток не будут двигаться и те которые еще не ушли с клеток, хотя клетка должна быть свободна. И переходы (i,m1,m2) - (i+1,m3,m4) m4 определяется по m1,m2,m3. Не особо оптимизил по времени, вышло: O(n*2^(3*n)) если чуть-чуть переписать, то будет: O(n*3^n*2^n).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня O(n*2^(2*min(n, m))), просто держу две последние маски и слежу, что-бы второй столбец который рассматривается после перехода был заполнен (то-есть что-бы все расстояния были не больше 1).
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Мда, собственно непонятно, почему N*M <= 40. Сразу веет каким-то перебором, поэтому тупанул с решением. Лучше бы дали N <= 8, M <= 1000 (что-то в таком духе).
        Ну и небольшой комментарий к решениям: N <= 6, так как мы можем спокойно повернуть поле, если это не выполняется.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можете поподробней объяснить свою идею ?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Как я понял ты делал изломаный профиль, что-бы добиться такой оценки?
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Забыл вчера учесть переход - да, у меня O(n*2^(3*min(n,m))).
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Так реалистичнее))
            Самое лучшее что можно написать это наверное: O(N*M*2^(2*N)) N<=M.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Поделитесь идеей, пожалуйста :)
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Тут вроде-бы все стандартно, добавляем по одной клетке, очевидно что интересующих старых будет N, потому-что то что было раньше уже не исправишь. Ну и как в моем решении храним две маски то что будем/не будем трогать и положение клеток, то-есть выполнилось или нет, соответственно с маской. Когда убираем последний бит, он обязательно должен быть в нужном состоянии. Кстати можно написать это за O(N*M*3^N), так-как вторая маска подмаска первой.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите , а почему взламывали вариантом n>y задачу 3 в втором? Это авторы не учли в претестах или они типа оставили пространство для взломов?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Понятно, что оставили пространство для взломов.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
      Ну так претесты на то и существуют, чтобы пропускать решения, походие на правильные. Но на сей раз количество взломов по С div.2 / A div.1 больше чем по всем остальным вместе взятым.  
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In division 2, C; test 50 looks like that: 2 1 1 and the supposed answer is 0 1. However, in problem it is said that all the numbers should be positive integers, it means 1 or greater. So with n=2, it is impossible to satisfy y=1. My answer was -1 then, but i got WA.
Did I miss something or it is a mistake in author's solution?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    No, your answer is 0 1, and the correct one is -1. At least, that's what I see below your solution.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Your answer is not "-1" but "0 1".
    You can see checker message in test protocol.

    In test 50 for your solution message is: "wrong output format All numbers must be positive, but the 1-th isn't (1-based)."
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я внезапно фиолетовый (:
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Excellent contest like it (though my rating went down)
Can anyone help me with the problem Div1C.....
How the answer for input 4 4 is 12............... 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
This is the first time in my life I've become Blue.

Nice Problem-set.
but I don't know why the judge queue took so much time.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think brief description is cool. With possibly as much mathematical expressions as possible to reduce ambiguity.
Thanks  Seyaua and sdya for problems :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ya bro...i loved the problem c...nice greedy...and look at the input set man....!!! when you go to check (Y-n+1)^2 here there remains input like 100 1 1... really cool...rare experience\m/
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если кому ещё может интересно, в задаче С у меня было дп по троичной маске, где варианты клеток: паук останется, паук сползет вниз, паука уже нет.
Для перехода перебирал двоичную маску где останутся пауки. Сложность O(N*(3^M)*(2^M))(N>=M).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А как работать с троичной маской? Все время делить?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice short-statements problem set!
Any one else didn't see the n.m<=40 constraint in C DIV-1?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Many didn't see (at least three other persons except me), that's why I personally don't like the round.

    UPD: Yeah, baby, give me more minuses, people never like truth =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      It could have been more clear this way (same meaning):
      The first line contains two space-separated positive non-zero integers n and m (1 ≤ n·m ≤ 40) — the board sizes.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It takes me about 45 minutes to find a solution for 1600 cells and after beind disappointed, I read the problem once again and saw that it is n.m<=40 not n,m<=40
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ohhhhh and I just realized!! I can't believe myself.

      n x m  would have been a lot clearer
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Finally Petr owns both TC and CF.
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Is there any way to see on which test case my solution was hacked i.e. the hacker's input during the contest?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can someone please explain the solution of problem E from Div 2? :D
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It is basically brute-force but reducing complexity to solvable limits by using memoization/bottom-up DP.
    1.first rotate the grid such that smaller side remains at top, which is of length <= 6. (sqrt(40)).
    2.then try all possible subsets (2^6).
    3.any particular state is given by settled spiders in curr. row and prev row. and the curr row number.
    4.Easy if you have solved similar problems previously.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

tunyash, я для этой задачи M раз делил(умножал) на 3.
Быстрее можно, если, например, предпросчитать результаты функций, аналогичных операциям битовым AND, XOR и тд. для небольших чисел. И для работы с большими числами разбивать на меньшие делением на степени тройки.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
it isn't fair!
the timer should be started as a problem is opened or at least when someone enters the contest area!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    But your first submission was only after 34 minutes, when judge has already begun to work properly
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think this is a fair complaint.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    As I understood this complain is not related to today's incident, but for CodeForces format as well. But it's the rules - the timer starts at the set time.
    But seriously, I don't get what isn't fair - that's the rules of this competition. It's like arriving late to a rock star concert and complaining afterwards that he started before you arrive. The advantages and disadvantages of particular format (CodeForces/ACM/TopCoder/IOI etc.) is another topic.
    Sorry if I misunderstood your post.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
yes, but I entered the room 26 minutes after the beginning and it should be 8 nor 34!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Why? This is not TopCoder.
    Here time is calculated like ICPC style, from the beginning of the contest. You can read about this rules in FAQ.
    And anyway, you've missed the time when judge had troubles.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мне очень понравилось решение Андрея Лопатина по задаче С. Он занял 44 место на раунде, посмотрите:)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Объясните в чем я не прав в задаче Д:
для m=1: ans = k^n
для m=2: нужно посчитать кол-во способов покрасить первый столбец в Т цветов и второй в Т цветов(причем использовать все Т цветов нужно), и для каждого Т их перемножить.
для m>2: у нас первый и последний столбец должны содержать одни и те-же цвета, а посередине цвета которые использовались по краям, но не обязательно все.
Получил ВА на претесте 4, видел что не у одного меня такой ответ на него выдавало. ЧТо не правильно?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не одни и те же, а они должны содержать одинаковое количество цветов. Это сильно меняет задачу
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Текст задачи:
      "для любой вертикальной прямой, проходящей по линиям сетки и делящей доску на две непустые части, количество различных цветов в обеих этих частях должно быть одинаковым."
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Чтобы это условие выполнялось, цвета должны быть одни и те же
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Нет же.
          Если покрасить доску 2x2 следующим образом:
          12
          23
          то условие выполняется, хотя множества цветов слева и справа не совпадают.
          • 13 лет назад, # ^ |
            Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

            Я имел ввиду для m>2. Хотя, по ходу, и здесь я не прав. Контрпример:
            132
            333
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Тоже неправда.
              122
              223
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Спасибо, понял. Жаль что не заметил на контесте, решение не сильно пришлось изменять что-бы получить АС,
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Когда будет разбор!!!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Разбор задач A-D.div2 уже есть, а E.div2 разобрана чуть выше. Не понимаю, в чем проблема.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Может, люди, которые решили по 4 задачи в 1 дивизионе, проведут какой-то разбор?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А почему у http://mirror.codeforces.com/profile/tourist по задаче D TLE 11 тест? А именно, если посылать соответствующий код под Delphi 7, он TL'ится, а под FPC -- AC с 750 мс. Есть объяснение данному феномену?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кажется, Delphi как-то очень тупо эмулирует int64 работой с двумя integer. Я сталкивался с тем, что число вычисления в int64 на Delphi работают в раз 5-10 медленнее аналогичного кода на C++ для типа long long. Может в FPC с этим получше, отсюда и разница?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, действительно оказалось, что взятие 64-битных чисел по модулю в Delphi работает на порядок медленнее, чем в FPC.

      Честно говоря, отсутствие возможности запустить код на сервере довольно сильно помешало (использовать то, что за WA1 баллы не снимаются, на контесте я не догадался :)). У меня локально работало примерно 7 секунд, а во всех задачах разница по сравнению с серверами CF была как минимум вдвое. Но не в этой...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hi! This was a great round, except for some technical issues that we all noticed, but oh well, they didn't really affect anyone's score in my opinion :D When is the editorial going to be available?
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Простите за глупый вопрос, но в див.2 в задаче А, как можно было коротко поменять все буквы скажем на нижнего регистра? Просто я не понял как такое организовать и написал цикл с кучей ифов и  вещей а-ля 'A'='a'

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

    как вариант можно использовать такое условие, когда проходитесь по строке.

    if (s[i]>='A' && s[i]<='Z')

    s[i]=s[i]-'A'+'a';

    а так есть ещё встроенные функции. например в с++ функция tolower(s[i]);

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The next context is coming soon.But the editorial still isn't available!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What an elongated "soon" you mentioned. The tutorial isn't available yet! :O
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

?detaR tI sI