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

Автор KOTEHOK, 13 лет назад, По-русски
Лог второго тура:

12:46 - Всё, пойду встречать ребят. Так ничего и не изменилось для команды России, похоже, так и останется два золота и два серебра. В целом >= 200 баллов уже у 86 участников, и, конечно, за оставшиеся 15 минут станет ещё больше.

12:24 - По задаче про попугаев стали появляться 99 баллов. Да, люди сильно продвинулись в изучении неточных решений. При этом сотен по этой задаче всего шесть. Также смотрю за Димой и Егором. У Димы много сабмитов по 26 баллов - похоже, он не придумал решения в слонах. А вот сабмит от Егора на 10 баллов, сделанный 15 минут, вселяет некоторую надежду, что у него просто какие-то баги в дереве.

12:11 - У Саши 100 за слонов! Надеюсь, два золота у нас уже железно. Догадается ли Саша сделать ход назад? И что же случилось у Димы и Егора?

12:00 - У Саши 295, 97 за слонов! К сожалению, Дима и Егор так и не вылезли пока из глубокого серебра, а Паша не заменил свои 98 на 100. При этом уже 65 участников набрали >= 200 баллов.

11:16 - Кстати, Дима дописал кучу в Дейкстре и у него стало 226. Все российские участники не ниже 9 места (хоть и 9 разделено с местами до 13). Эх, до конца бы так и оставить ;) Кстати, самое обидное, что если бы сейчас давали бы медали, то было бы всё равно два золота и два серебра. Это из-за первого тура так, получается то, о чём я писал ниже - выйти вперёд на этих задачах сложнее, а вот слететь...

11:15 - У Паши 98 по попугаям. Видимо, теперь надо сделать главный ход конём и догадаться до очень неожиданной идеи - в неточной задаче есть точное решение! На самом деле, это реально сложно, это как в шахматах взять предыдущий ход назад.

11:06 - У Паши 90 в попугаях. Всё-таки, он пошёл тем путём. Жаль... надеюсь, за два часа он сообразит про наличие абсолютно точного решения.

10:52 - У Димы сотня по попугаям! При этом уже 31 участник имеет >= 200 баллов, а 145 участников - >= 100 баллов. У наших у всех хотя бы 215 (Паша 281, Саша 248, Егор 224, Дима 215). Насколько этого достаточно, покажет время, но, думаю, будет ещё много подъёмов разных участников.

