Div.1 and Div.2 shared rated round

So I assume combined.

lol

Lol

Are you sure? If a lot of new users take part in round then, probably, everyone will increase his rating

Positive rating change means if you lose rating, you will realize its positive aspect, like a kind of lesson you get after your failure.

It will put you on top of the problemset scoreboard at least.

ad-hoc is not a garbage!!!

Rated.

A little bit of both.

Equivalent to "IS IT RATED". So down vote -_-

They would be very lucky if they don't have Samsung and give them Xperia instead.

You can use them with any phone :)

He didn't join any contest in the last six months

He's invisible.

We can use the exclusion method, first of all, this person is definitely not me :)

Don't predict anything ever!

No Delay yet.

I did a greedy thing that means iterating over the array and changing the number to its complement if its better . i passed pretests somehow

https://ideone.com/vmH4pj It works correct on sample test, will have to wait for systest to get over to submit. Too bad I was considering over k+1 bits and could not submit on time.

oh shit

1 2 1 5 1 2

set z = x, some guys used added 2*t3 in case when z = x, instead of 3*t3

Yes

Didnt have just couple of seconds to get AC on F.

Submitted on last minute and only in the last seconds, i get that i have WA1.

I printed first vertical and then horizontal lines.

When i push to sumbit new code, just got message contest is over. ((

wa1 Life is pain

Yes, it's a correct solution

You can compute maximal independent set instead which is complement of minimal vertex cover.

Maybe something like

6
0 0 0 0 0 0
5 4 3 2 1 0

I had a submission that failed on 7, that also failed on this case.

Something like

4
0 1 1 3
0 0 0 0

The moment I fixed this case, pretest 7 passed

Maybe this? 4 0 1 2 3 3 2 1 0

My (probably incorrect) idea is to maintain prefixes of xors and the count of them. Whenever I reach a number with even number of occurrences of xor prefix, I change it. Finally calculate number of subarrays using the same idea.

My solution passed pretests but I'm not sure of it though. I solved it greedily by iterating over each element and see if flipping it is better I flip it. To check whether flipping it is better I used trie tree. I hope not fail on system test :D

Sub-string [l, r] xor can be calculated as pref[r] ^ pref[l-1], where pref[i] is the xor-sum of prefix ending at i. So, sub-string [l,r] xor can be 0 if and only if pref[r] == pref[l-1]. Now, what is the impact of inverting some ai? pref[i], pref[i+1], ..., pref[n] will be inverted. So in general, you can invert some ai's to invert some specific pref elements.

Let the answer (ans) be initially n(n+1)/2. You can iterate on every pref element and its complement, check the counts of both elements (using map for example). Let the counts are c1 and c2. If you didn't invert any elements, c1(c1-1)/2 and c2(c2-1)/2 will be subtracted from ans.

To minimize the subtracted value, you can imagine you inverted some pref elements resulting in changing c1 and c2 to floor((c1+c2)/2) and ceil((c1+c2)/2), let these new values be x1, x2. So, x1(x1-1)/2 and x2(x2-1)/2 will be the values subtracted from ans.

Yoss))

What's the hack?

;_;

For every index sum the left and right. The answer is n-sum[k] for k < n.

Then you loop through the answer you found and check to see if it produces the correct left and right arrays.

I solved it using the logic of fill from max to min. Max element should have l,r = 0,0. So fill all such elements in answer as max (we can use max = n). Let's move to the second max element (let it be n-1), It exists in the positions where l = the number of elements already filled in the left, and r = number of elements already filled in the right. And so on till you fill the array.

If at the ith step the array is not filled yet and there is no such element where you can put the ith max, there will be no answer.

My solution: let's write . As we can see, here is polynomial which is same for all , we only have to compute its values for . We should take instead of j³ so polynomial will be of reasonable size. Now you should note that mod is prime and it has generating element g such that each element x can be represented as x = gⁱ. Now only think you need to do is to compute value of polynomial in all powers of g which can be done with Chirp-z transform. But since you'll have to take in elements, you can actually compute only powers of g², i.e. all values in points g^2k. But you can transform your polynomial to count all values in g^2k + 1 as . The last thing to mention is that you can half the size of polynomial you need to calculate values in by abusing the fact that you calculate 'em in g² (see my unreadable code below to get the notion of what's going on).

