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

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

Всем привет!

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

Спасибо Фурко Роману(Furko) и Геральду Агапову(Gerald) за помощь в подготовке задач, а Марии Беловой(Delinur) за перевод условий. Также выражаю благодарность создателю Codeforces Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему.

Удачи на раунде!

Разбалловка в первом дивизионе: 1000-1000-1500-2000-2500. Разбалловка во втором дивизионе: 500-1000-2000-2000-2500. Настоятельно рекомендую прочитать условия ВСЕХ задач.

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

1й дивизион:
1 место: Egor
2 место: Petr
3 место: tourist
2й дивизион:
1 место: antimatter
2 место: c175353
3 место: takaramono

Надеюсь, задачи вам понравились.

Разбор задач.


Немного личной информации.
В этом году я закончил школу и буду поступать в университет. Программированием занимаюсь почти 5 лет (с 7го класса). Помимо информатики, любительски увлекаюсь спортом: пауэрлифтинг, армрестлинг и плаванье.

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

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

Раунды от школьников всегда интересные!

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

so, we are gonna have some sports flavored problems!!

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

А какое будет распределение балов стандартное или динамическое ?

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

will the scoring be as usually or dynamic ?

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

    Dynamic scoring is nearer and nearer to become 'usual & default' :)

    UPD: not this time :D

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

      Well usually when the contest only for DIV 2, it's using dynamic, and for both Division they usually use normal scorring IMO

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

      I disagree..If you browse thorough the contests after Round #113(after dynamic scoring was introduced) you will find that apart from rounds #115 and #126 and all rounds from the trio NALP- Gerald-HolkinPV (which have dynamic scoring systems) ,,the scoring system has been traditional in other rounds. So I think they leave it on the authors to decide ..

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

Good Luck And Have Fun! :)

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

hacked by hackers

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

Спасибо автору за возможность посоревноваться, с нетерпением жду начала раунда

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
'Немного личной информации.
В этом году я закончил школу и буду поступать в университет. Программированием занимаюсь почти 5 лет (с 7го класса). Помимо информатики, любительски увлекаюсь спортом: пауэрлифтинг, армрестлинг и плаванье.'
А я Никита, ...
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to run my program at local machine? Above is quickly enough?

g++ xx -o exe

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

Что с разбалловкой в div2?

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

Почему в задаче В написано что запрещено использовать лидирующие нули, хотя в первом семпле ответ с нулем в начале?И еще написано что можно использовать не все цифры из набора, следовательно для третего семпла есть ответ, убрав одну двойку!

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

    Нужно, чтобы одновременно делилось на все 3 числа, читайте внимательно условие

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

    Связь с жюри в помощь

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

что там за 11 тест в б

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

UPD опечатка уничтожена.

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

Мне же не одному кажется, что это был ужасный гробовой контест?

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

    Либо я тупой и у меня сейчас все попадает, либо первые 4 задачи ну совсем простые

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

      Ну.. Я же не о вас, уважаемые гроссмейстеры, а о простых смертных =)

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

    Просто не было очевидных реализаций.

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

    У меня вот как раз сложилось впечатление, что это я идиот, а задачи вполне решабельные)

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

    D самая простая.

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

Забавный раунд, давно я B не оставлял. Хочется посмотреть, что же там.
Задача D порадовала. Интересно, это авторское: поставить пятиугольники рядом и начать с проведения длинной прямой линии?

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

    В В, казалось бы, перебираем первую цифру, а дальше рюкзак для каждой цифры. Итого 10^2 * n^2

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

Авторы, спасибо за отличные задачи! Попробовал все и не пожалел.

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