10:38 - У Паши уже 81 по попугаям. Видимо, это делается за 5 минут. Надеюсь, он не пойдёт дальше этим путём? Очень сбивает то, что эта задача с неточной оценкой, это психологически неожиданно и уводит от мысли искать простое точное решение :( Тем временем, Дима тоже получил 81 балл по этой задаче и имеет 196 баллов за этот тур. Надо бы ещё.

10:32 - У Паши 100 по слонам! Молодец! Не зря он в них сидел. Через минуту присоединился Гена и стал первым из абсолютных победителей. Паше остаются попугаи. Очень надеюсь, что он увидит в них сочетания с повторениями - на мой взгляд, это самый сложный момент в этой задаче. Иначе получается 98.

10:22 - У 17 участников >= 200, у 116 участников >= 100. Россия пока без изменений :(

10:12 - У Паши стало 126. Неужели он всё ещё сидит в слонах? Не пора ли заняться попугаями и сдать их на сотню?

09:58 - У Гены уже 297. Сейчас он чуть-чуть пооптимизирует слонов и станет одним из абсолютных победителей. Тем временем, у 11 участников >= 200 баллов, а у 100 участников >= 100 баллов.

09:54 - Тут же у Саши становится 98 баллов по попугаям (248 всего), и его обгоняет Гена с 250 баллами, у которого по попугаям одно из двух полных решений (другое глубоко внизу, что как бы намекает).

09:53 - Саша сдаёт попугаев на 93 балла и выходит на первое место по туру с 243 баллами. Но что же там за решения не на 100? И не придётся ли потом вместо них писать на сотню?

09:50 - У Егора 224, добавилось ещё 26 баллов по слонам. Что же он будет делать теперь, и что же за проблемы у остальных наших?

09:46 - Почему-то российские участники пока не двигаются (Егор - 198, Саша - 150, Дима - 115, Паша - 110). Очень волнуюсь, в чём же дело. Тем временем шестеро участников имеют >= 200 баллов, а 89 участников - >= 100 баллов.

09:38 - У одного из участников из Китая уже 237 баллов. У Егора тем временем 198 (98 по попугаям). Да, наверно, будет обидно из-за двух баллов писать совсем другое решение... 

09:32 - У Паши 10 баллов за слонов. Что бы это значило? Хотя бы 100 баллов уже имеют 68 участников.

09:26 - У Егора 81 по попугаям. Я вообще не понимаю, что там может быть за решение, кроме точного :( Неужели там есть жёсткий ложный след, как в задаче garden первого тура, где можно было вводить состояния не на вершинах, а на рёбрах, что до сотни не доделывается вообще никак?

09:15 - Странно, что сотня по задаче parrots только одна. Зато есть ещё два участника по 98 баллов. Неужели комбинаторика и построение объекта по номеру и номера по объекту - такая сложная вещь? Или не все знают про сочетания с повторенями? При этом хотя бы 100 баллов уже у 52 участников.

09:10 - у Димы 115, у Саши 150. Похоже, пошли в бой разные квадраты в слонах. Тем временем, у лидера из Вьетнама 207 (100 + 26 + 81), а >= 100 уже у 41 участника.

09:00 - у Гены 200. Мой прогноз при виде задач, что у Гены останется 4 часа на задачу elephants, оказался абсолютно точным.

08:49 - уже 28 участников с >= 100. У всех российских участников 100, кроме Димы, у которого 89 (без хипа?).

08:40 - уже 18 участников имеют >= 100. У российских участников 100 баллов у Паши, 89 баллов у Саши (сначала решил послать Дейкстру без хипа?)

08:35 - уже семеро участников имеют полный балл по одной из задач

08:20 - один из польских участников уже сдал задачу про крокодилов. Дейкстра с хипом, однако.

По информации от организаторов, контест начался в 08:00 и закончится в 13:00 (местное время - +3 часа от московского).

---

Условия задач второго тура: http://acm.math.spbu.ru/ioi-2011-day2/
Текущие результаты: http://www.ioi2011.or.th/results
Результаты в приличном виде (спасибо Снарку :): http://sc2.ioi2011.net:8070/contest/
Результаты от Снарка: http://158.250.33.215/~ejudge/player_all.html

Решения всех задач второго тура.
Он мне показался даже проще чем первый. Сколь-нибудь ненулевое время я решал только elephants, остальные две задачи мне вообще показались упражнениями на базовые темы.

1) crocodile
Алгоритм Дейкстры, только нужно хранить в каждой вершине два текущих минимальных ребра, и ответ от вершины - второй из этих минимумов. Доказательство: пусть для каждой вершины посчитан ответ, тогда верно, что D[u] = {второму из чисел D[v] + w[u, v]}, где (u, v) - все рёбра, связанные с u. Теперь пусть, как в Дейкстре, для некоторых вершин уже посчитано D[v]. Тогда если взять вершину u такую, что min {второго из чисел D[v] + w[u, v]} минимально возможен, очевидно, он правильный (так как иначе была бы вершина с меньшим ответом). Включим u в множество уже посчитанных вершин и отрелаксируем. Странно, что за кучу в Дейкстре дают всего 11 баллов...

2) elephants
Самая сложная задача, примерно по сложности как race. Заметим, что в фиксированный момент времени задача решается жадно - возьмём самую левую точку и покроем, и т.д. Теперь, если мы посмотрим на то, какую точку после какой мы покрываем жадным алгоритмом, мы увидим дерево, глубина вершины в котором и является ответом, если решать суффикс нашей задачи, начиная с этой вершины. Если читать это дерево сверху вниз, а внутри уровня слева направо, то мы получим список слонов в порядке справа налево. Осталось научиться поддерживать это дерево и уметь быстро вычислять глубину самой левой вершины. Для этого нужно понять, какие операции делаются с этим деревом. Можно разбить перемещение слона на две операции: удаление и добавление. При удалении берётся поддерево удалённой вершины и подвешивается к соседней на том же уровне, а если на этом уровне вершин нет, то к крайней на более высоком. Если же мы добавляем вершину, она добавляется на некотором уровне, подвешивается к одной из вершин более высокого уровня и у соседа отрезается последовательная часть детей и подвешивается к ней. Структура данных, которая замечательно выполняет такие операции - это декартово дерево 
по неявному ключу, если дерево хранить в порядке обхода dfs'ом. Единственное, в нём тяжело искать соседа по уровню, а также искать место, где нужно разрезать последовательность вершин при добавлении. Для этого я предлагаю хранить ещё одно декартово дерево, в котором ключом является координата слона, а также хранится дополнительная информация - ссылка на узел в дереве по неявному ключу. Тогда мы умеем в нём и искать нужную позицию, и переходить к соседу, и вообще делать всё, что нужно.

3) parrots
Видно, что исходное сообщение представляет собой размещение с повторениями (то есть, просто число в некоторой системе счисления), а конечное - сочетание с повторениями (если мы отсортируем все полученные числа, так как информация о порядке всё равно потерялась), число которых, как известно, равно C из n + k - 1 по k. Самый эффективный с точки зрения отсутствия отсутствия потерь информации способ их закодировать - это перевести исходное размещение с повторениями в номер, а потом по номеру построить сочетание с повторениями. Раскодировать, соответственно, обратно. Несложно видеть, что все подзадачи решены (ещё бы они не были решены, если это нельзя сделать таким способом - нельзя сделать никаким другим), например, для подзадачи 5 получается всего на несколько порядков больше сочетаний с повторениями, чем размещений - ограничения подобраны довольно жёстко. Да, несложная длинная арифметика ещё нужна.

