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

Автор nevidomy, 14 лет назад, По-русски
Добрый вечер!

Поздравляю всех с днём студента, спокойных вам сессий, легких экзаменов и множества новых знаний!!! Еще хочу поздравить всех Татьян с Днём Ангела!

Приглашаю всех поучаствовать в Codeforces Beta Round 53. Сегодняшний раунд готовили Михаил Мирзаянов, Невидомый Виталий, Артем Рахов и Мария Белова, автор задач nevidomy.



Контест окончен.

Поздравляем победителя tourist, который после раунда стал первым участником завоевавшим звания "Генерал"!!! Ссылка на результаты: http://mirror.codeforces.com/contest/57/standings

Разбор задач

Невидомый Виталий и команда Codeforces

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

14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Спасибо! Для меня это первый раз поэтому очень интересно! 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Слушай, ну ты вообще столько значения придаешь первому контесту на CodeForces :) Это обычные контесты, с немного нестандартными правилами. Если не смотреть на рейтинг, а вместо этого широко открытыми глазами смотреть на дорешку, то вполне себе хорошая тренировка.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Люблю просто быть в курсе всех нюансов, что бы потом не задавать лишних вопросов... 

      Может быть я такой человек что хочу все узнать и сразу. 
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится
    Тут правила, если Вы с ними еще не знакомы.
    Удачи на первом контесте.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks for the early English post!
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Сижу дома, весь закутанный в шарфы, свитера и одеяла. Кашляю с гигантским хрипом. И какое счастье, что в такой момент у меня есть компьютер, компилятор и мой любимый кодфорс. Что же еще остается делать больному человеку, так любящему программировать?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Имена героев задач напоминают имена из Гриффинов. Это случайность или все таки это они?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I'm trying to hack, but when I click on an run ID, no window pops up... is there some other way to see others' code?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I even tried going manually to the URL http://mirror.codeforces.com/contest/57/challenge/<RUN ID>, and no code shows up or anything. I've definitely locked the problems I'm trying to hack...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is there a way to go out of the competion? I tried to solve one problem, but then my ant came and now I only have 20 minutes left, I think my rating will fall down like an exponential function :(.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да уж, турист наломал...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вообще маньяк-сдать три задачи за 11 минут
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Код по С внушает страх перед Геной
    • 14 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -18 Проголосовать: не нравится

      Что-то один вдруг сказал "маньяк", второй повторил. С чего вдруг? Так и приклеиться может.
      Подразумевается "Маньяк — человек, не знающий чувства меры в своей деятельности"  или "Маньяк — излишне увлекающийся человек; обычно термин применяется к серийным убийцам и насильникам." ?
      Это две первые ссылки из Google/

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Прошу прощения у вас и у вашего сына, если обидел:) Просто мне действительно внушает уважение и это находится за пределами моего понимания(надеюсь, что пока) как можно так решать задачи и читать чужой код.
        Я применил второе значение слова маньяк, именно как серийный убийца. Серийный убийца надежд других программистов.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну почему же :)
          Я прекрасно себе живу, мы в разных странах, интересы у нас могут пересечься только на ВКОШП и IOI, но первое для меня не очень-очень важно, а до второго еще много времени :)
          Плюс есть еще LEGO-робототехника, которой Гена (вроде?) не занимается. По крайней мере команд от Беларуси на WRO я не видел.
14 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится
Really nice problemset:) Thank you. It is great to see here other fans of Family guy:P
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Какие-то жёсткие баги идут... Во время систестов моя попытка по третьей задаче отмечена -1 жирным, словно я её не сдал точно, и при наведении на неё выскакивает подсказка, что финальное тестирование не пройдено. Когда нажимаю два раза написано
В очереди [финальные тесты]
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Просто из таблицы исключены последние удачные сабмиты (те, которые еще не потестили). А до того был 1 неудачный - он и показывается. С другой стороны задача заблокирована - потому жирным
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это я понимаю, но при наведении написано 
      Финальное тестирование не пройдено, MS C++
      что очень пугает. (кстати в итоге она зачтена)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну так оно не было пройдено.
        Хотя заменить надписи, вероятно, можно
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да.. кажется я понял - имеется ввиду, что на данный момент не пройдено, а не как я понял - попытки не верны. Но всё-таки надпись пугает :)
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Очень порадовала задача D.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    интересно, что же в тесте 7...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мое решение валит вот такой тест

      5 3
      ...
      .X.
      ...
      ..X
      ...

      Ответ: 2.745562130177515
      Выдавало: 2.721893491124260

      WA7.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
