DISTDILEM Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S. Manuj Nanthan
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You are given an array A of N integers. You can do the following two types of operation any (possibly zero) number of times:

Pick two indices i and j (1≤i,j≤N,i≠j). Change A_j:=A_j+A_i and remove the i^th element from the array.
Pick an index i (1≤i≤N). Split A_i into two positive integers X and Y such that X+Y=A_i. Remove the i^{th} element from the array. Append elements X and Y to the array.

Find the maximum number of distinct elements present in the array after performing any number of operations of the above two types.

EXPLANATION:

For each test case, we are given the length of the array and the array of elements.

Since the first operation combines any two value of the array so the array can be reduced to a single element which is the sum of the array elements in this case.

Now the maximum number of unique elements in the array can be easily thought off as the sum of the array can be split in maximum partitions if we start with 1 and go in increasing order till the sum of these values outperforms the array sum.

The last added value minus 1 gives us the maximum possible distinct partitions of the array since the last number will be a repitition.

TIME COMPLEXITY:

O( \sqrt{(SUM(A))} ) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like
2

My idea is that ii break every no. in 1’s and 2’s and afetr that
starting from 1 till sum how mny no. i can make
why i getting wrong
heres my code can you check

void solve(){
ll n;
cin>>n;
vectorA(n);
ll cnt_2 =0;
ll cnt_1 =0;
for(int i=0;i<n;i++){
cin>>A[i];
cnt_2 += A[i]/2;
cnt_1 += A[i]%2;
}
// cout<<cnt_1<<" "<<cnt_2<<endl;
ll ans =0;
ll val = cnt_2*2 + cnt_1;
for(int i=1;i<=val;i++){
if((cnt_2>=i/2) && (cnt_1>=i%2)){
cnt_2-= i/2;
cnt_1-= i%2;
ans++;
}
}
cout<<ans<<endl;
}

3

i got it i have to break 2 in 1’s also then n*n+1/2 we can check how many no. i can make
my small mistake
my bad

4

cant we just add them all up and then write them as the sum of the first n natural numbers like ,
for the test case
1
4
1 1 3 5
what we can do is
iterate it in the follwing ways
1 1 3 5
2 3 5
5 5
10
4 6
4 3 3
4 3 2 1
this gives us four distinct integers instead of the 3 that is given in the solution
Could someone explain me whats wrong in this…
Thank You to whoever replies to this

5

here’s my solution O(n)
first I will get the no. of 1 that can be created. i.e sum of array.
Now I arrange the number as : 1, 1+1, 1+1+1, … . from all the 1’s that is present as to form 1,2,3,…k,(some remaining 1)
I need to find k such k(k+1)/2=sum

=> k=(√(8sum+1))/2 - 1/2
floor value of k is the solution.

6

Hey, the correctness of your solution depends upon what method you are using while splitting the single number back to the array.
Also, the testcase given in the example has the last value as 4, so this is a different case.

Also the method in the editorial is much more efficient as your method will require producing the array itself, which can go upto \sqrt {100000000} under maximum constraints, so the overall complexity is \sqrt{sum Of Elements Of The Array}