Почему в С настолько маленький МЛ?

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

    Потому что можно за O(N^2) памяти сделать.

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

      Красота :(. Ну что же, в очередной раз получаю по халявной задаче плохой вердикт.

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

    Гораздо печальнее то, что не хватает по-видимому совсем немного. По подсчетам вполне должно укладываться, возможно на С++ так и будет.

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

      Лично мне не хватает очень даже много (я потом послал в "Запуск", и ТАМ получил МЛЕ — превысил 512МБ). В следующий раз буду думать, прежде чем писать всякую такую бодягу с гигантскими массивами.

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

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

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

Very interesting B question in Div-2..It made me so involved that I did'nt have the time to read C,D,E..But I am happy I managed to pass th pretest finally after 11 WA..

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

Надеюсь, у меня в B какая-нибудь страшная математическая ошибка, а не дурацкая опечатка, которую я не нашёл за последние полчаса о_О Вот же обидно будет =Ъ

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

Спасибо за интереснейший контест! Наконец-то контест без очевидных реализационных задач

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

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

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

    Можно куда проще, напишу в разборе.

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

      Действительно D вышла простоватая, было бы круче, если "прямой цепочкой" размещать не влазило бы, решения были бы немного сложнее, а рисунки красивее.

      Остальными задачами очень доволен.

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

Свинство все-таки получилось с задачей D, по поводу того, что требовалось выводить хотя бы 9 знаков после точки.

1) " с точностью не менее 9 и не более 100 знаков после десятичной точки." Если бы не было слова "точностью", то эта фраза бы означала то, что задумывали авторы. А так, как мне кажется, написано "с абсолютной погрешностью не более 10^{-9}". Непонятно правда, что значит не более 100 в такой интерпретации.

2) Мне кажется в целом тупо давать WA (ладно бы еще PE) за то, что число выведено абсолютно точно (0.0), но не " с точностью не менее 9 и не более 100 знаков после десятичной точки."

3) В целом вроде как на нормальных контестах всегда можно вещественные числа выводить как угодно, и проверяется отклонение от правильного ответа того, что выведено.

Жду комментариев "сам себе злобный буратино" :)

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

    Создатель сайта не сторонник РЕ. пункт 3

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

      Я в курсе, это был как раз камень в его огород :)

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

    Все чудесатее и чудесатее: оказывается, целые числа можно было выводить, а вещественные но с 1 знаком после точки нет? Хотелось бы официальных разъяснений на эту тему :)

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

      Кстати, из математического формализма следует, что чекер работает идеально правильно. Если десятичной точки нет, то утверждение "не менее 9 и не более 100 знаков после десятичной точки" выполняется, так как содержит неверную предпосылку "десятичная точка есть".

      Действительно, [все] вещественные корни уравнения x^2+1=0 участвовали в этом контесте.

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

    А больше 100 знаков после десятичной точки правда нельзя? :)

    Долго пытался сейчас понять, как вообще интерпритировать слова "точность не менее 9 знаков". Пока самое разумное — с верными первыми 9 знаками. Жалко, что это означает не абсолютную погрешность 10^{-9}, а нечто необъяснимое — ответ (1-eps) неверен при правильном ответе 1.

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

На чем ломали В (Div 2)?

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

how can This Submission Pass the preetest but got compile error while Systest ?

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

The discription of the problem is quite clear.

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

Мое решение (1959817) получило "Ошибка компиляции" на тестах, однако сразу же после тестирования, на дорешивании оно же (1960480) прошло все тесты.. просьба разобраться.

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

Great contest, thanks to all of you.

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

It seems java needs more space than C++. In div1-C I initialize a 3-D array and get MLE.

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

    I did not look at your code but it may be the case of how you declared the array.

    Arrays are objects in Java, so a[1000][1000][2] creates one million objects and a[2][1000][1000] creates only 2000. There is an overhead for each object.

    If space is an issue, use a 1D array instead.

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

