# Editorial : Coyote and SuperVyas

Explanation :

Let’s start from a slow solution first.

Coming to think about it, you are asked to place X1 in 2nd free cell of your answer, then to place X2 in 3rd free cell of your answer while starting counting from position where you had placed X1 (and starting from the beginning if you reached end of array), then to place X3 in 4th free cell, and so on. It is quite easy to understand why it works – rotating deck around your pointer and rotating pointer around deck in opposite direction is basically same thing.

Now add one more optimization. At every moment you know how many free cells are in your array now. Assume you are at position X now, need to move 20 free cells forward, and you know that at given moment there are 2 free cells before X and 4 free cells after X. It means that you need to find 22nd free cell starting from beginning of array, which is same as going full circle 3 times and then taking 4th free cell. As you can see, we moved to a problem “find i-th zero in array”.

Naive solution is still O(N^2), but it is fast enough to pass and still have a very easy implementation!

However, you can speed it up.

Problem “find k-th 0 in array” is well-known. N*log(N) solution with segment tree: for every vertex store number of 0’s in given range. Start from root and move down to a leaf; at every vertex you know where you should go by looking at number of 0’s in left and right subtree. Suppose you need 5th 0 in range, and there are 8 of them in left subtree and 7 of them in right subtree. It is obvious that you need to move into left subtree and look for 5th 0 there. And what if you need 12th 0? In such case you have to move into the right subtree – but don’t forget that you’ll be interested in 4th 0 there, not in 12th (because of 8 more 0’s in left subtree).

N*log^2(N) solution with small hidden constant using Fenwick tree: use binary search to find minimum X such that there are at least Y 0’s among first X elements, it will give you position of Y’th 0 in given array.

You can also use BIT to store the number of free spaces on the left and right of every index.

Setter’s Code : http://ideone.com/9GKD4F

# Editorial : Mr. Pompom and his tricks!

Given a string S, we want to find the lexicographically smallest string A such that:

S ∈ Join(UltaPulta(A), Crazy(A))

Observation 1:

S ∈ Join(UltaPulta(A), Crazy(A))

<==>

UltaPulta(S) ∈ Join(A, Crazy(A))

We know that number of every ‘a’ – ‘z’ is equal to half of S. So we just need to find a smallest A with given number of ‘a’, given number of ‘b’, etc.

So, firstly we find the frequency of every character(can be done easily using Hashing or using dictionary in Python) in given string S. The frequency of the characters in the original string will be exactly half of this frequency.

Now, coming to think about it we have joined the two strings by maintaining the relative order of the characters in both. So our original string will be subsequence of the reverse of the given string(Because we have merged the reverse of the original string). So our aim is to find a lexicographically smallest subsequence in the reverse of the input string S.

Now if we apply brute force and try all the permutations of the string, it would be a very inefficient approach.

Question : So how efficiently can we find the lexicographically smallest substring in a string if we know the frequency of the characters we need?

So we follow the following procedure :             Start traversing each index of the string, check for the frequency of characters we “need” and we “have” (Both stored while counting the frequency of the characters)continously and choose the lexicographically smallest character from the subarray where the frequency of any one character occuring in that subarray increases than what we “need”.

Why? Because whenever any one character’s frequency increases than what we actually need, we will have to compulsorily take one character from that subarray.

For eg. :

Let S = “aegeaggg”

Ultapulta(S) = “gggaegea”

Now as we start traversing we see that at index ‘2’ the frequency of g will exceed(3) than what we need(2). So we, have to necessary take one ‘g’ from that. Next the string will be “ggaegea”. Now applying the same logic we will end up at index ‘4’ where the frequency of again ‘g’ will exceed than what we actually need and so we will take the lexicographically character in that subarray which is ‘a’ and this will be the second character in our answer. Now our string will be “ggegea”. Do this till the length of the string becomes half!

Happy Coding 😀

Solution Code(Python 2.7) :

from collections import defaultdict

answer = [] # This will store our required string.

S = str(raw_input())[::-1]

# Calculate the frequency of each character in the input String S and store it in a dictionary.

InputCount = defaultdict(int)

for c in S:

InputCount[c] += 1

# ‘Original’ will store the values of the frequency of characters needed in the ‘

Original = {}

# The Original frequency of characters is half than the Input string.

for c in InputCount:

Original[c] = InputCount[c] / 2

i = 0

while len(answer) < len(S) / 2:

Lowest_possible_char_index = -1

while True:

c = S[i]

if Original[c] > 0 and (Lowest_possible_char_index < 0 or c < S[Lowest_possible_char_index]):

Lowest_possible_char_index = i

InputCount[c] -= 1

if InputCount[c] < Original[c]:

break

i += 1

# Restore all chars right of the minimum character.

for j in range(Lowest_possible_char_index+1, i+1):

InputCount[S[j]] += 1

Original[S[Lowest_possible_char_index]] -= 1