### Lakh's blog

By Lakh, history, 3 months ago, ,

I am trying the following problem: https://www.hackerearth.com/practice/algorithms/string-algorithm/string-searching/practice-problems/algorithm/lost-in-strings-11fa4a5d/. I am using persistent trie to solve this problem by creating new version of trie for each add operation. For query, I am retrieving prefix count of query string from Rth version of trie and subtracting from this the prefix count from (L-1)th version. But my approach is giving WA. I also went through the editorial but it is not much understandable. So please suggest some other approaches for this problem using trie or some other data structure.

• 0

By Lakh, history, 4 months ago, ,

I have solved some basic problems involving persistent data structures like persistent segment tree, trie etc. I am still having doubts regarding the application of persistent data structures. I want to know how to come up with the fact that persistent data structure is required to solve a given problem. Please share your ideas and suggestions on this.

• +7

By Lakh, history, 8 months ago, ,

I am trying to understand the implementation of persistent trie data structure but unable to understand how range query works in case of persistent trie. Please provide some insight regarding range queries in persistent trie.

• +1

By Lakh, history, 12 months ago, ,

I am trying to solve some approximation problems but not able to analyze how to design algorithm for such problems. Please provide some tips on solving such kind of problems. Also if you have solved such kind of problems please share them. Thanks!

• 0

By Lakh, history, 15 months ago, ,

I am looking for some efficient implementation of the skip list. I tried implementing it in O(sqrt(n)) but getting wrong results. I searched for the same but unable to find some detailed explanation .Please suggest some useful resources for the O(sqrt(n)) implementation or some other approach.

• 0

By Lakh, history, 15 months ago, ,

I read the approach for finding Range minimum value using 2 Binary Indexed Trees. Is it possible to do this problem using only one BIT when updates are also there?

• +5

By Lakh, history, 18 months ago, ,

Given an array of N(N<=10^5) elements and -10^9<=A[i]<=10^9. Q(Q<=10^5) queries are there of two types:

1. L R K: Add K to all numbers in range [L,R] in array.
2. L R: Find no. of positive elements>0 in range [L,R].

I Thought of segment tree with lazy propagation but not able to understand what info to be stored in each node. Please suggest some approach for this problem.

• +1

By Lakh, history, 18 months ago, ,

I am trying to solve https://www.hackerrank.com/contests/world-codesprint-13/challenges/landslide.

Here given a tree of N(N<=2*10^5) nodes and Q (Q<=2*10^5) queries of 3 types:

1. d x y -- Remove the edge between city x and y if it exists else ignore this query.
2. c x y -- Add the edge between city x and y if previously an edge was present between x and y else ignore this query.
3. q x y -- Find the distance between x and y if there exists a path between x and y else print "impossible".

My approach:

I first performed dfs to store the in[] and out[] time of each node and code for finding LCA of two nodes. Now I created a segment tree on the basis of the in[] array and initialized each node to value 1 meaning that all nodes are initially form a single connected component. I took a variable counter=2.

Now for query of first type , suppose x is parent of y then I just updated all nodes in subtree of y to value counter using lazy propagation such that it represents a different component and increment counter by 1.

For query of 2nd type, if x was parent of y previously, then I just updated the entire subtree of y to the current value in node x so that entire subtree of y is again attached to subtree of x and y becomes part of the component to which x belongs.

For query of 3rd type I first computed LCA of x and y then determined the current values of node x, node y and node[LCA(x,y)]. If all the three values are not same then this means that x and y are not connected else i just print the distance between the nodes x and y as dis[x]+dis[y]-2*dis[LCA(x,y)]


Some of the tescases are failing. I am not able to understand what is wrong with my approach. Please suggest the problem with this approach.

My code: https://ideone.com/cXf4NX

• +5

By Lakh, history, 19 months ago, ,

I am solving the following problem:

Given T (T<=75) testcases . Each testcase consists of N (N<=10^4) strings and Q (Q<=10^4) queries. In each query you are given a number X.The task is to find the most common suffix of length X among the given strings and you need to print how common it is. Sum of length of all strings in a testcase is<=10^5.

