Home > Applied Algorithms, Arrays, Bit Manipulation, Iteration > Sub-sequences (ICPC 2011 Amritapuri Online Contest)

Sub-sequences (ICPC 2011 Amritapuri Online Contest)

Problem Statement: You are given a sequence of N numbers A[1..N]. Consider a sub-sequence (of continuous or non-continuous elements in the same order as given) such that the bitwise AND of all the numbers of the sub-sequence is equal to the bitwise OR of all the numbers of the sub-sequence. Amongst all such sub-sequences, find the sub-sequence that has the maximum sum of the numbers, and print this maximum sum.

Limits: 1<=A[i]<=10000

Hmm. So what are your first thoughts? You want to traverse over all the sub-sequences? Wrong! That would take hell lot of time. We’ll do it in O(n). All you need to do is pay attention to the properties of the bitwise AND and bitwise OR operator. These are two mutually exclusive operators. By using this term here, I mean to specify that no two different numbers can have the same result after their OR or AND. You can prove this by taking a few examples (Exercise left to you 😛 )

So the only AND and OR operations to satisfy the equality conditions can be performed on the same number itself. Your subsequences are thus reduced to those having the same number (and its duplicates). Hence, you can simply do the following :

1. Find number of occurrences of each element in the array, store it is OCCURRENCE[i] (corresponding to number i )

2. Find the maximum value of OCCURRENCE[i]*i by scanning through all the array positions.

This maximum value is your answer! 🙂 Once again, note why sub-sequences of duplicates are being made. It is because of the condition that AND of the subsequence should be equal to their OR.

It was an easy one but showed a nice Bit Manipulation property. 🙂

Advertisements
  1. Arth
    October 16, 2011 at 2:55 pm

    You can surely reduce the execution time if you increase the value of array like
    VALUE[i] += i;
    & then find the max on the spot..
    if n is no of elements then

    MAX=0;

    while(n–)
    {
    SCAN i;
    VALUE[i]+=i;
    if(MAX < VALUE[i])
    MAX=VALUE[i];
    }

    Then MAX will contain maximum value with one less loop… 🙂

    • October 16, 2011 at 2:59 pm

      Yes! Absolutely right! 🙂
      But it is better to explain it in this way 😉 Also, the complexity remains O(n).

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: