CGKLET - editorial

general
1

Problem Link

Click here for problem

Setter-pavan sai kiran

Editorialpavan sai kiran

DIFFICULTY

Hard

PREREQUISITES

sequence and series,floyd triangle

PROBLEM

According to the problem,you just have to find the string ‘B’ from the given string ‘A’ and find the kth character in the string ‘B’.

EXPLANATION

let us take String ‘A’ as “abcd” and k be 15, so now the string ‘B’ will be

“aababcabcdbbcbcdccdd”

a a b a b c a b c d b b c b c d c c d d

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

now using only the string ‘A’ by writting the corresponding number under its corresponding letter,this can be written as:

a–b--c–d

1

2–3

4–5--6

7–8--9-10

–11

–12-13

–14-15-16

-----17

-----18-19

--------20

now certain floyd triangles are formed starting with length 4 which is the length of string ‘A’ and ending with 1.Now find the floyd triangle in which k is present.We can find that using the last terms of the floyd triangles as they from a series.In this case the series is,0,10,16,19,20.The ith term of this series is found by adding sigma(n-i-1) to the (i-1)th term where n is length of string ‘A’ and first term of this series is always 0.

k is present in the floyd triangle whose last term is greater than k. In this way the triangle is found.Now we just have to find the row in which k is present.Now take a variable ‘j’ which has value n-1 and ‘x’ which has last term of triangle.let l be be the number of lines of the required triangle that is found.Now k is present in the upper most row whose last term is greater than k.This can be achieved by subtracting l from x and decrementing j and l simultaneously.when x is less than k,then the row below is required.now the required answer is just printing j-k-1 index of string ‘A’.

2

As can be seen in the above description, the total length of the expanded string is the sum of the first L triangular numbers (where L is the length of the base string) - these are the tetrahedral numbers. The formula for these is Te_n = n(n+1)(n+2)/6 and so by binary search, evaluating against the difference in tetrahedral numbers, we can find out which layer of the tetrahedron the required character position occurs on.

Similarly we can search the identified triangle layer of the tetrahedron to find the correct line and report out the desired character, without forming the expanded string (although doing that could certainly work for the first subtask and maybe the second).

My solution