REMOSET - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: likhon5
Tester & Editorialist: iceknight1093

DIFFICULTY:

1612

PREREQUISITES:

Basic combinatorics

PROBLEM:

You’re given an array A. Find the number of non-empty subsets of indices whose removal results in every subarray having even sum.

EXPLANATION:

Suppose we removed some indices, and the array satisfies the given condition, i.e, \displaystyle\sum_{k=i}^j A_k is even, for each 1 \leq i \leq j \leq |A|.

Then, in particular this holds for i = j, which means every element must itself be even.
Of course, if every element is even then every subarray sum is also even; so we’ve reduced our problem to counting the number of ways of removing indices such that all remaining elements are even.

That’s not too hard:

  • First, all odd elements must be removed.
  • Suppose this leaves K even elements. We can then choose any subset of them to remove, for 2^K possible ways.

There’s one edge case: since the statement asks for non-empty subsets, if K = N (i.e all elements of the original array are even), the answer is 2^N - 1; since we can’t choose the empty subset.

Since K \leq N, computing 2^K can be done by just repeated multiplication using a loop.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
#define endl '\n'
#define filein freopen("input20.in","r",stdin)
#define fileout freopen("output20.out","w",stdout)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std; 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mx=2e5+9; 
const int mod=1e9+7; 
int main()
{
    fast; 
    int t; cin>>t; 
    assert(t<=10000); 
    int total=0; 
    while(t--)
    {
        int n; cin>>n; 
        total+=n; 
        int odd=0,even=0; 
        for(int i=0;i<n;i++)
        {
            int x; cin>>x; 
            assert(x>=0 and x<=200000); 
            if(x%2) odd++; 
            else even++; 
        }
        long long cnt=1; 
        for(int i=1;i<=even;i++) cnt=(cnt*2)%mod; 
        if(odd) cout<<cnt<<endl; 
        else cout<<cnt-1<<endl; 
    }
    assert(total<=200000); 
}
Editorialist's code (Python) 
mod = 10**9 + 7
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    evens = 0
    for x in a: evens += (x+1)%2
    ans = pow(2, evens, mod)
    if evens == n: ans -= 1
    print(ans%mod)
2 Likes
2 
Let BB denote the array obtained by removing any non-empty subset of indices from the array AA.
The removal of subset of indices is said to be good if:

    Sum of the subarray B[i,j] is divisible by 2 for all pairs of indices (1≤i≤j≤∣B∣).

@iceknight1093 , as i understand the problem, it considers the removal as good if the sum of the subarray B is divisible by 2. You are directly removing all odd numbers.

But what about the condition where 2 odd numbers are in the subarray B then also the sum would be even.

To explain my point with a testcase

1
3
1 2 3

here the array A is [1, 2, 3], now if we run your solution the output is 2.
so your program is considering [] and [2].
But we can infact have 3 possible “good” outputs [], [2] and [1, 2, 3].

Is my approach correct? I understand that I may have misinterpreted the problem, kindly guide me.

PS- I asked chatgpt also, he says

The statement "Sum of the subarray B[i, j] is divisible by 2 for all pairs of indices (1 ≤ i ≤ j ≤ |B|)" means that for any pair of indices (i, j) where i is less than or equal to j, the sum of the subarray B[i, j] is a multiple of 2 (divisible by 2) for all possible subarrays of B.

Let's break it down step by step:

    We have an array B, which could be any array of numbers.

    The subarray B[i, j] represents a subset of elements from array B, starting from index i and ending at index j. So, it includes elements from position i to position j in the array.

    The statement says that for all possible subarrays B[i, j], where i is less than or equal to j (meaning we consider all subarrays starting from an index and ending at or after that index), the sum of each subarray is divisible by 2.

    Divisible by 2 means that when we divide the sum by 2, there is no remainder. In other words, the sum can be evenly divided by 2 without any leftover.

For example, let's consider an array B: [1, 3, 2, 4, 6].

If we consider all possible subarrays:

    B[1, 1] = [1]. The sum is 1, which is not divisible by 2.
    B[1, 2] = [1, 3]. The sum is 4, which is divisible by 2.
    B[1, 3] = [1, 3, 2]. The sum is 6, which is divisible by 2.
    B[1, 4] = [1, 3, 2, 4]. The sum is 10, which is divisible by 2.
    B[1, 5] = [1, 3, 2, 4, 6]. The sum is 16, which is divisible by 2.

And so on for all possible subarrays. In this case, the statement holds true for all pairs of indices (i, j), and the sum of every subarray is divisible by 2.

I hope this explanation helps clarify the meaning of the statement.
1 Like
3

Even I thought the same, but it doesn’t say, sum of elements of B should be even. It says, sum of every subarray of B should be even. That’s why, we should make sure every element of B is even, so that every subarray sum in B is even. The question is constructed specifically to trick us.

3 Likes
4

And trick us it did. Thanks for the clarification @lachu49.
Actually i assumed this is some HARD problem based on the submission ratio, most of us got tricked i guess.

5

