MGCSET - Editorial

editorial
, ,
1

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Basic combinatorics

PROBLEM:

You have a sequence of integers a_1,a_2,\dots,a_n and an integer m.

Good sequence is an integer sequence such that sum of elements in each of its subsequences is divisible by m.

You have to calculate number of good subsequences of a.

QUICK EXPLANATION:

Output 2^k-1 where k is number of a_i divisible by m.

EXPLANATION:

Sequence is good \iff all of its elements are divisible by m. Both implications are obvious: \Longleftarrow follows from the fact that if a and b are divisible by m than a+b is also divisible by m and \implies follows directly from definition of the good sequence. Thus if a_{i_1}, \dots, a_{i_k} is subsequence of all numbers divisible by m, you can use any its subsequence except for the empty one. Thus the answer is 2^k-1 because for each element of this subsequence you will either take it or not and we subtract 1 to not count the case when we don’t take anything.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

1 Like
2

I dont think that this is a correct solution because there might be duplicates present in the sequence in which case the solution won’t be simply 2^n -1 where n= no. of ai dvisible by m. Please correct me if I am wrong.

3

Please give an example of that. I am unable to get your query. :slight_smile:

1 Like
4

Let’s Consider the case where a[]={2, 3, 5} and m = 5, and the answer would be 3 ({2, 3}, {5}, {2, 3, 5}). But according to above definition, since 2 and 3 are not divisible by 5, the value of k is 1, which gives the answer as 1. Can you justify above explanation for this case?

5

ALL sub-sequenes must be divisible by 5. In {2,3} , the sub -sequences {2} and {3} are not divisible by 5

6

subsequences can have duplicate subsequences too…
link all subsequences of
2 2
are
2
2
2 2
so there are exactly 2^{n}-1 subsequences…
Remember its not “power set”… its subsequences…

7

I need to refresh page to get to know that someone already answered and I get busy typing instead xD

1 Like
8

@vijju123 “She defines a good sequence of integers as a non-empty sequence such that the sum of the elements in each of its non-empty subsequences is divisible by m”, From what i have understood is division is performed over summation of the elements ins the sub sequence, the sum of sub-sequence {2, 3} is 5 which is divisible by 5. Did i understand wrong?

9

yes you understood wrong… u have to sum elements of subsequences of subsequence…
That means one of its subsequence is {2,3}
but now sum of elements of subsequences of {2,3} should be divisible by m
i.e. subsequences of {2,3}
are
{2} (not divisible)
{3} (not divisible)
{2,3}
( 2+3 divisible but doesn’t matter u need all the subsequences to be divisible… and {2} , {3} are not )

10

@l_returns Got it now ! Looks like problem setter is inspired by inception while creating this one xD

2 Likes
11

Let’s say the sequence is {5,10,15) So the possible sequence will be {5},{5,10},{5,10,15},{10},{10,15},{15}.
Hence there will be just 6 subsequences. I don’t think {5,15} is a valid subsequence.
According to me, there should be n*(n+1)/2 such possible sequences.

12

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

So {5,15} is a valid subsequence of the given sequence.

The n*(n+1)/2 cases you are talking about, they are subarrays and not subsequences

13

couldn’t solve this too easy XD

14

haha xD…

15

Hi, I have certain reservations regarding the general formula.

When I tried the solving the problem considering the following sequence a = [1,5,10,15] and M=5. It would have the following subsequences [1],[5],[10],[15], [1,5], [1,10],[1,15],[5,10],[5,15],[5,10,15],[10,15],[1,5,15],[1,5,10,15].
out of which only [5],[10],[15],[5,10],[10,15],[5,15],[5,10,15], [1,5,10,15]. are the subsequences that satisfy the criteria as said by the above general formula.

However, If I Tried the same general formula using another sequence b=[1,2,3] and M = 3. you have the following subsequences [1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]. Out of which [3], [1,2],[1,2,3] are good subsequences. but if you go by the formula, the number of elements in the main sequence that are divisible by 3 is just 1. so pow(2,1)-1 = 1
but it’s the wrong answer. What’s with that? can somebody tell me where I’m going wrong?

16

How is [1, 2] a good sequence? A good sequence is a sequence all of whose subsequences are divisble by m. [1, 2] has subsequences [1], [2], [1, 2] and out of these only [1, 2] is divisible by 3 while [1] and [2] aren’t.

1 Like
17

The question says that the sum of the elements should be divisible by m, the test case where 1 and 2 are the ai’s, even though 1 and 2 individually are not divisible by 3 their sum(1+2 = 3) is divisible by 3, but the expected answer to this test case is 0, whereas, one sequence {1,2} is a valid answer, so should the answer not be one? I am confused here.

18

Good sequence is defined as a non-empty sequence such that the sum of the elements in each of its non-empty subsequences is divisible by m.

For {1,2}

Its non-empty subsequences are {1},{2},{1,2}

for a good sequence all of the subsequences should divisible by m but {1},{2} are not divisible by 3.

19

Alright! “in each”, got it.

20

[1,2] is a good subsequence since 1+2 is divisible by 3. The problem statement mentions a good subsequence if its sum is divisible by 3, and by not parting the subsequence into another subsequence as you have done by parting [1,2] into [1], [2], [1,2]. The original [1,2] is already a subsequence. Please correct me if I am wrong. Thank you!