Hello everyone!

I am glad to welcome you on Codeforces Beta Round 94. I hope, some more early time of start will not have bad effect on you results =)

I'm author of today problems. I'm a graduated student of SPbSU, Valery Samojlov. This is my second round. I hope, today nobody will be sorry of his participation. I want to say very big thanks to RAD, who rend me very big support with preparation of problems. Also thanks to Maria Belova, who has translate statements to English.

Please, don't be startled of unusually cost of problems:

Div-1: 1000 - 1500 - 1500 - 2000 - 2500

Div-2: 500 - 1000 - 2000 - 2500 - 2500

It's a comfortable time for me, 2PM in China.

I code better at night. =D

Every night,my school will cut down the power at 23:30.

I always take the contests in the dark.

Delayed 10 minutes?!

I have college after it ends with 30 minutes, now it become 20 minutes :\ Hope I could make it on time!

Very nice problems!

A good point of the contest was brief problem statements.

http://codeforces.com/contest/128/submission/870700

I agree.

Idea is to use a priority queue. For example

abc, 5. You will do the following:

Push ("a", 0), ("b", 1), ("c", 2) on the heap. You will then pop the first element ("a", 0). Because 0 + 1 < size (3), you now push ("ab", 1) on the heap, and so on.

Do this k-1 times and the top most element of the heap is the sought after substring.

This gets AC. I'm not sure if you can construct a test case in which the comparison for the heap will make it too slow. I tried with aabbbbb...b and 10000, which should be very bad because all comparisons will be strings like aabbbbb and aabbbbbb, but it ran way fast enough.

Any ideas in problem D?

My approach is greedy. First, create a circle min, min+1, min+2,...,max,max-1,max-2...,min+1. Then check if it's possible to pair the rest numbers such that every pair consists of consecutive numbers since these pairs can be consistently added into the initial circle.

I liked this problem enough to write a blog post about it: http://codeforces.com/blog/entry/3196. It has a "proof" for a greedy solution similar to what you describe. Hope you find it useful!

There's a solution if the histogram is a sum of histograms of overlapping circles.

You can modify the circles greedily until each one is empty: Pick one the circles on the left side. Remove two pieces of the circle so that the min value is increased by one. In the histogram, it means removing 1 to the two leftmost bins. That's implemented in this solution .

My gredy solution works as follows:

let a1, a2 be the value of the biggest and second biggest value (without duplicates). Let c1, c2 be their associated counts. If c2 >= 2 we can "merge" an a1 with two a2s creating a segment: a2, a1, a2. This can now be seen as one a2, so we decrease c1 and c2 by one.

The base case is when a2 is is also the smallest value (only two values). In this case c1 must be equal to c2.

At all points we must have a1 - a2 = 1.

The Div 2 D.string

I use STL heap.

This is my code,it got TLE

If turn to this can AC

it really have big difference？

Is construct function make it slow,or access top()，or else？

^{2}/ 2.I know this is an ancient comment but could you tell me how is it O(n+k)?

for a test case like "aaaaaa..." wont it run in O(n^2)

nand want to pickkintervals each of which is strictly contained in the previous one. The number of ways to do this is justC(n- 2, 2k) because for any choice of 2kvalues in the range [1,n- 1] we can take the min/max to be the first interval, next min/max to be the second interval, and so on.I still don't understand your explanation, can you make it more clearly? First, why the two dimensions are independent. Second, why is C(n-2,2k), where comes the 2k?

n], [1,n- 1], ...m], [2,m- 1], ...ksteps, respectively. So the first box is obviously (0, 0) to (n,m) and the second is (1, 2) to (n- 1,m- 1). We observe that for any two sequences of the left/right bounds and top/bottom bounds we get exactly one sequence of boxes. It suffices then to count the number of such sequences and multiply them together.n], [1,n- 1], [3,n- 2], ... and rewrite it "in order" like this: 0, 1, 3, ...,n- 2,n- 1,n. We know that 0 is always at the start andnis always at the end and there are exactly 2kvalues from 1 ton- 1 (two for each of thekintervals). Moreover, for any 2kvalues in [1,n- 1] we can uniquely construct thekintervals by taking the outermost values to be the first interval, then the next outermost to be the second, etc. For example: 0, 3, 4, ...,n- 3,n- 2,nbecomes [0,n], [3,n- 2], [4,n- 3], ....kvalues in the interval [1,n- 1] of which there areC(n- 2, 2k).There's just a slight mistake in your formula. It is supposed to be

C(n- 1, 2k) since there aren- 1 different values in the interval [1,n- 1].I've submitted the same code for problem D Div.2 with both MS C++ and GNU C++. First one gets TLE, while the second one is accepted! Is there a point I'm missing here?

Tourist's solution on div1 problem A?

You can use DP with state x, y, #moves.

You win iff you can survive 8 moves.

Then for each mem[x][y][cmove] you need to check if there's a rock in the cmove places above (it would move on you, so you die) or if there's a rock cmove-1 places above (it would be there when you tried to move, so invalid move).

is_{reachable}(step,x,y) the following way: if now we are at stepSand in point (x,y) your simply check if the point (x+dx[i],y+dy[i]) is free of statues and no statue will move there after this step ( can be calculated inO(1). After all, if anyis_{reachable}(8,i,j) is true, you win, otherwise you lose.Looking at your code, i see suspicious line int xx = sum[t][i]. May be problem is there.

If there were only one banana, then the answer would be 1 + K * (K+1) / 2 (it's easy to construct such a placement of lines, where each line intersects all previous, and all intersection points are different).

Now suppose we have several bananas.

If there is a line that intersects all bananas (intersects, but not touches), then the answer is 1 + K * (K+1) / 2 + (K + 1) * (N - 1). This formula means that we take an answer for one banana, and we cut all the remaining bananas by K lines into K+1 parts (because all intersection points are situated in the first banana). Why is it optimal to put all intersection points into one banana? Because each intersection point adds +1 to answer, so we've already achieved theoretically maximum possible value.

So, the problem is in reality the following: given N circles, determine, how many of them can be intersected using one line. I've solved it in O (N^2 log N) in the following manner: we suppose that the line touches one of the circles (we iterate over all N of them), so the position of the line can be described as polar angle. So any other circle can be described as an interval [angle1; angle2), where angle1 and angle 2 are the angles, when our line touches this circle. (We exclude the right end of the segment, because we don't want to find an answer, were a line touches several circles, but can't be made to intersect all of them.)

So, the algorithm now is to find the point with maximum number of intervals covering it, which can be done in O (N log N).

when will the editorials come out.Waiting for it desperately.....

in russian, it is there - http://codeforces.ru/blog/entry/3219

Some hint for Problem B Div 1 with Suffix Array? I am dead!

my submission using suffix array

Solution for Div1 B, please?