I think it's time to reconsider your friendships :-)

Are you guys downvoting me because I am a Turk? Do you even know what I am thinking about the event? I haven't even stated my thoughts!

I genuinely wonder what your perspective is, upon the motivation of the Turkish state. What do you think is their purpose?

Whooooosh

Revision 2 looks much better, the newlines were essential!

Why do you think winning medals under Russian flag has anything to do with government? Do you really think this weird sanction is constructive at all?

Yeah, "we're banning your nation but don't get offended" xD

Many long hours of discussion yet they made the wrong decision xD

I'm not sure how the first one helps with the linear solution. Let's consider a chain tree from $$$1$$$ to $$$n$$$ and say the deepest node in the tree (when rooted from $$$1$$$) is $$$n$$$. Then $$$dp[n]$$$ will have one entry, $$$dp[n - 1]$$$ will have $$$2$$$ entries and so on, $$$dp[1]$$$ will have $$$n$$$ entries. This makes $$$\mathcal{O}(n^2)$$$ memory. Where don't I understand, exactly?

I see only plain text when I go through previous revisions of comments, and it doesn't get fixed when I go back to the recent revision. Also, the icon is not rendered in comment previews.

I like it except that the icon is so similar to the like button Facebook used sometime.

This. I feel like individuals (often newbies/pupils) tend to think of the round as "unbalanced" or "not beginner friendly" when their performance is bad. I think everybody should be aware of how hard it actually is to prepare a contest and not complain about the "free food" they have. Well, I understand that by each day, expectations from problemsetters grow but if there isn't a clear mistake about the contest (such as very weak pretests, suddenly adding extra 15 minutes or really really huge difficulty gaps), people should be understanding.

I'm not sure whether the proof in E is called contradiction or exchange argument. Can somebody elaborate?

Edit: Oh, the editorial is updated! There was the word "contradiction" sometime and I commented on that. I also had too many doubts about the first revision of the proof but everything is now clear to me. Thanks!

Solution for problem D without the log factor:

For every person, find $$$B_i$$$. $$$B_i$$$ means the best shop to choose while buying a gift for person $$$i$$$. From now on, I'll rephrase "buying a gift for a person $$$i$$$ from shop $$$s$$$" as "assigning person $$$i$$$ to shop $$$s$$$.

Case 1: Number of different "optimal" shops (i.e. number of distinct integers $$$B_i$$$ for $$$1 \leq i \leq n$$$) does not exceed $$$n - 1$$$. We can assign person $$$i$$$ to $$$B_i$$$ and calculate the answer directly.

Case 2: Otherwise. Then there has to be at least one person $$$i$$$ such that it's not assigned to $$$B_i$$$. Let's call such a person "unhappy". Then I claim that there is no more than $$$2$$$ unhappy people in an optimal assignment. Proof is left as an exercise for the reader.

What we can conclude from here is that in an optimal assignment, we'll choose exactly $$$2$$$ people and assign both of them to the same shop. Note that none or one of them can be assigned to their best shop. And every person $$$i$$$ in remaining $$$n - 2$$$ people are assigned to $$$B_i$$$.

Call the shop with $$$2$$$ people assigned as $$$s$$$, and friends to be assigned to $$$s$$$ as $$$x$$$ and $$$y$$$. Without loss of generality, assume that $$$p_{sx} \leq p_{sy}$$$. What is the answer for a fixed $$$x$$$, $$$y$$$, $$$s$$$? Turns out it's the minimum of $$$min_{1 \leq i \leq n, i \neq x, i \neq y}(p_{B_ii}), p_{sx}$$$ and $$$p_{sy}$$$.

Note that we can assume as if $$$y$$$ is also assigned to $$$B_y$$$ because we know that $$$p_{sy}$$$ can't minimize the answer while $$$p_{sx}$$$ is there. Therefore we don't have to iterate over $$$y$$$'s and only take the minimum of $$$min_{1 \leq i \leq n, i \neq x}(p_{B_ii})$$$ and $$$p_{sx}$$$. So let's iterate over different $$$x$$$ and $$$s$$$. But we have to find a way to ensure that there is at least one $$$y$$$ such that $$$p_{sx} \leq p_{sy}$$$ holds for a fixed $$$x$$$, $$$s$$$.