I couldn't make it below 4s during the contest, because author is probably a cuck and thinks that you can't say that you solved a problem if you didn't optimize all constants in your code or if you don't think exactly as the author does. But at the very end I realized that there is 2 times optimization in the length of vectors which probably would allow my solution to pass after system tests end. Optimized solution itself: #Jq5TzC. (I used quasisphere code for fast mod multiplication)

I believe your solution is correct, we have something very similar to what you have written.

I had some trouble with precision but it passed, the primitive root idea isn't needed. You can take the discrete logarithm of ANY primitive root for every prime in the pair of groups and group it together after. http://mirror.codeforces.com/contest/1054/submission/44524051

Let c=2^k-1.

In that case complement to a is just c-a;

You can take the compliment and then mask the right k bits by taking bitwise AND with 2^k-1

Nah. Crashed systests were slower. Systests taking hours just because they're slow aren't so uncommon on CF.

Are you sure it's related to being in ITMO? Some contests take longer to judge than others. It looks like today's was rather heavy in this regard; it seems like problems have a lot of tests. Also, problem B was solved by a lot of people, but had O(n) complexity with n = 10⁵. Often, problems that get a lot of submissions have like O(1) complexity or much smaller n.

If you build prefix xor array, then xor of interval can be 0 if there is x and x in that array. If we count occurencies of min(x,x^((1<<k)-1)) then this is really similar, because we need to have as even number of x as flip(x).

We need to minimize the number of subarrays with xor==0.
Let's build a prefix xor array, P, and use a map, F, to track the frequency of each element in P.
If we cannot change any element, then answer would be:

If we can change elements to its complement, we can try minimizing the summation.

To do so, we can try breaking up a single element with large frequency to many elements with lower frequency. This will decrease the sum because of the property a₁² + a₂² + ... ≤ (a₁ + a₂ + ...)² for non-negative integers.

We can iterate over the prefix array and if x is the current element and as its complement, we choose the element with the smaller frequency until this point and increment its frequency.

Now, the only case left is how do we handle choosing when .
It actually does not matter.

Suppose we choose x over , then it would only negatively impact us when we have another element later on with x as one choice and the second choice being some other value apart from . But this will never happen because each x is associated with only one, unique .

Hence, the greedy algorithm would work.

Not sure what's going on, but the second solution is giving correct outputs too. It's just offset by a certain number (idk how), e.g. the first testcase is offset by 2 from the jury answer. The problem statement doesn't require for the smallest number to be 1, so that is fine. I don't think the testcases were weak.

http://mirror.codeforces.com/blog/entry/62563

http://mirror.codeforces.com/blog/entry/62563

Really neat!

I had something else in mind:

let's imagine any correct solution, and find any leaf l in the tree. It's connected to some other vertex v. Then we can see that for each group A of vertices in the input such that |A| ≥ 2, from follows (l is connected to v only, so any "non-trivial" set containing l has to contain v).

Moreover, if we find any two vertices (l, v) fulfilling the property above, we can safely assume that l is a leaf connected to v only. (Proof: let's take any solution. If a group of people contains l, then it also contains v, which means it also contains a whole path between l and v. We can safely remove l from the tree, attaching all subtrees that were connected to l to the second vertex on the path. Then we can reattach l as the leaf connected to v only.)

The idea is now straightforward: find a leaf, remove it, find a leaf in the remaining tree and so on. The only problem is how to find a pair of vertices (l, v) as above. For each pair of people i, j, I am maintaining b_i, j, the number of groups larger than 1 containing i, but omitting j. (These can be computed directly from w_i, j in the parent post.) A pair of vertices (l, v) fulfills the condition above if b_l, v = 0. b_i, j's can be straightforwardly updated after the removal of a single vertex.

This leads to another solution in time.

My approach:

1. Move everything from (0, 0) to (1, 0) and from (1, 1) to (0, 1).
2. Move all zeroes and ones from every cell to (0, 0) and (1, 1), respectively.
3. Fill all cells (i, j) having j ≥ 2 with target value. If there are two moves needed (because the row AND column differs from (0, 0), resp. (1, 1)), first move within the same column.
4. Fill all cells (i, j) having j < 2 and i ≥ 1 with the target value. If there are two moves needed, first move within the same row.
5. Assemble the target value of (0, 0) in (1, 0) and target value of (1, 1) in (0, 1).
6. Assemble the target values of (1, 0) and (0, 1) in their cells.
7. Move the value of (0, 0) from (1, 0) to (0, 0). Similarly with (1, 1).

In the steps 1 and 2, we move every digit at most twice. In the moves 3-7, we again move each digit at most twice.