В общем, к сожалению, наши шутки на тему того, что второй тур может быть ещё проще, чем первый, оправдались :( И это очень грустно для нашей команды, потому что упасть на таких задачах можно запросто, а вот подняться - почти нереально. Нужно ставить на количество абсолютных. Я ставлю на 6. И остаётся только молиться, чтобы среди них были Паша и Гена.
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Пашка рви! удачи им!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На 43-ей минуте у сборной России уже три сотни и одна 89. Вот и дальше бы так оперативно :) .
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У Гены 200!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    200 на первом часу — выглядит как проблемсеттерский фейл.

    И мини-баллы за последние подзадачи тоже как минимум спорный ход. Например, в elephants всего 3 балла за то, чтобы уметь обрабатывать в два раза больше запросов. И в условии сказано, что последняя задача может не пройти, если пользоваться C++ и STL.

    То есть по замыслу те, кто напишет структуру данных быстрее STL-аналога, получат 300 баллов и займут место типа ~1-7. А те, кто напишет структуру данных медленнее STL-аналога, получат 297 баллов и займут место ~8-14. Зато те, кто хоть что-то не сдал в первом туре, могут уже о Top 10 не мечтать. Нда.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я, честно сказать, не очень понимаю, как решать с STL. Использовать rope? (нет, не луковое - предыдущее слово надо читать по-английски ;)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну вспомогательное декартово дерево в твоём решении точно можно заменить на map.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Надо признать, что фейла не случилось. Хотя сотен по каждой задаче не меньше шести.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    (double post)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    300! Я знал!!!  
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Табличка Снарка, в которой не надо листать, чтобы видеть все числа:
http://158.250.33.215/~ejudge/player_all.html.
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Одна золотая медаль нашла своего хозяина=)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А кто бы сомневался? :)

    Квота мест по медальным зонам в этом году такая же как и в прежние годы?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, там чёткий алгоритм - не менее 1/12 золотых, не менее 1/6 серебрянных, и не более 1/2 всего медалей.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Спасибо!
        А то мы тут кроме всех наших братьев-славьян болеем за золото у ещё одного человека: Baris Kaya, а после града 100% результатов первого тура этот вопрос и возник.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ? Если не секрет
          • 13 лет назад, # ^ |
            Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

            Не секрет - у нас дистанционно на сайте сборная Турции готовилась, да и М.Г.Медведев проводил зимой у них в Анкаре с использованием нашего ресурса 10-дневные очные сборы.
            Так вот от этого парнишки ожидают первого для страны "золота".
            Ну, естественно, мы также в первую очередь болеем за "золото" всех наших (во всяком случае медалей 100%), а что из этого получится - уже недолго ждать осталось - скоро увидим. :)

            Грубая прикидка: 25 - золото, 50 серебро и 75 бронза - чтобы можно было как то по текущим местам ориентироваться.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Мне кажется, что так правильнее будет :
              25 золота, 50 серебра, 75 бронзы.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    походу 1 абсолютная уже есть:)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
