Yes, you can treat it as a normal Div. 1 + Div. 2 round.

probably the onsite contest will be held at the same time.

Try to do the paper in 1 hour :P

Like someone said it's probably held at the same time as the on-site contest, and different countries hold APIO at different times so it's hard to avoid anyway.

Yes

You truly are living on the edge! I wish I could be as bold as you...

Yes :)

Финалисты

i predict there will atleast be a question on dp.

I predict D will be a Graph problem as the two previous contests that made by zscoder !

I predict that problem A will be easy

Hi, esmoooooo.

yeah i saw too -_-

i didnt know someone already posted it or i would not have posted it....

And sepanta is blue now :|

He is too lucky to enter the same room with his another fake account !

i got it now

I glare on the statement. It looks so easy. Then I see success ratio. It is about 1./2. What a nice confusing problem!

456
123
answer?

B was easier if you looked for which height should you cut, in order to find a triangle of area i/max_area

binary search, but I'm sure there is some equation to solve it in linear time

I guess B is a pure mathematical problem. The k-th answer (indexed from 1) should be sqrt(k/n) * h.

O(1) solution using some geometry properties.

I think B was very easy math. You got lucky to solve C on first attempt, because it was little tricky — check the successful ratio — 659/1914. Anyway, nice problems, hope you agree.

You can compute Tan (a) =h/0.5, and then x*x*tan (a) =i*area., where I represents the first I triangle, and X is half the base of each triangle.

I had N^1.5*10, didn't passed 16'th test. But I hope it can be optimized in the way to pass.

xyz abc => answer is xcy

So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. If all chars from s1 are smaller then it would be easy, you would simply use a greedy to fill the word putting it at the leftmost position. Now, lets have the case where the elements from the first set are larger than the second. You would want to put your largest chars to the right most position, as that minimizes its penalty. So now in these case, you go from largest to smallest and put them in rightmost position. Same is true for the second player

My solution consisted in the following points :

• First, you can know which letters will Egor play, because, as he wants to minimize lexographical order, it's not worth playing its «worst» letters, i.e. he only plays his (n+1)/2 lowest letters.

• Same for Igor, who always plays his n/2 biggest letters.

• Now, suppose it's Egor playing : his goal will be to minimize the lexicographical order, and thus he wants the lowest letter to be in front. If he has got at least one letter with lower rank than one of Igor's letters, he immediately puts it in front, because it will give him a better score than if Egor plays a largest place instead at the front. However, in the rare case where all his letters are bigger than Igor's one, he wants to play at the back of the string his biggest letter, by a similar argument.

• Same for Igor : he will play his biggest letter at the front, except when all his letters are lower than Egor's, in which case he will play his lowest letter at the back.

Implementation isn't really hard, it's simply important not to forget to use sets to quickly retrieve lowest and biggest letters from each player.

i think graph should be linear line of compressed cliques and vertices of degree 1 and 2. i.e if deg>2 it should form a clique in combination to other nodes. else -1. but not able to code in time.

Edit: i got the mistake. it need not be clique.

B was easier if you looked for which height should you cut, in order to find a triangle of area i/max_area

After systems test is over for that particular solution I guess.

What is general idea for E?

Don't worry, he'll be banned =)

Give it a time :) It will work out itself

Probably, it checks how you process the case when min of Oleg equals max of Igor.

try this case abcxyzzzz zyxcbaaaa Each turn the string shouuld be - a???????? - az???????
- azb??????
- azby?????
- azbyc????
- azbyc???c
- azbyc??yc
- azbyc?xyc
- azbycxxyc

Basically the whole triangle's area is h/2. So, each the n parts' area should be h/2n.

So, for every cut i, you should find h(i) so that the resulting triangle has area i*h/2n. Note that if such a triangle has height h(i), that the base has length (h(i)/h). Therefore, you have to solve (h(i)^2) / 2h = i*h/2n, and the answer is sqrt(i/n)*h.

See above .many coders shared their idea!

I hope they follow same speed in posting editorials :)

dad

lol

the limits is 300000 but you set #define MAX 200001

When I submit it with GNU C++ 11 I get a RTE verdict on test 11 instead of a TLE verdict.

It looks like all successful hacks are made by cheater

What if Oleg puts b in 3rd position. It will become ??b. Then it obviously becomes aab

Oleg should place the 'b' in position 3. Then Igor has to put an 'a' somewhere. Whether it is placed in the first or second location, Oleg will put their 'a' in the other one, giving 'aab'.

Oleg will place 'b' at 3, and after Igor makes his turn ('a' at place 1 or 2, it is irrelevant), Oleg will place 'a' at last empty space. Answer will become aab, which is smaller than aba.