SEPTEMBER COOK-OFF UNOFFICIAL EDITORIALs

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…

4 Likes

Thankyou very much taran . The third editorial is pretty nice and is perfectly explained in sort of a layman language .

if x denote the number of elements in array which are a power of 2,
then n-x would the numbers which are not power of two ,after recursion (or) of any two numbers can genertate numbers greaters than 2^k then the size of the the array may be equal to 1<<K then if equal to 1<<k why to answer k-x

Can someone point out the error in my code? This code gives WA. https://ideone.com/7lPdMw

Did you type it all during the contest? Wasnt it better to try the 4th problem instead? :stuck_out_tongue:

Haha…

I started writing it during last 15 minutes of contest, (posted only after end of contest)…

I’m quite new to combinatorics, so i knew that the fourth problem was well beyond me…

As for the fifth problem, diagonal updates were a nightmare for me… :smiley:

Hope I’ll learn from those two problems

Agree so much. The diagonal updates were nightmare :frowning: .

Mate

Suppose all powers of 2 from 1 to K-1 are present in given array

Say array = {1, 2, 3} K = 3

x = 2 {because only 2 powers of 2 are present}

If we add 4 to array

3 = 1^2

5 = 1^4

6 = 2^4

7 = 1^2^4

This way, after one recursion, all the elements would be present in array, thus breaking the recursion cycle.

Only one element thus need to be added.

In the problem, all the elements in array are smaller than 2^K,

So, we just need first K powers to get all numbers between 1 and 2^K-1

x = number of powers of 2 present.

k = total number of powers of 2 required…

So answer = missing powers of 2 = total - present
answer = K-x

Feel free to ask anything…

Glad you find these helpful… :slight_smile:

Just one more clarification . In the example input 1 , initially array is 1,3 . Going by the given algorithm , the size of b should be equal to 1<<k i.e. 4 . But even after adding 2 to the array , the maximum size of the array b remains 3 .

lot of thanks now it is clear to me…

There is possibility of repetition of values in given array…

Your code fails on following case

3 3

2 2 4

Your code gives answer 0 while correct answer is 1

Upvote if you find this helpful…

Glad to hear that… :slight_smile:

In the algorithm, they consider all subsets of given array, including empty set which, by default, have value 0

So after first run, 0 is added to array as i can know…

Hope that clarifies…

1 Like

Oh, such a silly error! I feel stupid! Thanks for pointing out the mistake.

No problem… :slight_smile:

Can you provide some good resources to learn FFT

Preferably in terms of polynomials, not in electric signals as i’m a commerce student… :slight_smile:

thanks …