У китайца 599...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Интригующий вопрос на последних минутах: так сколько будет абсолютных победителей?
    Скорее всего прогноз о 6-ти не подтвердится.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Никто не решился делить абсолютную победу с Геной)
      Мои поздравления команде РФ! Молодцы!
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Самый удивленный сейчас, наверное, Гена =)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
     Поздравляю всех рускоязычных участников, получивших медали!  Рад что Гена - единственный абсолютный чемпион. По моему это справедливо. Особые поздравления "молодёжному" составу Гомельской области (Гена, Адам - 10 класс, Сергей и Влад  - 9) с завоеванием золота и 3 серебра!!!
13 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
Переводчику условий надо напомнить, что collection templates -- это не коллекции шаблонов, а вовсе даже шаблоны коллекций.

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

Присоединяюсь ко всем ранее озвученным и тем, что ещё будут звучать далее, поздравлениям!
Гена - МОЛОДЕЦ!
Вообще команды России и Беларуси заслуживают уважения и отдельного поздравления.
Большое спасибо Андрею Лопатину за классную ленту-комментарий с места событий (а какой ещё комментарий мог быть у дважды чемпиона мира? - :) ).


Наблюдая за интересующими меня командами, свёл результаты в одну табличку, вот что получилось:

 

 Золото

 Серебро

Бронза

 Беларусь

 1 

 3

 -

 Китай

 3

 1

 -

 Польша

 2

 1

 1

 Россия

 2

 2

 -

 США

 3

 1

 -

 Турция

 1

 1

 2

 Украина

 -

 1

 2

 Хорватия

 3

 -

 1

Комментарии к ней излишни (сортировка в алфавитном порядке).

Ещё раз поздравления всем победителям, призёрам и просто участникам IOI-2011!

  • 13 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится
    Забавно, что оба Китая показали одинаковые результаты :о)

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Странно что один китаец второй раз поехал. Им же только 1 раз разрешают. Ладно еще, если бы он прошлый раз 1 абс взял или что-то такое и ему в порядке исключения разрешили, а у него было серебро.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        Если не ошибаюсь, на форуме топкодера когда-то писали, что им не дают участвовать в IOI еще раз как раз при наличии золотой медали и только её (отжёг - молодец, дай другим).
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Это неправда. Weidong Hu участвовал в 2004 и 2005. Zeyuan Zhu участвовал в 2005 и 2006. Оба получили по две золотые медали. И это только те, кого я помню. Думаю, что случаев было больше.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            http://apps.topcoder.com/forums/?module=Thread&threadID=613160&start=0&mc=328

            Если верить информации от китайских участников IOI, то то, что я утверждал верно с 2006 года.

            В составы их команд я, правда, посмотреть поленился.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Да, точно. Это только для золотых медалистов. Я тогда прочитал пост crazyb0y, на первой странице, но не прочитал пост yuhch123 на следующей и думал что это ко всем относится :)
13 лет назад, # |
Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

