Блог пользователя cryo_coder123

Автор cryo_coder123, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 года назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;
    }