parveen1981's blog

By parveen1981, history, 2 months ago,

Hi guys, hope you are doing well. I came across this problem 2 days ago and solved it with intuition. The same algorithm is also given in the editorial.
The problem is that I couldn't find a proper proof for that algorithm. I found this comment which seems to give some proof but I couldn't convince myself that it is a proper proof. Now, I am not able to move forward i.e. skip and solve another problems. I tried to find a proper proof for 2 days but it seems impossible. It would be great help if someone can give a proper proof. Thanks in advance.

• +13

By parveen1981, history, 2 months ago,

Hi guys, hope you are doing well. I wanted to create my debug template but I can't get around this error?

code
error

• 0

By parveen1981, history, 3 months ago,

Hello guys, I wanted to ask if there is any way such that I can pass a function to the constructor of the class and then store it as some variable so that I can execute it later.

• -3

By parveen1981, history, 3 months ago,

So, I was solving this problem today which I couldn't solve on my own. Then I saw the unofficial editorial by neal. Neal has given an amazing algorithm to solve this problem but unfortunately no proof was provided. So, I took upon myself to prove that algorithm. I would also like to ask neal to please check my proof if it is correct. Thank you. Here is my proof.

Editorial for 1400E — Clear the Multiset

Algorithm

You can only do two actions for an optimal solution. Let's say we want to find out answer for $[L,R]$.

So, first option is to take $R-L+1$ and second is: $a_m + f(l_1,r_1) + ... + f(l_z,r_z)$. So, the answer is

$f(L,R) = min(R-L+1,a_m + f(l_1,r_1) + ... + f(l_z,r_z))$, where $a_m$ is the minimum element in the segment $[L,R]$ and $[l_i,r_i]$ is the range which does not contain $a_m$ and each element of this range is decreased by $a_m$. Now, the main point for this algorithm is that when we perform operation 1, then we do so $a_m$ times and not less. Otherwise we don't perform operation 1.

Proof

First of all, we observe that if we don't apply operation 1 to $[L,R]$ and apply operation 1 to any $[l_i,r_i]$ at any later point of time, then it is better that we instead apply operation 1 to $[L,R]$ first and apply remaining operations to $[l_i,r_i]$. This will not make our answer worse. So, we can say that we only have two choice, first is that we apply operation 1 to $[L,R]$ and then recurse for remaining $[l_i,r_i]$ or we don't apply operation 1 at all and take our answer as $R-L+1$.

At first, let's consider the case when all elements are equal (valued $x$) in our array. For this case, our answer will be, $ans = min(x,len)$, where $len$ is the length of array. Let's prove this with contradiction, let's say we decrease all elements by $y$ which is smaller than $x$. So the total will be $len + y$ (after applying operation 2 on each element) which is greater than $len$. So, we either decrease the whole array by $x$ (when $x \leq len$) or we just take the length of whole array (when $len<x$).

Now, we will prove the above algorithm with the help of induction.

Step 1

Base Case: When we have two types of elements (valued $x$ and $x+m$).

First we will prove that taking elements of equal value (valued $m$) in one block will give us better value than if we take those equal elements in multiple blocks.

Let $len$ be length of the whole block and $len_1, len_2, ..., len_z$ be the lengths of multiple blocks. So, $len = len_1 + len_2 + ... + len_z$. Now, the answer for one block will be $ans_{one} = min(m,len)$.

Now, if $ans_{one} = len$, then it would mean that $ans_{multiple} = len_1 + len_2 + ... + len_z$, where $ans_{multiple}$ is the answer for multiple blocks. So, in this case, $ans_{one} = ans_{multiple}$.

And when $ans_{one}=m$, then $ans_{multiple} = w.m + len_{left}$, where $w$ is the number of blocks for which $m$ is smaller than the length of block and $len_{left}$ is the sum of lengths of remaining blocks for which $m$ is greater than or equal to the length of block.

So, we can finally conclude that $ans_{one} \leq ans_{multiple}$.