для меня, выглядит странным, что парень из Грузии в 2010 был 7-ым а в этом году занял 79 место, причем подметив это после первого тура, я наблюдал за ним во втором и он первые 4 часа вообще был за бортом....
UPD: если кому интересно, некто - Tsotne Tabidze
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
на мой взгляд странно получилось с задачей про попугаев, на мой взгляд очевидно преобразование между сортированной последовательностью из 5 * n байт и неким числом из 8 * n бит. безо всякого знания комбинаторики пишется простое дп позволяющее по числу получать последовательность и по последовательности её номер.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится
    Какое преобразование вы имеете в виду? По-моему, это не совсем верно для общего n.
    Например, если n=80, то для кодирования (по сути 640-битного числа) нужна будет последовательность хотя бы из 420 чисел (при R=255), т.е. больше чем 5*80=400.
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -37 Проголосовать: не нравится

      я не знаю как ты считал эти цифры, но если сортированных последовательностей из  5 * n байт меньше, чем 256^n то задача решения не имеет. 80 вроде бы выходит из диапазона, там до 64 n. кстати для n <= 32 можно не 5 * n а 10 * n

      UPD: вот тут код дп, который я написал специально для тебя, урод.

      для n = 64 получаем число последовательностей порядка 2^565. 565 / 64 ~ 8.828
       этого вполне достаточно
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

        Не понял ваше "специально для тебя, урод" ? Это теперь норма для CF или у вас какая-то претензия лично ко мне?

        А если по делу, я ведь только спросил, что именно за преобразование. 8n бит превратить в 5n байт (без учёта порядка) в общем случае невозможно.
        upd: Суть моего высказывания в том, что (как мне раньше казалось, а теперь я уверен) иногда вместо 5n нужно хотя бы 6n и т.д.  При росте n коэффициент перед n нужно увеличивать.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Что касается задачи, вы правы в том что коэфиициент увеличивается с ростом n, но для ограничений задачи достаточно 5. Ваше замечание к моему первому комментарию претендовало на то, что предложенное мною решение неверно. В итоге у моего комментария было -1 у вас +2, дело не во вкладе, а в самом факте такой идиотской ситуации, кто-то ляпнул чушь и в итоге верное утверждение минусуют, а неверное плюсуют. В тот момент, когда я увидел ваш провакационный ответ, я выпивал пиво с друзьями и пожаловался на вашу наглость, вместе мы и придумали достойный ответет. Я вместо того чтобы обсуждать интересные для нас темы писал это дп, специально для вас, уважаемый. Ну и дабы подчеркнуть что я к вам лично ничего не имею, я таки зачеркнул обращение выражающее моё недовольство относительно вашего поведения.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Я не вижу, между каких строк вы читаете, и в чём заключалась моя "провокация" или "наглость".

            Когда я решал Parrots я (теоретически) вывел коэф. перед n, который растёт неограниченно с n. Увидев фразу "легко видно преобразование между 8n бит и 5n байт", я просто решил поинтересоваться, что именно это за преобразование, чтобы разобраться, работает ли оно при всех n (тогда моя оценка неверна) или имелось в виду n<=64.

            Конкретно у меня получилось
            c = 8L / log(combin(L+R,R))
            (логарифм по основанию 2)
            L - кол-во попугаев
            c - (как минимум) во сколько раз n должно быть меньше L

            И да, мне не кажется, что я где-то "ляпнул чушь".

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

              Я сделал все чтобы пояснить вам мой подход к решению, если вы и после третьего комментария и выложенного кода не понимаете, то я тоже уже ничего не понимаю. Вы дурак или прикидываетесь?  Я не верю что вы не поняли предложенное решение, у вас неплохой рейтинг и вы скорее прикидываетесь. Я не верю в то что вам до сих пор не понятно что коэффициент 5 я взял не с потолка, а из условия задачи. Мой комментарий описывал подход к решению задачи, а она подразумевает коэффициент не более 5 и n <= 64.

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

              И вы не "ланули чушь" вы ляпнули чушь. Которая привела к минусованию моего комментария, описывающего верное решение. В этом то и заключалась "наглость" или "провокация",  то, что огорчило меня и заставило ответить вам описав решение. Я не говорю что вы совсем не правы в своем ответе, просто он послужил поводом для кого-то меня минусовать, а возможно вы минусанули, не поняв о чем я сказал.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        А можно без "уродов" и "дураков" пояснить вот эту фразу "для n = 64 получаем число последовательностей порядка 2^565. 565 / 64 ~ 8.828
         этого вполне достаточно".

        Ведь по условию задачи в полном решении отношение длин исходной и закодированной последовательности должно быть не больше 5-ти.
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

          Ну смотрите, мы можем передать одну из 2^565 последовательностей, такое сообщение несёт информацию 565 бит. Нам требуется передать 64 * 8 бит 565 / 64 > 8 бит (нам же хватит и 8 бит на каждый кусок из 64). С другой стороны можно 565 поделить на 8 и получить число байт, которые мы можем передать, получиться 70.625, что опять же больше 64 байт. Еще раз, по другому. Мы хотим передать 64 байта, их можно рассматривать как число x, x >= 0 && x < 2^(8*64). 2^(8*64) = 2^(512). мы, умея преобразовывать сортированную последовательность в число и наоборот, можем передать число до 2^565, и таким образом нам не составит труда передать сообщение x, даже еще останется место.

          Теперь поясню почему это будет работать и для меньших значений n.

          Количество информации в сообщении из 5 * n байт равно 8 * 5 * n битам, что соответсвует 2^(40 * n) возможным сообщениям. Оценивая сверху потери информации при сортировке байт будем считать что все числа различны, и перемена мест любых двух байт меняет сообщение. То есть, информация которая потерялась при сортировке может быть восстановлена с помошью перестановки 5 * n чисел.То есть нижняя оценка для информации, которую мы можем получить передав сообщение (которое потом перемешается и отсортируется) есть log2(( 2^(40 * n) ) / ( (5 * n) ! )) чем больше n, тем больше бит мы теряем с каждым очередным членом в факториале (числа постепенно возрастают) чем меньше n, тем лучше для нашего метода.

          UPD: для большей наглядности раскрою скобки, и уберу деление из логарифма.

          F(n) =  log2(( 2^(40 * n) ) / ( (5 * n) ! ))  = 40 * n - log (5 * n)!)

          F(n + 1) = F(n) + 40 - log((n * 5) - log(n * 5 - 1)   - log(n * 5 - 2)   - log(n * 5 - 3)   - log(n * 5 - 4) 

          как видим, при росте n потери информации возрастают. Замечу еще раз что это нижняя оценка для количества информации, и да, она станет отрицательной при устремлении n далеко в бесконечность.

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

            еще раз поянсяю, мы берем последовательность 5 * n байт сразу, коэффициент всегда равен 5, а формулы считают информацию, которую можно передать в таком сообщении.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится


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

            Не хочу ни с кем ссориться, но справедливости ради отмечу, что оценка слишком груба для n=64.
            Т.е. F(64) ~= 353 бита, а 353/8 ~= 44<64.
            (но 5*64 попугаями всё же можно передать 64 байта исходного сообщения)

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

            =========================
            Спасибо.
            С теорией информации я знаком, просто я не вижу в чем заключается конструктивное решение.
            Я понимаю задачу так. Есть сообщение из 64 байт, его надо закодировать не более чем в 320 байт, и, после случайного перемешивания, восстановить исходное сообщение.
            На IOI решение на 100 баллов упаковывало 64 -> 262. А у Вас как?
            • 13 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              У меня тоже 64 -> 262, что является минимальным.
              Идея в том, что все невозрастающие последовательности из 262 байтов можно пронумеровать от 0 до comb(262+255,255) (например лексикографически), и первые 2^512 из них поставить в соответствие 64-м байтам исходного сообщения (но Вы, веорятно, это и так знаете?:)), и функции encode и decode просто конвертируют из одного представления в другое.

              edit: извиняюсь, не заметил, что добавили разборы.

              edit2: я всё-таки поторопился, сказав, что 262 минимально. Ведь длина закодированной последовательности тоже несёт информацию. Sum_{k=1..261}(comb(k+255,255)) > 2^512, следовательно 261 попугаев достаточно для n=64.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится
                ====================================
                Разборы не добавили, они изначально там были.
                Вот, кстати, любопытно. Оказывется, если бы не SnapDragon, то на IOI был бы дележ, как минимум 1-4 места =). 
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Наблюдая за финалами АСМ, всегда приятно видеть, что из 12 медалистов 5 из России (за последние несколько лет так, за исключением пары лет, когда было 4), что больше чем у всех остальных стран. Ещё и нередки чемпионства. В общем в АСМ у России как будто бы всё хорошо.