Here is a way to check it: We can store for every shop the value of its most valuable gift and its count. Call it $$$V_s$$$ and $$$C_s$$$ for shop $$$s$$$ respectively. If $$$p_{sx} \lt V_s$$$ or $$$p_{sx} = V_s$$$ and $$$C_s \geq 2$$$ then it is a valid $$$(x, s)$$$ pair.

Complexity is $$$\mathcal{O}(nm)$$$:

In case 1, checking is done in $$$\mathcal{O}(nm)$$$. In case 2, at every iteration of $$$x$$$, you first find $$$min_{1 \leq i \leq n, i \neq x}(p_{B_ii})$$$ in $$$\mathcal{O}(n)$$$ and iterate shop $$$s$$$ in $$$\mathcal{O}(m)$$$. Total runtime is $$$\mathcal{O}(n(n + m))$$$, which is bounded by $$$\mathcal{O}(nm)$$$ because $$$n \leq m$$$ must hold at case 2.

See example submission: 140114559. Note that I have swapped the dimensions of $$$p$$$ in the problem for implementation simplicity. I also have a vector $$$d$$$ to count the number of distinct shops for case 1.

Can you recommend other problems that require finding the first $$$k$$$ best answers but solvable with a DP that looks like this?

Do you guys recommend any article about problem D? Or can somebody come up with a simpler explanation without diving into too much technical language? I can't understand it with my current knowledge.

You've just made my day.

I think problem B and C required relatively simple ideas but I found them hard to implement. Problem B was uncomfortable to write yet doable. However, I just lost too much time over problem C trying to figure out how to implement "properly".

To be able to binary search for an answer, you should know that:

If some value $$$x$$$ doesn't satisfy the requirements for an answer, then all values lower than $$$x$$$ (or greater than $$$x$$$, depending on the question) doesn't also satisfy the requirements.

AFAIK it's formally called a monotonic function. Definitely not a professional on CP but from what I've seen I can say that plenty of interactive questions or some "minimum number of operations that satisfy the requirements" involve binary search. As for Codeforces, the first three Div. 2 problems doesn't involve too many BS questions. Other than that, I can say that if there's an array that you can apply sliding window, you can combine these two techniques together, it's not uncommon.

Problem D is very nice and the way the recurrence is built is very interesting. I have never seen such a way of thinking :

"Instead of finding the answer for a whole subarray, find the sum of the answers if this subarray is splitted into $$$k$$$ independent groups. If we do it this way, the answer for the whole subarray is stored in the 'DP for splitting the subarray into 1 group'."

It is very, very clever to do so. Are there any other problems that relies on this idea or is it a very specific DP? If there are no known similar problems, Bartol [orz], can you at least share the story for the preparation of the problem? Thank you so much.

Being able to hover over graph vertices would be also really nice, I didn't realize that I used it so often on Codeforces. So I definitely suggest improving graphs to be your first priority. Thanks for such a cool website!

I think I have thought a very similar way, but I couldn't build DP. First, I considered sorting the array. Then I thought of building a DP like $$$dp[i][j][k]$$$ where this element holds the number of ways of permuting numbers from $$$i^{th}$$$ index to $$$j^{th}$$$ index such that at least $$$k$$$ slots are needed for permuting that way. Can I continue from here or do I need to think something else?

I've waited for someone more experienced than me to answer this but I will share what helped me.

• Reading editorials without skipping math parts

• Learning how to use the sigma notation

• Trying to write even trivial equations and/or greedy solutions in a formal fashion

• Trying to prove the correctness of your solution

• For a good start, learning very basic formulas such as sum of powers of two (above) or sum of integers from 1 to n

• Hanging out on Cp-Algorithms

• Finally (and obviously) having an interest in math

PS: I GOT FST!

