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.