+230, я рад.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Гуд, пожелтел)

Понравился проблемсет
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за 7-ой тест в D ? У многих решение упало на нем, причем ответ отличается от правильного не сильно
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Скорее всего там первый раз встречается случай когда две частицы удлиняют какой-то путь.
    Типа
    AXAAA
    AAAXA
    из левого верхнего в правый нижний путь 7 а не 5 как обычно.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
It seems the test case 7 in problem D is not valid:  (By mistake, the "..." in the last means ellipsis,but the same as "." in data)
Test: #7, time: 10 ms., memory: 48516 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
Input
47 24
........................
........................
........................
........................
........................
........................
X.......................
........................
....X...................
..........X......
Output
23.6657545509435892
Answer
23.670250896057
Checker Log
wrong answer 1st numbers differ - expected: '23.6702509', found: '23.6657546', error = '0.0001900'
14 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
Основное tourist
В профиле. Может в этом большой смысл...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    General tourist :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кхм, для званий использовали машинный перевод (:
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      не машинный, наверняка там есть разные контексты. Из двух одинаковых по названию языковых константы, сайт подхватил не ту.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Задумался над этим комментом. Я имел ввиду машинный перевод, а не машинный (автомобильный) контекст. Я правильно понял мысль?
        Просто удивило, что локаль не переправили руками.
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Может быть, тут используется что-то вроде этого. Тогда можно напороться на "general" и перевести не так, как надо, ведь контекст невиден. Сам попадал впросак, например, было "register", и в одном месте у меня появилось "пожалуйста, зарегистрироваться, чтобы ..." (register использовался в разных контекстах).
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, я уже прочитал сообщение админа внизу. Просто сначала подумал о переводе ресурсной строки "General %username%" как "Основное %username%", что навело на мысль о машинном переводе ресурсов.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Нет, не правильно, я имел ввиду именно то что потом объяснил Mike :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Блин, даже это переводится гуглопереводчиком...

    ...что уж говорить про условия тогда.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Неправда, просто у этого слова есть двойное значение. Я был неправ, когда в бэкенде использовал General без контекста.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Извини тогда — не знал, что оно так устроено.

        Кстати, английские условия стали лучше. Сегодня английские условия не менее понятны, чем русские, а непонятна и там и там разве что задача B с первого раза.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится
    Основное Геннадий одержал.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И Гена мощным рывком выходит на первое место по потраченным усилиям на отлов багов в Codeforces :)
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
It is the first time that my score is not changed after a contest.....冏
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is there a way to see what hacked my code?
MY problem C was hacked, but the same code passed the system test after the competition.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The admin didn't add the hack data to the system test?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Now I know the hack data.
      But my bad code passes the system test.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        But how to get the hack data?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Sorry.
          I didn't get the hack data which was actually used to hack my code.
          I found only what kind of test case hacked my code by viewing my code with cmd's advice.
          I don't know how to get the hack data.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    try 59052
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    It is impossible to consider all probable bugs. We are working on automatic adding of all the hacks in the final tests. It will be introduced soon.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      That's good news!
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      I know that CodeForces has already hosted many contests in this format but
      I would like to give a suggestion to change a little bit the hacking system.

      I think it's pretty unfair that someone gets the lucky of having his solution hacked and get a chance to resubmit while others don't. Taking it to the extrem it can even be seen as working in teams.

      But, I also thing that it's nice this hacking phase during the programming phase and also the locking feature is important to allow resubmissions if someone noticed a mistake in his own solution before seeing others.

      So, my suggestion is to don't tell the contestant that his solution has been hacked until he locks it.  He can still resubmit but he needs to recheck the code and find his mistake without other people helping him. 
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        I give you my opinion.

        Today's hack system looks for me as in real life: if someone noticed bug, he will say about it to the author. Or he will wait till the bughaver released his software with this bug, and only after that he says "I saw a bug in your program but didn't tell :p!"? Looks strange if this is a situation in one company, community, like CodeForces are. :-) Yes, you're right, it's a teamwork. :-)

