C++

Forum

 
I dont know why its not working

Pages: 12
alcatraz98 (12)
Katya has a sequence of integers a1,a2,…,an and an integer m.

She defines a good sequence of integers as a non-empty sequence such that the sums of all its non-empty subsequences are divisible by m.

Katya wants to know the number of good subsequences of the sequence a. Can you help her?


I have written a code for this question...but its showing wrong answer. Now i dont want source code for this question.. I just want to know whats wrong in my source code???





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <iostream>
#include<cmath>
using namespace std;

 
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int arr[n];
        int sum_of_arr = 0;
        for(int i = 0 ;i<n;i++){
            cin>>arr[i];
            sum_of_arr+=arr[i];
        }
        int count = 0;
        unsigned long int optsize = pow(2,n);
        for(long int counter = 1;counter<optsize;counter++){
            int len = 0;
            int ans = 0;
            for(int j = 0 ;j<n;j++){
                if(counter & (1<<j)){
                    len+=1;
                    ans+=arr[j];
                }
            }
    
            int po = pow(2,len-1);
            if((po*ans)%m==0 && ans != sum_of_arr)
                count+=1;
        }
        
        cout<<count<<endl;
    }
 
    return 0;
}
Last edited on
closed account oG3kizwU (15)
@alcatraz98 can you please tell in brief about your logic?
alcatraz98 (12)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include<bits/stdc++.h> 
using namespace std; 
  
// Return sum of sum of all sub-sequence. 
int sum(int arr[], int n) 
{ 
  int ans = 0; 
  
  // Finding sum of the array. 
  for (int i = 0; i < n; i++) 
    ans += arr[i]; 
  
  return ans * pow(2, n - 1); 
} 
  
// Driver Code 
int main() 
{ 
  int arr[] = { 6, 7, 8 }; 
  int n = sizeof(arr)/sizeof(arr[0]); 
  
  cout << sum(arr, n) << endl; 
  
  return 0; 
}


This code is use for generating sum of sum of all subsequences...You can refer it here...
https://www.google.co.in/amp/s/www.geeksforgeeks.org/find-sum-sum-sub-sequences/amp/

And to generate subsequences of sequence we use below algorithm...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
 #include<bits/stdc++.h> 
using namespace std; 
  
void printSubsequences(int arr[], int n) 
{ 
    /* Number of subsequences is (2**n -1)*/
    unsigned int opsize = pow(2, n); 
  
    /* Run from counter 000..1 to 111..1*/
    for (int counter = 1; counter < opsize; counter++) 
    { 
        for (int j = 0; j < n; j++) 
        { 
            /* Check if jth bit in the counter is set 
                If set then print jth element from arr[] */
            if (counter & (1<<j)) 
                cout << arr[j] << " "; 
        } 
        cout << endl; 
    } 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = {1, 2, 3, 4}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "All Non-empty Subsequences\n"; 
    printSubsequences(arr, n); 
    return 0; 
}
..
You can refer to this...
https://www.google.co.in/amp/s/www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/amp/

Now you can understand what I did ...
blackmamba (122)
its gonna give tle anyway,
tyr a different approach
alcatraz98 (12)
But we have to generate subsequences anyway...and I know this method only ...
blackmamba (122)
again think of a different method
hint: u dont have to generate subsequences
alcatraz98 (12)
Can anyone tell me how to do it??
closed account oG3kizwU (15)
@alcatraz98 pm me.
closed account 3UohqMoL (121)
can anyone help with this

You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X.

Next, consider the number of pairs of indices (i,j) in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y.

Find the minimum possible value of X+Y.
closed account 3UohqMoL (121)
can Anyone help me with his

You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X.

Next, consider the number of pairs of indices (i,j) in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y.

Find the minimum possible value of X+Y.
healer29 (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin>>t;

	while(t--)
	{
		long long int n,m,i,j,k,sum=0,count=0;
		long long int sumall=0;
		cin>>n>>m;

		long long int v[n];

		for(long long int i=0;i<n;i++)
		{
			cin>>v[i];
			sumall+=v[i];
		}
    
    	for (i=0; i <n; i++)
    	{
        	for (j=i; j<n; j++)
        	{
        		sum=0;
            	for (k=i; k<=j; k++)
            	{
            		sum=sum+v[k];
                //cout << v[k] << " ";
            	}

            	//sum=sum*(j-i+1);

            	//cout<<sum<<"x"<<pow(2,j-i)<<endl;
            	sum=sum*pow(2,j-i);

            	if(sum%m==0)
            	{
            		count++;
            	}
 
            //cout << endl;
        	}
    	}

    	long long int l=sumall*pow(2,n-1);

    	if(l%m==0)
    	{
    		count=count-1;
    	}

    	cout<<count<<endl;
		
	}
}


In this way the number of comparisons are reduced by many many factors as compared to alcatraz code. TLE is now not coming but still this is WA. When inputs are a[n]=1,2,3,4,5 and M=3, my output is 6 and alcatraz output is 10. I know from my friends that 6 is not correct output, But I am not sure about 10.

Can anyone give idea how to improve this code.

Alcatraz goes with 2^n , max = 10^9;
My code does n^3 at max, max=30^3=27000;
healer29 (3)
Now, I get it. Just do one thing ,if any one is lagging somewhere. count the number of numbers that are divisible by m, then count the number of possibilities of those number.

Try, search, try, search......till you get correct answer.
closed account (Lwk3URfi)
Listen everyone!

There is no need to write such complex codes. The problem is very simple once you understand the meaning of the question. You have to find the number of sub-arrays of the given array such that :
1. all the elements in the sub-array are divisible by the given number.
2. Sum of the elements in sub-array is divisible by given number(this is automatically satisfied if
u satisfy the first condition.So, dont bother about this.)

So, now you know what to do. You have to count the number of elements in the main array which are divisible by the required number(let it be x). And find the number of sequences you can generate by using these x elements(which is (2^x)-1).

Do this and you will get 100 points.
blackmamba (122)
@NamelessGirl done no strings attached?
closed account (Lwk3URfi)
No. I tried, but got WA in all the sub-tasks. Anybody who can help me?
imrajkumar (2)
Is 1 , 2 with m=3 a good subsequence? I am confused by the definition of a good sequence as sum of all its subsequences ("1"+"2"+"1,2") is 6 which is divisible by 3. But according to the question "1","2","1,2" all of them must be divisible by 3 which is not satisfied.

So please help.
Last edited on
blackmamba (122)
sum of each subsequence must be divisible,
as 1 is not divisible so its not.
closed account (Lwk3URfi)
@imrajkumar
Please read the two conditions I have mentioned above.
Both the sum and the individual elements must be divisible by m.
here, if u consider the sub array {1,2}, only the sum(which is 3) is divisible by m.
But the individual elements(which are 1,2) are not divisible by m.
so, it cannot be considered as a required sub-sequence.
closed account (Lwk3URfi)
Example : If u consider array {1,2,3,4,5,6} with m=3

Only 3,6 are divisible by 3. so count=2
no.of subsequences=(2^2)-1=3 which are {3}{6}{3,6}. Hence 3 is the answer.
Note that , both the sum of these subsequences and individual elements are now divisible by m.
I hope u understood now.
imrajkumar (2)
thanks @NamelessGirl . This question never requires to find the subsequences at all , got to know about it just after posting this question.
Pages: 12