DP approach in XOMMON(Practice)

help
, , ,
1

Can someone help with the approach of this problem? I already have a brute force solution but it exceeds time limit.

Here is the link to the problem: XOMMON Problem - CodeChef

3

You can first find all the pairwise xor values of the elements of the array and store them in a vector along with the elements. Then you can sort the vector created according to the increasing values of the xor values.

Then make a dp array and assign all the values of the array initially as 1. Then traverse the xor values and find the maximum increasing sequence.

suppose the vector : vector <array<int,3>> store;
then store the all the pairwise xor values on 0 index, first value in 1 index and second value in 2nd index.

dp[store[i][2]] = max(dp[store[i][2]],dp[store[i][1]] + 1)

then find the maximum element in the dp array.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define ar array


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r+", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w+", stdout);
#endif

    int n;
    cin >> n;
    ll arr[n];
    for(int i=0;i<n;i++) {
    	cin >> arr[i];
    }
    vector <ar<ll,3>> store;
    for(int i=0;i<n;i++) {
    	for(int j=i+1;j<n;j++) {
    		store.pb({arr[i]^arr[j],i,j});
    	}
    }

    sort(store.begin(),store.end());

    vector <ll> dp(n,1);

    for(auto u: store) {
    	dp[u[2]] = max(dp[u[2]],dp[u[1]] + 1);
    }

    ll ans = *max_element(dp.begin(),dp.end());
    assert(ans != 0);
    cout << ans << '\n';
}
2 Likes