Given an array of n integers, count all different triplets whose sum is equal to the perfect cube i.e, for any i, j, k(i < j < k) satisfying the condition that a[i] + a[j] + a[j] = X3 where X is any integer. 3 ≤ n ≤ 1000, 1 ≤ a[i, j, k] ≤ 5000

Input:

N = 5

2 5 1 20 6

Output:

3

Explanation:

There are only 3 triplets whose total sum is a perfect cube.

Indices Values SUM

0 1 2 2 5 1 8

0 1 3 2 5 20 27

2 3 4 1 20 6 27

Since 8 and 27 are prefect cube of 2 and 3.

Given two positive integer n and n. The task is to find the number of arrays of size n that can be formed such that :

Each element is in range [1, m]

All adjacent element are such that one of them divide the another i.e element Ai divides Ai + 1 or Ai + 1 divides Ai + 2.

Examples:

Input : n = 3, m = 3.

Output : 17

{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1},

{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},

{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},

{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1},

{3,3,3} are possible arrays.

Input : n = 1, m = 10.

Output : 10

can any one help me in this interesting dp problem?

Actually I am looking for a good problemset on codeforces.If any user while solving problems keep their information please mention your list of problems according to topics.Basically advance data structure problems would be a big plus..Thanks in advance.

Given an array, we need to find two subarrays with a specific length K such that sum of these subarrays is maximum among

all possible choices of subarrays.

arr size <10^5

n<10^3

Examples:

Input : arr[] = [2, 5, 1, 2, 7, 3, 0]

K = 2

Output : 2 5

7 3

We can choose two arrays of maximum sum

as [2, 5] and [7, 3], the sum of these two

subarrays is maximum among all possible

choices of subarrays of length 2.

Input : arr[] = {10, 1, 3, 15, 30, 40, 4, 50, 2, 1}

K = 3

Output : 3 15 30

40 4 50

Given an array arr[] of n elements,

update all elements of given array to some minimum value x i.e, arr[i] = x (0 <= i < n),

such that product of all elements of this new array is strictly greater than the product of

all elements of the initial array, where 1 <= arr[i] <= 10^10 and 1 <= n <= 10^5

Input : arr[] = [4, 2, 1, 10, 6]

Output : 4

4 is the smallest value such that

4 * 4 * 4 * 4 * 4 > 4 * 2 * 1 * 10 * 6

Input : arr[] = [100, 150, 10000, 123458, 90980454]

Output : 17592

Expected time Complexity:O(N)

Given an array of integers. Find the total number of subarrays whose product of all elements doesn’t contain repeating prime

factor in prime decomposition of resulting number.

Input: 2 3 9

Output: 3

Explanation:

Total sub-array are:-

