5 hours. 9-12. gyms are not rated

The words of wisdom. However, today the situation has been different. We moved the contest from our old system and we made a mistake copying samples from the pdf. Our solutions ran as there was no mistake.

And this year's competition are made with Polygon. We will write validators, so I hope that the contest will be much better.

I've solved C with a BIT.

You can solve C with segment trees.

I 'll assume that you now how segment trees work. The node that represents each interval is an array of 26 ( frequency of each letter in the range ).

You build the segment tree in a normal way: You store at the leaf a single character. For the parents you need to merge the two arrays of frequencies of the two children.

For the sort query: Sort the original string form [l, r] and then update the segment tree at those position from l to r.

For the query: You search for the intervals that are within [l, r] and return their frequencies.

Note: You do not need to use lazy propagation the sum of all updates is less than or equal to 10⁵.

Here is link to my submission: link

For G you should notice that 10⁹ + 7 is prime.Then instead of finding pairs ab = 1(mod10⁹ + 7) we should find b for the given a and check whether we have b in the list of the given numbers. The funny thing is that b is the reciprocal for a in the finite field and we can use extended Euclid's algo to find it (see e-maxx.ru/algo, as usual). Moreover for any a there is one and only one such b (because our module is prime). We count how many times each number is present in the given sequence, e.g. by having a hashmap of number to count. Then we iterate on all given numbers and for each we calculate min(count(a), count(reciprocal(a)) / 2. Sum of all minimums is the answer (we divide, because we count both (a, b) and (b, a) pairs).

You can solve it by the next way.

Let f[letter][i] — amount of symbols s[k] == letter for every 0 <= k <= i

Answer for query g l r is array cnt[i], where cnt[i] = f[i][r] — f[i][l — 1]

Let's try to sort s[l]..s[r] quickly Let's calculate how many symbols 'a', 'b', 'c'... is in [l..r] (f[i][r] — f[i][l — 1])

Then in s beginning from l there are cnt['a'] letters 'a', cnt['b'] letters 'b' e.t.c.

You can easily recalculate all f[i][l..r] by simply iteration from l to r

It's all:)

Of course, you can improve this solution, but during the training I didn't need it.

My solution: click

for C You just need use : sort (a+l,a+r+1) for s l r and print all between l & r in string!

My code: http://ideone.com/sp5hN7

Problem C is Easy, if We see it Easy :D

It is almost correct, just:

Find the maximum spanning tree with respect to the 'nr' (non-resistance) values, then find the minimal nr value for each of the target nodes for paths from the source node, then output those target nodes that has the maximum of those values with the minimum distance from the source.