Editorial Fitness Freak Coyote

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote

In this question there are two types of query.

  1. Add number in your data structure
  2. Return number whose rank is floor of n/3

And both query come at any instance of time.

So we can use Balanced Binary Search Tree. But that take O(log n) time complexity in both query.

The better approach is use two heaps.

Create a min heap of size n/3 and create max heap of size 2n/3

So for the second query we give minimum element from the min heap whose rank is floor of n/3

which takes time O(1).

For the first query there can be four cases occur.

-If size of min heap is less than floor of n/3 this is due to increase in n.

in this case we will add that number in the min heap and than compare min of min heap and max of max heap

If max of max heap is greater than min of min heap than we will swap this two elements.

-If size of min heap is equal to floor of n/3

In this case just add it in the max heap.

So the time complexity of this is  O(log n)

Java implementation code

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote/submissions/code/3618642

Editorial : Coyote and SuperVyas

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/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 : Coyote and his balls

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-balls-p

Required Knowledge : naive logic

Explanation : There are 2 possible solutions to this problem but the logic in both is the same. Consider we have been given n balls. Now we do 1 comparison using weighing pan. Here we divide the balls into 3 parts which are approx 1/3rd of n.                For  3n balls – n,n,n ; for 3n+1 balls – n+1,n,n ;  for 3n+2 balls- n,n+1,n+1 . We compare the last 2 parts using weighing pan. If they are equal, then the non-identical ball lies in the 1st part. If they are not equal, the non-identical ball lies in the pan which was lighter of the two. So effectively we reduced the problem into 1/3rd its size. So if we go on doing this, we will require log n(base 3 ) – ceiling comparisons. This is one possible solution.                                                                                                                         The second possible solution is a recursive method. Let ans() be the recursive method. The two base cases are n=1 and n<=3 for which the answers are 0 and 1 respectively. For n%3==0 , we divide into 3 parts each having n/3 balls. Therefore we return  ans(n/3) + 1 . If n%3 !=0 in worst case we will have to look at (n/3)+1 balls. Hence we return ans(n/3 +1 ) +1 and not ans (n/3 ) +1.

Setter’s  solution: http://ideone.com/e.js/lgvYbc        (This one uses recursive method)

Tester’s Solution: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-balls-p/submissions/code/3630098                                          (This one uses log to base 3 method)

For any doubts feel free to contact me on 201401114@daiict.ac.in.

 

Editorial : Coyote and his enemy Daddu ji – 2

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-enemy-daddu-ji-2

