Yesterday's daily problem, E1913. Maximum Product Difference Between Two Pairs, is a very easy one.
Description:
The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).
For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.
Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.
Return the maximum such product difference.
Constraints:
4 <= nums.length <= $10^4$
1 <= nums[i] <= $10^4$
This problem is very easy, one just needs to find the largest two numbers and the smallest two. This works because all the elements are positive.
So, naturally, I wonder, what if 0 and negative numbers are allowed? I.e, the second constraint becomes $-10^4$ <= nums[i] <= $10^4$?
At first, I thought, this is just a little more complicated. But as I attempted to solve it, I figured that this problem has quite a few special situations that I must take care of. It takes a lot of patience and carefulness.
Here is the test program that I wrote in C++. Are you able to solve this problem correctly? (The solution must still be $O(n)$.)
(Let me know if you translated it into a different language. I'll add them or link them.)
```cpp
#include <bits/stdc++.h>
using namespace std;
int yourSolution(vector<int> &v){
//input your solution here
}
int bruteForce(const vector<int> &v,int &i1,int &i2,int &i3,int &i4){
const int sz=v.size();
int r=0,e1,e2,e3,e4,t;
for(int i=0;i<sz;++i){
e1=v[i];
for(int j=i+1;j<sz;++j){
e2=v[j];
for(int k=j+1;k<sz;++k){
e3=v[k];
for(int l=k+1;l<sz;++l){
e4=v[l];
t=abs(e1*e2-e3*e4);
if(t>r) r=t,i1=e1,i2=e2,i3=e3,i4=e4;
t=abs(e1*e3-e2*e4);
if(t>r) r=t,i1=e1,i2=e3,i3=e2,i4=e4;
t=abs(e1*e4-e3*e2);
if(t>r) r=t,i1=e1,i2=e4,i3=e3,i4=e2;
}
}
}
}
return r;
}
default_random_engine rg(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<int> rollEle(1,10000);
const int optSize=12;
const int maxSize=32;
uniform_int_distribution<int> rollPos(0,maxSize-1);
uniform_int_distribution<int> roll0(0,1);
uniform_int_distribution<int> rollExtreme(0,1);
void noNeg(vector<int> &v){
v.resize(maxSize);
for(int i=0;i<maxSize;++i) v[i]=rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
}
void noPos(vector<int> &v){
v.resize(maxSize);
for(int i=0;i<maxSize;++i) v[i]=-rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
}
void mixed(vector<int> &v){
v.resize(maxSize);
for(int i=0;i<maxSize/2;++i) v[i]=rollEle(rg);
for(int i=maxSize/2;i<maxSize;++i) v[i]=-rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
}
void neg2posN(vector<int> &v){
if(rollExtreme(rg)){
v=vector<int>{1,1,1,1,1,3,1,-1000,1,1,1,1,1,1,1,-1000,1,1,1,1,2,1,1,1,1};
if(rollExtreme(rg)) v=vector<int>{1,1,1,1,1,3,1,1000,1,1,1,1,1,1,1,-1000,1,1,1,1,-2,1,1,1,1};
if(roll0(rg)) v[0]=0;
return;
}
v.resize(maxSize);
for(int i=2;i<maxSize;++i) v[i]=rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
v[0]=-rollEle(rg);
v[1]=-rollEle(rg);
}
void neg1posN(vector<int> &v){
v.resize(maxSize);
for(int i=2;i<maxSize;++i) v[i]=rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
v[rollPos(rg)]=-rollEle(rg);
}
void pos2negN(vector<int> &v){
if(rollExtreme(rg)){
v=vector<int>{-1,-1,-1,-1,-1,-3,1,-1000,-1,-1,-1,-1,-1,-1,-1,1000,-1,-1,-1,-1,-2,-1,-1,-1,-1};
if(rollExtreme(rg)) v=vector<int>{1,1,1,1,1,3,1,-1000,1,1,1,1,1,1,1,-1000,1,1,1,1,2,1,1,1,1};
if(roll0(rg)) v[0]=0;
return;
}
v.resize(maxSize);
for(int i=2;i<maxSize;++i) v[i]=-rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
v[0]=rollEle(rg);
v[1]=rollEle(rg);
}
void pos1negN(vector<int> &v){
v.resize(maxSize);
for(int i=2;i<maxSize;++i) v[i]=-rollEle(rg);
if(roll0(rg)) for(int i=0;i<3;++i) v[rollPos(rg)]=0;
v[rollPos(rg)]=rollEle(rg);
}
void pos2neg2(vector<int> &v){
v.resize(4);
v[0]=rollEle(rg);
v[1]=-rollEle(rg);
v[2]=-rollEle(rg);
v[3]=rollEle(rg);
}
void pos2neg2and0(vector<int> &v){
v.resize(maxSize);
v[0]=rollEle(rg);
v[1]=-rollEle(rg);
v[2]=-rollEle(rg);
v[3]=rollEle(rg);
}
void pos2neg1and0(vector<int> &v){
v=vector<int>(maxSize,0);
v[0]=rollEle(rg);
v[1]=-rollEle(rg);
v.back()=rollEle(rg);
}
void neg2pos1and0(vector<int> &v){
v=vector<int>(maxSize,0);
v[0]=-rollEle(rg);
v[1]=rollEle(rg);
v.back()=-rollEle(rg);
}
void neg1pos1and0(vector<int> &v){
v=vector<int>(maxSize,0);
v[1]=rollEle(rg);
v.back()=-rollEle(rg);
}
void (*updateTest[optSize]) (vector<int>&)={noNeg,noPos,mixed,neg2posN,neg1posN,pos2negN,pos1negN,pos2neg2,pos2neg2and0,pos2neg1and0,neg2pos1and0,neg1pos1and0};
int main(){
int i1,i2,i3,i4;
int repeat=10000;
vector<int> test;
uniform_int_distribution<int> rollOpt(0,optSize-1);
for(int i=0;i<repeat;++i){
updateTest[rollOpt(rg)](test);
int result=yourSolution(test);
int maxi=bruteForce(test,i1,i2,i3,i4);
if(result!=maxi){
cout<<"iteration number:"<<i<<endl;
cout<<"input is ";
for(auto e:test) cout<<e<<",";
cout<<endl;
cout<<"Your answer is "<<result<<", but the maximum is abs("<<i1<<"*"<<i2<<"-"<<i3<<"*"<<i4<<")="<<maxi<<".\n";
return 0;
}
}
cout<<"All passed!\n";
return 0;
}
```
For simplicity and speed, the test cases are not randomly shuffled, but it probably doesn't matter too much in this context. A bigger problem is, the extreme cases are too rare, so I added some of them manually. If you think there are other extreme cases that should be included, let me know!
I wrote my own solution and it passed all test cases, but I'm still not 100% sure it's correct. Let me know if you wrote a better test case generator that covers more corner cases!
No comments:
Post a Comment