{2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:-

{9} -> {3 * 3}, Since 3 is a repeating prime

factor in prime decomposition of 9

{3, 9} -> {3 * 3 * 3}, 3 is a repeating prime

factor in prime decomposition of 27

{2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating

prime factor in prime decomposition 

         of 54

Hence total subarray remains which satisfies our

condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

Given an array of N positive integers. Count the number of pairs whose sum exists in the given array. While repeating pairs will not be counted again. And we can’t make a pair using same position element. Eg : (2, 1) and (1, 2) will be considered as only one pair.

I was able to solve problem in O(n2).I want a solution less then this.

Please read all examples carefully.

Examples:

Input : arr[] = {1, 2, 3, 5, 10}

Output : 2

Explanation : Here there are two such pairs:

(1 + 2) = 3, (2 + 3) = 5.

Note : Here we can't take pair (5, 5) as

we can see 5 is not coming twice

Input : arr[] = {1, 5, 6, 4, -1, 5}

Output : 4

Explanation : (1 + 5) = 6, (1 + 4) = 5,

(5 + -1) = 4, (6 + -1) = 5

Note : Here (1, 5) comes twice will be

considered as only one pair.

Input : arr[] = {5, 5, 5, 5, 10}

Output : 1

Explanation : (5 + 5) = 10

Note : Here (5, 5) comes twice will be

considered as only one pair.

Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.

eg. k=3 arr[1,2,3,-3,-4,1,0,-2,5,4,5]

ans=12 sum from [-2,5,4,5]

Suppose a chemical Formula is given C6H2(Cl3(OH2)3)3

Print: C-6 H-20 O-9 Cl-9 (Print the number of atoms of each element in a compound)

My approach->

create a hash map that contains the value of the ending index of the previous sequence.

For example

when we get 1,3,5 the hash map is

1 0

3 1

5 2

key is the number and the value is the index where it occurs.

when we get 4, we have to check for the index of 3 and 5. (One above and one below)

the value at 3 is 1 and 4’s index is 3, so they can’t be paired.

We then check for 5. 5’s index is 2 and 4’s is 3, since they are together, they can be paired.

1 0

3 1

5 2-3

4 2-3

and then we check for 3 again, 3’s index is 1 and 4’s index is 2-3, so they can match

1 0

3 1-3

5 1-3

4 1-3

We go on.

Then they alterd the question like

modified more to include distributed systems in it. And asked me if there were several systems which received the input in round robin manner, how would I implement the above algorithms.

Given a binary tree return a matrix where mat(i,j) is 1 when i is an ancestor of j. only one traversal required and no extra space required,

Can any one explain the topic and also tell me the list of some good problems.Thanks in advance.

Given a number n and a pattern that follows like:

(1 to 26): a,b,c,….z

(27 to 52): aa,ab,ac,…az

(52 to 78): ba,bb,bc,…bz

. . . za,zb,zc,…zz

aaa,aab,aac,…aaz

aba,abb,abc,… . . . find the nth pattern

A binary tree and a number, say k are given. Print every path in the tree with sum of the nodes in the path as k. (A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree)

You are given a string and 2 operators ( & , | ). Return the total number of ways in which you can evaluate to true using the given string and operator set.

Example : Input : TF Output : 1 Input : TFF Output : 2 ( T | F & F , T | F | F )

Delete the least number of integers from a given set of integers so that the product of the remaining integers in the set is a perfect square. In case there is more than one solution then find the solution that gives the largest perfect square. Assume that each integer contains five or less number of digits. The total number of integers in the given set is twenty or less. You are required to write a program for a problem as simple as this.

Input The input may contain multiple test cases. For each test case there is a single input line. The line contains the given set of integers. The input terminates with a line containing 0 as input. Output For each test case there is only one output line. The line simply prints the integers to be deleted in ascending order. There are two special cases; print output for these cases as indicated below.

Case 1: No integer is to be deleted: Print `0' as output.

Case 2: All integers are to be deleted: Print all integers in ascending order.

Sample Input

2 3 12 18 24

12 10 15 18

4 12 10 15

10 12 15

Sample Output

24

0

10 12 15

10 12 15

https://icpcarchive.ecs.baylor.edu/external/44/4467.pdf

Given any two nodes in a binary tree, find the path from 1st node to another, and tell if the path is a straight line, or there are turns on the line, find number of turns.

Find the maximum difference between any combination of child and parent node in a given binary tree. Here child node can be any level below parent node, but should be in the same sub tree starting from parent node

Create a Data Structure which is collection of integers. Create methods to add an element, retrieve an element and addToAll method in O(1) time

Given 3 characters a, b, c, find the number of strings of length n that can be formed from these 3 characters given that; we can use ‘a’ as many times as we want, ‘b’ maximum once, and ‘c’ maximum twice

Given an array of size N, there exist a pattern such that, a[i]-M <= a[i+1] <= a[i]+M . Suggest an algorithm to search for a number in the given array. The solution should be better than O(n).

Given a fully connected graph with n nodes and corresponding values. One node can interact with other node at a time, to replace/ignore/add its value to other node’s value. Assuming this operation takes 1 unit of time, how much time would it take for all the nodes to have value equal to sum of all the nodes. Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.

Can any one tell me the solution of the problem.

Eg. Input: 2 3 9 Output: 3 Explanation: Total sub-array are:- {2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:- {9} -> {3 * 3}, Since 3 is a repeating prime factor in prime decomposition of 9 {3, 9} -> {3 * 3 * 3}, 3 is a repeating prime factor in prime decomposition of 27 {2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating prime factor in prime decomposition of 54 Hence total subarray remains which satisfies our condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

Unable to understand the problem,Can anyone explain this please?

http://codeforces.net/problemset/problem/510/C

http://codeforces.net/problemset/problem/414/B

Can anyone help me in understand the problem.Just need explaination.Thanks in advance