Fixed :)

где это? :-D P.S. Fixed.

ахаха Увы, вы не правы :)

Суровая ситуация... Компилировать, кстати, можно и на стороннем online-judge. Например, acm.timus.ru

ideone.com? Только главное галочку "частный" не забыть поставить, дабы код не палился ;)

dp[pos][end] — количество подпоследовательностей t, оканчивающихся не правее pos, у которых последний символ — это s[end]

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

ans+=cur[i];
cur[i+1]+=cur[i];

d[i][j] — сколько есть подпоследовательностей/подстрок, которые в S заканчиваются на i-м символе, а в T — на j-м. Пересчет:

d[i+1][j] = 
{
d[i][0] + ... + d[i][j-1] + 1, если S[i+1] == T[j]
0, иначе
}

Чтобы делать быстро, насчитываем суммы на префиксах. Почему переход именно такой? Мы пытаемся добавить по символу к каждой из подстрок меньшей длины и добавляем в ответ строку из одного символа.

Сам придумал ближе к концу контеста, в связи с чем мне очень стыдно.

Не забыли по модулю взять?

возможно, потому что решение неверно ?

Суфф. ссылки у Ахо-Корасика вроде дерево образуют и тогда можно ее решать как тривиальный боян... вроде бы..

Ну эта информация в открытом доступе. Почему нет?) Я, иногда смотрю на чем задачу сдают мои товарищи, потому что если на Java, то в ней нужны BigInteger'ы)

Думаю, если бы вы всем не рассказали, то у вас было бы меньше конкурентов:))

А если серьезно, по-моему вполне нормальное использование лежащей на видном месте информации

Я как раз сегодня тоже обнаружил это. Нашел в статусе, сколько памяти занимала E у tourist, убедился, что карась с несжатыми ссылками.

мне видимо повезвло, но у меня прошло без eps

1. Не используем eps
2. ???????
3. PROFIT!

Yeah, thanks for the speedy tests!

Да, давайте начнём их искать... я 179...

У меня такое же решение. Прошло.

у меня на 37 это упало...

Надо было использовать long. Просто все умножить на (v1+v2)

Я использовал для сравнения точек long long, только при счете вероятности для подсчета длин отрезков использовал double. Жалко, в одном месте написал границу массива 4*n вместо 2*n, и рантайм эррор 17)

yes, now system is in safe mode

This isn't even a problem from this contest :/

for 10^9 iterations only 10 ms. Looks like compiler is optimizing the loop into a single statement. Modern days compiler are so smart.

Эм, так wildcard же будет. Или всё, что не по правилам acm или codeforces, вы не решаете? :)

Вообще, задачи с точностью 1e-9 у меня тоже вызывают внутренний протест ))

Я в очередной раз повторил свой тупой подвиг и ошибся в решении ровно в одном символе (100 -> 200 итераций), так что да стремненько (хорошо хоть прошел)

O(n^3): You have O(n^2) states and O(n) moves from each state.

Also, you can try launch your solution with n = 1000 and n = 2000 and measure running time. Is t2 / t1 = 8 -> O(n^3)
t2 / t1 = 4 -> O(n^2)

It's O(n^3).

Вполне нормально, ИМХО.
Больше 1000 они не стоили. а в 2 раза различать — ну как-то нехорошо.

ВОТ, я даже вопрос отсылал жюри, они сказали без комментариев. Я такие решения успешно хакал таким тестом: 2000 1 1999 1..много единиц..1 1000000000 Я так 3 штуки взломал, странно, что после системного тестирование такие решения проходят!

У меня вообще мое решение не проверили :)

Hm... You could never use all elements. In 2nd test from statement we never uses element.

Input:
987
1234567

Output: 987 ~~~~~

I think the difference between "allowed to use not all" and "not allowed to use all" is pretty clear.

This is not ambiguous at all.

But I made too many iterations and got TL :)

Yes, I made 50 while 80 was enough. There should be an option to change 1 byte of the solution after the contest ;)

И когда по мск выложат задачу.

It's rational number.

ja = Jury answer, pa = Participant answer

ja = jury's answer, pa = participant's answer

Ну 10^9 быстрых операций, не лезущих рандомно в память проходят иногда.

возможно оптимизации компилятора

maybe yet another g++ bug?

UPD: Works in MSVC++.

Isn't it obvious from what you are printing :) ?

because judge system loves Mike Mirzayanov too)

This happens because of a precision problem. GCC actually compares 80 bit doubles instead of 64 bit, so if you don't add an epsilon they don't compare to equal. The reason why it works with printf is a little more complicated and has to do with the cache being cleared up when you call the function.

More info here: http://apps.topcoder.com/forums/?module=Thread&threadID=440256&mc=26

EDIT: look at this 1417682

Да и opencup незачётный.

http://codeforces.net/blog/entry/4187?locale=en

There is a difference between phrases:

"You are allowed to use not all elements from S"

and

"You are not allowed to use all elements from S"

If you are allowed to do something, it does not mean that you are not allowed to do the opposite.

I also made the same mistake and when I tried to convey the ambiguity above, I got a lot of negatives for my comment. I think the statement was very complex to understand in the contest environment and could be explained in a better way or with a simple test case.

Мы не на ТопКодере.

Хотите рейтинг повыше, или как? :)

Тот, кто выбирает "сабмитим", знает, на что он идет.

Полностью согласен. Знаю некоторых людей, которые любят вообще не делать сабмитов, если задачи не понравились. Ведь вроде и участвовали, и ничего не решили, а в пересчете рейтинга не учатсвуют. Имен называть не буду — боюсь получить по своей плюшевой голове плюшевой лапой.

Especially for you. http://codeforces.net/blog/entry/4187

The announcement section says, "All Round 3 contestants will receive VK Cup T-Shirts". So I think you should participate ( or at least register (?) ) in round 3 to receive T-shirts. Admins, please confirm !