zholnin's blog

By zholnin, 10 years ago, In Russian

Я временно перестал участвовать в соревнованиях по "личным обстоятельствам", но продолжаю урывками прорешивать задачки на разных сайтах. Напоролся на задачку (точнее мой генератор случайных чисел напоролся на задачку) 8843 Complete the Set.

Честно говоря ничего в голову не приходит — судя по параметрам задачи — 1100 случаев в одном тесте, 65536 чисел в одном сете — полный перебор вряд ли пройдёт, я имею в виду каждое число с каждым пробовать по OR и AND пока не перестанут появляться новые числа. (хотя бы понятно, что в такой ситуации не надо пробовать что-то большее, чем пары чисел — уже прогресс от "absolute brute force").

Но в голове вертится одна из недавних задачек с Topcoder, где нужно было смешивать краски с помощью XOR и решалась она элегантно гауссовой элиминацией — может быть и здесь какая-нибудь хитрость?

Задачка не очень порешенная, "запылившаяся", решило её меньше 50 человек и разборов в интернете я не нашёл. Если знаете как решать, подскажите только идею — в какую сторону копать.

Большое спасибо!

  • Vote: I like it
  • +13
  • Vote: I do not like it