Fail to pass Few test Cases

Can someone please help me, where my code fails. It’s as per editorial. I understood the algorithm but can’t code it for all test cases.

Made a lot of submissions, now I need the help of the forum.

link-Best maximum product

my solution - ide

I devoted lot of time Please help me!!

Seriously, your code is not very concise, which makes it diffcult to debug. Can you make your code simpler and your mind clearer? Remember, less is more!:blush::blush::blush:

4 Likes

Updated, and simplified code as far as I can.
Plz have a look

Your Code gave me brain cancer. NOT COOL.

Updated code.
Its as per editorial.

your code gives wrong answer for this case:

1
5 2
-10 10 2 -1 -3

actual answer 30, your code gives 20

Fixed
Thanks But still WA

In fact, your thinking is still not concise enough, which makes your code a lot of unnecessary places, which increases your thinking capacity.

For example, it’s unnecessary for you to judge every number you choose, because there will be modular operations in the operation process, which will make the problem more troublesome.

I tried to understand by referring other codes, but too lengthy and difficult to understand.

My advice to you is to find K dights with larger absolute value directly, then see if there are odd negative numbers in them, and pay attention to some special cases.

I think there may be more cases, like these, you should hear to what fruitloop is saying

Bro that is correct output

Oh, I didn’t read the whole problem… cool, but still your code is giving WA, so try to use a different approach maybe…

I think I’m doing a mistake in finding modulo.
Can anyone tell equation to find modulo of product of series of numebers?

For eg- I want to find the product of modulo from -10^3 to 10^3 (suppose excluding zero)
what will be code formulation.

So…After trying this problem, here’s few points:

1.) there are 2 cases, 1st check if result is gonna be neagtive(i.,e max is negative and k is odd), then simply pick the greatest values(negative, so absolute is less).
2.) in 2nd case, you need to see if you pick two negatives or two positives which will give better result.
3.) You can simply use two pointers, for left and right part of the sorted array.
4.) It’s better to pick raw inputs and run through the code. you’ll understand it better.

I have tried to code concisely, So that you could understand it better:

#include <bits/stdc++.h>

using namespace std;
const int MOD	= 1e9 + 7;
int main() {

int t;cin>>t;while(t--){

	int n,k;cin>>n>>k;
	vector<long long> arr(n);
	for(int i=0;i<n;i++)
		cin>>arr[i];

	sort(arr.begin(),arr.end());  //sort here, increasing order

	long long res=1;int left=0,right=n-1; //initialise res, and left part, right part

	if(arr[n-1]<0 && k%2==1)  //1st case where result will be negative
	{
		for(int i=n-1;i>=n-k;i--)  //multiply till k values
			res=(res*arr[i])%MOD;
		
	}
	else  //2nd case
	{
		for(int i=left,j=right;i<n && j>=0 && k>0;)  //pretty straightforward
		{
			long long x=(arr[i]*arr[i+1]);  //first two (2 negatives)
			long long y=(arr[j]*arr[j-1]);  // or last two (2 positives)

			if(k>1)  //if(k is 1, then only pick positive)
			{
				if(x>y) //if negatives gives better result
				{
					res=((x%MOD)*(res%MOD))%MOD;  
					i+=2; //since you picked two negatives +2
					k-=2; 
				}
				else
				{
					res=((arr[j]%MOD)*(res%MOD))%MOD; //choose only 1 positive at a time
					j--;
					k--;
				}
			}
			else
			{
				res=(res*arr[j])%MOD; //told above
				j--;
				k--;
			}

		}
}
	
res=(res+MOD)%MOD;  //you need to do only this, to get both positive or negative values correct
cout<<res<<"\n";
}
return 0;
}
1 Like

Thanks.
Range for array value is -10^9 to 10^9. So multiplying directly will not cause overflow??
It shud be :

((arr[i] % MOD) * (arr[i+1]%MOD))%MOD

??

Just use a long long array.
Why would it? it’s long long, it should be fine.