Dhanadeepa_Red's blog

By Dhanadeepa_Red, history, 5 months ago, In English,

Hey Guyz, any one ever purchased LEETCODE premium subscription?? Please give your reviews

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 7 months ago, In English,

While I was solving this DP ,

http://codeforces.com/contest/73/problem/C

I think we can do it by 3d-DP.But I am able to make only two states dp[i][j][?] where i is currently index and j is how many letters we can change.Can any one suggest me the third state or the approach??

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 7 months ago, In English,

I was trying to solve the problem http://codeforces.com/problemset/problem/380/C .I saw Segment tree approach in the editorials.Now I was thinking Can we do it by memoization.Increasing the value +1 for every "(".Now we have two options ,Whether we should include next character to close this subsequence on not.Initially it would be exponential but by doing memoization I think we can do this.Looking to hear from you guyz?????

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it  
  • -6
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 7 months ago, In English,

Hello All, While reading http://codeforces.com/blog/entry/325 blog advance section I saw problems of the topic k-th lexicographical string but all are from codah.club,Can any one of you suggest me some Interesting k-th lexicographical string problems on codeforces.

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 7 months ago, In English,

While solving problems on topcoder,I some time face this issue.

If any one can solve the issue or faced same issue .Please reply

unable to open the problem

https://community.topcoder.com/stat?c=problem_statement&pm=10195&rd=13695

Read more »

 
 
 
 
  • Vote: I like it  
  • +16
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 8 months ago, In English,

Hey, Everyone I am unable to understand that how should I apply knapsack in this problem

http://codeforces.com/problemset/problem/741/B

Because it contains different groups.Thus Mine complexity is coming O(W*N*N).I saw the editorial but unable to understand the solution.Can anyone explain ?

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 8 months ago, In English,

http://poj.org/problem?id=3046

I need help in this problem,I am unable to get the approach.Thanks in advance.

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 8 months ago, In English,

Given a string S of length n and a positive integer k. The task is to find number of Palindromic Subsequences of length k.

Examples:

Input : s = "aabab", k = 2

Output : 4

Input : s = "aaa", k = 3

Output : 1

Input: s= "abdbcabda",k=4

Output : 6

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 8 months ago, In English,

Given 3n numbers placed in a circle, you and two of your friends are playing a game. Each time you pick a number first, then the two neighboring numbers of the one you picked are picked by your friends. All the picked numbers are removed from the circle and the left numbers compose a new circle. This game terminates when all the numbers are removed.

Write a program to find the maximum sum of the numbers you picked.

Eg, if nums = {1,2,3}, it returns 3

if nums = {1,2,3,4,5,6}, the first run you choose 6 and your friends choose 5 and 1. then nums = {2,3,4}. The 2nd run you choose 4. Thus, it returns 4+6=10;

Note-The numbers need not to be sorted.

Read more »

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 9 months ago, In English,

https://leetcode.com/problems/remove-boxes/description/

I need help in this problem..I tried till O(n3) complexity but not able to do...

Read more »

Tags dp
 
 
 
 
  • Vote: I like it  
  • -22
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 9 months ago, In English,

https://leetcode.com/problems/zuma-game/description/

Need help in this Interesting DP problem...

Read more »

 
 
 
 
  • Vote: I like it  
  • -10
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 9 months ago, In English,

https://leetcode.com/problems/zuma-game/description/

Need help in this problem,Unable to understand...

Read more »

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 9 months ago, In English,

http://poj.org/problem?id=2385

need help in this problem.I am able to solve the problem by heap.But Unable by Dynamic Programming

Read more »

 
 
 
 
  • Vote: I like it  
  • -17
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 9 months ago, In English,
Tags #dp
 
 
 
 

By Dhanadeepa_Red, history, 10 months ago, In English,

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [2,-1,4,-3,5,-7,6,8,9]

array size < 10^3

Read more »

 
 
 
 
  • Vote: I like it  
  • -13
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.

n<10^3 arr.size<10^3

Input: n = 3

pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on

arr[] = {3, 5, 6, 4, 1, 2}

Output: 2

We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

(Google Interview)

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

Minimum operations required to remove an array Given an array of N integers where N is even. There are two kinds of operations allowed on the array.

  1. Increase the value of any element A[i] by 1.
  2. If two adjacent elements in the array are consecutive prime number, delete both the element. That is, A[i] is a prime number and A[i+1] is the next prime number.

The task is to find the minimum number of operation required to remove all the element of the array.

size of array 10^5

size of element 10^3

Examples:

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

