29.09.2013 в 5:30(UTC) состоится September Lunchtime contest, который будет длится 3 часа.
Этот контест проводиться в стиле IOI. Поучаствовать могут все желающие.
Автор задач — Roman Furko.
Более подробную информацию вы можете найти здесь.
Предлагаю после контеста обсудить здесь задачи.
Удачи!
Подозреваю, что этот топик должен был создать автор контеста.
На самом деле, так сложилось, что анонс создает админ CodeChef'а.
Я спросил у автора он сказал что не будет постить.
What's Memory Limit in all tasks?
Sorry for the late info. The memory limits can be found here: http://www.spoj.com/clusters/. Yes it is the SPOJ judge that we use.
Ok, thanks!
The contest is over now. The editorials are being published here: http://discuss.codechef.com/tags/ltime04/
Подскажите пожалуйста как решать задачу про xor трех чисел
Решим задачу, когда нам нужно найти максимальный 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)