It's out of my hand :D and always I sleep during contest

achievement failed! :(

Посмотрим 2 соседних позиции в суфф массиве. Пусть это a и b. Тогда если a + 1 стоит в массиве раньше, чем b + 1, то мы можем поставить на эти позиции одинаковые символы, а если нет, то обязаны поставить разные. Ответ — сколько раз надо поставить разные + 1

If you notice the trick — medium is obvious. If you do not — you are screwed. And coding is not really much harder for 250

It depends. I found that 250 was pretty straightforward and came up with the right approach right after I finished reading the statement. The implementation might be a bit trickier than usual, hence it could be set as 275 or 300. For 500, I struggled to find a decent solution and gave it a try with a fairly naive one (keep decreasing the elements if it's still possible). That makes 500 the harder one for me.

(btw, I assumed that nodes were numbered from 0 to N - 1, which resulted in a resubmission and very low point for my 250)

if you are right, why only 92 user have solved 500 div1, and 192 person solved 250?

There is bug with challenges too.

http://community.topcoder.com/stat?c=problem_solution&rm=323312&rd=16061&pm=13287&cr=22913297

In fact "find the lexicographically smallest string", "is that string lexicographically smallest", "how many different characters do we need" can be solved by same way.

I don't know which one is easy and which one is hard, but there is one reason for using "is that string lexicographically smallest" as Div2-Hard: the algorithm "change one character (decrease by 1 if it is not 'a') and check if the SA remains same." can pass, and I thought some people can come up with it.

Try every subset of nodes (backtracking) and check if they meet the condition.

I guess it is 2-sat ...

The official solution involves 2-SAT, however there was another brute-force-like solution, which passed system test and was working several times faster than the intended one on all test cases we've tried. Unfortunately, we don't know neither how to prove it or how to break it. I think cgy4ever can describe his 2-SAT solution better than me, so I'll describe mine. Maybe someone can prove it or provide a counterexample.

The idea is quite simple. Let's maintain the minimum and maximum possible value for each variable. At the very beginning they are [1, 100] for all N variables. On each step of the recursion we do the following:

1) Output the answer if all intervals have length 1.

2) Repeatedly try to shorten each interval if its ends are conflicting with some other intervals. Stop when we can't change any interval without making any assumptions (i.e. we cut intervals' ends only if we know they conflict with other intervals without making any guesses and going deeper into recursion).

3) If after the previous procedure some interval has length 0, go out of the recursion.

4) Take any interval that has length greater than 1 and try to fix the corresponding variable's value (i.e. iterate over all values from its interval). When we fix it's value to X, replace its interval by [X, X] and make recursive call (i.e. go to 1).

5) Output {} if the recursion didn't find any answer.

The reason why I think it works is following. I tried to run it against a lot of random test cases and couldn't find any single one where we should go out of the recursion at least once (except for the ones in item #3 in the list above). That's why I suspect it makes exactly N recursion steps and on each one it fixes one variable.

UPD: I've submitted it to the practice room and its maximum running time is 68ms.

Yes, the intended solution is 2-SAT.

For each x[i], we add 99 variables to the 2-SAT system: (x[i]>=2), (x[i]>=3), (x[i]>=4), ..., (x[i]>=100). And we have: (x[i]>=100) -> (x[i]>=99), (x[i]>=99) -> (x[i]>=98), ...

Then what is amazing is that all conditions can be described in this 2-SAT system. For example if we have x[1] * x[2] >= 50, then it can described as (x[1]<2) -> (x[2]>=50), (x[1]<3) -> (x[2]>=25), (x[1]<4) -> (x[2]>=17), ....

And you need to think about how to handle these 20 different cases: 4 operations * 5 relations.

No, that need some insights, but you don't need to know some advanced knowledge about suffix struct.

Suppose we know that the rank of each suffix of string S is {2, 3, 0, 1}, then we know s[2]s[3] < s[3] < s[0]s[1]s[2]s[3] < s[1]s[2]s[3]. Thus we know s[2] <= s[3] <= s[0] <= s[1].

Now we need to know if we can set s[2] = s[3] (and something like s[3] = s[0] and s[0] = s[1]): we must ensure s[2]s[3] < s[3] still holds, that means we need s[3] < "" (or, suffix[3] < suffix[4]), that is not true. So we know s[2] < s[3]. Also we can know s[3] can be equals to s[0] since suffix[3+1] < suffix[0+1].

After that we can allocate letters into s[]. s[2] = a, since s[2] < s[3], we set s[3] = b and so on.

And now you can see why that one line of code can work.