cryo_coder123's blog

By cryo_coder123, history, 4 years ago, In English

Recently one of my friends shared this problem with me. I really found this beautiful and thought of giving it a share.I won't spoil the essence of this problem, but definitely expecting some nice approaches and solutions in the comment.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by cryo_coder123 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

dp[i] = the longest subsequence from the first i element which has the condition (xor = k) and the last element in the subsequence is arr[i]. then dp[i] = dp[last (arr[i] ^ k)] + 1, and you can save what is the last x.

»
4 years ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

First if k=0 we can see the answer is the frequency of the element which occurs maximum number of times in the array. Else we can do the following:

First keep track of vector of positions of each element in the array. It is easy to see that the required subsequence must be of the form [x, x^k, x, x^k.....] for some 1<=x<=10^6. So just brute force for each possible value of x and greedily check the subsequence with maximum length we can obtain by using the vector of positions for x and x^k.

Time complexity: O(10^6) + O(n)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya did the same thing... have a look at my piece of code

    int maxSubsequenceLength(int n,int k,vector<int>arr){
    	int maxe=*max_element(arr.begin(),arr.end());
    	vector<int>all_pos[maxe+1];
    	for(int i=0;i<n;i++)
    		all_pos[arr[i]].pb(i);
    	vector<bool>vis(n+1,false);
    	unordered_map<int,bool>hash;
    	for(int i=0;i<n;i++)
    		hash[arr[i]]=true;
    	int ans=1;
    	for(int i=0;i<n;i++){
    		if(hash[k^arr[i]]==true and vis[i]==false){
    			int a=arr[i];
    			int b=k^arr[i];
    			int count=1;
    			bool first=false;
    			int pos=i;
    			vis[pos]=true;
    			while(1){
    				if(first){
    					auto it=upper_bound(all_pos[a].begin(),all_pos[a].end(),pos);
    					if(it==all_pos[a].end()){
    						break;
    					}
    					count++;
    					pos=all_pos[a][it-all_pos[a].begin()];
    					vis[pos]=true;
    					first=false;
    				}
    				else{
    					auto it=upper_bound(all_pos[b].begin(),all_pos[b].end(),pos);
    					if(it==all_pos[b].end()){
    						break;
    					}
    					count++;
    					pos=all_pos[b][it-all_pos[b].begin()];
    					vis[pos]=true;
    					first=true;
    				}
    			}
    			ans=max(ans,count);
    		}
    	}
    	return ans;
    }