Я решал 250 с прошедшего SRM'а неприлично долго, зачем-то вместо жадного решения писал перебор, но дело в другом. Я решаю обычно прямо в арене, поэтому написал примерно вот такой код: http://ideone.com/3KPBI (на самом деле, тогда код отличался от указанного тем, что закомментированной строчки в нем не было), сразу запустил его на сэмплах и получил на них на всех ответ "NO".
Я пару раз быстро просмотрел глазами весь код, ошибок не увидел и решил приступить к отладочному выводу. Для начала я решил добавить одну строчку - ту, которая закомментирована. Стал смотреть по сэмплам, какие тройки индексов у меня используются, увидел что почему-то выводятся не все тройки,... и случайно обнаружил, что код стал работать на всех сэмплах!
В итоге я решил не тратить время на то, чтобы разрешить этот парадокс, т. к. и так уже убил на эту халяву кучу времени, послал решение, и оно оказалось Passed System Test.
Попробуйте объяснить, почему, когда строка закомментирована, решение не проходит, а когда строка присутствует, то проходит. Подозреваю, что объяснение очень простое, попробуйте его найти не прибегая к отладке)
Я пару раз быстро просмотрел глазами весь код, ошибок не увидел и решил приступить к отладочному выводу. Для начала я решил добавить одну строчку - ту, которая закомментирована. Стал смотреть по сэмплам, какие тройки индексов у меня используются, увидел что почему-то выводятся не все тройки,... и случайно обнаружил, что код стал работать на всех сэмплах!
В итоге я решил не тратить время на то, чтобы разрешить этот парадокс, т. к. и так уже убил на эту халяву кучу времени, послал решение, и оно оказалось Passed System Test.
Попробуйте объяснить, почему, когда строка закомментирована, решение не проходит, а когда строка присутствует, то проходит. Подозреваю, что объяснение очень простое, попробуйте его найти не прибегая к отладке)
После добавления строк
template<typename T> class myvector : public vector<T> {
public:
myvector(const vector<T> &vec) : vector<T>(vec) {}
T& operator[](int id) { return this->at(id); }
};
и замены vector<> на myvector<> на сервере решение получило YES. Т.е. выходов за границы массива нет. Это напрягает - обычно дебаг вывод мешает ловить именно такие приколы.
Скорее всего это потому, что на topcoder-е юзается очень древний gcc (плюс, разумеется, с патчами от redhat). Я уже сталкивался с тем, что вполне безобидный код у меня локально на последнем gcc и у них выдает разный результат.
И почему ни на одном известном мне online-соревновании нельзя при отсылке указать ключи компилятору? Вполне возможно, что в описанном случае с -O0 вместо -O2 заработало бы.
P.S. Вообще это лучше обсуждать на форуме topcoder-а. ;)