Печалька((( у компилятора на сайте vector :: erase не работает((( Из-за него ВА получал на 2 тесте. Не подозревал что такая ошибка будет

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

    Эм, может пример покажете? Ссылки на отправки, все такое.

    Возможно очередная бага g++.

    Простейшие примеры в запуске работают

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

    Советую создать минимальный пример, который демонстрировал бы неправильное поведение vector<>::erase. С очень высокой вероятностью окажется, что баг не в erase, а в самой программе.

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

      1956309 вот номер посылки. На компе моем (mingw) выводит как в сэмпле. (3 четверки посередине), а здесь — 4. (через запуск тоже самое((()

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

        Переменная sum не инициализирована. Чтобы получить предупреждение об этом, надо компилировать хотя бы с параметрами -Wall -O2.

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

In the contest, I got many wrong answer on pretest 1 of problem D,.. After the contest, I found out the mistake, only one mistake: 10.0 => 1.0. And I got AC after fixing it... So sad!! :(

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

For div2 B, can someone confirm test 13 is the same with test 14, i.e. the input is ten thousand 0s? My solution passed 13 but failed on 14, quite weird.

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

very nice problem set!

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

The problemsets are nice, thank you, Sereja.

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

Problem B was very confusing.. as in the problem statement, it was written: Each digit is allowed to occur in the number the same number of times it occurs in the set.

Then how the ans for second test case is: 5554443330 since in input set 4 is occurring 4 times but in output integer it is occurring 3 times only.

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

    It is permitted to use not all digits from the set

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

    They said: " It is permitted to use not all digits from the set"

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

      I took it as.. if i am not taking any digit then i am not supposed to use that digit in the output at all. Means that digit's count would be made 0. I tried other way also, but because of a very silly mistake my solution got hacked.

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

    May be you missed this -> '**It is permitted to use not all digits from the set**'

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

I Think It Would be better to increase Contest Time for some contests like this To let People have more Fun !

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

The comment is hidden because of too negative feedback, click here to view it

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

    It's interesting to see how many downvotes that comment will get, because it'll mean that some people actually care about comments that downvoted a lot.

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

    One of the advantages of being Petr is that you can make such troll-jokes without throwing your reputation towards S = {x : x < 0} where x belongs to R.

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

    When I try to click "here" the page scrolls to the top and the comment doesn't show up.

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

Does the intended solution for div1 E use hashes? I saw only hash solutions and wonder if they can be hacked using ideas from recent anti-hash articles.

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

    I think that this is the reason why people submited this problem in last minutes of the competition — not to be hacked...

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

    I'm quite sure it can be solved with something similar to KMP.

    Assume we can, after preprocessing, quickly compute functions prev(k, i) and next(k, i) for a permutation P, which give the first element j in [i, k — 1] preceding / succeeding k in P.

    Let suf[k] be the minimum j > 1 such that the part of A composed of elements [j, k] is (EDIT) the same permutation as the part of A composed of elements [1, k — j + 1]. We can compute suf[] using a linear number of calls to prev() and next() on A.

    Later we can use suf[] like a KMP table to compute all shifts that match with a linear number of calls to prev() and next() on A and B. :)

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

How can I know number of 1's in testcase number 12 in div2 problem B ?

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

    There is no way to do this.

    But... You can count them, and guess counter by binary search. (For example, if cnt < 4000 then cause TLE, otherwise get WA)

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

      I found a better way compared to this. print out number of 1's for this particular case . number of 1's are 49898 . :D

      anyway thanks for your help.

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

Когда рейтинг обновят?

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

One Does Not Simply
Update the rating quickly

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

i am new on codeforces.com and how add friend???

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

tourist lost his Codeforces Red Target :(

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

When will the editorials be available for this contest's problemset? Thanks in advance

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

Задачи клевые автору спасибо

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

Кому не трудно не могли бы сказать как в Задаче Е (див. 2) в этом тесте получилось 508?

5
4 32 1 18 41
47 38 7 43 43
48 23 39 40 23
26 39 33 5 36
31 29 7 26 47
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    первый идет по пути 4-47-47-26-39-33-7-26-47 второй по пути 47-36-23-40-39-23-38-32-4

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

Wrong answer on test 65 on problem B, div 2. Don't you know what it is?

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

Да, как показала практика, у меня проходило и без ресабмита

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

when the Problem's Analysis will be placed ?

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

Пинг. Sereja/Gerald/MikeMirzayanov: не объясните официальную позицию по поводу цифр после запятой в задаче D (см. мои комментарии выше в этом треде)? Она существенно повлияла на мой контест.

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

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

    Рекомендую писать в личку или на почту MikeMirzayanov (если вы знаете его e-mail ;) ).

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

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

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

        Насколько я помню, из последних контестов проблемы были примерно в половине. О сделанных выводах — вопрос.

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

    Добрый день.

    • Как было замечено ранее, формально, чекер был правильный;
    • Первый семпл (попытки по которому не считаются в итоговых баллах) не проходится неправильными пониманиями.

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

    Что касается менее формальных рассуждений, конечно же, впредь такие моменты в условиях будут выделяться болдом, да и вообще, при возможности избегаться (почему в этой задаче от такого вывода нельзя уйти, я объяснил ниже). Понятно, что такой вывод не является стандартным.

    По поводу того, зачем так было сделано. Задача достаточно специфичная, чекер в ней не стандартный, а в условии, в 2х строчках не объяснишь как конкретно он работает (сохраняя при этом всю формальность). Здесь очень сложно отличить точные решения от неточных, чтобы формально все было честно.

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

      Привет,

      со мной можно на "ты", я еще не старый! :)

      Спасибо за объяснения. К сожалению, не совсем их понял.

      Почему пропускание целых чисел формально правильно? Они же с 0 знаками после точки?

      Про чекер: фраза "Обратите внимание, что правильность ответа проверяется не абсолютно точно. Постарайтесь получить как можно более точное решение. Все вычисления в проверяющей программе выполняются в предположении, что абсолютная погрешность ответа участника не более 10 - 8." как раз по-моему отлично объясняет (в той мере, в какой это можно объяснить в 2 строчках), как работает чекер. А как этому помогает запрет выводить мало цифр после запятой?

      И еще — можно ли было выводить числа в экспоненциальной форме?

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

        Я предлагаю не обсуждать это здесь. А поговорить лично, например в GTalk. Насколько я понимаю, проблемы с точностью коснулись только тебя.

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

          My first submit was on 1:42, and last one (change cout for printf and replace "0 0" with "0.000000000000000 0.0000000000000000") on 1:59. So it's not only Petr.

          P.S. Sorry for english, but my written russian is horrible.

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

          Судя по количеству плюсиков, вопрос "почему 0.0 нельзя писать, а 0 можно" много кому интересен. Мне, например. (Мне как раз случайно повезло написать "0", но в чем разница все равно хотелось бы знать.)

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

      Извиняюсь, какой-то я очень негативный сегодня.

      Спасибо огромное, что указали мне на ошибку! И вообще спасибо за контест, в остальном все было круто.

      Я правда хочу понять, чем это ограничение помогало чекеру :) Может быть, имелось в виду, что число "0.0" означает "0.0+-0.05", как иногда учат в школе про вычисления с приближенными числами?

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

Although I liked the problems, I think problem C was a bit of a fiasco. On one hand the exact same problem has been given before in TopCoder, SPOJ, one Bulgarian competition (okay, no way to know that) and God knows where else. Thus many people had the chance to solve it in several minutes (I for one needed 9 minutes, and other people even less). Anyway, this happens (I know from bitter experience).

I also was happy to see the negative numbers (which means negative results are possible). This is another TopCoder trick I've felt for before — if you use memoization and you initialize your array with -1 (which is valid number in this case) you have a correct, but possibly too slow solution. For those of you who don't know it — if the answer to the problem is -1, then some of the states will be calculated over and over again and it can turn really slow. So I was looking for such solutions in my room, however most were using standard iterative dp (which is okay with that) and didn't have the chance to challenge anyone.

However, such a test was not present in the system tests, so some (possibly plenty) of wrong solutions passed.

The test is rather simple to create:

int n = 300;
fprintf(stdout, "%d\n", n);
for (int i = 0; i < n; i++)
    for (int c = 0; c < n; c++)
        fprintf(stdout, "%d%c", ((i + c == 580) ? -1 : 0), c + 1 == n ? '\n' : ' ');
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    But, is there a way to use a smaller state (not 598x300x300) so that you don't get memory limit exceeded? Because if that can't be done then I guess that could justify the absence of such cases

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

      Yes, sure. See my solution, it uses twice smaller state (if I initialize my dyn[][][] array with -INF instead of using additional array).

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

When I click the tutorial link, I can see a tutorial, but not in English. Why? The English tutorial has been released, I think.

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

Hello! I don't know where to post my problem so i'll post it here. I apologize if posting this here is wrong.

Well i have tried the problem Numbers(D div2, B div1) and i finally solved it. The source code is here http://codeforces.me/contest/214/submission/1974583

I get WA on test 10 (100 0 0 0 0 0 0 0 0 0 0). The strange thing is that when i run the code it prints the right answer on my computer. Here when i submit it, the answer on the same test is different and i don't get it why it does that.

Please help me to see what is wrong :(

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

    In your code, len can be 0, so in Comb[len - 1][j] index goes -1 and so you get weird numbers from uninitialized memory, instead of expected 0 value.