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

Автор meret, 14 лет назад, перевод, По-русски

Разрешите от всей души поприветствовать вас на Codeforces Beta Round #11. Я основной автор этого контеста. Надеюсь, что вам понравятся подготовленные задачи :-)

Спасибо Mike Mirzayanov'у за то, что возможность проведения контеста и Ania Piekarska за тестирование задач.


Удачи, Jakub Pachocki

Это перевод оригинального поста, поэтому английский в комментариях приветствуется [примечание переводчика].


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

14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Thanks in advance to Jakub for the prepared problems and thanks Julia for translating of everything that it was possible to translate. =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    ))) That was not me, who translated the problems this time. They were originally in English, and Mike translated them into Russian ;-) I have nothing to do with the coming contest. But thank you anyway for being so kind )))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну вот, кто минусует за просто так, признавайтесь.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Thanks for arranging this event.
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
http://codeforces.com/contestRegistrants/11
lovexx почему-то зарегистрирован дважды
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Fixed. Видимо какой-то race-condition. Пофикшу, это просто.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вообще у меня во время контеста фатально сайт поплыл... справа, в окошке под названием FAndES с моей фоткой, ссылка Блог была написана аж 4 раза... в окошке прямой эфир тоже все темы по 4 раза, при этом их вместе с копиями всего 15, т.е. как и должно быть... только должно быть без копий. Тестил в хроме и ие.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        везде "блог" написан 4 раза, даже наверху, где "главная"

        в прямом эфире тоже всё по 4 раза :)

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да, проблема есть. Она не только у вас.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Кстати.. ещё давно заметил что в таблице рейтинга нет чёткости красный-жёлтый-синий-зелёный... То есть среди синих могут быть и зелёные, а среди жёлтых могут быть синие. Почему так?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И чужой код после контеста просматривать не могу. Про упразднение этой фичи, вроде, слышно не было
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    а, кстати, стоило бы запретить копипастить код другого участника

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

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

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

      А вот мне иногда хотелось бы прогнать чье-то решение на моих тестах.

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну это проблемы самого читера, а для начинающих чужой код полезен
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        а как же процесс "подумать"? он более чем полезен для начинающих

        а чужой код не обязательно копипастить; для того, чтобы чему-то научиться, достаточно read only

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks for the round!

I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за тест №4 в задаче В ?

