You should solve ABC in 30 minutes

I think solving ABC super fast is not primary goal to go 1600+, instead try to solve ABCD in 2 hours.

Of course!

Depends on how fast you are, where in pupil range you are, and of course how hard the tasks are, but generally I don't think so. You may try solving at least A and B, which I think in most case will give rating improvements.

BTW. I don't think that there is a big gap between Div.2 AB and Div.3 AB. Difficulty gap between 2 different div2 contests are actually larger (in my opinion, but problem rating data also kina shows similar results.)

This is not possible :)

maybe 3? i guess

Yes.

with good pretests uninteresting hack))

add anything... like a space or anything to that code somewhere

Sort by $$$(a_{i}-b_{i})$$$

Notice that $$$a_i(j-1)+b_i(n-j)=j(a_i-b_i) + n b_i - a_i$$$. So, what matters is the value $$$a_i - b_i$$$.

Dissatisfaction be rewritten as $$$j(a_i-b_i)+b_in-a_i$$$. Thus, we are trying to order $$$i$$$'s to minimize the sum of $$$j(a_i-b_i)$$$. Just sort them in decreasing order of $$$a_i-b_i$$$ and that should be the minimum. You can use an exchange argument to prove it.

Hint: What's the formula for number of components in a tree?

Expand the formula for dissatisfaction

ans = sum (a[i]*(i-1) + b[i]*(n-i)) for i=1 to n
    = sum ((a[i]-b[i])*(i-1) + b[i]*(n-1))
Now to minimize ans you should minimize (a[i]-b[i])*(i-1)
So sort (a[i]-b[i]) in reverse order.

since ans = summation(a[i]*j + b[i]*(n-j)),so we have to assign positions such that for each i if a[i] > b[i] start filling it from left and from right otherwise ,but since j factor is there ,so more the (a[i]-b[i]),put it most left..

Hint: What's the formula for number of components in a forest?

First Compress the array by merging consecutive indices with same value in one component.

Consider $$$dp[r] = \sum_{l = 1}^{r} f(l, r) $$$.

Now, we have $$$dp[r] = (\text{number of elements with value r}) * r + dp[i - 1] - \text{number of edges that occur when we add elements with value r} $$$.

the last term can be found by going through elements with value r, and checking its neighbours, If the neighbour's value is less than r, say x, it means for l <= x there will be an added edge. hence you add x to the last term in dp.

Let's consider the starting of any component. Let it start at position i. Now, this is a starting position iff a[i — 1] does not belong to the range [l, r] and a[i] belongs to the range [l, r]. So we'll calculate the number of ranges [l, r] s.t. a[i] is inside this range and a[i — 1] is outside this range. The sum of the number of possible ranges over all i will give you the answer.

I did one successful hacking attempt in B, and the testcase was:

2 2 // H, W
8 9 // A[1][1], A[1][2]
8 8 // A[2][1], A[2][2]

The only possible answer is TAK: C = [2, 1], but I found a submission which is assuming that $$$C$$$ is non-decreasing, so I could hack this solution.

Yup

Why are you using doubles? Just use ints/long longs and modulo 1e9+7 as you go.

You should not be using floating point numbers in a problem like this, where the exact answer can be found using integers.

Solution: It is enough to calculate the sum of values in the range [1..M], because then the sum of values in the range [L..R] can be found doing a subtraction. To find it, we can recreate the process in which numbers are written in the blackboard to find how many odd and even numbers where added. Something like this:

int to_add=1, remaining=M, numodd=0, numeven=0;
while (M > 0) { // Complexity log(M) because you are substracting powers of 2
  if (remaining >= to_add) then
    sum to numodd or numeven;
  else
    put the rest in numodd or numeven;
  to_add*=2;
}

Once you know how many odd and even numbers are the in the black board, you can calculate two sums of the form 1+3+5+... and 2+4+6..., which are easy arithmetic sums (use a formula). In addition, remember that you must perform the operations modulo 10^9+7.

Hope it helps.

I haven't solved it But I have some idea with stack、、wait for help too.

Number of connected components $$$f(l, r) = 1 + (\text{number of cut edges}) - (\text{number of cut vertices})$$$

You can calculate total number of cut edges and cut vertices in $$$O(n)$$$ each.

The idea look like dp

dp[510][1024]

dp[i][j] means The preceding i-line scheme for forming number “j”

and dp[510][1023] can be optimized to dp[1024]

Basically if a row contains at least two different numbers then there is a solution. If not any row contains two differents numbers, then just compute bitwise xor of a_(i,1) for i in range (0,n). If it's 0 then the answer is NIE, else you have your solution

observation: if a != b, a ^ b > 0 (in this problem i used bruteforce).