А на IOI нет никакого доминирования России.

В чём проблема? Дети к универу умнеют, а в школе пока ещё не такие умные? Тренеры в школах менее активные (тренеры-то почти одни и те же в школах и универах?)? 
Или в других странах может школьному движению уделяют большее внимание, чем студенческому? 

P.S. Вопрос наверное прежде всего  к тренерам.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Ну почему нет? Сборная России на IOI всегда выступала хорошо.

    Тут скорее всего проблемы другого характера: причины в разном формате соревнований.

    АСМ - это командные турниры, а IOI - личные.
    На
    IOI действует ограничение на максимальное представительство школьников от одной страны - больше 4-х их быть не может.
    На АСМ действует ограничение на количество команд от одного ВУЗа, но не действует ограничение на количество команд ВУЗов от одной страны.
    Так что доминирование на АСМ говорит, наверное  и скорее всего, о высоком уровне преподавания во многих, я бы даже сказал, в большинстве ВУЗов Росии, в то время как в других странах ВУЗов с высоко поставленным уровнем преподавания намного меньше.

    Учитывая, что практически во всех странах школьники по окончанию школы стремятся поступать в престижные ВУЗы, то шансов попасть в команду на финал АСМ у бывших призёров
    IOI или просто талантливых школьников в других странах намного меньше чем в России.

    Это, конечно, чисто мой субъективный взгляд со стороны, но кажется мне, что это достаточно близко к истине.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Мне одному кажется, что высокие результаты в СП скорее коррелируют с тренерами ВУЗа и студентами, которые там учатся, нежели с высоким уровнем преподавания?

      Т.е. существует куча ВУЗов, в которых замечательно преподают, но нет тренера - нет результатов.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        Естественно - и это тоже.
        Без классного организатора, почти фанатически преданного этому делу, успеха добиться на несколько порядков будет тяжелей.
        Кстати, абсолютно аналогичная картина и в школьной олимпиадной информатике.
        Т.е. "Кадры решают всё!", ну во всяком случае если не всё, то многое... :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В этом-то и дело, что сборная России на IOI выступает хорошо, а на АСМ отлично.

      Никакую статистику не подводил, но создаётся впечатление, что в АСМ Россия примерно на одном уровне с Китаем (чаще даже повыше) и выше на голову остальных.

      В IOI Китай стабильно выше нас. Редко очень мы выше. Последние годы и США вроде как подтягивается.

      Выходит, в одном мы можем, а в другом не можем.

      Объяснение про ограничение от ВУЗа и от страны по-моему странное.
      Всё равно больше всего крутых АСМщиков в среднем у нас в ИТМО, МГУ, СПбГУ. И многие студенты оттуда не могут выйти на финал из них, хотя могли бы выйти из других универов спокойно (Славу все помнят :) ). В итоге ездят не на столько сильные, на сколько можно.

      А вот в IOI тренеры вольны собрать 4х самых крутых со всей России и отправить невзирая на ограничения.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      За то время, сколько я участвовал в олимпиадах, количество задач в которых мне помогли знания, приобретенные в университете, можно пересчитать на пальцах. Да и то, эти знания совсем не из программирования.

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

      Думаю что самое важное - это желание студентов, а остальное просто помогает развиваться и подталкивает в нужном направлении. У нас в университете, например, не проводятся регулярные тренировки или что-то подобное. Команды в основном сами тренируются на разных архивах задач/виртуальных контестах. Ну и еще ездят на разные сборы, онсайты олимпиад и т.д.. Разумеется, есть люди в университете, которые организовывают эти поездки и выбивают деньги на них. Но все же основную часть времени команды тренируются сами.

      Так что, как мне кажется, тут обратная связь. Сильные школьники вправе выбирать вузы и, само собой, идут в престижные вузы, где хорошо преподают. Затем они организовывают команды и ездят на АСМ. Отсюда и получается, что практически все победы на АСМ исходят из таких вузов.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        И это всё верно и не идёт в разрез с выше сказанным. Просто мы с разных точек (углов) зрения говорим практически в пользу одно и того же.
        Ещё один пример в поддержку вышесказанных тезисов на базе украинских ВУЗов: если раньше можно было говорить только о киевской и харьковских студенческих школах и командах на АСМ, то сейчас кроме Киева и Харькова появились Львов, Донецк, Симферополь, Днепропетровск, Винница, подтягиваются и другие - всех не перечислишь, да и в перечисленных городах растёт количество ВУЗов, где занимаются спортивным программированием на более высоком, можно сказать профессиональном уровне. Это всё со стороны хорошо просматривается. Как один из результатов - тот факт, что Украину в этом году выдели в отдельную зону.

        Да и перспективные и одарённые школьники, выбрав и поступив в престижный ВУЗ и ощущая там конкуренцию от этой самой конкуренции становятся только сильнее.

        Главное тут, что если им в некоторых ВУЗах не помогают в этом, то пусть хоть не мешают... :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Два случайных довода, которые могут коррелировать с тем, что это так:

    1. В России раньше, чем в среднем по остальным раундам, заканчивается школа. Значит, дети в среднем менее взрослые.

    2. У NEERC несравненно большая квота для команд-финалистов. Легче 5 из 13 команд оказаться в медалях, чем, например, 5 из 1.
