Problem **SubSequence Equality**

In this problem, the key insight is that problem allows us to have a 2 subsequences of length 1 such that A[i] == B[i] ie A == B

So, this way, the problem reduces to

Find whether given string contains a character more than once.

This can be solved using maintaining a count array

boolean[] count = new boolean[26];

for(int i = 0; i< s.length(); i++){

```
if(count[s.charAt(i)-'a'])ans = false;
else count[s.charAt(i)-'a'] = true;
```

}

if(ans)System.out.println(“yes”);

else System.out.println(“no”);

Problem **Statistics Construction**

Let’s assume that the problem require median of selected subsequence to be N

Then, we can be sure

if N is even

(N-2)/2 elements are smaller than N-1 and (N-2)/2 elements are greater that N+1 and middle two

elements are N-1 and N+1 so that median is N

if N is odd

(N-1)/2 elements are smaller that N and (N-1)/2 elements are greater than N, the middle element is N so that median of subsequence is N…

So, by generating any such sequence, we will get the answer.

The answers i generated

if N == 3 output 1 3 5

if N == 4 output = 1 3 5 7

if N == 5 output = 1 3 5 7 9

Thus, we can observe, one of the acceptable answer for this problem is the sequence of N consecutive odd numbers.

We can generate this sequence as follows:

String output = “”;

for(int i = 1; i<=2*N-1; i+=2)output += i+" ";

System.out.println(output);

Problem **Infinite OR Game**

This problem can be restated as,

By taking OR of any two elements in given array and adding that number to array, if not already present, can we get all the numbers from 1 to 2^K-1 in the array

Another observation,

lets take a number 5, binary representation 101

Either it is already present in given array or, we need 5 as the OR of elements of any subset of given array.

we see that 1|4 = 5

So, if the array contains 1 and 4, we don’t need 5.

Same way, take number 4, binary representation 100

We cannot generate 4 as OR of two other elements other than 4, So, If 4 is missing from given array, we have to add 4 to given array.

Now, the General solution for this statement is…

if x denote the number of elements in array which are a power of 2,

The required answer is K-x

Proof, the numbers which are a power of two, cannot be generated as OR of any other elements, so we have to add them explicitly.

The numbers which are not a power of two, can be generated as the OR of exisiting elements and thus need not be added…

pseudo code

int N = in.nextInt(), K = in.nextInt();

boolean[] val = new boolean[K];

int count = 0;

for(int i = 0; i< N; i++){

```
int x = in.nextInt();
for(int j = 0; j<K; j++)if(x == (1<<j))val[j] = true;
```

}

for(int i = 0; i<K; i++)if(!val[i])count++;

System.out.println(count);

Hope you find this helpful…

Feel free to ask anything…