Спасибо за доверие) див.1 тоже бывали несколько раз совместно с другими авторами, однако див.2 раундов действительно больше и их несколько проще подготовить)

спасибо, в след раз в личку)

hah, good luck and have fun!

Too bad you did not show up :D

I'd also like to raise similar question. This is third CodeForces round for me. Each time it was 19:30 Moscow time. Apparently when people from all around the world participate it is impossible to always choose time which is convenient for everybody. Some other platforms try to rotate timings so that different rounds are more or less convenient in different time zones.

So the question is — Does Codeforces always conduct rounds at 19:30 Moscow time? If so — will it change at some point in the future? or is it conscious decision because the platform is Russia-based? Still, even for Russian cities — like Vladivostok — 19:30 is hardly convenient.

Agree!

I eat banana 3 minutes before the contest. So have to eat two bananas if it is postponed by 10 minutes :) If they ever do postpone it several times, I might not be able to participate.

yes. there was one, but later removed. :(

kursatba324.c:2:55 Error: expected ";"

TO everyone

Я буду по своей обычной (A -> B -> C -> D -> E -> ой, поломали CDE -> ой, AB не прошли системное тестирование). Удачи!

No Problem, ratings are not important What you will achieve is important ;)

Интересную? Ух ну и вкусы у людей)

Мне тоже буквально двух минут не хватило!

Нужен суффиксный автомат с учётом количества вхождений. Ну и z-функция для проверки. Прогоняем всю строку по автомату, на каждом шаге проверяя с помощью z-функции, подходит ли нам этот префикс.

Прошла z-функция + бин. поиск.

Problem D is about suffix structure? I never code a suffix structure before. I just know KMP:(

I think it was simple dp. But maybe i am mistaken an nlogn one.

Suffix machine gives O(n) solution.

My O(n log^2n) Suffix array solution got AC 6626473

The answer should only consist of A,B and C. If your anwser has letter D or others your solution is 100% wrong.

Oops I found my presumption was wrong

The main idea of the problem is greedy, while you have to check for three sides(up,left,right) when enlarging the square

Hi, Could you please explain your solution of E?

Thanks in advance. :)

За квадрат

while (!z.empty() && !z[0]) z.erase(z.begin());

OK

Philosophically thinking this is almost exactly the same situation as if you just left your solution to be crashed by pretest. So take it easy.

3 6
AAABAA
AAACAA
AAABCB

Или даже так:

10 6
AAAAAA
AAAAAA
AAAAAA
AAAAAA
AAAAAA
AAAAAA
BBBBCB
BBBBAA
BBBBAA
BBBBCB

Вот тест вроде ломает. 30 31.

мой алгоритм такой же (и тоже падает на шестом тесте) и падает на тесте: 6 4. Выдает: AAAA AAAA AAAA AAAA BBCC BBCC , хотя две последние строки должны быть по идее BBCB BBAC

Я правильно понимаю, что нужно заполнять A наибольший возможный квадрат, ставить рядом с ним цепочку BCBC...BCB и переходить к меньшей задаче?

Not really Goldbach conjecture i think. It's just construct minimum prime partition of a swap-range

Yes, with this theory we can achieve at most 3n operations.

It always took more than an hour!

Most likely this submission was not your final solution. Meaning later into the round you resent submission for this problem. When you resend submission for you problem, all previous submissions are "skipped". Seems that your new solution was wrong, while previous one was correct. Bad luck.

If this is not the case, then you probably should contact admins.

I calculated Z-function for the string s (but z[0] = n). Then I found all the prefixes coinciding with suffixes ("necessary" prefixes), i.e. stored all their lengths in set V (I mean all values of z[i] which were equal to n-i). Besides, I stored the number of occurences of each value of z[i] in a map C. Then I calculated the number of occurences for each prefix. Here is an example: let C['ab'] = x1, C['abc'] = x2, C['abcd'] = x3 ... => # of occurences of 'ab' is equal to the sum of occurences of bigger prefixes (x2 + x3 + ...) + C['ab']. We can calculate this with O(n) complexity. I also created a map M, where I stored the number of occurences of "necessary" prefixes, and outputted all its contents.

problem c was simple , for each number i= 1 to n , swap the number to greatest left position such that length of swap is prime , start from (pos-i+1) search nearest prime , repeat down till its sorted position is obtained

Simply, you can follow an optimal strategy which is :

for every i from 1 to n swap the element which has the value i with index j;

index j is the closest element to i whose distance to the element with value i is a prime number

in other words you have to find the maximum prime number which is not larger than distance between the index of the element which has a value of i and index i

binary search is the best way in my point of view

according to Goldbach's_conjecture complexity will be at most O(5 n log(n))

here is my AC code 6629271

I know two solutions for problem D.

The first one is based on Z-Algorithm. If you compute Z[i] — largest substring starting at the i-th position, which matches with the prefix of the same length, when you have a prefix which matches with the associated suffix, you have to count how many values of Z[] are >= the length of the current prefix.

The second one, a bit harder than the first one, is based on KMP (Prefix function) and hashing. First of all, you have to compute for each prefix and each suffix their hashcodes. If you compute Prefix[i] (from KMP) and consider a tree where edges are from Prefix[i] to i (nodes are labeled from 1 to N), you can find Nr[i] — how many times does the prefix [1..i] match with the entire string by counting how many nodes are in the subtree rooted at node i.

Here is the code which computes this:

for(int i = N; i; -- i)
{
    Nr[i] ++;
    Nr[Prefix[i]] += Nr[i];
}

Now, if you find a prefix which matches with the associated suffix (by comparing their hashcodes), you know the answer for that prefix :)

I used KMP. We can easily calculate, for each prefix of length i, the second longest prefix which matches it (is its suffix); its length is prev[i]. Then, we can calculate the number of times P[i] the prefix of length i appears in the string: a bruteforce would iterate j=prev[j] starting from each and increment each P[i] encountered, but it can be simplified by iterating i from N to 1 and adding P[i] to P[prev[i]] (it basically processes all iterations j=prev[j] at once). Counting prefixes which match a suffix is even easier: these are the ones which are iterated by j=prev[j] starting from j = N.

Because of trivial approach in Z-function. It goes in O(n^2). Here is AC verdict for your solution with modified Z-function.

Your simple Z algorithm really runs in O (N^2), which is not fast enough to pass the time limit under the given problem constraints.

We don't need binsearch actually: 6637149 And no magic, small observation: if we have substring with L length X times, we also have additional X substrings with [1; L-1] len. Too bad that i didn't write solution correctly on contest.

P.S. Sorry for my bad english.

Nice explanation. You can consider the prefix sum instead of binsearch to make it O(N)

6637312