Большинство на нем падали :(
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    n=10^9, правильный ответ 44723 вместо 44722
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Надо по-другому решить задачу. Я тоже на нем упал по-началу. Потом применил формулу суммы арифметической прогрессии и сравнивал с abs(x).

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    х=abs(x)
    Я находил первое число ans, которее сумму s от 1 до ans даст большую либо равную чем х. Потом заметим, что если мы изменим знак любого числа чисел в этом ряду, мы уменьшим нашу сумму s на чётное число (например вместо 1 станет -1, это значит что s уменьшится на 1 и ещё на 1, т.е. на чётное число). Значит если (s-x) - нечётное, мы никак не получим х изменением знаков элементов в ряду. Значит нужно увеличить ans. Так до тех пор, пока (s-x) - нечётное. Т.е. код такой:
    	ans=0;
            s
    =0;
           
    while (x>s){
                    ans
    ++;
                    s
    +=ans;
           
    }
           
    while ((s-x)%2==1){
                    ans
    ++;
                    s
    +=ans;
           
    }
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Сори за лишние enter`ы
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня подобный код не проходил до тех пор, пока не добавил условие, что (s-x)/2 не должно превышать sum. 
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Читать как "не должно превышать s"
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А как может быть при x - положительном (s-x)/2>s ?
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Н-да, затупил я по-черному. Ошибка, очевидно, была не в этом. Сейчас поищу в чем.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача 4 решается динамикой по профилю?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    дп по маскам. очень похоже на поиск количества гамильтоновых путей.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ну вобщем у меня да. решение динамикой по маске. за O(2^N * N^2)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня динамика D[mask][last_v], где mask - маска посещённых вершин, last_v - последняя вершина, а D[mask][last_v] - число путей из клетки minimum_bit(mask) в last_v. Переходы - добавляем одну вершину в конец пути (любую v, но всегда v > minimum_bit(mask)).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ouch! Not being able to read bold text correctly for 40 minutes is something I experienced for the first time.
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Problem E is very nice :) I've got it accepted 3 minutes too late. The final solution is really short and cute, but it took a long time to get to.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    About other problems: I believe problems B and D were too well-known :(
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I invented B, D and E by myself (the other tasks were Mike's), so I'm surprised to hear B was well-known. As for D, it does look a bit classic, but I've never personally seen it in any contest, and I figured it requires a nice enough idea to deserve a place in the contest :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        With the idea being?

        I'm trying to find previous occurrences of B.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Finding all cycles containing a vertex v in O(2^n * n^2), then removing v from the graph and repeating, so that the total number of operations is about is 2^n * n^2 + 2^(n - 1) * n^2 +... = O(2^n * n^2), instead of O(2^n * n^3) achieved by a simple DP approach.
          • 14 лет назад, # ^ |
              Проголосовать: нравится +2 Проголосовать: не нравится
            Oh yeah, that's a good point indeed. I take my words about D back :)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            can you give some insight for how to solve E?  Thanks.
            • 8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              There seems to be no editorial for this round or description of how to do this problem, so I will post my solution here.

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

              does petr reply only to red coders ?

      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Perhaps many people found A140358.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Hmm. Conjecture? Interesting... That's why I didn't cope to prove the idea during the contest :)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Yes ;-)
        • 14 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится
          I'm surprised it's just a conjencture on OEIS. The proof goes as follows:

          Let n be a positive integer. Consider any k such that 1 + 2 + ... + k >= n. Then n is reachable in k jumps if there is a subset A of {1, 2, ..., k}, such that when we make all jumps from A go left and all jumps not from A go right, we reach n. This is equivalent to k(k + 1)/2 - 2 * (sum of numbers in A) = n. It's very easy to prove that the sum of numbers in A can be any number between 0 and k(k + 1)/2, so it's possible to reach n iff the difference between k(k + 1)/2 and n is even.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А почему сократили длительность контеста? Ведь было объявлено 2:30 часа, а оказалось 2 часа.
И никакой информации о изменении длительности контеста.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    На мыло было разослано объявление о предстоящем контесте, в нём было сказано также, что время контеста оставят 2 часа.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так как я знал время контеста, то прочитал только заголовок письма и письмо удалил, не получая)

      А информация о изменении времени начала и продолжительности, наверное должна быть хотя бы в теме посвященной контесту.

      Хотелось хотя бы около 1.5 часов порешать)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В письме-оповещении вроде было написано последним предложением.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Лично мне вчера пришло письмо, в котором оповещалось об 11-ом раунде. Там были такие строки:

    "На сайте некоторое время назад было опубликовано, что продолжительность контеста составит 2 часа 30 минут, но после пересмотра заданий соревнования было решено не менять формат и сохранить "стандартную" длительность 2 часа."


    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Интересно когда на сайте 2:30 заменили на 2:00?
      Вроде и сегодня еще было 2:30 часа. Хотя может я был не очень внимательным, и просто не ожидал замены)
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Странно получилось, за 2 секунды до конца отправил решение задачи C, но оно, как выяснилось не отправилось, при этом никаких уведомлений об этом не было. А потом, когда отправил в дорешивании, оказалось, что решение правильное... Обидно, что из-за багов системы не сдаются задачи...

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А сайт упал в последние секунды, насколько я понимаю.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Может и упал, а может и таймер в браузере отстаёт (часто замечал это). Поэтому когда у тебя ещё оставалось 2 секунды, на самом деле всё могло закончиться  секунд 10 назад.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Но в любом случае это как-то неправильно.
      На самом деле сайт достаточно часто виснет, за первые пять минут я даже не смог открыть условия задач, аналогичная ситуация наблюдалась в последние секунды контеста и сразу после него, на сайт просто не заходило, причем я пробовал с разных браузеров (Opera, IE, FireFox). Поэтому я думаю, что проблема все-таки не в таймере из браузере.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Я в первые ~5 минут тоже ничего не мог открыть, так же как и сразу после конца. Правда, старт вроде бы сдвинули из-за этих проблем.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Я тоже думал, что сдвинули, по крайней мере таймер показывал что остается 15 минут до старта, а потом когда сумел зайти в контест, оказалось, что он уже 5 минут как идет :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В разделе "Рейтинг" результаты 11-го раунда залазят на "Прямой эфир" и т.д.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это известный баг, который сов временем будет исправлен.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А в хроме всё нормально :-D
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Чувствую, скоро Opera меня наконец-то задолбает, и я перейду на Хром :-)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        На самом деле я люблю оперу.. просто там щас у меня много вкладок и я боюсь туда заходить :) поэтому щас пользуюсь хромом... Хром у меня достаточно часто глючит :) 
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Сохрани сессию (сохранить сеанс), закрой все окна (не по одному, конечно =) =)) и работай в чистом окне на здоровье. =)

          А потом сеанс сможешь восстановить.

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

На 12-ый раунд зарегестрировано несколько синих. Наверно, это вызвано тем, что регистрация на 12-ый раунд началась до завершения 11-го. :-)

14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Where can I read about problems like D? (Counting cycles, Hamiltonian paths etc)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Rus:  где можно почитать про число гамильтоновых циклов и путей?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      нашел что то отдаленно напоминающее
      http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77
      и разбор:
      http://informatics.mccme.ru/moodle/mod/book/view.php?id=489

      а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу))
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        и все таки не могу найти что почитать на эту тему оО только разве что порешать.

        самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно)
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I have problem in my head or codeforce has problem in its head....

my contest code of B got WA in test 4 using scanf and printf

but in practice same code got AC using cin and cout?

is there any explanation anyone can give?

here is my WA in test 4 code

http://pastebin.com/cbBH5nzz

if u replace scanf("%lld",&num)==1 with cin>>num and printf("%lld\n",i) with cout<<i<<endl; it gets AC ...

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

    As you can see there is an 2005 MSVS compiler and it doesn't work with %lld, but with %I64d!

    Or you can just make all variable int (it's enough) and use %d.


    I tested it just now.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Try to replace scanf("%lld",&num) with scanf("%I64d",&num) and printf("%lld\n",i) with printf("%I64d\n",i).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Beaten :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I submited my code in GNU C++,,GNU supports long long ,right?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        As you see, no.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          then its a shame to me...I have been coding knowing that GNU C++ supports long long ...I haven't faced any problem except this.even in my windows pc GNU C++ compiler(CodeBlocks) supports long long well....If codeforce's GNU C++ doesn't support long long ,,then I have nothing to say. :)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Codeforces uses MinGW, which DOES support long long, but DOES NOT support %lld. %I64d should be used instead. Or you can simply submit using MSVC compiler, in most cases it will be fine.
          • 14 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            AFAIK, gcc actually uses the OS's C library to make the call to printf. That's why  on Windows the format for long long is %I64d because the Windows C library uses that format, even though the compiler is gcc.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If anyone wants to see my both code but cant see from the provided link..I will paste it here.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Btw 2008 VS works with %lld. So don't be uncertain.
14 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Do all hadn't a respond from the site at the start of a contest?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    I couldn't open any page for about 5 minutes, but judging by the standings page, many people submitted A at 0:03-0:04...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      It's strange.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Same problem here.  But I guess that doesn't really make a big difference.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        I think it does make a big difference. If you lost 5 minutes in the beginning and solved N problems then you'll get 5*N extra penalty time. 

        If I could access the site immediately from the beginning I'd be 1 or 2 positions higher in the ranklist, and will probably be red today.
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Thank you, Jakub, for interesting problems. It is an essential aid for Codeforces. I'm very glad to work with you.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Does anybody want to share the solution of problem D and E?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
задача С это простая задача которую нужно было решить теоремой Пика?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    то есть не Пика, блин все путаю(( там где мы считаем углы и потом из уравнения находим количество прямоугольников.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не смотря на то, что там квадраты? :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я делал так:
      Идём сверху вниз, слева направо. Если встречаем 1, то это либо левый верхний угол квадрата, либо верхний угол "прямоугольного ромба", либо баг. Проверяем первый случай - пока 1 идём вправо, таким образом выявим длину стороны квадрата. Если получили длину 1 - значит это либо квадрат со стороной 1, который нам не подходит, либо прямоугольный ромб. Если нет, то проверяем, чтобы это был квадрат, у которого вне него есть минимальный квадрат из нулей и внутни него максимальный квадрат из нулей. Т.к. при известной длине стороны и левого верхнего угла у нас квадрат фиксирован, мы проверяем тупо фором, без появления двоякх ситуаций. В случае с повёрнутым квадратом мы тоже проверяем его стороны... это как и с квадратом сделать достаточно легко. Потом чтоб не париться, проверяя смежные клетки, я просто для всех точек этого квадрата смотрю сколько у этой точки соседних точек. По восьмисвязности у каждой точки должно быть ровно 2 смежные 1-цы. В итоге этого алгоритма я получаю квадрат и увеличиваю ответ на 1, или не получаю квадрата. В любом случае я запускаю восьмисвязную рекурсию от этой точки, таким образом удаляя этот квадрат, или этот баг - мне и то и то нужно удалить.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не всегда ровно 2. У обычных квадратов точка, примыкающая к вершине имеет 3 соседки, а если сторона квадрата 3 - то 4
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я же написал, что это для повёрнутых квадратов. Для обычных тупо фором смотрим наибольший квадрат из нулей внутри и наименьший квадрат вне. Также можно было сделать и в случае перевёрнутого.. но там много гемора и я не стал так делать.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ясно. У меня просто все решение основано на количестве соседей
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Или, или, можно сделать так: для каждой точки считаем, сколько единиц слева от нее, сколько справо, сколько по диагонали главной и сколько по побочной
      Также для нулей.
      Теперь проверить, что у нас квадрат легко - просто сравниваем количество единиц. Проверить, что он не касается ничего тоже не сложно - проверяем, что вдоль наших сторон количество нулей достаточное.
      Кодяки правда надо атата скока :о(
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        DFS-ом выделяем компоненты. считаем по ним Xmin, Xmax, Ymin, Ymax. теперь по ним просто тупо строим квадраты, какими они должны быть и тупо сравниваем множества (выделенную компоненту и квадрат). для быстроты введены всякие хаки вида (Xmax - Xmin == Ymax - Ymin), проверки на то, что размеры выделенной компоненты 4(d-1) - вертикальный квадрат или 2(2d-1) - наклоненный квадрат, где d - высота квадрата, т.е. d = Xmax - Xmin + 1 = Ymax - Ymin + 1, и числовой юзед =) мне представляется это самым простым и коротким способом,  да еще тут набажить негде =)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я закодил этот алгоритм вообще без ошибок компиляции и сдал с первой попытки, для меня это редкость :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Извиняюсь конечно за вопрос,но где-то прочел что якобы можно смотреть код других людей...если это так,то подскажите каким образом? 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    это в статусе по контесту или по нажатию на что то вроде  x465 напротив задачи. а там уже нажимаем на номер понравившегося решения.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Но так можно посмотреть только последние сдачи.. а как увидеть другие сдачи? Решения самых лучших как раз и не видно
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Попробуйте отсортировать по разным параметрам. Например, по времени сдачи — обычно самые лучшие и сдают раньше. 

        Хотя это, конечно, хак. Должна быть возможность хотя бы перелистывать страницы и фильтровать по языку.

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Это даже не хак.. потому что сорт происходит тех данных, которые уже расположены на странице и более ранние посылки всё равно не подгружаются.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Нет, это не так. Сортируются все данные. Попробуйте ещё раз.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Новые видимо появляются так: происходит сорт со всеми и выбираются последние или первые "несколько" (в зависимости от критерия). Поэтому т.к. Petr пишет быстро и на яве это обеспечивает ему шифрабильность на простых задачах :) Кстати у меня всё же нет возможности увидеть самых быстрых кодеров, потому что сорт по времени сдачи происходит и дальше выбираются последние, т.е. первых я в этом списке не увижу.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится
                Изначально сортируются по убыванию, да. Но можно вручную подправить параметр и получить сортировку по возрастанию: http://codeforces.com/contest/11/status/A?order=BY_ARRIVED_ASC
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Здорово! Спасибо! Что-то я сам не придумал как его подправить...
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Короче будет очень круто, когда появится возможность прям из таблицы видеть код.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thanks for the problems, but I'd like to pay attention to some inaccuracies in them. 

1. B: "He can go either left or right with each jump." One may think that Jack can go either left or right from his point of view. For example, going left and then right would move him (0,0) -> (-1,0) -> (-1, 1). That will make the problem two-dimensional and thus much more complicated. A friend of mine spent much time until he realized his mistake. It would be better to write something like "He can go either back or forth with each jump."

2. C. What is a diagonal of a non-square matrix? It is a rarely used term, at least I've hardly found a mention of it only on the second page of Google's result. It would be much better if the definition of this term was given in the problem. It requires only a sentence or two, but clarifies the problem.

3. C. "a square must contain at least one 1 and can't touch (by side or corner) any foreign 1". What does "foreign" mean here? Is it a "1" which doesn't belong to this square or to any square?

4. Also "a square must contain at least one 1", but earlier "A square should be at least 2×2". I understand, that there is no contradiction, but why increasing the confusion?

Thanks.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think the authors should explain the examples for all the problems in the contest.

    For example: the authors should explain why the result is 1 for the 1st  test case, 2 for the 2nd test case... for the problem C. 

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В дополнение к предыдущему комментарию скажу, что перевод на русский был не очень, в смысле, с ошибками.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Я уже жаловался автору на просторечное «заместо» в задаче Е, но ничего исправлено не было :(
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Did anyone solve problem B using DP solution?
I want to do but I can't...
I hope someone show me the code.
Thanks.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I don't know a DP solution.

    For example. If you want to reach 10^9 position, in some you'll be near it. Let it be a 10^8 position (of course the real position place will be close to 10^9, you can prove it yourself). So we need to compute 10^8 cells. It takes more than 1 sec time. :(

    And you need about 120 MB to store billion length bool array.

    Maybe there is a much better DP solution, and maybe even it got AC, but i solved that with little formula and very little bruteforce (most of participants use only brute).

    If you request a code you can get it there - http://codeforces.com/contest/11/status/B?order=BY_ARRIVED_ASC
    • 10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am new to programming. The people have solved problem D quite easily as it is quite trivial for them. I am not able to understand how they are solving using DP. what is the subproblem. I have spent 3-4 days trying to understand the solutions but no success. Can anyone help ? I will be grateful for the same

      • 10 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        Комментарий удален по причине нарушения правил Codeforces
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача B мне понравилась) у меня на C++ 9 строк кода получилось) У кого меньше?)
#include<cstdio>
int main()
{
    int x, i = -1, y, fl = 1;
    scanf("%d", &x);
    if (x < 0) x *= -1;
    while (fl) if ((++i * (i + 1) / 2) >= x && (x + (i * (i + 1) / 2)) % 2 == 0) printf("%d", i), fl = 0;
    return 0;
}
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain how to solve B? I saw people using logic while (sum<x || (sum-x)%2==1) {ans++; sum+=ans;}, what is the logic behind (sum-x)%2==1?

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

    Let us suppose you take j jumps to reach some point y where y >= 0. Let us suppose you took some forward and some backward jumps. Clearly, we can write : 1. (sum of forward jumps) — (sum of backward jumps) = y ...equation(i) 2. (sum of forward jumps) + (sum of backward jumps) = j(j+1)/2 .... equation(ii)

    Combine both to get: j(j+1)/2 — 2(sum of backward jumps) = y

    The above equation is the key. [Note : sum of backward jumps -> is the sum of some elements from the set {1,2..,j} which can take any value between 0 to j*(j+1)/2 ..not too difficult to prove]

    Hence, if (j(j+1)/2 — y) is even and (j(j+1)/2-y)/2 lies in the range [0,j(j+1)/2] then clearly we can reach y in j moves. Hope it is clear!!

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

I will try my best to explain the my approach on problem 11D without using sum of subsets dp. Denote d[last][mask] as the number of ways to form a chain consists of every elements with its bit on in the mask, the first bit (first_bit) in mask is the head of the chain (we are fixing the order of the cycle) and last is the last element in the chain. The transition is easy, take every possible next bit that satisfies next > first_bit, next doesn't appear in the current mask, next and last share an edge and d[next][mask^(1 << next)] += d[last][mask]. Check through every dp state that there is an edge between last and first_bit and add them to the final answer. Finally divide the answer by 2 as we repeated the calculation in the last step.

My submission: 79403398.