# XD Subsequences approach help codemelange

Can anyone share their approach here ?

let time be n sec.
take square root of n, let it be no_x. This is the no. of minimum x in required string.
now no.of D after all the X=floor(n/no_x).
still we need (n%no_x) of XD(s). so place 1 D after (n%no_x)th X in the previous string

It was very interesting problem. I have also used the same approach as Shaswat but I can explain in a better way: suppose you have number of "X"s=a and number of "D"s=b. now you know that length of string will be (a+b) and you can contain maximum value a*b by forming a string in which all "X"s will come before all "D"s. example:- “XXXXDDD” have a=4 and b=3 hence maximum value it can give is 12. suppose we want to find string for n=13. then we can simply put one more “X” before one “D” at the end, i.e. string will be “XXXXDDXD”. for the value of n=11, we can just shift the last x one position after a “D” and string will be “XXXDXDD”. In this way we can first find the equivalent generating string and then modify it accordingly.
Happy Coding

If n is a perfect square, then we can directly find the correct string by writing ‘X’ sqrt(n) times followed by 'D’s sqrt(n) times.
However, what if n is not a perfect square?Well, in that case we need to find the maximum number which is a perfect square but is less than n.
For example, if we have n = 13, then we will first solve for 9 since 9 is a perfect square and is less than 13.Lets call this perfect square we just derived as num.So, num = 9 i.e X’s = 3 and D’s = 3.Lets call them x and d resp.
Now, what we do is count the number of remaining 'XD’s.This is done by n - num.In case n was already a perfect square, we would get rem as 0 and we don’t need to do anything.However, in case of say 13, we will get `rem = 13 - 9 = 4. Now we already know that at this point of time, we have sqrt(num) X’s and D’s i.e 3 X’s and 3 D’s i.e XXXDDD.Now we will check that

``````while (rem > 0 and (d+1)*x<= n){
//Adding 1 'D' at end would increase our XD's x times.
rem -= x
//Since we can append a 'D' at the end without overshooting n, hence we increase the count of 'D'
d += 1
}
``````

The second condition in the while loop is to prevent overshooting n by appending a ‘D’ at the end.If we are overshooting it, then we go to the next step which finds the correct answer for us.
Now in case we are unable to append a ‘D’ at the end so as to prevent getting more subsequences then required, then we need to add an ‘X’ somewhere in between the 'D’s.

``````if(rem >0){
//find the position as which we need to insert X in between the D's.
idx = d - rem
//increment d since we are also appending an X so that the for loop we will use will work for the correct number of D's
d += 1
}
``````

Finally print the number of X’s.But while printing the D’s, check if we need to insert any X in between them.If we do, then while printing D, also print an ‘X’ at the correct position which is given by ‘idx’.

Here is a link to my solution - https://www.codechef.com/viewsolution/18044138

Let’s assume you are given an XD string you have to determine how many XD subsequences are there in the string.

This is pretty easy. Just count the number of D after every X and sum them up.
example: XDXXXDDDXD : 5 + 4 + 4 + 4 + 1 = 18

Now think you have given this sum and you have to form minimum XD string.
Let’s say this sum(n in the question) is a perfect square:
example:

1 : XD,
4 : XXDD,
9 : XXXDDD,
16 : XXXXDDDD,

as you can notice from the pattern if n is a perfect square you just need to print sqrt(n) ‘X’ followed by sqrt(n) ‘D’ ( and this is optimal ).

Now what if n is not a perfect square:

example n = 15:

lets say x = floor(sqrt(n))
therefore x * x<=n
in this case x=3
so we can form solution for n=9 using x=3
remaining XD subsequences are n-xx ( 15 - 33 = 6)
Now we somehow have to insert the remaining XD subsequences in this string
Use logic discuss in the starting
if we insert a D after ‘k’ 'X’es then we form ‘k’ extra subsequences
in our example
XXXDDD
insert ‘D’ after 3 ‘X’ (as there are no more ‘X’)
XXXDDDD
subsequences still left to add = 6 - 3 = 3
again insert ‘D’ after 3 ‘X’
XXXDDDDD
now we have got our answer

proof:
maximum difference between n and x*x could be 2x (it is easy to derive mathematically)
we have x 'X’es in our string
after inserting 2 'D’s after all the 'X’es we can make our required string.