Hello, guys!

I invite you to take part in the last year's competition which took place in Kaunas University of Technology and had participants from three different Universities in Lithuania.

The best participant was selected to KTU #1 (the 30th place in the last year's ACM finals) and other top KTU participants were selected to KTU #2 and KTU #3 teams.

Moreover, some of the hardest tasks were used in the preparation for IOI competition.

The contest is scheduled on Saturday, Sep 20, 2014, at 12:00 PM.

As the contest has three stars of complexity, it may be very interesting for Div. 2 participants, but I don't recommend it for Div. 1 participants and those who already participated in the contest.

All kinds of feedback are gladly accepted, as this contest is also a dress rehearsal for this year's KTU qualification round which is prepared with Polygon and will be made public for all Codeforces participants.

Enjoy the contest!

Solutions written by the authors of the problems:

**All problems have been fixed**

What is duration of this contest

How long it lasts ? how many problems ? is it rated ?

5 hours. 9-12. gyms are not rated

>> KTU qualification round which is prepared with Polygon>> the sample test case in the system was incorrect, as a result, this task was ruinednot writing validators is harmful

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.

How to solve C and G?

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

^{5}.Here is link to my submission: link

thanks

For G you should notice that 10

^{9}+ 7 is prime.Then instead of finding pairsab= 1(mod10^{9}+ 7) we should findbfor the givenaand check whether we havebin the list of the given numbers. The funny thing is thatbis the reciprocal forain the finite field and we can use extended Euclid's algo to find it (see e-maxx.ru/algo, as usual). Moreover for anyathere is one and only one suchb(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 calculatemin(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

This shouldnt pass or the testcase is weak coz there is nothing said about the limit of g operation and it might be up to 6*10^8 which is alot !

Actually no, there was a note down there saying that all the sum of r — l won't exceed 1e5 so in other words you will sort the whole string only once no more in the worst case.

I also missed it at the beginning.

m

What is the idea behind E (Magical Code)?

What's the idea to solve problem D? I tried this way : Find the maximum spanning tree with respect to the 'nr' (non-resistance) values, then find the maximin 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. But it results into WA.

It is almost correct, just:

Find the maximum spanning tree with respect to the 'nr' (non-resistance) values, then find the

minimalnr 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.Sorry, I actually meant that. After getting the maximum spanning tree, I find the minimum nr value on the path to each target node, which is the maximin path value for each target on the initial graph. Here is my code: link

Can E be solve by dynamic programming?If so then what is the approach?