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).

Advertisements

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

How to solve competitive programming questions with ‘Queries’?

Many questions in competitive programming are based on update and find queries.

For e.g. given an array of N elements and Q queries. Each query has L and R and you need to print the minimum array element from a[L] to a[R]. N = 10^5, Q = 10^5, 1 <= L <= R <= N. If you do it naïve it way, it would take O(N*Q) which would give TLE.

Basically, there are two types of approaches for solving such type of questions.

Online approach:

You just print the answer for each query instantaneously in the order they appear in input.

Offline approach:

You input and store all queries, sort them according to some comparison function, solve all in sorted order, output answer for all queries in order they appear in input.

Online approaches:

  • PreOrder Array:

Create another array pre[] , where pre[i] stores information about [0,i]

For eg, you need range sum from L to R in each query quickly.

Solution: Create preorder array, where pre[i] = sum from 0 to i = pre[i-1] + a[i]

So, for each query, answer = pre[R] – pre[L-1].

But this is a static structure and it doesn’t work when you need to update array elements.

  • Segment Tree: This is the most useful data structure for this type of questions.

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://en.wikipedia.org/wiki/Segment_tree

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

Segment Tree with lazy propagation: (For range update queries)

https://discuss.codechef.com/questions/38770/lazy-propagation

http://stackoverflow.com/questions/11765838/how-to-implement-segment-trees-with-lazy-propagation/30622980#30622980

  • Binary Indexed Tree/Fenwick tree :

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

http://www.sanfoundry.com/java-program-implement-fenwick-tree/

http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

  • Square Root Decomposition :

http://www.quora.com/How-does-the-technique-of-sqrt-N-decomposition-work-and-in-what-kind-of-problems-is-it-useful

  • Disjoint Set Union :

https://proclubdaiict.wordpress.com/2015/06/11/disjoint-set-data-structure/

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Offline Approaches:

  • Reverse Process Queries:

Process queries in from last to first. For example, if query is to delete something, solving queries in reverse order, it becomes insert instead of delete. This approach helps when inverse operation is easier to process then normal query operation.

https://www.codechef.com/MARCH15/problems/MTRWY (Do read editorial for it.)

  • Sorting queries based on their ‘R’. R = right end of range query (L,R)

Question: http://www.spoj.com/problems/DQUERY/

Solution: http://codeforces.com/blog/entry/8962

  • Mo’s Algorithm:

http://blog.anudeep2011.com/mos-algorithm/

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)

Editorial:Mr. Pompom & Dragon

Problem Link:

https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-dragon

Difficulty: Moderate

Prerequisites: Basic intuition or Dynamic programming

Problem in short:

There are N kingdoms numbered 1 to N. From i-th kingdom you can go up to (i + arr[i]) th kingdom. (You can choose any kingdom between i and (i + arr[i]) ) Mr Pompom starts from 1st kingdom and wants to reach N-th kingdom. Determine minimum number of kingdoms he will have to traverse to reach N-th kingdom.

Approach 1:Using basic intuition and observation (Range maximizing approach)

Explanation:

Ask yourself a question, where I would like to reach at any kingdom??Answer will turn out to be I want to go farthest kingdom possible as you want to reduce number of steps.

 So at each kingdom’s tunnel, we select a tunnel within the coverage of present tunnel having maximum range, and continue doing the same till the range becomes equal or exceeds the position of last kingdom which is our destination. If there are more than one tunnels with same range then we select the farthest tunnel.

Now we can do some tricks while doing this like if the tunnel which is already taken into consideration in previous case and not chosen, then we won’t check for it another time as it won’t get selected anyway.(Why?)

Implementation (Source Code):

https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-dragon/submissions/code/3544402

Approach 2:Using Dynamic programming

Quick Explanation:

Use dynamic programming approach. Let dp[i] be the minimum number of kingdoms he will have to traverse to reach i-th kingdom. We can calculate dp[i] by (dp[Xi] + 1) , where Xi is minimum index from which we can reach i-th kingdom. The answer to the problem will be dp[n-1].

Explanation:

We will use dynamic programming to solve problem. Let dp[i]=minimum number of kingdoms needed to traverse to reach i-th kingdom.(Here 0-indexing is used)

dp[0]=1;

So we will start looping from 0-th kingdom to N-1-th kingdom(0 -indexing) and keep assigning dp[] to all such remaining vertices that can be reached from that kingdom as dp[j]=dp[i]+1. We will break the Loop when no kingdoms are left. In each loop we will keep track of index from which kingdoms are remaining. Thus answer will be dp[n-1].

Pseudo code

read(n)
for (i=0;i<n;i++)

read(arr[i]);

dp[0]=1;

startKingdom=1;

for(i=0;i<n;i++)
{
for(j=startingKindom;j<=(i+arr[i]) && j<n;j++)

{
dp[j]=dp[i]+1;

}
startKingdom=j;
if(startKingdom>=n) break;

}

print dp[n-1];

Link to Solution(Code)  using DP approach:

https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-dragon/submissions/code/3538715

Time complexity analysis:

Both approaches have same time complexities of O(N). But as Dynamic Programming approach uses much memory it slightly takes more time than Range-Maximizing approach. Nevertheless both approaches are fast enough to pass out all the test cases.

NOTE:There is another possible acceptable solution which runs in O(nlog(n)) time complexity using bottom-up DP and segment tree.

Modification of question in which dp becomes much useful:

Suppose the position of firesafe bunker wasn’t fixed but changes in each query asked then in this case the answer would be directly dp[query]. Here, storing intermediate values by dynamic programming approach enables us to answer the query in O(1).

Authors:

Suparshva Mehta & Aayush Kapadia