Here is my code for this specific problem, but I’m not sure why it is failing. I have given custom input and it works perfectly on them (also the sample input). But after submission, not even a single case is passed. Kindly rectify the problem I’m making.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
ll n,sum=0,ans=0;cin>>n;
ll arr[n];
for(ll i=0;i<n;i++)
{
cin>>arr[i];
sum+=arr[i];
}
for(ll i=0;i<n;i++)
{
ll sum_here=0;
for(ll j=i;j<n;j++)
{
sum_here+=arr[j];
if((sum-sum_here)%2==0)
{
ans++;
}
}
}
cout<<ans<<endl;
}
int main()
{
int t;
cin >> t;
while (t–)
solve();
return 0;
}

6

A more intuitive way was, since it was mentioned that each subarray sum is even, and a single element is subarray in itself so every element has to be even. The edge case was for when array only had even elements.

1 Like
7

But what about the edge case? when all elements are even … can anyone tell me why in this case the ans will be 2^n - 1. I didn’t understand it.

8

This is a fundamental question on PnC. Lets consider your edge case when vector has all even elements and total elements be n. Then we can remove 1, 2, 3 and so on and so forth till n.
The series will be nC1 + nC2 +… +nCn but we cannot choose nC0 since subset has to be non empty and
nC0 will mean we have not deleted any element. The sum of this series is 2 power n - 1

1 Like
9

I have one doubt.

  • When I tried this line of code to get the 2^N
    long ways = (long)Math.pow(2,evens) % mod;
    But it was the wrong answer how it is I don’t know.

    The Difference between correct answer and wrong answer for specific test case is only 1.

  • But when I changed to

             for(int i=0; i<evens ; i++){
             ways *= 2 ;
             ways %= mod;
         }

Then it was correct.

  • I use Java
10

Tricky Question but easy!

11 
#include <iostream>
using namespace std;

long long power(int a,int b, int p)
{
    long long res=1;
    
    while(b>0)
    {
        if(b&1)
        res=(res*a)%p;
        
        a=(a*a)%p;
        b=b>>1;
    }
    return res;
}
int main() {
	// your code goes here
	int t;
	cin>>t;
	
	while(t--)
	{
	    int n;
	    cin>>n;
	    
	    int a[n];
	    for(int i=0;i<n;i++)
	    cin>>a[i];
	    
	    int even=0;
	    int odd=0;
	    for(int i=0;i<n;i++)
	    {
	        if(a[i]%2==0)
	        even++;
	        else
	        odd++;
	    }
	    //long long total=0;
	    if(odd==0)
	    {
	        cout<<power(2,even,1000000007)-1<<endl;
	    }
	    else if(even==0)
	    {
	       cout<<1<<endl;
	    }
	    else
	    {
	       cout<<power(2,even,1000000007)<<endl;
	    
	    }
	}
	return 0;
}

I don’t understand where I went wrong, pondered for over 1.5 hrs yesterday; I considered the all evens/ all odd case as well. I also know that we need to consider only even elements in the ‘B’ output array. Can some1 please point out whats wrong with the code ?

12

*Bij can be an sub array even a single element in the array B is considered a subarray; u didn’t consider the constraints properly. 1<=i<=j<=n (so i=j is a possibility)
*Theyve mentioned that u remove " any non-empty subset of indices from the array A.", so u need to remove at least one element.

1 Like
13

I don’t understand what you are trying to do, but i think you need to read the editorial once again.

If you understand the point that we only have to consider the even elements, then the total possible “good” removals that we can have is 2^N (N=number of even elements). This is maths.
Example for [2, 4] you can have [], [2], [4], [2, 4] i.e. 2^2 = 4 possible combinations.

Now the edge case is when array A contains only even numbers, we have to substract 1 from the final ans because the case where B=A is not possible as we have to remove atleast 1 element from the array.

Let me explain with testcase

  1. Assume we have array A [1, 2, 4], here the subarray combinations with even elements is [2], [4], [2, 4], [] where we remove [1, 4], [1, 2], [1], and [1, 2, 4] from the array respectively.

  2. Assume we have array [2, 4, 6] here the subarray combinations with even elements is [2], [4], [6], [2, 4], [2, 6], [4, 6], []. Here we can’t have [2, 4, 6] as B=A in this case and we need to remove something.

let me know if you need further clarification for any point.

1 Like
14

you don’t have to eliminate all odd no. if odd number are in even quantities that will make overall sum even we have to consider those combinations also.

15

yea, thats what I’ve done right?!
if there are only even numbers: 2^n-1 (at least one element must be removed)
else: 2^even.
I’ve calculated exactly that. Or am I wrong?

16

We have to make sure that the subarray B[i,j] is divisible for ALL pairs. so any pair that contains odd number won’t qualify.

17

I think I found the issue, the problem is with your power function.

a*a is getting overflowed. Use 1LL * a * a to perform multiplication with long long intermediate result and prevent overflow.

1 Like
18

thank you for explaining this edge case.

19

yes right, this was trick, most of us got too caught up in the case of even odd integers.

20

this is because when you are calculating power , it will get overflowed because n can reach very high . So better technique is to use modular exponentiation which will result in 0(log(power)) time complexity. Your second approach is correct and has worked because n was less than 10 power 8. Had it been more you would have got TLE.