# COST_MANIA - Editorial

Author: Akshat Gupta
Tester: Anshul

EASY-MEDIUM

# PREREQUISITES:

Math, Bit-wise Operations

# PROBLEM:

Given an array A and B of lengths N.
H(i,j)=i \cdot j-D \cdot (B_i \oplus B_j)
Find the Maximum value of H(i,j) such that A_i \leq j

# QUICK EXPLANATION:

It can be proved that only i , j such that N-2*D \leq i , j can contribute to the answer.
Hence we can use brute-forced on this range having time complexity O(D^2)

# EXPLANATION:

It can be observed that for every i \neq N , A_i \leq N, Hence Every i can have a reaction with N.

H(N-1,N)=(N-1) \cdot N -D \cdot (B_{N-1}\oplus B_{N})
The Maximum value (B_{N-1}\oplus B_{N}) can have is 2 \cdot N
Hence, H_{\min}(N-1,N) is (N-1) \cdot N -2 \cdot D \cdot N

Now, Let i \in [1,N-1]
H(i,N)=i \cdot N -D \cdot (B_{i}\oplus B_{N})
The Minimum value of (B_{i}\oplus B_{N}) is 0
Hence ,H_{\max}(i,N) = i \cdot N
also H_{\max}(i,j) < H_{\max}(i,N) \forall j \in [2,N-1]
So H(i,j) is at most H_{\max}(i,N) = i \cdot N

Any i can possibly be answer only if
H_{\min}(N-1,N) < H_{\max}(i,N)
\Rightarrow (N-1) \cdot N -2 \cdot D \cdot N < i \cdot N
\Rightarrow (N-1) -2 \cdot D< i
\Rightarrow N -2 \cdot D \leq i

So we can check \forall i,j \in [N-2 \cdot D,N] and i<j

# SOLUTIONS:

Setter's Solution
        #include<bits/stdc++.h>
using namespace std;
#define nl <<'\n'
#define sp <<" "<<
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long int

template<class T>
void _dprint(vector<T> a){display(a)};
template<class T>
void _dprint(T a){cerr<<a<<"\n";}
void solve()
{
ll n,d;
cin>>n>>d;
vector<ll> a(n+1),b(n+1);
for(ll i=1;i<=n;i++){
cin>>a[i];
}
for(ll i=1;i<=n;i++){
cin>>b[i];
}
ll ans=-1e15;
for(ll i=max(n-2*d,1ll);i<=n;i++){
for(ll j=a[i];j<=n;j++){
ans=max(ans,i*j-d*(b[i]^b[j]));
}
}
cout<< ans nl;
}

int main()
{
fast_io;
int t;
cin>>t;
while(t--)
solve();
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std ;

#define ll              long long
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2401
#endif

int _runtimeTerror_()
{
int n, d;
cin >> n >> d;
vector<int> a(n+1), b(n+1);
for(int i=1;i<=n;++i) {
cin >> a[i];
}
for(int i=1;i<=n;++i) {
cin >> b[i];
}
ll ans = -INF;
for(int i=n-1;i>=max(1, n-2*d-10);--i) {
for(int j=a[i];j<=n;++j) {
amax(ans, i * 1ll * j - d * (b[i] ^ b[j]));
}
}
cout << ans << "\n";
return 0;
}

int main()
{
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initncr();
#endif
int TESTS = 1;
cin >> TESTS;
while(TESTS--) {
_runtimeTerror_();
}
return 0;
}

3 Likes

Similar problem to this :-https://codeforces.com/problemset/problem/1554/B

7 Likes

Can anyone explain/ give proof why

The max value of B[n-1] xor B[n] is 2*N?

1 Like

As the maximum values of d*(bi xor bj) can be 2 * n * d so the maximum values our i * j can decrease will be 2 * n * d . Hence is it sufficient to only check for j = [n-log2(2 * n * d) , n] and i = [n-2d, j] .
Is this approach correct if not what is the flaw?
this approach passes system tests… so like if it’s wrong then system test cases must be weak…
Ac submission for this approach

Is there any significance of the condition (i+1)<=Ai<=N ?

Use the code below to find the max value of XOR of 2 number. Change the value of N as needed. Ultimately none of the max value will exit (2 x N). Most of the case it is less then (1.5 x N). But it is safe to use (2 x N) as highest limit.

int mx=INT_MIN, I, J, N;
N=1000000;
for(int i=0; i<=N; i++)
{
int j=N;
if((i^j)>mx)
{
mx=(i^j);
I=i;
J=j;
}
}
cout << I << " \t^ \t" << J << " \t: \t" << mx << "\n";


What’s the purpose of x=log2(n2d) ?
It should’ve been x=2nd , isn’t it?

The max value will never exceed 2*N because in the worst case, N can be a power of 2, here if we consider B[n] = N, and B[n-1] = N-1, we have their bit representation as:

N1000000...
(N-1)0111111...

And their XOR will be (2*N) - 1, which does not exceed 2*N

Yes, it to assure that the reaction can only be done to elements where j>i, and there will always be some reagents with whom salt i can react with.

As on now I cannot think of any particular case at which this would fail.

This approach is incorrect consider this test case.

1
5 1
2 3 5 5 6
2 2 2 4 3


The correct answer should be 14 but your algorithm will return 13.

I’m getting 14 as the answer! Though had to make some changes in the code!
Link to ideone: IUdtjA - Online C++0x Compiler & Debugging Tool - Ideone.com