14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Спасибо Виталию за контест. Задачи были интересные, но, на мой взгляд, сложнее чем обычно.
По каждой задаче вкратце:
Задача А: Ну не умею я такое решать и писать быстро. Задача простая, формулируется просто, а все учесть тоже надо уметь. Еле накорябал и зашла на Божей помощи. 
Задача B: Господи, откуда в такой простой задаче столько много буков?! Задача легче (для меня уж точно), чем задача A, но пока я на три раза не прочитал, так и не понял ее. Слава Богу, решение в лоб зашло.
Задача C: Вот, типичная задача C. Не так-то просто решить, но решаемо. Написал динамику, узнал, биномиальные коэффициенты, нашел закономерность и AC, получи и распишись.
Задача D: Супер задача. Без понятия, как ее решать. Жду разбора. Единственное, что могу сказать про нее: написал вероятностное решение, которое по выборке пыталось угадать ответ, и Сергей Фёдоров (да простит он меня) сделал на нем неудачный взлом. Ну на систесте оно еще и TL16 умудрилось поймать.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А-забил на случаи и написал ширину. Вероятно ограничения надо было больше делать? Или А-оно А и есть?)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Да тут как бы такая задача, которая меня ставит в тупик. Ширину ради такого и писать стыдно, а частные случаи думать лениво. Зашла и главное :) Задачу не в чем упрекнуть, тут надо упрекать себя в этой патологии.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Я решил А так: выравниваю квадрат в отрезок, считаю расстояние между точками v и беру минимум от v и 4n-v. Быстро можно написать:

    int n;

    int f (int x, int y) {
        if(x == 0) return y;
        if(y == n) return n + x;
        if(x == n) return 3 * n - y;
        else return 4 * n - x;
    }

    int main ( ) {
        int x1, y1, x2, y2; cin >> n >> x1 >> y1 >> x2 >> y2;
        int v = abs(f(x1, y1) - f(x2, y2));
        cout << min(4 * n - v, v) << endl;
    }
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    A. Как такое за 3 минуты сдавать?! Минут 15 пытался придумать аналитическое решение, потом забил и написал поиск в ширину.
    B. Задача очень плохая. Минут 15 вкуривал в условие. Пожалуйста, пишите условия понятнее. Что за лестницы, что за камни? Что за дорога к Солнцу? После первого прочтения вообще подумал, что там кубики надо друг на друга ставить.
    C. Эта задача хорошая. Правда, я так и не нашел закономерности, обидно.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      C из (2н-1) по н неубывающих. Столько же невозрастающих. минус те, что и там и там (н)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В А можно было писать что угодно, например Флойда.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        <ironic>Лучше Дейкстру да за O(n*log(n))!</ironic>
        За куб уж слишком трудоёмко. :3
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    А, в принципе, простая. Два случая:
    1) Если точки на противоположных сторонах квадрата, то нужно n + минимум из двух возможных направлений движения для встречи.
    2) Если точки на смежных сторонах,  то просто сумма модулей разности соотв. координат.

    P.S. А упала из-за дурацкой опечатки в первом if: "y1 == 0 && y1 == n". Обидно.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Эммм... Михаил Расихович, кто другой из админов.... Посмотрите на профиль Гены. Основное? Может быть все-таки генерал?
  • 14 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится
    Да, RiaD-WaW, хотел то же самое написать. И вообще это надо было... в личку что ли? Или на почту. Явно не сюда.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      Почему в личку, забавно же -)
      Сначало у Гены график не умещался, теперь это. В общем, тестируем Codeforces на крайние случаи...

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да просто уже было вами написано сообщение выше про Основное, зачем ещё то одно. :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я полагаю через три-четыре контеста Гене опять не хватит доступной шкалы :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      У меня почему-то показывается, что этот пост будет написан 19.02.2011 18:25:02.

      При этом он всё время выделен, как новый.

      Это баг или фича?

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Таж фигня... а я понять не мог, почему он постоянно отмечен как новый :)
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Very nice problem D...
Kudos to the author.
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
После этого контеста RAD стал чёрным :) ... давно пора
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ymondelo20:

01:32:38  Неудачная попытка взлома участника shioshiota
01:32:38 (+0сек)  Неудачная попытка взлома участника Heruman
01:32:41 (+3сек)  Неудачная попытка взлома участника sajjad_gh
01:32:43 (+2сек)  Неудачная попытка взлома участника Ragvena
01:32:45 (+2сек)  Неудачная попытка взлома участника ashi009
01:32:48 (+3сек)  Неудачная попытка взлома участника magdi

Интересно, это ботом один тест всем кидался или просто с нескольких вкладок?
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Измените домен ссылки на результаты с .com на .ru
14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Can someone explain me how can i solve the C problem because i have no ideea better than O(N^2)? Thx
Edit: look here for solution: http://www.codeforces.com/blog/entry/1169
14 лет назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится
По задаче С. На будущее авторам (не конкретно этого контеста, а в общем): если вы делаете задачу, где инпут состоит из одного или двух чисел и ответ -- одно число, имейте в виду, что числа из оутпута, образующие последовательность, могут легко гуглиться.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    На онсайте не погуглишь, так что норм.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Онсайтов по сравнению с онлайн контестами достаточно мало и такие задачи ставят участников (онлайн контестов), если не в неравные, то уж в неприятные условия точно.
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится
        По двум числам сложно чтото заметить, а вообще одно из решений предполагаемых автором - писать брутфорс и искать закономерность. Это задача С. Смысл в том что математика позволяет решать её быстрей, кто не хотел или не умел подумать - пусть пишет брутфорс, дело только в потере времени
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Я подразумевал, под кол-вом чисел в инпуте не кол-во семплов, а параметры. В данной задаче только один -- n. Брутфорс пишется не больше чем за 3 минуты и первые 4 числа к примеру вбиваются в известный многим сайт.

          Например http://oeis.org/search?q=4%2C17%2C66%2C247&language=english&go=Search

          Найти закономерность самому гораздо затратнее.

          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Но заметь, для этой последовательности не написано решения...
            • 14 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится
              А надпись "binomial(2n,n)-n" ни о чём не говорит? :)
              • 14 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

                Ну во-первых это не верно... binomial(2n-1,n)-n

                Во-вторых всё-равно понадобится какой-нибудь не лобовой алгоритм для подсчёта binomial(2n-1,n).


                UPD. Ой, я не прав. 2*binomial(2n-1,n)-n=binomial(2n,n)-n   :) сори

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

                  Почему не лобовой?

                  Разве посчитать в цикле факториалы и поделить одно число на другое по простому модулю - это не лобовое вычисление?

                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Нуууу.. я писал расширенный алгоритм Евклида... может я и протупил... а как сделать проще?
                    • 14 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится

                      Если ты про деление, то можно ещё воспользоваться тем, что ap - 1 ≡ 1 по простому модулю p.

                      То есть .

                      Хотя, тут надо быстро в степень возводить. Так что что-нибудь писать всё равно придётся.

                    • 14 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      Можно было посчитать показатели степеней простых входящих в C-шку , для факториалов они легко считаются.
          • 14 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Проблема определить, что является common knowledge а что нет.
            Например, биномиальные коэфициенты являются common knowledge? Надо ли не давать задачу, требующую биномиальные коэфициенты (их, я думаю, сложно вывести, если не знать)
            Я например в свое время одновременно узнал как посчитать количество выборок K элементов из N и количество неубывающих последовательностей на комбинаторике, и для меня это одинаково common knowledge. Мне даже в голову до этого топика не приходило, что C(n+k-1,n) можно не знать :о

            Если посмотреть на эту задачу с другой стороны - пусть последовательность не нагугливается. Тогда те, кто знают формулу, сдадут за три минуты, а те, кто не знают - за минут 30. Казалось бы, лучше пусть можно будет нагуглить.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Врятли ее много кто знает, но она легко придумывается.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Так что, теперь такие задачи на онлайн-контестах вообще не давать? Я просто не понимаю в чём была исходная претензия.

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

    :-D Что-то я не додумался на контесте посмотреть...

    По 4-ём введённым числам оказалась второй в списке, а по трём уже далекооо не на первой странице (oeis).

    А вообще вот она http://oeis.org/A045992. Причём даже с таким же условием...

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не знал куда написать, пишу сюда. В правилах не нашел ответа на вопрос: можно ли взламывать свои решения?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    :-D забавно..
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    А, кстати, это же выгодно! За пересабмит теряешь 50 баллов, а за взлом набираешь 100 :)
    Но мне кажется, что такой возможности нету.
    Наверное, никто и не пробовал.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это разумно, в общем-то:) если ты знаешь что на каких-то тестах твой алгоритм не работает но не можешь придумать решения-получи 50 баллов. Это лучше чем послать решения и не знать всех случаев.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        ничего разумного нет:)

        int main()
        {
        if (n == 10)
        {
        cout<< "BlaBlaBla";
        }
        //решение
        }
        взламываем при n = 10 и получаем на халяву 50 баллов
        • 14 лет назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится
          А смысл? Вот такого? Если ты посылаешь задачу и потом сам себе ее ломаешь-значит знаешь когда она работать не будет, знаешь тест. Зачем еще и blablabla? Сразу бери тест и ломай:) Понимаю что ты скажешь-тест мол может быть большим(хотя генератор написать-архисложно:)). 
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А потом можно и по шапке получить от "штаба" за читерство *joke* %)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну тут нет чита. Я просто спросил вот почему. В этом раунде, я сделал неудачный взлом, и в логе увидел, что правильный ответ, не совпадает с моим. Ну понятно стало, что закралась лажа. Начал вычитывать код, нашел баг. И вот если бы была возможность взламывать себя, то я хотя бы получил 100 очков как утешительный приз, вместо 0 (позже меня взломали).
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Посмотрим на ситуацию по-другому. Ты знаешь, что твое решение - неправильное. Претесты зачастую проходит все, что только можно. Как результат, ты посылаешь на задачу E решение в лоб, которое проходит все претесты и тут же, заблокировав его, получаешь за его взлом 100 баллов. 100 баллов - не так много, но лучше, чем ничего.
          Как результат 100 баллов на ровном месте, которые тебя могут неплохо подкинуть вверх в общей таблице.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ломать свои решения нельзя, я проверял. :o)
