because you 1501 and wanna be Expert  

hahaha Wish you all +100 rating

Hope next div.3 will be soon :) Now I'm too busy with the studying and other activities but I'm trying to prepare it as soon as possible

Me too. Unfortunately it seems early morning weekends is the only option.

no way

Instead of that I would ask for balanced problem-set. You know what happened in last few Educational rounds.

Pretests will indeed be strong. They will be as strong as System Test...

Every one knows how to solve D except me.

This round will be rated for the participants with rating lower than 2100.

What this means ?

Don't know how much truth is there in whatever you wrote but if it is true then it is friggin' awesome.

How much is your RPS? (reload per second) ;D

It sucks.

I guess so!

I wasted time, thinking that there must be a simple and elegant solution. But I was wrong :(

This is my solution of A 43153166, I don't know if this is too much implementation for A.

my mind just goes back to "candidate master in next contest"

Delete a tree from the graph. You are left with a graph of at most 42 nodes. You can use distance pre-processing on the tree (lca) and on the remaining graph (floyd-warshall) to answer the queries.

For more details: http://mirror.codeforces.com/contest/1051/submission/43144878

Cut the given graph down to any spanning tree. There will be at most ~20 spare edges, you can calculate distance between any two nodes in O(log n) if you drop these spare edges out and consider only spanning tree.

Now we will have to consider edges that we dropped out. Let G be complete graph where edge (U,V) is minimum of the path between U and V in the spanning tree and the length of spare edge between (U,V) if it exists. G contains only nodes from the initial graph which have at least one spare edge attached to it, so G is not larger than ~40 nodes. Let's calculate the shortest path between any two nodes in G (e.g. using Floyd algo).

Ok, now for each query we just take the spanning tree path length between U and V as the initial answer and try to make it better by choosing every two vertices U', V' from G and taking spanning tree paths U-U' and V'-V plus G path U'-V'.

I think it's easier to think about it this way:

Let T be any spanning tree of the graph, S be the set of edges in the original graph but not in T, and V be the set of vertices in S. Note |V| ≤ 42. Then any path that is not entirely in the tree must pass through at least one vertex in V. So the answer for a query (u, v) is min((dist(u, v) in the tree), (dist(w, u) + dist(w, v))) over all w in V. So you can run a Dijkstra from all such w and compute the answers this way.

Maybe something like:

5
1 1 1 1 2

Don't see that much of a gap between D and E, however E is really tricky in implementation

not harder than D

more like B < D < C < A

try this: 101 0 101

Fuck! I wrote

if (a[i] == '0' and l[1] == '0') {
  f[i] = f[i + 1];
} else {
  // ...
}

instead of

if (a[i] == '0') {
  if (l[1] == '0') f[i] = f[i + 1];
} else {
  // ...
}

The difference is not immediately obvious. :'(

Please check this when previous column layer is BW or WB then adding BB or WW in current column doesn't change number of components

Yes. The English problem statement is incorrect.

To quote: "Vasya has a multiset s consisting of n integer numbers. Vasya calls some number x nice if it appears in the multiset exactly once."

When you type "the multiset", it refers to some specific multiset (the one mentioned). If you were to write "a multiset", it could refer to some other multiset as well. The problem statement was unambiguous regarding which multiset is used to define which numbers are nice: "the multiset" s given in the problem statement.

Pretty annoying to spend 20 minutes of competition time just trying to figure out what kind of error was left in the problem statement.

if count of x is odd,then it can be a nice number, not only count of x is 1
such as
8
1 2 2 2 3 4 5 6
it can be split : 1 2 3, 2 2 4 5 6

The problem statement is misleading, what they mean is that can you partition the multiset into A and B so that No. of nice elements w.r.t A in A= no. of nice elements w.r.t B in B Not

no. of nice elements w.r.t S in A= no. of nice elements w.r.t S in B

Already 285 successful hacks have been done

yes, i was thinking something like this must have happened. was getting WA in the contest.

i had kept my array size as 1e5 + 5.

split them like 1 2, 3 4, ..., i i+1

and gcd(i, i+1) is always 1

Yes

AC Code: 43149185 the test case 11 has M = 100020

it doesn't affect)

You can use dynamic programming.

dp[i][j][k] equals to the number of ways to color i columns, the last column has the state j and the total component count is exactly k.

The state is 0 if both cells are white, 1 for white upper cell and black lower cell, 2 for black upper cell and white lower cell, 3 for both black cells.

Base case: dp[1][0][1] = dp[1][1][2] = dp[1][2][2] = dp[1][3][1] = 1.

Is validator fixed now?
How people will be affected if test cases are corrected? (In case it is fixed.)
Considering that 116 people got AC during the contest, RE(?) and WA(?).
If no of people <50 then we can probably ask those people do you want an unrated contest for you?
And it can be kept rated for others?

halyavin rank 839...are we in the real world or tron has taken over

It is rated for div 2 only, so halyavin doesn't effected

I had a meeting at work and had to start half an hour later.

Also think so, CF-prediction for being #329 in Div2 was +123 while I got +15 which is about right.

it cannot be. how can you "solve" something like this. constraints say m <= 1e5. test case has m = 1e5 + 20

Let dp[i] be the total number of ways to partition the suffix of a starting at i. And let dp[n]=1 (n is the last character index+1). To calculate dp[i], you need to know the smallest index i' (i'>=i) such that the sub-string a[i, i+1, ..., i'] forms a number >= l, and you need to know the largest index i'' (i''>=i) such that the sub-string a[i, i+1, ..., i''] forms a number <= r. dp[i] will be dp[i'+1]+dp[i'+2]+...+dp[i''+1]. To find i' and i'', you need an algorithm which finds for every i the longest prefix starting at i which is also a prefix of l, and the longest prefix starting at i which is also a prefix of r (Z algorithm does this in linear time). And to sum the dp values, you can use cumulative sum on dp as you are calculating it. There is a bunch of corner cases that need to be handled of course.

But some participants wasted time on F...They may got higher ratings if there was no problem

Run floyd warshal or dijkstra for each pair or dijkstra on every query. There is no fast solution without that condition.

Maybe some A* or some probabilistic stuff — no idea how that works in practice.

if doesn't exist any i,j(i!=j) such that a_i=a_j or a_i=a_j+1

then obviously we can't do any operations and they are pairwise different

so the answer is 0

and now consider we got a new (x,y)

lets look at the 2 conditions below:

(1) lets say that there exists a_i+1=x and b_i<y, we should apply operation(2) to x and apply operation(1) to a_i so that we can add b_i-y(which is a negative value) to our answer

(2) if there exists a_i=x, then we must apply operation(1) to one of them to make it pairwise different, and obviously, we should apply the operation to the one with smaller b

after we have done our operations, we should get something like (a_i,b_i1),(a_i+1,b_i2),(a_i+2,b_i3)....

be aware that these b are sorted so that b_i1>b_i2>b_i3 ...

To conclusion, let consider we get (a_i,b_i1),(a_i+1,b_i2),(a_i+2,b_i3)...(a_i+m-1,b_im) ,(a_j,b_j1),(a_j+1,b_j2)...(a_j+k-1,b_jk) (a_j>a_i+m-1+1)

if we get a new (x,y) that a_i<=x<=a_i+m, we should rearrange the them so that we get a new sequence (a_i,b_i1),(a_i+1,b_i2)...(a_i+m,b_i(m+1))

and if a_i+m+1=a_j

we should merge the two((a_i,b_i)... and (a_j,b-j)...) into one((a_i,b_i)...)

we could do this by using a BST and Heuristic merge in O(Nlog(N)log(N))

sorry for the bad explanation, you can check my code if you need

Not the first time that North Koreans are cheating https://mirror.codeforces.com/blog/entry/14150

It is not similar, in task you mentioned, there is a solution just using lca, so you need there just to code simple lca (nlog(n), log(n)), here you should code something harder, but of course they have some similar part

+205 xd

I don't remember the time, when the contest was rated for everybody except some people, because of mistakes in some problems, so in my opinion, contest would be rated for everybody, or unrated

they are fixing test cases for problem F, which are incorrect

Or maybe codeforces should first make you expert and then think about what would be the best in everyone's interests?

It's not about the problem but about the number of people affected and the consequences of that issue.