For Div.2 C what I did was for every $$$i$$$, finding the nearest $$$j$$$ such that $$$j + 1$$$ is not divisible by $$$a[i]$$$ and pushing the index $$$i$$$ to $$$mp[i - j]$$$. Here, $$$mp$$$ is a map of vectors. $$$mp[d]$$$ eventually stored the indices that become erasable after $$$d$$$ elements from their left gets erased.

Obviously we need to start by erasing some element in $$$mp[0]$$$. Here, starting with the rightest element $$$x$$$ is the optimal because minimum number of elements gets negatively affected from this operation. So we erase $$$x$$$ from $$$mp[0]$$$. After erasing $$$x$$$ we have to check whether there are new erasable elements to the right of $$$x$$$ and such elements can only be in $$$mp[1]$$$. Thus we check whether the rightest element of $$$mp[1]$$$ (let's call it $$$y$$$) is bigger than $$$x$$$. If not, we have to keep erasing from $$$mp[0]$$$. If yes, it is a good idea to first erase $$$y$$$ along with the indices that get erasable after erasing $$$y$$$ (It is a recursive process). Only after that we can continue with erasing from $$$mp[0]$$$.

Eventually all the vectors should become empty in $$$mp$$$. If they are empty then the answer is "YES", otherwise the answer is "NO".

Here is some in-contest ugly code but it failed the system test :( 133669599

What the code does is there is a function solve(k, iterator) and k means the rightest element we have deleted before calling this function and the iterator basically finds the most recent non-empty vector waiting for their elements to get erased. Can anybody help me what is wrong with my solution?

The DP solution gives me strong KMP vibes.

FYI I saw here and here today, the migration seems temporary...

Especially problem D was great.

God, I love that game but my computer is garbage (just not intended for games) so I don't get the satisfaction I am supposed to xD

Though I still wonder if it's 100% about my computer or the system requirements are actually a bit high... How exactly is your PC configuration?

I mean, I'm talking about "cf-predictor extension" and the calculation of yesterday's contest is based on our previous ratings, like the system is literally missing two last contests' rating changes. I don't know about any rating roll back and I didn't mean that.

Yes, that must be the issue. Neither my friends' rating or mine are up-to-date.

About the ongoing discussion about rating predictions in cf-predictor being wrong, I'd like to say something. The ratings of the people I've checked (including mine) are not up-to-date, that's probably the reason why the calculations of deltas are incorrect.

Sorry, you're right. Fixed that.

You're welcome!

Maintain a 2D DP array. Here, $$$dp[i][j]$$$ means the value we'll get in interval $$$[i,j]$$$ if we reverse the interval $$$[i,j]$$$. It is not hard to see that $$$dp[i][j] = dp[i+1][j-1] + a[i]*b[j] + a[j]*b[i]$$$ because when we reverse an interval $$$[i,j]$$$ , interval $$$[i+1,j-1]$$$ gets reversed and we swap $$$a[i]$$$ and $$$a[j]$$$. Now, maintain a prefix and a suffix array $$$pre$$$ and $$$suf$$$. Here, $$$pre[i]$$$ denotes the answer for prefix $$$[1,i]$$$ without any reversing and $$$suf[i]$$$ denotes the answer for suffix $$$[i,n]$$$ without any reversing. The answer is maximum of $$$pre[i-1] + dp[i][j] + suf[j+1]$$$ for all intervals $$$[i,j]$$$.

I guess you'll need prefix sums anyway. From now on, assume that the universities are sorted in non-decreasing order by size. The thing with the "two pointers" must be that when you encounter a university with size smaller than current $$$k$$$, you have to move your "left pointer" (you shouldn't evaluate universities on the left of the left pointer because their size are smaller than $$$k$$$). As with the right pointer, it just doesn't exist.

P.S. : It is my understanding of this tag.

This is probably the intended solution and it's $$$O(nlogn)$$$. It's not about the test cases, it is indeed $$$O(n)$$$ except sorting. Because, if done so, we will consider a university with size $$$s$$$ in only $$$s$$$ different $$$k$$$'s. Since the sum of all $$$s$$$'s is $$$n$$$, complexity is $$$O(nlogn+n)$$$, that is, $$$O(nlogn)$$$.

You might want to check out my comment. I've explained the solution with proof and details.

Let's say you have four equal elements. Your array initially looks like this : $$$a\;a\; a\;a$$$.

You can xor the first element with the second. Your array is now : $$$0\;a\;a$$$.

You can xor the first element with the second. Your array is now : $$$a\;a$$$. You have only 2 elements left.

Let's say you have five equal elements. Your array initially looks like this : $$$a\;a\; a\;a\;a$$$.

You can xor the first element with the second. Your array is now : $$$0\;a\;a\;a$$$.

You can xor the first element with the second. Your array is now : $$$a\;a\;a$$$. You have only 3 elements left.

For bigger number of pieces you can apply the same thing.

I've explained a proof with details. You might want to check my comment.

For problem C, the idea of continously dividing all elements by two until an odd element seems intuitive, however, I needed a proof. After some thinking, I came up with one and guess it would be helpful to those asking. We have three cases to consider :

Case 1 : We already cannot split the array into two.

This happens when either sum of all elements is odd or the sum is even but we just really can't divide them to two. (Latter can be checked with DP.) Answer is 0.

Case 2 : It can be split into two but there is at least one odd element in the array.

If we remove one of the odd numbers in the array, sum becomes odd. Since we know that the lower bound for the answer is 1, we've handled this case optimally.

Case 3 : It can be split into two and there is no odd element in the array.

If we can show that this can be handled by only removing one element (and since the answer is at least 1) , we'll be handling this case optimally too. Now consider two arrays $$$A$$$ and $$$B$$$ s.t. $$$A$$$ $$$B_i = 2*A_i$$$ for $$$i = 1 $$$ to $$$n$$$.

What we want to prove is :

If we can "break" (i.e. turning a good array into a bad one) $$$A$$$ by removing only one particular element, say, $$$A_i$$$ ;
We can remove the corresponding element $$$B_i$$$ to break $$$B$$$.

If we are able to prove this we can just continuously divide every element in our array by two until we get an array that can be handled in case 2, mark an odd element (to be removed) in our latest array, and backtrack the steps by multiplying by two, and get the element that is going to be removed. At the end, we'll be removing only one element (which is optimal).

Let's prove it with contradiction. We assume that there is such an array $$$A$$$ that we can break by removing $$$A_i$$$ but we are still able to partition $$$B$$$ even after removing $$$B_i$$$. This means there is some partition $$$[{S_1 , S_2}]$$$ of $$$B$$$ after $$$B_i$$$ is removed. We can divide all of the elements in $$$S_1$$$ and $$$S_2$$$ by two, turn any element $$$B_k$$$ in the sets $$$S_1$$$,$$$S_2$$$ into $$$A_k$$$ and name the sets into $$$S_1'$$$ , $$$S_2'$$$ . This means we can partition $$$A$$$ as $$$[S_1',S_2']$$$ and this partition doesn't contain $$$A_i$$$. But $$$A$$$ had to be broken after $$$A_i$$$ was removed. Contradiction!

UPD : If we have an array that needs to be handled at case 3 and when we continuously divide all of its elements by two, there is no way of encountering a case 1-array. Because, in a very similar matter of thinking with the above statement (which we proved), we can claim that if an array already cannot be split into two, "multiples" of this array can't be split into two either. Proof is again very similar to the above statement's.

You can because it is roughly ~40MB (in case of ints) and in CF the memory limit for most of the problems is 256MB.

Do not use pow, I do not know your intended solution but pow can result in both precision error and linear calculation (which makes your whole algorithm $$$O(n\;maxB)$$$ if you iterate through $$$n$$$ values and use pow to calculate some power $$$a^b$$$ in $$$O(b)$$$ time instead of $$$O(log\;b)$$$ time with binary exponentiation.)

Seriously though, I felt the necessity for a proof, otherwise I would've solved that. How does one prove that the greedy thing works?

AFAIK std::abs can be used with integers as it seems to be overloaded and I didn't have problems using it. See here.

I think this will help : https://mirror.codeforces.com/blog/entry/77846?#comment-760270

I personally found problem G's editorial hard to understand, and I thought it could be helpful for others if i shared my understanding.

First things first, notice that the number of $$$1$$$'s in the rows must be equal to the number of $$$1$$$'s in the columns. This means $$$n \times a = m \times b\;$$$. If this doesn't hold for given $$$n,m,a,b$$$ , the answer is NO. Otherwise, it can be shown that the answer is always YES. From now on, I am going to use zero-based indexing.

We can follow a greedy algorithm :

1. Fill the first $$$a$$$ consecutive cells with $$$1$$$'s in the first row. Here, the column we started to fill the $$$1$$$'s is $$$0$$$ and let's call this starting column $$$c$$$.
2. For the rows $$$1$$$ to $$$n-1$$$ respectively, set $$$c = (c +a)\;(mod\;m)\;$$$ and starting from column $$$c$$$, fill the first $$$a$$$ cyclically consecutive cells with $$$1$$$.

In this way, we know that every row has exactly $$$a$$$ cells with $$$1$$$'s. The first condition is fulfilled.

Now it remains to check if we have $$$b\;\;1$$$'s filled for every column. Now when we fill the rows this way, notice the pattern of filling the columns :

First, we fill columns $$$0$$$ to $$$a-1$$$ for the first row , and then we fill columns $$$a$$$ to $$$2a-1$$$ for the second row and so on , and before ever going back to column number $$$0$$$ we fill the column $$$m-1$$$. We start again from column $$$0$$$ and keep doing the same thing until we fill $$$n \times a\;1$$$'s. The final filling sequence of columns looks like this :

$$$0,1,2,...,m-1,0,1,2,...,m-1,0,1,2,...,m-1,...,m-1$$$.

The sequence must finish at column $$$m-1$$$ because there is no remainder when $$$n \times a$$$ is divided by $$$m$$$. Since all the columns appear in the same frequency ,the sequence also shows that every column has exactly $$$\frac{n \times a}{m} = b\;\;1$$$'s filled.

I hope it helps.

How does one prove in Div. 2/D that the given relation is "actually" an equivalence relation? The reflexivity and symmetry seems trivial but I cannot come with a proof for transitivity, nor I can build any intuition strong enough to convince myself.

Thanks for clarification!

It should be 1 because we can provide the required property with the 3rd segment by deleting only the 1st segment.

Since any element of your initial input array can appear in at most $$$O(log(n))$$$ different vectors , the total space complexity would be $$$O(n*log(n)).$$$ The question should now be : Why would an element be in $$$O(log(n))$$$ vectors in the worst case? Think about the number of your recursive calls. In the worst case it's $$$O(n)$$$ because we might have leaf nodes for all the $$$n$$$ elements in our recursion tree and the number of internal nodes in such tree is $$$n-1$$$, which overall concludes to $$$2n-1$$$ nodes. Coming back to the real question, in a recursive call, an element will either go to the left or to the right vector and in our recursion tree (in the worst case) this element will appear over all the corresponding $$$O(log(n))$$$ nodes (this indeed happens when all the elements in the array is some sort of permutation) and generalizing this for all elements in the input array , we need $$$O(n*log(n))$$$ space. But please note that this $$$O(n*log(n))$$$ space complexity can be further reduced to $$$O(n)$$$ with only passing indexes of your input array to your recursive function.

Can anybody help me with the SPOJ-PERMPATT problem? I saw people building segment trees for finding minimum element but there should be one more idea i cannot catch.

Thank you a lot for your explanation, I think I got the idea, but I think there is a little typo over there : "But what happens, if we rearrange pairs x[i],y[i] so that for fixed i and all j>i:" Did you intend to say "for fixed j and all i<j"? Because you gave an example for j=7 and it seems j is fixed there. Or am I missing something?

"So, now, you only need to go through the sorted list and take best value of adjacent indices." why do we have to iterate? Think of sorting them, say in ascending order, isn't the answer N-1th element? Because Nth element is the biggest element all over the array, and N-1th element is the second-biggest element, and when we get min of them it gives second biggest element.

Can I ask how you modified DFS?