Call in Google)

ଘ(੭*ˊᵕˋ)੭* ੈ♡‧₊˚!

hmm same. I couldn't solve D1 B and later got my A hacked, which I couldn't fix by the end of the contest either.

unfortunately only russians can understand this

here before atilla gets negative contribution

Programmers who create the AI :

hello

:-))

If wishes would've worked this way, I would be a lgm by now.

DmitryGrigorev for the great coordinating and helping us with preparing probles.

typo in problems

Edit: fixed

No.

Yes, it is rated for everyone.

Thanks, you too

I wasted on A. Took less time on B and C than A

What other rules are on Codeforces?

Do not use anybody photo except yours. It is uncultured and could confuse Codeforces users.

You don't need to guess, dp[i][sum] = 1..i, sum = sum of a, it's easy to calculate the answer.

I figured that minimization actually but couldn't able to implement can anyone tell how to minimize |sum(a)-sum(b)|?

"You need to guess".

I don't think there is any guesswork to this problem.

Expand $$$(a_i + a_j)^2$$$ as $$$a_i^2 + a_j^2 + 2 \cdot a_i \cdot a_j$$$. Clearly the two square terms will occur regardless of which array you are in.

Toying around with equations a bit, we can realize sum $$$2 \cdot a_i \cdot a_j$$$ over all $$$i \lt j$$$ is just $$$(\sum{a_i})^2 - \sum{(a_i^2)}$$$.

The second part is again constant regardless of which array we put it in. So now we clearly want to minimize $$$(\sum{a_i})^2 + (\sum{b_i})^2$$$ which is identical to your condition.

you don't have to guess, just $$$dp[i][sum]$$$ — min cost of $$$a[0...i]$$$ + $$$b[0...i]$$$ after doing swaps on first $$$i$$$ positions and sum of $$$a[0...i]$$$ is $$$sum$$$.

I solved B really quickly but took an hour on C and had to leave the contest before I had a chance to solve D

You can solve it in $$$O(n \sqrt n)$$$ without unordered sets, though the TL is pretty tight even then.

I had to replace a map of vectors with a single vector of pairs to pass pretests since the constant factor difference in iterating over them was too heavy.

My $$$O(n \sqrt n)$$$ passed pretests in 967/2000 ms

Mine passed pretests with O(n root(n) ), but i dont use any maps or hash tables for the bottleneck part of the code, e.g. the (n root(n) ) part doesnt use any maps, i map the values to [1 ... n] beforehand.

I used map and also passed pretests. Hope I wouldn't fail system test.

My $$$O(n \sqrt n)$$$ almost got TLE on pretest (1965/2000ms). Why $$$n \le 3 \times 10^5$$$ and 2s TL if $$$O(n \sqrt n)$$$ is intended?

My $$$\mathcal{O}(m\log^2n)$$$ solution with segment tree gave TLE twice before it passed all the pretests.

The problem is likely the hash function you are using. See this comment.

I'm kind of surprised to see that the TL was so tight for others since my $$$O(n\sqrt{n}\log{(n+m)})$$$ solution passed in 530 ms.

O(n * lg(n) + m * lg(m))

I solved it in O(N*sqrt(N)) with the ideia that if the sum of elements is equal N the number of different is O(sqrt(N)).

I solved it in O(nlogn + mlogm) complexity (or something like that) and the "logn" and "logm" factors come from the C++ STL maps and sets I used, as well as the STL sort function. If you really want, you could replace the maps and sets with their hash-based counterparts and the STL sort with a count sort and get a linear time complexity... (I think)

$$$dp[i][j][k] := $$$ the maximum cost to split $$$b[i, ..., j]$$$ into k subsegments minus j-i+1 (which means $$$dp$$$ includes only the sum of $$$MEX$$$ part).

base case: $$$dp[i][j][1] = MEX(b_i, ..., b_j)$$$

transition: $$$dp[i][j][k] = \max(dp[i][x][1] + dp[x+1][j][k-1]) \ \ \forall x \in [i, j)$$$

time complexity for calculating $$$dp$$$ is $$$O(n^4)$$$, then add up the solutions for all subsegments.

for a subsegment $$$[i, j]$$$ we care about the $$$k$$$ s.t. $$$dp[i][j][k] + j-i+1$$$ is the max.

For each a[i], I set its value to 2 if a[i] is 0 else 1. Then for each number, multiply its value by the number of subsegments it is in and add that to your answer. Finally, print your answer.

notice that max cost on a subsegment is simply length of subsegment + number of 0's in subsegment. Just sum this value over all subsegments to get answer.

(One of) the best way(s) to break each subarray is always to break it into single elements. It brings the length of subarray plus number of zeroes in it. So the result is the sum of lengthes of all possible subarrays plus number of occurencies of zeroes in all of them. With given constraints, it is possible to brute force it.

How do you come with the sqrt solution in E? I still don't quite get it. So basically we can just store the frequency of all numbers and bruteforcing each possible pairs?

Did your solution work? I think you need more than 2 elements per count in case those two elements form a bad pair.

Agreed. Despite having a solution to G but writing stupid buggy code and not being able to fix it in time, I really liked the round. My favourite problem was F (with my implementation, it was a data structure problem!) but I liked E as well.

I got stuck at D for 1.5 hrs... Can I know how you mean by "very standard"? What's the first thought/idea after you read the problem?