I was asked this problem in one of the interviews :

Given an undirected graph with N nodes and M edges. Each node is initially having some value A[i]. We are also given a number K.
Now in one operation we can take one of the edges and increment the value of the 2 nodes linked through that edge by K.
I have to find minimum no. of such operations to make value of all nodes in the graph equal or -1 if it is not possible.

Wasn't able to come up with any optimized approach. I was thinking to start with node having minimum value since in order to minimize the operations we should do as less operations as possible on maximum value node. But still not able to reach any correct approach.

Constraints : Not available . Please help if you have some other way to solve this problem.

You are visiting a fair in byteland. You are shopping and want to buy Q items. Each item cost exactly B[i] amount of money. You have no money but you have a magical bag on which you can apply an operation any times you want. In bag there are N integers denoted by array A. In one operation, You choose two integer X Y from A and deposit all of the amount of money M you have, this will magically increase your money by X ⊕ Y. Note: You have to deposit all money you have otherwise you will be exiled from Byteland for your greed. Also, shopkeepers have no change, So you have to pay exact amount. :p Treating each item as independent and starting with 0 amount of money, Can you find if we can buy each item? 

Problem Constraints
2 ≤ N ≤ 1000
1 ≤ A[i] ≤ 10000
1 ≤ Q ≤ 100000
0 ≤ B[i] ≤ 10^9

Input Format 
First argument contains an integer array A of size N. Second argument contains an integer array B of size Q. 

Output Format 
Return a binary string of size Q containing i as 1 if its possible to buy ith item else 0.

Example Input 

Input 1:
A = [1, 2], B = [3, 5, 10, 15]

Input 2:
A = [1, 2, 3], B = [1, 5, 10]

Example Output 

Output 1:
"1001"

Output 2:
"111"

My approach : As N is only 1000 we can generate all possible xor pairs whose value will not exceed the maximum possible value of array element (i.e.10000). Let's store all the xor values from all possible pairs in another array XOR_ARRAY. After this for each query we basically need to find if there exists some subset in the XOR_ARRAY whose sum is equal to the required value. Seems like subset sum problem but constraints are large so I am stuck here.

Please let me know if I am thinking in correct way or is there some other approach to solve this problem. Thanks in advance :)

Hamid is visiting a fair near his village. There are N shops of toys arranged in a line from left to right numbered 1 to N. There are two types of toys in each shop. The toy of type 1 costs A[i][0] coins and the toy of type 2 costs A[i][1] coins. 

Now, he asks you to solve Q queries for him. 
Each query will be of type-> l r x y -> He visits each shop from l to r in this order and he will buy exactly one toy from each of the visited shops. But, he wants to buy at least x toys of type 1 and at least y toys of type 2. Help him find the minimum cost for buying the toys. Since the answer can be large, return it modulo 10^9 + 7. Problem Constraints

1 <= N, Q <= 10^5
1 <= l <= r <= N
0 <= x + y <= r-l+1
1 <= A[i][0], A[i][1] <= 10^9

Input Format 

The first argument contains a 2D array A of size N x 2, denoting the prices of toys. 

The second argument contains a 2D array B of size Q x 4, denoting the queries. 

Output Format 

Return an array of size Q denoting the answers to the queries.

Input 1:

 A : 
 [
 [1, 2]
 [4, 2]
 [3, 2]
 [4, 3]
 ]
 B : 
 [
 [2, 3, 1, 1]
 [1, 4, 2, 1]
 ]
Input 2:
 A : 
 [
 [2, 3]
 [4, 5]
 [2, 1]
 ]
 B : 
 [
 [2, 3, 0, 1]
 ]
Example Output 

Output 1:
 [5, 9]

Output 2:
 [5]

I am applying segment tree and storing sorted prices of both types of toys in every node. But not sure hot to apply the x and y constraints mentioned in the query to minimize total price. Also only one toy can be purchased from a particular shop. Please suggest correct way for maintaining segment tree . Thanks in advance :)

Edit : Problem is from a contest which is completed now :)

Edit : Waiting for someone to throw some light on how to solve this problem. Please help!!

