COST_MANIA - Editorial


Div-2 Contest
Div-3 Contest
Div-4 Contest

Author: Akshat Gupta
Tester: Anshul




Math, Bit-wise Operations


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


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)


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


Setter's Solution
        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;
            vector<ll> a(n+1),b(n+1);
            for(ll i=1;i<=n;i++){
            for(ll i=1;i<=n;i++){
            ll ans=-1e15;
            for(ll i=max(n-2*d,1ll);i<=n;i++){
                for(ll j=a[i];j<=n;j++){
            cout<< ans nl;
        int main()
            int t;
Tester's Solution
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__)
#define debug(...) 2401

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
    #ifdef NCR
    int TESTS = 1;
    cin >> TESTS;
    while(TESTS--) {
    return 0;

Similar problem to this :-


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… :thinking:
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;
for(int i=0; i<=N; i++)
    int j=N;
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:


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.

Yes, your approach seems correct.
As on now I cannot think of any particular case at which this would fail.

This approach is incorrect consider this test case.

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 -