So we should say thanks to Zlobober :)

For some reason round writers never thank themselves..

Since the last contest, div2 were waiting the same amount of time

I am div2,and I am proud.I want to become blue gay!

daiyu.

actually Good Bye 1393

happy new year! :D ( 4 shanbe sooriam hast :-P )

Done, thanks.

All non-russian-speaker codeforces users became to know that "и" means "and" so there's no problem

Your user name and the way you comment sounds fishy. But I'll just let it slide.

what is difference between div 1 and div 2?

Hey, what are FAQ for?

lets define function F — number of different characters between two strings, then we could do something like that:

difference = F("div1", "div2") // should be 1

We'd better use English -_-#

More information can be found here

you can register now

registration is still open.

You still have time to register because of the delay

wow, thanks God

Nope, their fault i can't wait anymore

This was an old message , MikeMirzayanov forgot to change it back to "codeforces is temporary unavailable"

you're lucky :-)

Let's reverse a problem:

Points a and b are connected only if distance between them is smaller than sum of their weights.

In this case, we can imagine one point as interval [x - v, x + v].

When two intervals overlap, corresponding points are connected.

To find a result, we need to find the largest subsets of intervals that are not connected (in original problem — the largest where every two are connected).

Why do we need reverse problem? Because it makes everything much more easier. Every point correspond only with one interval (in original problem — with two) and simple sweep from left to right will do whole job.

First of all, if x_a < x_b < x_c and a connected to b and b connected to c then a connected to c, so if we have connected sequence of points it's a clique. Now we should find largest connected sequence of points. Let us consider the points with weights as segments with length as two weights and centered in point. We are looking for max set of non-intersecting segments. Here we get events: starts end ends of points. Sort them and go from left to right. When segment starts, answer for this segment (size of the max set of non-intersecting segments from segments from most left segment to segment under review) is max from already closed segments plus 1. It's just a variable, which is updating then segments closes. 10322276

Sort the point by the coordinate. Consider 3 points i, j, k (i > j > k). If there are edges (i, j), (j, k) then there'll be also edge (i, k). Because:

x[i] - x[j] >  = w[i] + w[j]

x[j] - x[k] >  = w[j] + w[k]

 <  =  > w[i] - w[k] >  = w[i] + 2w[j] + w[k] > w[i] + w[k]

<=> there is edge (i, k)

That means if we add i to the clique which contains j, when we'll have a new clique.

Now everything left is a simple DP with Fenwick tree :D You can check my submission for more detail :D

Contest is rated for Div2 participants.

Contest is unrated only for those Div1 participants who write me a private message shortly.

Why would it be unrated?

I solved it with brute force. Ran max test in 1.6s in Custom test.

UPD: It passed sys test.

I am surprised that this problem was used for today's contest; its solution is described at e-maxx.ru (one of most popular sites with algorithms for competitive programming in russian) in article about FFT, so it should be well-known for russian-speaking participants.

What is your solution? I wrote Euler path and for my solution it doesn't matter if graph has self-loops.

Yes solution for Div1.D is FFT.

1) Iterate over 'A', 'G', 'T', 'C'

2) Let's denote current letter c. Construct new string a' and b': a'[i] = [exist a[j] = c and |j — i| <= k], b'[i] = [b[i] == c].

3) Now lets apply b' to a' with offsets 0, 1, ..., n — m and calculate scalar product for each offset. If the value of scalar product is not equals to the number of ones in b' than offset is bad.

4) If offset is not bad for all four letters than it's good.

Third step can be processed in O(n * logn) time: let's duplicate string a', reverse string b and multiply them. Now in positions from m — 1 to m + n — 2 we have the scalar products that we need. Multiplying we can do using FFT.

I answered queries in reversed order with disjoint set union, but I think that there is simpler solution.

I used multiset for distances between cuts and set for coords of cuts

I used segment tree to solve it, I hope it will pass. The idea is for each column to store the maximum width of a rectangle using this column. It is the same for the rows. When I was reading the codes of people in my room, I saw solutions with sets or priority queues. Can somebody explain such solution?

thanks 4your ideas.

It's also tested almost instantly there, looks like all submissions are already tested and results are cached.

here is pseudo-code for Div2 A

while(a>0 && b>0) { if(a>b) { res+=a/b; a%=b; } else { res+=b/a; b%=a; } }

Test #11

2 xy zz

Output is 2 -1 -1

• Suppose we're comparing two points and x1 ≤ x2, then x2 - x1 ≤ w1 + w2, which can be transformed to x2 - w2 ≤ x1 + w1. So, build a pair<int,int> array with the values {x - w, x + w} for all points.
• Sort that array.
• Let DP[i] be the maximum clique we can build using points with indices  ≥ i. Let's iterate the elements from the new array from the last one to the first one (from N to 1) then if we're processing index i, we do a binary search to find the first element j such that x_j - w_j ≥ x_i + w_i, and set DP[i] = max(DP[j] + 1, DP[i + 1]). The answer will be DP[1].

Sadly, it took me an hour and a half to figure what to do with the values x + w and x - w (the last step)...

sankear, malcolm, MikeMirzayanov

I also thought on this problem, too.

Didn't realize why 10315968 got accept until reading this thread. My test case is:

4
acbc
bbaa

I thought the correct output should be:

2
1 3

But the below output also passed:

3
2 3

The problem says it must be "as small as possible" not just "reducing some".

The storyline is okay. The world would be boring if every problem has a description like "Given blahblah, you need to find blahblah". The real problem is the key point was hidden in one or two unremarkable phrase, make it difficult to understand.

I (blindly) guess that the original problem statement was written in Russian and this is a translation issue.

Unrated contest because of long statement? Isn't it too forward? Indeed some people were affected by wrong test, but that is a small amount and most of them ended up with a decent position, so it is not helpful for them to make contest unrated :P

I strongly disagree:

1) "And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!" — problem D is expected to be pretty hard and most people in Div1 know it, those who decided to try it and actually got a solution are very small amount of all Div1 participants, and those who didn't try it — didn't even realize that there was a wrong pretest. Of course it's unfair for those who've tried it, but an option to unrate their participation is available, so why make other people (like me) who didn't even attempt the problem unrated?

2) Problem C while a little bit confusing had an amusing story and the pictures cleared it up for me. I think if you read it carefully you would also find it understandable. The problem is very nice actually and I enjoyed coming up with a solution for it even though I couldn't debug it.

I agree with 1st point. I misunderstood problem statement of C and tried to solve a different problem, until I saw the announcement :(.

Like! But I really don't wanna this contest to be unrated. I believe many contestants having the same idea with me.

Hah, yes, that one was pretty confusing, I needed to read this many times too :P.

I think that the unrated option is only in case the test for Div1 D affected you and the code for Div1 D cannot be submitted in Div2.