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.
1 Like
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?
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.
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?
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.
2 Likes
import java.util.*;
class chef2
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int ar1[]=new int[t];
int l=0;
for(int j=0;j<t;j++)
{
int f=0;
int n=sc.nextInt();
int m=sc.nextInt();
int ar[]=new int[n];
for(int i=0;i<n;i++)
ar[i]=sc.nextInt();
for(int i=0;i<n;i++)
{
for(int r=1;r<=n;r++)
{ int c=0;
for(int k=i;k<r;k++)
{
if(!(i==0&&r==n))
c=c+ar[k];
}
if((c%m==0)&&c!=0)
f++;
}
}
ar1[l]=f;
l++;
}
for(int i=0;i<t;i++)
{
int z=ar1[i];
System.out.println((int)(Math.pow(2,z)-1));
}
}
}
hey can anyone tell why this solution is giving WA for second task?..
when i am submitting like this it is giving AC -
int sum=pow(2,freq)-1;
link for correct solution.
https://www.codechef.com/viewsolution/20327375
but when i am using this-
cout pow(2,freq)-1 ;
it is not giving AC
link…CodeChef: Practical coding for everyone
thanks in advance…
@vijju123 @vivek_1998299 @meooow
1 Like
pow(2,cnt)-1 is giving WA in second test case but 1<<c gives CA. Why?
Please give an example of that. I am unable to get your query. 
2 Likes
ALL sub-sequenes must be divisible by 5. In {2,3} , the sub -sequences {2} and {3} are not divisible by 5
1 Like
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…
I need to refresh page to get to know that someone already answered and I get busy typing instead xD
1 Like
@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?
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 )
@l_returns Got it now ! Looks like problem setter is inspired by inception while creating this one xD
3 Likes
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
couldn’t solve this too easy XD
haha xD…
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
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.