DELDIF - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A. You can repeat the following operation:

  • Choose indices i, j such that A_i = A_j. Delete A_i and A_j from A, and append |A_i - A_j| to the array.

Find the minimum possible final length of A.

EXPLANATION:

Since we have A_i = A_j, |A_i - A_j| = 0 always.
That means every operation just involves deleting two equal elements from A and appending a 0 to it.

Each operation reduces the length of A by 1, so our aim is really just to perform as many operations as possible - this is what will minimize the length of A.

Since the only element we can possibly create is 0, for any integer x\gt 0 that occurs \text{freq}[x] times in A, we can perform \left\lfloor \frac{\text{freq}[x]}{2} \right\rfloor operations using x.
Note that each operation functionally increases the number of zeros, so increase \text{freq}[0] by \left\lfloor \frac{\text{freq}[x]}{2} \right\rfloor for each x.

Once this is done, we have no more than one occurrence of anything that’s \gt 0, so let’s look at the zeros.
Each operation done on zeros reduces the frequency of zeros by 1; however since we need two operations to do so, it’s not possible to reduce the frequency below 1 if it’s already 1.
Essentially, we can set \text{freq}[0] \to \min(1, \text{freq}[0]).

After all changes have been made, the answer is the sum of the \text{freq} array.

An alternate implementation is to note that the process can just be simulated: for each x, while \text{freq}[x] \geq 2, reduce \text{freq}[x] by 2 and increase \text{freq}[0] by 1.

TIME COMPLEXITY:

\mathcal{O}(N ) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    freq = [0]*(n+1)
    for x in a: freq[x] += 1
    for x in reversed(range(n+1)):
        while freq[x] >= 2:
            freq[x] -= 2
            freq[0] += 1
    print(sum(freq))
1 Like
2

hello i am unable to determine where my code is going wrong for this question the code is as follows can u please give the testcase in which it fails (it failed in the 3rd test case)

include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int x;
unordered_map<int,int> f;
for(int i=0;i<n;i++){
cin>>x;
f++;
}
long long count = 0;
for(auto it : f){
if(it.first == 0)
continue;

        if(it.second > 1) 
            f[0] = 1;
        if(it.second&1)
            count++;

    }
    if(f[0]>=1) count++;
    cout<<count<<endl;
}
return 0;

}