Minimum 5 operation are required.

  1. Increase the 2nd element by 1 { 1, 2, 4, 3 } -> { 1, 3, 4, 3 }

  2. Increase the 3rd element by 1 { 1, 3, 4, 3 } -> { 1, 3, 5, 3 }

  3. Delete the 2nd and 3rd element { 1, 3, 5, 3 } -> { 1, 3 }

  4. Increase the 1st element by 1 { 1, 3 } -> { 2, 3 }

  5. Delete the 1st and 2nd element { 2, 3 } -> { }

Input : arr[] = {10, 12} Output : 3

Read more »

 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

Given an array of n integers. Find the maximum value of arr[i] mod arr[j] where arr[i] >= arr[j] and 1 <= i, j <= n

where arr.size<10^3 n<10^3

Input: arr[] = {3, 4, 7}

Output: 3

Explanation:

There are 3 pairs which satisfies arr[i] >= arr[j] are:-

4, 3 => 4 % 3 = 1

7, 3 => 7 % 3 = 1

7, 4 => 7 % 4 = 3

Hence Maximum value among all is 3.

Input: arr[] = {3, 7, 4, 11}

Output: 4

Input: arr[] = {4, 4, 4}

Output: 0

Read more »

 
 
 
 
  • Vote: I like it  
  • -36
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

Given two arrays A[] and B[], write an efficient code to determine if every element of B[] is divisible by at least 1 element of A[]. Display those elements of B[], which are not divisible by any of the element in A[].

Examples:

Input : A[] = {100, 200, 400, 100, 600}

B[] = {45, 90, 48, 1000, 3000}

Output : 45, 90, 48

The output elements are those that are

not divisible by any element of A[].

n<10^5 arr.size<10^5

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

Given a non negative array, find the number of subsequences having product smaller than K.

k<10^2 arr.size<10^3

Examples:

Input : [1, 2, 3, 4]

k = 10

Output :11

The subsequences are {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}

Input : [4, 8, 7, 2]

k = 50

Output : 9

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

Given an array with non negative numbers, divide the array into two parts such that the average of both the parts is equal. Return both parts (If exist).

If there is no solution. return an empty list.

Example:

Input:

[1 7 15 29 11 9]

Output:

[9 15] [1 7 11 29]

The average of part is (15+9)/2 = 12,

average of second part elements is (1 + 7 + 11 + 29) / 4 = 12

arr.size<10^3

Read more »

 
 
 
 
  • Vote: I like it  
  • -18
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.

Examples:

Input : points[] = {-1, 1}, {0, 0}, {1, 1}, {2, 2}, {3, 3}, {3, 4}

Output : 4

Then maximum number of point which lie on same

line are 4, those point are {0, 0}, {1, 1}, {2, 2}, {3, 3}

where arr.size<10^3

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By Dhanadeepa_Red, history, 10 months ago, In English,

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2

Output: [0, 3, 5]

Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].

We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

nums.length will be between 1 and 20000.

nums[i] will be between 1 and 65535.

k will be between 1 and floor(nums.length / 3).

Read more »

 
 
 
 

By Dhanadeepa_Red, history, 11 months ago, In English,

We have N (where N > 2) stones of various heights laid out in a row. Task is to make a pyramid from given array of stones. In a pyramid, height of the stones start from 1, increase by 1, until it reaches some value x, then decreases by 1 until it reaches 1 again i.e. the stones should be 1, 2, 3, 4…x – 1, x, x – 1, x – 2 … 1. All other stones not part of the pyramid should have a height 0. We cannot move any of the stones from their current position, however, by paying a fee of 1, we can reduce the heights of the stones. We wish to minimize the cost of building a pyramid. Output the minimum cost to build this pyramid.

N<10^3 height<10^4

Examples:

Input : 1 2 3 4 2 1

Output : 4

The best pyramid that can be formed in this case is:

1 2 3 2 1 0

The cost is thus:

(4 — 2) + (2 — 1) + (1 — 0) = 4

Input : 1 5 2

Output : 4

We make a pyramid 1 2 1

Input : 1 2 1

Output : 0

We already have a pyramid, we do not need to do any

further construction.

Read more »

 
 
 
 

By Dhanadeepa_Red, history, 11 months ago, In English,

Given an integer n > 0, which denotes the number of digits, the task to find total number of n-digit positive integers which are non-decreasing in nature.

A non-decreasing integer is a one in which all the digits from left to right are in non-decreasing form. ex: 1234, 1135, ..etc.

Note :Leading zeros also count in non-decreasing integers such as 0000, 0001, 0023, etc are also non-decreasing integers of 4-digits.

Examples:

Input : n = 1

Output : 10

Numbers are 0, 1, 2, ...9.

Input : n = 2

Output : 55

Input : n = 4

Output : 715

where n<10^3

Read more »