I will never trust such comments again in my life :(

I really enjoy the contest, problem C and D are very good.

Fixed, I hope that too.

Let's hope they don't miss problem "C".

orz

Here it is.

It's not about difficulty, it's just tedious to make sense of a wall of text. And usually problems "feel more beautiful" if they are concisely (but still understandably) stated.

(I don't care about that so much unless it's like two pages long, but still, this is why people like short statements.)

Like arc84B Small Multiple. Only one sentence which seems like Div.2A/B. But actually it's in the difficulty of Div.2D/E

gitgud

I think this is the biggest difference between hiring-focused platforms and olympiad-focused platforms. But I agree some easy problems should be included in early part of Div.2.

Can problem C yesterday be regarded as "graph problem" and problem E yesterday be regarded as "easy dp"?

Yes.

Yes. Registration before rating change can lead to such problem.

It's actually a known bug in CF, and I've written a post for it. Unfortunately CF hasn't fixed it. :(

DownVotesForces :D

Me too!!!!

Quite puzzled

let HI be the highest value that is adjacent to a -1. let LO be the lowest value that is adjacent to a -1. the value of k is equal to (HI + LO) / 2. let DIF be the maximum difference between two adjacent elements that are different from -1. the answer would be the maximum between DIF and the maximum between HI — k and k — LO.

In fact, you need to minimize the number of pairs $$$(l, r)$$$ such that substring $$$s[l:r]$$$ contains only zeroes. This can be calculated separately for each group of adjacent zeroes. For a group of $$$x$$$ adjacent zeroes it is $$$x(x + 1)$$$. So the problem can be rephrased like this:

$$$\text{Split } n - m \text{ into several numbers } a_i \text{ such that } \sum a_i(a_i + 1) \text{ is minimum possible}$$$

It is easy to see that the solution to this problem is to: (1) split $$$n - m$$$ into as many numbers as possible (keep in mind that you cannot have more than $$$m + 1$$$ groups of zeroes); (2) when splitting, make $$$a_i$$$ as equal as possible.

you need to minimize the largest substring that only contains 0's. to do this you just need to distribute the 0's between the ones. for example if n is 8 and m is 2 is should be distributed like 00100100. then to count them you have to count the number of substrings n * (n + 1) / 2 then subtract the number of substrings that contains only 0's, to count that you need to divide the number of 0's by the number of ones + 1, and count separately the regions that contain one more 0 than the others (if the number of 0's is not divisible by the number of ones + 1) for example if n is 10 and m is 2 the distribution would be something like 0001000100

Imagine the string as groups of zeroes separated by ones. The answer will be the number of all substrings — the number substrings in each group of zeores(Z). To achieve the highest answer to the original problem we want the number of substrings in each group to be the lowest.

We achieve that by spreading all zeroes in as many groups as evenly as possible. the groups(G) will be n — m if n — m <= m and m + 1 otherwise(write down some cases and you will see why, that how I found that during the contest). The number of zeroes in the groups will be their overall count of zeroes divided by the number of groups. If we have reminder(R) in this division then we can put 1 extra zero in Z % G groups to keep the zeroes as evenly as possible spread.

By now we have G — R groups of Z zeroes and R groups of Z + 1 zeroes and using that we can calculate the answer as ((n + 1) * n / 2) — (G — R) * ((Z + 1) * Z / 2) + R * ((Z + 2) * (Z + 1) / 2).

I hope that was helpful :)

I enjoyed the implementation — which has it's own set of puzzles. Unfortunately I forgot to remove a debugging infinite loop counter before submitting, :( I'm gonna kill myself if my code actually passes after removing the counter.

If the largest element that is adjacent to a -1 is a and the smallest element that is adjacent to a -1 is b, then we should set all -1's to be the average of a and b say c and that will minimise the differences. the maximum difference will be max(maximum difference between the elements that were already defined,c-a,b-c )

I solved it with binary search,

You can take a look at my implementation.

A.C Submission

If you have any doubts, you can ask.

I tried it with euler circuit.The conditions of euler circuit are satisfied for all matrices i believe.

Yes. That's what kinda what I did. I found an euler tour that also ran through all the edges.

My O(t) solution got TLE in PyPy3 but got AC (795 ms) in Python3. They are the same code. Are there any strange testcases?

if you append your answers in an array and print at last, it will pass

I had no luck on both pypy and python 3. However switching from input() to sys.stdin.readline() made it pass (even though testing on my local machine the latter isn't supposed to be faster, both versions take around 500-600ms).

Use the Fast I/O Method As the number of Test cases is about 1e5, So you have to take input 1e5 times. Therefore Fast I/O reduces some time.

I tried switching from input() to sys.stdin.readline(), and my solution passed both in PyPy3 (748-779 ms) and in Python3 (701 ms). I'll use this fast I/O method from the next contest. Thank you.

all codeforces rounds are like this recently. also انت طري

There is a constraint in output that $$$a\leq3000$$$. So Euler Circuit doesn't work.

Calculate 2D prefix sums for each colour.

For each possible size $$$i$$$ ($$$1$$$ to half of $$$n$$$ or $$$m$$$) and each possible position, calculate whether you can make the required shape by checking if the partial sums of each colour in respective regions are equal to $$$i^2$$$, and if so mark it down (e.g. on top-left corner). Do partial sums on each possible size.

To answer a query, binary search on the largest possible size. The partial sums you just calculated helps you determine if there exists at least one square of such size.

Time complexity: $$$O(n^3 + q log n)$$$

I realized it can be binary searched after the contest.

add it to the list then :p https://mirror.codeforces.com/blog/entry/73470

while (arr[l] == -1) l++;
while (arr[r] == -1) r--;
minar = maxar = arr[l];

This is wrong, when array doesn't start -1, you are including a[0] to compute min and max. correct one 71018156

You're right. Thanks a lot!

You solved it very late!

the round tutorial link here , can't help with something other than that tho.

What is "Pure ternary search"?
Care to elaborate more?