Вчера немного поспешил с числами.

(1 << (20 / 2)) * (1 << (20 / 2)) = 1024 * 1024 = 1048576
((1 << 20) / 2) * ((1 << 20) / 2) = 524288 * 524288 = 274877906944
274877906944/1048576 = 262144

Так что перебирается не в миллион раз меньше комбинаций, а 250 тысяч :)

Впрочем, суть ошибки это не меняет. Кстати, если её исправить, возможно проявится другая проблема с тестов. Вернее, выяснится, что он работает слишком медленно и его надо переделывать.