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.
Alright! “in each”, got it.
[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!
whats wrong with this?
no question is wrong.
I am getting partial correct answer with this can anyone tell me whats the issue is?
int main(void){
long int t;
cin>>t;
while(t–){//cout<<t<<"\n";
long long int n,m,x,cnt=0;
cin>>n>>m;
while(n–){
cin>>x;
if(x%m==0)cnt++;
}
cout<<(pow(2,cnt)-1)<<"\n";
}
return 0;
}
When you are directly doing cout << pow(2, freq)-1 it will output it as it is which means pow(2, freq) is outputting answers in double format which can make answers wrong for bigger constraints. But when you are putting it in int sum = pow(2, freq)-1 it converts/casts itself to int and then outputting the ans will give AC even for bigger constraints.
If you directly want to output the answer then you have to do like this cout << (int)pow(2, freq)-1;
which is casting the double to int.
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
//Your Solve
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] res = new int[n];
for(int i=0;i<n;i++)
{
int a = sc.nextInt();
int[] t = new int[a];
int k = sc.nextInt();
for(int j=0;j<a;j++)
{
t[j] = sc.nextInt();
}
for(int i1=0;i1<t.length;i1++)
{
int count = 0;
int sum = t[i1];
if(sum%k == 0)
{
count++;
}
for(int j1=i1+1;j1<t.length;j1++)
{
sum = sum+t[j1];
if(sum%k == 0)
{
count++;
}
}
res[i1]=count;
}
}
for(int i=0;i<n;i++)
{
System.out.println(res[i]);
}
}catch(Exception e){
return;
}
}
}
this is my code i guess this will work please check this code and please say if i am wrong
Sir can you prove why the answer will be 2^k-1 ? please 
Sir can you prove why the answer will be 2^k-1 ? please
can you prove why the answer will be 2^k-1 ?
its a deep request