# DP approach in XOMMON(Practice)

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: https://www.codechef.com/problems/XOMMON

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]] = max(dp[store[i]],dp[store[i]] + 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] = max(dp[u],dp[u] + 1);
}

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