From now on, we will only consider $ans_{one}$, which will denote the worst case.

So, to the final proof for base case. Let $t$ the number of elements which are equal to $x$, so $len-t$ elements will be equal to $x+m$. Now, we consider two cases, first is when we decrease all elements by $x$, and second is when we decrease all elements by $y$ which is smaller than $x$.

For case 1,
$ans_{case1} = min(len,x+min(len-t,m))$.
For case 2,
$ans_{case2} = min(len,t+y+min(len-t,x+m-y))$
Let's analyze the second term in case 2, i.e. $t+y+min(len-t,x+m-y)$. When $min(len-t,x+m-y) = len-t$, our term will become $t + y + len - t$ equals to $len + y$ which is worse than $len$ (since our answer cannot exceed $len$). And when $min(len-t,x+m-y) = x + m - y$, our term will become $x + t + m$ which is worse than $x+m$ in the first case, since $x-y \geq 1$. Hence $ans_{case1}$ is always better.

So, we can conclude that if we apply operation 1, then we should apply it $a_m$ times, otherwise we should not apply it at all.

Step 2

Case for k+1 type elements: When we have elements whose values equals to $x, x+m_1, x+m_1 + m_2, ..., x+m_1+m_2+...+m_k$. We assume that our answer is:
$ans_k = min(len_k, x + W_{k-1})$, where $len_i$ is the length of array when there are $i+1$ types of elements, and $W_{k-1}$ is the minimum cost for case of $k$ types elements.

Step 3

Case for k+2 type elements: When we have elements whose values equals to $x, x+m_1, ..., x+ m_1 + ... + m_{k+1}$.

Now, we consider two cases, first is when we decrease all elements by $x$, second is when we decrease all elements by $y$ which is smaller than $x$. Here, $t$ is number of occurrences of $x$ in the array.

$ans_{case1} = min(len_{k+1}, x + min(len_k, m_1 + W_{k-1}))$
$ans_{case2} = min(len_{k+1}, t + y + min(len_k,x + m_1 - y + W_{k-1}))$

Now, let's analyze the second term in case 2. In one case, it will become, $t + y + len_k$, we know that $t+ len_k = len_{k+1}$, so it will become, $y + len_{k+1}$, which is worse than $len_{k+1}$. And in the other case, it will become $x + m_1 + W_{k-1} + t$ which is worse then second term in case 1, i.e. $x + m_1 + W_{k-1}$.

So, we can see that $ans_{case1}$ is always better than $ans_{case2}$.

So, we can finally conclude that it is always better to either decrease all terms by $a_m$ or not decrease at all.

• +18

By parveen1981, history, 3 months ago,

In the editorial of this problem, Can someone please tell me how do we arrive at the these equations and what are pos, x, y?

$\begin{cases} pos \equiv x \pmod n \\ pos \equiv y \pmod m \end{cases}$

• +6

By parveen1981, history, 6 months ago,

Hi guys,
I was solving this problem and I came up with somewhat wrong solution. Although my solution was wrong but I came up with new data structure. I don't know if you know this but here it is.
At first, I want to describe what I wanted to do and for what:
1. We are given a linked list in which nodes are numbered from $1$ to $n$ and they are all connected ( 1-2-3-4-...-n).
2. I wanted to remove some nodes whenever I want in $O(1)$.

So we can maintain two arrays here: $next$ and $prev$. $next[i]$ will tell us the next node which $i$ is connected to and $prev[i]$ will tell us the previous node which $i$ is connected to.
So, initially we will have $next[i]=i+1$ and $prev[i]=i-1$
Now, to remove some node, we can do the following:
$next[prev[i]]=next[i]$
$prev[next[i]]=prev[i]$
So this is the basic remove operation and you can customize it however you like.

code

• +3

By parveen1981, history, 7 months ago,

I was learning about maximum matching in bipartite graphs but I can't understand one thing i.e. augmenting path always has one extra matching edge.
Link: Hopcroft Karp Algorithm Geeks for Geeks