There is a well known algorithm of searching the largest common subsequence of two sequences with lengths N and M in O(N·M) time: Link to the algorithm description

But I've recently heard there is some technique that allows to reduce time if one of the sequences is short enough and works in O(min(N, M)² + max(N, M)). Does anybody know how to do it?

Why the post about CF Round 421 was closed after found bug in tests for task A1/C2?

Hello, guys!

Today in Codeforces round 402 (Div 2) I tried to challenge this solution with a test:

5 2
1 1 1 1 1
5 5 5 5 5

So, as you can see in the code this cycle has no any check for reaching the end of the vector "v":

...
while (v[j].first<0||j<r)
{
sum1+=v1[v[j].second];
j++;    
}
...

Obviously "j" will be out of the vector for such testcase and we will check whether "v[5].first<0" or not, but no any Runtime Error when trying to get nonexistent element of vector. So, as you can understand, challenge was unsuccessful. Why?

Здравствуйте!

Подскажите, пожалуйста, если кто в курсе, где можно посмотреть код такой реализации Дейкстры, у кого-нибудь есть ссылка? Насколько оправдано применение Фибоначчиевой пирамиды на практике? Т.е. заметно ли ускорение по сравнению с реализацией Дейкстры с обычным heap-ом? В теории понятно, что O(E + N * logN) лучше, чем O(E * logN), вопрос насколько велика скрытая константа.

Спасибо!

Seems like during all of the day (26.06.16) TopCoder web-interface login not works (i.e. I could not login in "https://www.topcoder.com/login/"), does anyone has the same issues?

Arena Java-applet still works fine.

Good luck for everyone in 347 round again ))) It will be based on last 347 round problems :))

Здравствуйте!

Подскажите, пожалуйста, если кто в курсе, почему так долго нет SRM на топкодере? И в расписании пока пусто, что в июне, что в июле, в плане SRM.

А нельзя уже сделать как на топкодере, контесты в разное время? Я, конечно, понимаю, что основной контингент хороших программеров России обитает в Питере, Москве, Саратове, и им удобно, когда контест начинается в 19-30, 20-00 и т.д., но чем восточнее город, тем решать становится сложнее, и реально не прет решать задачи на ночь глядя после рабочего дня и ещё 4-5 часов ожидания. Просто сложно нормально выступить, даже если ты неплохо кодишь.

Привет, Codeforces!

Меня зовут Олег Василенко, я работаю в компании 3DiVi — стартапе, который занимается решением задач компьютерного зрения. Мы решили провести небольшой контест, состоящий из одной оптимизационной задачи на поиск ближайших точек с символическим призом в 5000 рублей за первое место.

Подробности здесь: http://www.3divi.com/rus/index.php/contest

P.S. Это наш первый опыт проведения соревнования по программированию, поэтому просьба сообщать о найденных проблемах, предложения и замечания также приветствуются.

Обнаружил не так давно одну интересную проблему с компилятором Microsoft Visual C++ 2010.

Посылка № 4997092 на "acm.timus.ru" от 2 июня 2013 по задаче 1542 получает "Wrong Answer" на первом тесте на компиляторе Visual C++ 2010 и получает Accepted на всех версиях G++.

Я попытался выяснить, в чем проблема. В решении был фрагмент кода:

...
    for (int i=1; i<=k; i++) {
        sch[i] = find_max(a,b);
        update(sch[i], -1);
    }
...

где функции find_max() и update() — для работы с деревом максимумов. С таким фрагментом — "Wrong Answer 1" (на Visual C++ 2010).

Однако! Если добавить никогда не выполняющийся "if" или просто сделать какое-либо действие с sch[i], то получается "Accepted":

...
        for (int i=1; i<=k; i++) {
            sch[i] = find_max(a,b);
            
            if (sch[i] < 0)
               printf("ha-ha-ha"); // if никогда не выполнится (а если бы выполнился,
                                   // то тогда всё равно WA должно быть, а не AC) 
            
            update(sch[i], -1);
        }
...

См. посылку № 4997093 от того же числа.

Как это объяснить? В голову приходит только мысль о том, что оптимизатор Microsoft Visual C++ 2010 просто подсчитал один раз значение функции find_max(a,b) и использовал в дальнейшем его, не вызывая функцию на последующих итерациях цикла, что является неверным, т.к. find_max(a,b) использует дерево tree, изменяющееся в вызовах update(sch[i], -1).

Может быть, есть возможность изменить параметры компиляции, чтобы такого не происходило?

Примечание 1: в ключах компиляции стоит 2-й уровень оптимизации, даже не 3-й. Вроде бы не должно тогда такого происходить.

Примечание 2: на Codeforces такая ошибка тоже проявляется.