fix a row that has > 1 unique value (if there's any, but if none than you can pick any row).

let k be the fixed row, after that you xor any value of a[i][0] excluding that row (that is a[0][0] ^ a[1][0] ^ ... ^ a[n — 1][0] ^ a[k][0]), let the value val.

now you try all possible value x in this row k, if any val ^ x > 0, then you found the answer (n — 1 column 1 and 1 column in the fixed row).

My submission: 52983517

Carry a cell from each row, as your wish... if the xor of all values equal 0, then just try change any of those values from any row..if it is not possible, then NIE

If x is not y, then (x xor a) is not (y xor a).

Randomly assign one number from each row. If the xor of all the assigned numbers is greater than 0,the problem ends there, else changing any one number among the chosen ones will change the xor. Try replacing each number in the matrix and when the xor is not equal to zero, that's one solution

Well, you can consider each bit separately (there are $$$\leqslant 10$$$ bits). Now for $$$\operatorname{xor}$$$ to be non-zero you need an odd number of $$$1$$$'s. If the answer is 'yes' for at least one bit, then you have found a solution.

Look at it as a dynamic programming problem. N <= 500, A_{i,j} <= 1023 Try them all and save the answer.

I don' t know how to use latex or markdown in comments, sorry for bad formatting.

Carry a cell from each row, as your wish... if the xor of all values equal 0, then just try change any of those values from any row..if it is not possible, then NIE

Could I add another "very"?

My solution was 'sorting' the array and I was printing the modified indices and somehow that passed the pretests. In, normal occasions this solution should not even pass the samples.

https://codeforces.me/blog/entry/66576?#comment-506224

Agree that they should have swapped C and D instead, but I think many of the problems require nice insight (like B, D and E).

Please do not doubt — I am pretty surprised and happy that I won this round, and I was lucky that ecnerwala participated 30 minutes after the contest begins (if he participated from first, I think I lost).

So, why did I take order B, D, C, E, A, F? I did pretty strategical.

- First, opened problem B because I thought that opening problem B is lighter for servers than opening problem A. Then solved in ~3 minutes. It was not so difficult.
- Second, opened problem C. But updating standings every ten seconds, I found out that problem D is already solved by someone! Hence, I immediately moved to problem D. I have came up with the solution in ~15 seconds, and the implementation was easy, so I solved in like ~2.5 minutes.
- Then, re-thought problem C. Implementation was not so difficult, but my code bugged so it took ~6 minutes to solve.
- In this time, the solver of E existed, so I moved to problem E. I had came up with the idea of "we should only care about difference in position $$$i$$$ and $$$i+1$$$ (+ two sides)", 1 seconds after I read the problem statement completely. The implementation was easy, so I could solve in 5 minutes.
- Then, I moved A and solved easily. I had a pretty difficult time in solving F, because my matrix library is really slow (but the TL is 1 second), so I coded without using own library.

I am very happy to win in such contest, in contrast to last contest taking 30 minutes in easy Div.2 B.

P.S. You said that the coding style differs. What pair of problems are you pointing?

I think code for D can be written in 1 min. And if you get the idea straight then it's an easy problem. Just read A. Statement and so many conditions, but still people have submitted in <3 min. Where i found A hard than D to code and understand. So writing code in 2-3 min for D is fine. Even problem E is too easier, if you know the logic. Just count of cut edges and cut vertices. Thinking may take 3-4 minutes. But code can be definitely written in 1 min. So I don't see any kind of cheating. You just go through other good coders' submissions, most of them have solved D, E in <= 5 min.

You can change the problem into weighted graph that has $$$4Hn$$$ vertices and up to $$$16 \times 4Hn$$$ vertices. Use binary jump (I don't exactly know the formal name of these kind of techniques) to calculate after $$$k$$$ moves in this graph.

For your information, $$$nHr = n+r-1Cr$$$.

I couldn't code my idea in last 20 minutes.

not)) this is just boolshit))

Let $$$z$$$ be the number of zeroes in the array. Consider the block of first $$$z$$$ bits: array is sorted iff it's all zero.

Let $$$dp[i][u]$$$ be the probabilty that after $$$i$$$ steps we will have $$$u$$$ ones in the first $$$z$$$ bits. Then the answer will be $$$dp[k][0]$$$.

Starting from $$$dp[i][u]$$$ there are three possibilities after the next step:

• $$$u$$$ didn't change. Either we swapped something inside a block (there are $$$z \cdot (z - 1) / 2 + (n - z) \cdot (n - z - 1) / 2$$$ ways to do that), or we took same bits from different blocks: $$$u \cdot (n - z - u)$$$ ways to take two ones and $$$(z - u) \cdot u$$$ ways to take two zeroes.

• $$$u$$$ increased by one. This can only happen if we took a $$$0$$$ from the first block and a $$$1$$$ from the second. There are $$$(z - u) \cdot (n - z - u)$$$ ways to do that.

• $$$u$$$ decreased by one. Then we took $$$1$$$ from the first block and $$$0$$$ from the second. There are $$$u^2$$$ ways to do that.

You can easily change the calculation of this DP to backward and then use matrix exponentiation.

Carry a cell from each row, as your wish... if the xor of all values equal 0, then just try change any of those values from any row..if it is not possible, then NIE

If you want the whole solution, you can read the editorial. If you just want a hint, try to think of a formula by which you can solve this. It's similar to calculating the sum of the first n numbers, you just have to change it a little bit. :)

I can offer other order A,D,B,C,F,E

Yes, B can be solved by DP. You can maintain a DP of size 510*1024, Here dp[i][j], i is the row number and j is the xor of numbers. So, all dp[i][j] values will be 1, if we can have xor j at an ith row, otherwise, the value will be 0. If the value is non zero, store the parent i.e. the element in (i-1)th row which xor with current element will give the xor j.

Please look at code for more clear representation.