PROBLEM LINK:
Div-2 Contest
Div-3 Contest
Div-4 Contest
Author: Akshat Gupta
Tester: Anshul
DIFFICULTY:
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;
}
