^Very True.I also think that the solution should be opened for all to see and learn new techniques.Please see if this can be done.

I agree with you! It will be very useful for many programmers, if the solutions of all participants will be available after you've finished the contest.

I think soooo

Gym contests are unrated.

Thanks a lot for you and your teammates! It was really good contest — well-prepared and interesting. Also I'm sure it is right policy to share contests with community.

Hope, it could be a good tradition to use local contests for public trainings.

K

Since P = product of primes, it can have at most 2^7 divisors (when P = 2*3*5*7*...). Thus you can do dynamic programming with state (how many number used, divisor of P).

G

It is data structure problem. You need to maintain which person is standing and how many pairs using some data structure. It's quite hard to explain in words. You can see code of ntu_tst_004

L: let's generate graph of alphabet by edges from input. It's obvious that this graph is some numbers of cycles. Let's look on first character of our text, call this character s0. We must change it to lexicography best character. Let we change it to some other symbol — obvious that this symbol must be the best lexicography symbol in cycle which contain s0. Let this symbol is placed d0 symbols after s0. Than X = l0*k0 + d0, where l0 — the length of cycle which contain s0, k0 — some number.

Let's look on i-th possition. Tryed to place different d[i], we must choose such that system of equations l[i]*k[i] + d[i] solvable and this d[i] best lexicography. How to check if solvable? Prefix of system of equations [1..i-1] solvable, we must check that last i perhaps for first [1..i-1]. Check it: solve this system l[j]*k[j] + d[j] = l[i]*k[i] + d[i], it's diophantine equations.

I hope that you understand our solution:)

the problem E require more precision geometry

If they open solutions, standings will be spoiled by solutions with less than 1 minute. I know that some people aren't bothered with that stuff, but some ARE.

Try to enumerate answers for little sizes. Then you will seen some interesting things with sum of elements)

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

Наблюдение: Если есть отрезки которые полностью содержат другие отрезки, то их можно выбросить и больше не рассматривать. Так как если есть оптимальный ответ, который содержит какой-нибудь подобный отрезок, то его можно заменить на более мелкий(который содержится в нем), от этого хуже не станет.

Утверждение: если мы знаем про какой-либо отрезок, что он содержится в оптимальном ответе, то набор отрезков, которые входят в этот ответ можно набирать жадно, начиная с текущей по часовой стрелке.

Алгоритм: перебирать все отрезки, а потом начиная с них запускать жадный алгоритм, может не уложиться по времени. Поэтому можно заметить, что нам можно жадно брать сразу кучу отрезков, а не один, пока хватает длины окружности. Для каждого отрезка сохраним какая длина нам нужна если мы возьмем жадно 2^k (для каждого k) отрезков начиная с текущей. Теперь мы можем для каждого отрезка за логарифмическое время найти максимальное количество отрезков, которые мы можем взять (прыжками по степеням двойки, подобно алгоритму нахождения lca двоичным подъемом).

Еще можно так решать (доказывать решение не умею):
развернем 2 цикла отрезков, т.е. возьмем помимо отрезка [L, R] еще и отрезок [L+M, R+M]. Для нового набора отрезков решим задачу жадно. Теперь пройдемся двумя указателями по решению, находя лучшее решение, начинающееся с каждого из выбранных отрезков.

I wrote a partial one. here