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

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

29.09.2013 в 5:30(UTC) состоится September Lunchtime contest, который будет длится 3 часа.

Этот контест проводиться в стиле IOI. Поучаствовать могут все желающие.

Автор задач — Roman Furko.

Более подробную информацию вы можете найти здесь.

Предлагаю после контеста обсудить здесь задачи.

Удачи!

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

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

Подозреваю, что этот топик должен был создать автор контеста.

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

    На самом деле, так сложилось, что анонс создает админ CodeChef'а.

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

    Я спросил у автора он сказал что не будет постить.

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

What's Memory Limit in all tasks?

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

The contest is over now. The editorials are being published here: http://discuss.codechef.com/tags/ltime04/

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

Подскажите пожалуйста как решать задачу про xor трех чисел

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

    Решим задачу, когда нам нужно найти максимальный xor двух чисел за время O(N log N). Будем перебирать одно число и для него искать число с максимальным с ним ксором. Заведем структуру данных бор (префиксное дерево), для хранения чисел в двоичном представлении. Тогда чтобы ответить какое число из бора имеет максимальный ксор с числом K, нужно применить алгоритм : пусть мы стоим в вершине, и из нее есть два ребра 0 и 1, и соответствующий бит числа K равен b, тогда мы идем по ребру b^1 (если оно существует). Когда мы пришли к лист, он соответствует числу, xor с K которого максимален. После этого добавим число K в бор. Теперь легко обобщить задачу, когда у нас нам нужно найти xor 3-ех чисел. Будем перебирать 2 числа (пусть A и B) и искать в боре число с максимальным ксором с A^B. Время : O(N^2 log N)