E.g. Input :

1
5 4

abccba
abddba
xa
abdcba
aneverknow

1
2
4
3


Output:

4
3
1
2


I am inserting the given strings in a trie and storing a variable count in each node to find number of strings along the given path with suffix of length K. Now for all possible length of suffixes I am updating the ans[] array which stores the result for a given suffix of length K. and hence answering queries in O(1) but I am geting TLE. I am not able to optimize it further . How to solve this problem?? My code: https://ideone.com/fNAWjb

• +3

By Lakh, history, 19 months ago, ,

I am solving the following problem:

Given an array of N (N<=5*10^5) numbers. Consider the GCD of all the subarrays and print the no. of distinct GCD's found over all subarrays. A[i]<=10^18.

I am using the fact that for a fixed element A[i], GCD decreases as we increase the subarray length starting from element A[i]. So I considered all subarrays starting from index i and using binary search + sparse matrix(for range gcd) computed the indices where GCD changes and inserted the GCDs in a set and did the same for all other indices. But getting TLE. Please suggest some optimization or some other approach for this problem.

My code: https://ideone.com/zeDVkD

• +2

By Lakh, history, 19 months ago, ,

I am solving this problem http://codeforces.com/gym/101804/problem/J.

Here we are given the alphabet size N (N<=26). So if N=4 ,then the alphabet set is=[A,B,C,D] . Now we are given a permutation of the above alphabet. The permutation represents the encoded value of an alphabet . For e.g. if permutation is [D,C,A,B] then A changes to D, B changes to C , C changes to A and so on. Now Q (Q<=10^5) queries are there of three types:

1. 1 s: Add string s to the list. (|s|<5*10^5)
2. 2: For all the strings currently in list , encode them according to given permutation.
3. 3 s: Check if s is prefix of some string in the current list. (|s|<5*10^5)

Sum of length of strings over all queries is<5*10^5.

My approach : Here whenever a string is added , I computed all the N encodings of the string as maximum cycle length can be N after which strings will be repeated and stored them in N maps. I stored the hash of prefixes of the string in a map. For type 2 since all strings are encoded so i just took a counter and increment it to (counter+1)%N. For type 3 query i just checked if hash of s is present in map of current counter. however i am getting TLE. Please suggest some optimization to the approach or some other method to solve this. I also implemented this problem with trie but got MLE.

• 0

By Lakh, history, 19 months ago, ,

Given an array of N elements count no. of pairs having XOR less than K. How to solve this problem??

• +6

By Lakh, history, 19 months ago, ,

Given an array A of N (N<=10^6) elements. Here Ai denotes the height of ith plant. There are Q (Q<=10^6) queries of 3 types: 1. CUT h: Here for all plants with height greater than h ,cut them to height h. 2. GROW i x: Increase the height of ith plant by x (x<=10^6). 3. MAGIC y: Increase the height of all plants by y (y<=10^6).

For each query of type 1 , we have to print the total length of plants that is to be cut . Please suggest some approach to solve this problem.

• 0

By Lakh, history, 19 months ago, ,

I am trying to solve http://codeforces.com/problemset/gymProblem/101102/J . The summarized form of the problem is as follows:

There are T testcases. In each testcase You are Given an array of size N and Q queries. (N,Q<=10^5).Array elements<=10^9 In each query you are given range [L,R] and a set of distinct integers lying in range [1,10]. Now for each query you have to report no. of elements in range [L,R] which are divisible by atleast one element from the set.

My approach:

I am storing a 2D prefix sum array which tells the no. of elements divisible by X(1<=X<=10) in range [L,R]. Now for a given query I am generating all subsets of elements in the set and then using inclusion-exclusion principle to find the numbers divisible by atleast 1 element from set. But getting TLE .

Please Suggest some optimization or some other approach to this problem Thanks in advance.

• +1

By Lakh, history, 21 month(s) ago, ,

I know how to build and perform queries on a merge sort tree. But how to do point updates in the merge sort tree efficiently