Problem Link : https://www.codechef.com/NCCW2021/problems/AKNTWRK

AK works in a logistics company, and he is assigned with a task to build a road network between N cities. The size of a city is Pi and AK would like to build N−1 bidirectional roads connecting two cities such that any city can reached from any other city.

Assuming that the cost of building a road between ith and jth city is abs(i−j)∗D+Pi+Pj. Find the minimum possible cost to achieve the task

Input:
The first line contains two integers N and D.
The second line contains the array P of size N.
Output:
Print the answer.

Constraints
1≤N≤2∗10^5
1≤D≤10^9
1≤Pi≤10^9
Sample Input:
3 1
1 100 1

Sample Output:
106

EXPLANATION:
This cost can be achieved by, for example, building roads connecting City 1,2 and City 1,3.

I was thinking in terms of some MST(Minimum Spanning tree) based approach to solve this problem but the complexity will be greater than O(NlogN). Not able to come up with some efficient approach for this problem.

Please suggest some optimal approach. Thanks in advance :)

An array of length N is given . In one operation we can increment/decrement any array element. We have to find minimum no. of such operations to make array strictly increasing.

For e.g. N = 5
         5 4 3 2 1
         Ans: 12

I tried this problem using concept known as Slope trick where first we convert all array elements in following fashion : A[i] = A[i] — i;

After this I tried finding LIS of new sequence and then updating the elements which are not a part of LIS. However, there may be multiple LIS sequences present in the tranformed array. In that case how to decide which sequence to take.

Also let me know if my approach is correct or if any other approach is there to solve this task. Thanks in advance :)

An array of size N is given. In one operation we can add 1 to element at index i and subtract 1 from element at index j. (i!=j).

Using this operation we have to minimize the difference between maximum and minimum array elements and print minimum no. of operations required to achieve this minimum difference.

E.g. N=2, A=[1,6] -> Answer is 2.
     Steps : [1,6] -> [2,5] -> [3,4] (This is minimum difference configuration that we can achieve]

E.g. N=5, A=[1,2,3,4,5]-> Answer is 3.
     Steps : [1,2,3,4,5] -> [2,2,3,4,4] -> [3,2,3,4,3] -> [3,3,3,3,3] (This is minimum difference configuration].

Constraints : 

N<=10^5, Array elements <= 10^4

I tried by taking the sum of elements and then taking the average and making each element equal to average but didn't work out. Then thought to apply binary search to find minimum possible difference value but couldn't come up with any good implementation regarding how to apply binary search here.

Please suggest some approach for solving this problem. Thanks in advance :)

Today I was thinking of a problem where we are given a static array like a=[1,1,3]. Now we have another array which is initially filled with zero and it's size is > 3 . Let's say 10. Now suppose we have Q queries and each query contains range [L,R] of length = 3 (i.e. R-L+1==3). Now for each of these ranges we we have to add the array a=[1,1,3]. Finally we have to output the resulting new array formed.

For e.g. a=[1,1,3], b(initially zeros) = [0,0,0,0,0]

Queries : (0,2) -> updates = [0,0,0,0,0]-> [1,1,3,0,0]
          (1,3) -> updates = [1,1,3,0,0] -> [1,2,4,3,0] ( Added [1,1,3] to the array from indices 1 to index 3)

Final output : [1,2,4,3,0]

Not sure about the constraints part.

I am thinking if it's possible to apply segment trees here but still no progress. Is it possible to solve such a problem using segment trees?? Looking towards some ideas for solving this kind of range update operation. Thank you in advance :)

Given an array of size N*N (1<=N<=1000) . We can select only one element from each row. Once an element is selected from a given row the column containing that element is freezed. Now for further rows we can't select any element from that column. The problem is to minimize the sum of selected elements .

I am thinking of some dp approach but size of N seems a bit large. Please suggest any other way to solve this problem. Thanks.

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.

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.

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.

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!

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.

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?

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.

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

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.

Link to problem: http://codeforces.net/gym/101502/problem/G

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

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

I am solving this problem http://codeforces.net/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.

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

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.

I am trying to solve http://codeforces.net/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.

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