wish_me's blog

By wish_me, history, 7 years ago, In English

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

Full text and comments »

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

By wish_me, history, 7 years ago, In English

While I was solving this DP ,

http://codeforces.net/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??

Full text and comments »

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

By wish_me, history, 7 years ago, In English

I was trying to solve the problem http://codeforces.net/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?????

Full text and comments »

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

By wish_me, history, 7 years ago, In English

Hello All, While reading http://codeforces.net/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.

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years ago, In English

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

http://codeforces.net/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 ?

Full text and comments »

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

By wish_me, history, 7 years 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.

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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.

Full text and comments »

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

By wish_me, history, 7 years 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...

Full text and comments »

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

By wish_me, history, 7 years ago, In English
  • Vote: I like it
  • -10
  • Vote: I do not like it

By wish_me, history, 7 years ago, In English

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

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

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years ago, In English
Tags #dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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)

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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

Full text and comments »

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

By wish_me, history, 7 years 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).

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By wish_me, history, 7 years 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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By wish_me, history, 7 years 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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it