Required Knowledge : Segment Tree(https://en.wikipedia.org/wiki/Segment_tree), Binary Search(https://en.wikipedia.org/wiki/Binary_search_algorithm).

Explanation : 

You are given n numbers and an integer k, you are asked to find the length of minimum sub-array whose gcd is k. If any number is k then the answer should be 1 as that sub-array will have gcd k and length 1 which is the minimum. Now what to do if no number is equal to k. We need to find all the sub-arrays whose gcd is k. Let us now declare a minimum variable whose value is more than n. Now start with index 1, we will now find the gcd of sub-array 1 to (n/2)index using segment tree. If gcd is = k we, we store the minimum of the length of the found sub-array and the original value of minimum in minimum. minimum = min(minimum, length of found sub-array). If gcd is greater than k then we will get the sub-array with gcd k further as moving back will give gcd more than k. So now binary search b/w n/2 and n. Similarly if gcd is less than k, we will either get gcd k b/w index 1 and n/2 or we will not get any sub-array with gcd k. So now finding gcd of a sub-array will have time complexity of O(logn) and binary search will also happen in log(n). Therefore for each index total complexity of O(logn*logn). Since there are n index we need to find for all, therefore the required complexity of the solution is O(n*(logn)^2).

Now if value of minimum is equal to the assigned value in the beginning, print -1 else print minimum.

Some useful links on segment tree :

http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

http://www.cse.iitk.ac.in/users/aca/lop12/slides/06.pdf

https://proclubdaiict.wordpress.com/2015/01/25/segment-trees/

Setter’s Solution : http://ideone.com/wqVgEI

For any doubts you can contact me at 201301151@daiict.ac.in or message me on Facebook (https://www.facebook.com/nikhil.tekwani.18).

Editorial : Coyote and his enemy daddu ji

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-enemy-daddu-ji1

Knowledge Required : Finding a^b in time complexity of O(logb) rather than O(b).

Explanation : 

A = a*m;

Therefore A is multiple of m and A%m = 0;

Similarly, after carefully looking B and C. They are the multiple of m as well. Therefore the equation f(i) = (i^i + Ai^4 + Bi! + C((i^i)^i))*(f(i1)) reduces to f(i) = (i^i)*f(i-1) on finding f(i)%m as A%m, B%m and C%m = 0. So now the question is to find f(i) = (i^i)*f(i-1).

if(n>=m) the ans is 0 because while running loop upto n we will have to compute m^m whose modulo with m comes out to be 0, thus making the entire function 0 as 0*something is 0.

Therefore we have to run the loop maximum upto m-1 if n is less than m.

For each i the time required is log(i) and the loop will run upto n. Therefore time complexity O(nlogn).

The editorial to find a^b in logb can be found here http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/.

Setter’s solution : http://ideone.com/8iPMcf

For any doubts you can contact me at 201301151@daiict.ac.in or message me on Facebook (https://www.facebook.com/nikhil.tekwani.18).

Editorial : Corote And Queries

Coyote And Queries:

Problem Link: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-queries-2

Problem In Short: Give an array, you have to answer many queries on it. For each query, you need to output the number of distinct integers whose frequency from L to R >= ceil((R –L+1)/3).

Offline Approach: Simple application of Mo’s Algorithm. You create another count array such that count[c] stores number of integers which frequency >= c. Refer to any solution which has got 100 points in Coyote And Queries 1 for this.

Online Approach:  For Coyote And Queries 2, online solution was needed.

First we would create one frequency array, such that freq[i] stores number of intgeres in array equal to i.

Let us define a term heavy element.

For each 1 <= I <= 10^5, if freq[i] >= SquareRoot(N), then i is a heavy element.

Total Number of heavy elements must be <= SquareRoot(N). Think about why this!

Each query can be categorized in two parts.

  1. R – L + 1 >= 3 * squareRoot(N)
  2. R – L + 1 < 3 * squareRoot(N)

Queries of type (b) can be solved in O(R – L + 1) = O(squareRoot(N)) using brute force. However creating a map, would increase the complexity by one log factor, which would not be enough to get 100 points. But because A[i] <= 10^5, you can create a single 10^5 size global array and use it for each query of this type. For details, look at the reference solution.

For queries of type (a) , R – L + 1 >= 3 * squareRoot(N) implies C = ceil(S/3) >= squareRoot(N). But only heavy elements have frequency >= squareRoot(N). Hence, you only need to check heavy elements. AS said earlier, total number of heavy elements is <= squareRoot(N). So for each element , you check its frequency from L to R and if frequency >= C, ans++. However, again using some sort of binary search or segment tree data structure to calculate frequency for each heavy element would increase complexity by a log factor. But because there are no updates, you can create a prefix array for each heavy element.

Prefix[i][j] = number of times heavyElement[i] occurs in [1,j].

So , for each heavy element, frequency in [L,R] = prefix[i][R] – prefix[i][L-1].

Hence, O(SquareRoot(N)) per query.

P.S. There was a hacky 100 points AC solution with segment tree but it’s not correct, so don’t refer to it.

Hence, total Complexity = O(N * sqrt(n) + Q * sqrt(n))

Make sure you look at the reference solution to learn few tricks on reducing one log factor.

Reference Solution: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-queries-2/submissions/code/3671816

Editorial : Mr. Pompom and his tricks!

Link to problem : https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/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

answer.append(S[Lowest_possible_char_index])

i = Lowest_possible_char_index + 1 #Go for the next possible lexicographically smallest character.

print ”.join(answer)