14 лет назад, # |
Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится
Спасибо за контест.
Задача А:
У меня решение аналитическое, отличное от того, что в разборе. Просто рассмотрим несколько случаев. Сначала проверим, если точки совпадают вывести 0. Если точки лежат на одном ребре, вывести модуль разности различных координат. Если точки принадлежат параллельным сторонам, то выбрать минимум из двух результатов: 
    int res1 = xx1 + xx2 + yy1 + yy2;
    int res2 = abs(n - xx1) + abs(n - xx2) + abs(n - yy1) + abs(n - yy2);
Если смежным сторонам, то res = abs(xx1 - xx2) + abs(yy1 - yy2);
Задача В:
Для понимания условия мне понадобилось - больше десяти минут. Долго не могла разобраться, какие данные что обозначают. Позже поняла, что задача легкая, для меня она была проще первой, т.к. я не сильна в геометрии. Мое решение один в один, решение в разборе за O(K*M).
Задача С:
Очень красивая задача. Очень жаль, что не решила её. Принципиально не читаю разбор. Завтра попробую еще раз. Очень хочу придумать решение сама.
Мне очень понравился контест. Правда после первой задачи я очень испугалась, что потеряю синий цвет. Вторая задача, пугала меня заковыристым условием, а потом неописуемой простотой. Мне даже казалось, что я ошиблась в решении. Обошлось. Задача С. Она просто потрясающая. Дважды находила закономерность и оба раза находила тест, который это повалит. Утром в спокойной обстановке решу. В общем, спасибо авторам, за упражнения для ума.
P.S.Забавно, но как раз перед контестом, я смотрела Гриффинов. )
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I want to ask...why is c++ compiler giving garbage value....when I use memset()...or malloc() ??
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It was working correctly in my system!!
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      memset is fill bites, not sell of bites. 

      int a[10]; memset(a,1,sizeof(a)); 

      give a[0]=...=a[9] = 00000001 00000001 00000001 00000001 = 16843009

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

        see


        #include <iostream>
        #include <cstdlib>
        #include <string.h>

        using namespace std;

        int main()
        {
           
        long long int n=0,m=0,k=0,soln=0;

           
        long long int *v;
           

            cin
        >> n >> m >> k;

            v
        = (long long int*)malloc(sizeof(long long int)*n);
           
        memset
        (v,0,sizeof(v));

           
        for(int i =0 ; i < m;i++){
               
        long long int a=0,b=0,c=0;
                cin
        >> a >> b >> c;
               
                v
        [a-1]+=c;
               
        long long int f=0;
               
        for(int j=a;j<b;j++){
                    f
        ++;
                    v
        [j]=v[j]+c+f;

               
        }  

        //      for(int i=0;i<n;i++){
        //          cout << v[i] << endl;
        //      }
        //      cout << endl << endl;
           
        }

        //  for(int i=0;i<n;i++){
        //      cout << v[i] << endl;
        //  }
           
        for(int i=1;i<=k;i++){
               
        long long int t;
                cin
        >> t;
                soln
        = soln+v[t-1];
           
        }

            cout
        << soln << endl;
        }





        whereas...similar code...this one....

        #include <iostream>
        #include <cstdlib>
        #include <string.h>
        #include <vector>

        using namespace std;

        int main()
        {
           
        long long int n=0,m=0,k=0,soln=0;



            cin
        >> n >> m >> k;

            vector
        <long long int> v;

           
        for(int i=0;i<n;i++){
                v
        .push_back(0);
           
        }

           

           
        for(int i =0 ; i < m;i++){
               
        long long int a=0,b=0,c=0;
                cin
        >> a >> b >> c;
               
                v
        [a-1]+=c;
               
        long long int f=0;
               
        for(int j=a;j<b;j++){
                    f
        ++;
                    v
        [j]=v[j]+c+f;

               
        }  

           
        }
           
        for(int i=1;i<=k;i++){
               
        long long int t;
                cin
        >> t;
                soln
        = soln+v[t-1];
           
        }

            cout
        << soln << endl;
        }


        ...this got accepted....


        I concluded that memset was giving garbage..I dont knw why..!!....
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          long long int *v; 
          sizeof(v) is equal to size of pointer to long long int
          you need write memset(v,0,sizeof(v[0]) * n); 
          instead of
          memset(v,0,sizeof(v)); 
14 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
The problem statement for B is maybe a little bit hard to understand. It took several minutes for me to completely catch what the problem asked. I think it should've been worded better.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Problem B statement not just little bit hard,it was too hard to understand.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Right. The English version was really troublesome and confusing. I don't know about the russian version but if it was not that the problem was make difficult to understand, then the problem-setters should be more careful.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      The Russian version seemed hard to understand to me as well. I probably spent more time reading the statement rather than coding the solution.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Don't worry, the russian version was complicated too =) I read it three times before understood something...