13 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится
Забавный сюжет на телеканале Россия 24:

  • 13 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится
    >тесты
    >мехмат СПбГУ
    >Павел Куняев
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Слов нет. Одни нецензурные. Ну честно.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Ладно-то меня в Питер отправили, но вот Пашу жалко, ему фамилию придется менять.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    http://saratov.kp.ru/online/news/944449

    Я что-то пропустил?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Ну, логика - третье место -> завоевал "бронзу".
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Механико-математический факультет и туда добрался.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Следующий шаг логической цепочки - я пятый, Паша - третий, а Дима с Егором - вторые(так серебро же). При этом у Паши лучший результат.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Кто занял первое место? Первое место мы уступили КИТАЙЦАМ.
    На такое я могу только матом...
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Это, видимо, про суммарное количество баллов по всем участникам из одной страны.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Да, но тут ожидается что скажут "Геннадий одержал".

        Наверняка по политическим мотивам не сказали об этом ;)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится
          Да, я тоже сначала так подумал. Потом только до меня дошло, почему сказали про китайцев.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Закономерный вопрос не только к этому видео, но и вообще к журналистским выходкам. Возможно ли за распространение заведомо ложной информации кого-то засудить? И если да, то кого, каким образом и на какое наказание?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вряд ли она заведомо ложная.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Для кого-то в цепочке фабрикования новости информация является либо заведомо ложной, либо заведомо взятой с потолка.
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          "Кто владеет информацией - тот владеет миром..." :)

          Но девчонка заслуживает немного уважения: не въезжая не то, что в тему, а вообще в элементарную терминологию, так уверенно рассказывать обо всем в течении около 10 минут - только за это можно немножко зауважать...
          А потом вспомнить, что журналисты - это тоже одна из древнейших профессий и просто улыбнутся - ну не виновата же она в конце концов, что у неё работа такая... :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        Да, это не заведомо ложная информация - это бред...Страшно представить, сколько ошибок, неточностей и вообще треша показывают в новостях длиной полчаса, если за 3:26 успели их допустить чуть больше, чем 100500
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Думаю не тот телеканал, чтобы кого-то пытаться "судить" :-(
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
В последнее время меня все больше и больше раздражают такие журналисты.