Hello everyone!

I am glad to welcome you on today round of Codeforces. I hope that recent color revolution and a more later time for start of round will make some variety into process of solving problems:)

An author of today problems is me. RAD helped me to prepare this round, Delinur translated statements into English.

Good luck.

UPD.

The round ended, ratings was updated.

Winners of div1:

1. Egor

2. tourist

3. unicef

4. sevenkplus

Winners of div2:

1. RainbowDash

2. cjtoribio

3. miraliv

5. majia5

Yippee!

Editorial.
mind it, he is no professional, but an (international) master :)

То есть профессионал - это человек, у кого много опыта!

По крайней мере, я имел ввиду это!

Just a reminder, a contest starting at 1:00am or 2:00am local time is really inconvenient for the people live in East Asia.

havalizasaid, but in normal rounds it isn't possibile to join as a teamwhat's worse!!

for an Australian...the contest start at 3:00 am local time ><!

That's why I like when the contest time vary a lot, like TopCoder. If it's not a good time for you today, it will probably be a good time in the next round.

But this is an international site right where most participant are outside russian. I think CF must anticipate contest time. most in Indonesia CF contest start at 10 PM and now it start on 12 AM.

tis the answer, then it's a prefix ofsand a substring ofs[1..len(s) - 1]. Moreover, each prefix oftsatisfies this condition. So one can find the longesttwith binary search: checking if one string is a substring of another (fixed) string can be done in linear time with hashing.tthat is also a suffix ofs. Again, linear time and hashing.I would like to see the solution without hashing that fits the time limit.

Edit. Especially I don't understand why KMR algorithm got TLE?

Egor

How do you make your own library in java

pofswhich are also suffixes, and examine whetherpappears in the middle ofs.It is solvable by KMP. You must count the length of the maximal prefix that is also a suffix for each position, let's say in table p. Then you are interested in checking if p[n-1] is also somewhere in the middle (if p[n-1] = 0 the answer is NO). To check this, it's enough to count the number of positions where p[i] = p[n-1]. If there is more than one such position it means that we have found substring somwhere in the middle. If not, then you must use the fact that another maximal prefix that is also a suffix is p[p[n-1]-1]. You check if it's greater than 0, if yes than you have your substring otherwise, the answer is NO.

nupside down"generated here

for(int i = 0; i < 1000000; ++i)

s[i] = (i%2 ? 25-i%26 : (i%26))+'a';

for(int i = 0; i < 1000000; ++i)

s[i] = (i%100 ? 25-i%26 : (i%26))+'a';

i think is really hard to optimise it, probably imposible :/

Does it have anything to do with optimizers ?

how can we recognize that the bath is going to be fulled? there is no data about bath size :?

vector<int>v[2000]

as you said... but the case is the same.

actually i was intended to have a map of the positions of the certain character that appears in the string. and whren i get char x at position i in the given string i do the followings:

v[x]<--i ; so i should need actually v[] of size 124. think problem is some where else.....

Thank you.

Thanks. :)