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…
.