Although I understand the intuition behind the solution, I am not able to prove the greedy approach formally. Can someone please help me with the proof of greedy solution for this problem ( https://leetcode.com/problems/longest-happy-string/ ) ?

Thanks.

You are given a number x. you have to find the minimum number of steps required to reach n from 1. At a particular point, you have two choices

1) increment the number by 1

2) reverse the integer (remove leading zeros after reversing)

eg: n=42

sol: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>41>42 (15 steps)

The minimum steps to reach 42 from 1 is 15. This can be achieved if we increment numbers by 1 from 1 to 14 (13 steps). After reaching 14 we can reverse the number which will give us 41 (1 step). From 41 we can increment number by 1 to reach 42(1 step). hence total 15 steps which is then minimum

Note that if we reverse the number after reaching 12 or 13, we will not get the minimum steps

1>2>3>4>5>6>7>8>9>10>11>12>21>22>23>32>33>34>35>36>37>38>39>40>41>42 (25 steps)

eg: n=16

sol: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>15>16 (15 steps)

In this case we have to increment the numbers till 16 which will give us the minimum of 15 steps.

Constraints:- 1<=n<=10^14.

I can only think of BFS/DP here which doesn't look like optimal solution.

Link to the question:- https://www.interviewbit.com/problems/rook-movement/

I tried BFS where in each state I store min steps,direction (up,down,left or right). I am getting TLE for large inputs.

Can someone help me ?

Thanks.

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.) Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: position += speed, speed *= 2.

When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1. Now for some target position, return the length of the shortest sequence of instructions to get there.

Constraints:- 1<=target<=10^4

1) Input:- 3 Output:- 2 (shortest instruction is AA)

2) Input:- 6 Output:- 5 (AAARA)

3) Input:-5 Output:-7

Can someone please help me with this problem?

Thanks.

I solved this problem on hackerrank ( https://www.hackerrank.com/contests/dcl2k15/challenges/mice-v1 ) based on greedy approach. I am not able to understand the proof of the greedy approach.

The proof says max( |a1-b1| , |a2-b2| ) <= max( |a1-b2|, |a2-b1| ) for a1<a2 and b1<b2. Can someone help me in proving the inequality?

I came across this problem on leetcode. ( https://leetcode.com/problems/task-scheduler/ ) . I get the intuition of why greedy approach (round-robin fashion) should work but not able to prove that it's always optimal.

Can someone help me in proving it ?

Thanks.

I tried solving this problem on leetcode ( https://leetcode.com/problems/dungeon-game/ ). I got AC with bottom up approach but wrong answer with top down approach.

Can someone help me in proving why only bottom up approach works and not top down (tabulating values from top left to bottom right)?

Thank you.

I am solving this problem (https://leetcode.com/problems/minimum-cost-to-merge-stones/ ).

The solution uses 3-D dp with following transitions:-

1) dp[i][j][m] means the cost needed to merge stone[i] ~ stones[j] into m piles.

Initial status dp[i][i][1] = 0 and dp[i][i][m] = infinity.

2) dp[i][j][m] = min(dp[i][mid][1] + dp[mid + 1][j][m — 1])

I am not able to understand the 2nd transition properly. Why are we trying to merge stones i~mid into only 1 stone and not considering other possibilities ? Shouldn't the transition be dp[i][j][m]=min(dp[i][j][m],dp[i][mid][x]+dp[mid+1][j][m-x]) for x in range(1,m-1) ?

Thanks.

Algorithm to find the diameter of a tree is :-

1) Choose a random node s and find the farthest node u from s.

2) Find the farthest node v from u.

3) d(u,v) is the diameter.

Can someone please explain why this algorithm works ?

Thanks

Is there any way to get index of an element in TreeSet?

I want a data structure(like set in c++) which can handle deletions in O(1) and do search(like lower_bound in c++) in O(logn) time.

Is there any inbuilt data structure in Java which supports the above operations?

Link to the problem:- http://codeforces.me/problemset/problem/437/B

I read the editorial where it says we have to use greedy approach by iterating from limit to 1. I don't understand why this approach works here.Iterating from 1 to limit doesn't work here.

Can someone help me in proving why greedy approach(iterating from limit to 1) works here ?

Thanks.

How to solve this problem ?http://codeforces.me/contest/205/problem/B

Thanks.

Here is the link to the problem:- http://codeforces.me/problemset/problem/2/B

If we have input matrix(2 rows and 3 columns) as:-

2 3

3 4 5

5 1 5

If we take 1-indexing, then at cell (2,2), we have 2 choices to get 0 number of trailing zeroes. One is (3*4*1) or (3*5*1). But we if we take (3*4*1)=12, then at the end cell (2,3), minimum number of trailing zeroes will be 1(by path 3-4-1-5). If we take 15 at cell 2, minimum number of trailing zeroes at the end will be 0 by path (3-5-1-5).

How to decide which number should I pick at cell (2,2) so that it doesn't affect the future cell (2,3)?

Thanks.

Can someone please help me with this problem (https://www.codechef.com/COOK94B/problems/CHEFLAKE) ? I am not able to understand the D.P approach behind this problem.

Thanks.

You are given a list of positive integers along with a sequence of operations from the set {∗,+}. You construct expressions from these two lists so that:

The numbers in the expression are drawn from the first list, without repetition and without altering their order. All the operators in the second list are used in the expression, in the same order. For example, if the two lists are [1,3,2,1,4] and [′∗′,′+′], the set of possible expressions you can form are 1∗3+2,1∗3+1,1∗3+4,1∗2+1,1∗2+4,...,2∗1+4 For each expression, the value is computed by bracketing operators from the right. That is, the expressions above are evaluated as 1∗(3+2),1∗(3+1),1∗(3+4),1∗(2+1),1∗(2+4),…,2∗(1+4). The aim is to determine maximum value among these expressions.In this example, the maximum value is 18, from the expression 3*2+4, which is evaluated as 3∗(2+4). You may assume that the length of the first list is more than the length of the second list.

How do I solve this problem ?

Link to the problem :- http://www.spoj.com/problems/TEMPLEQ/

In this question for answering type 3 queries where we have to update the nodes with value greater than x, we create a segment tree and do lazy propagation. In segment tree, internal nodes are maximum of left and right child.

For answering type 1 queries (updating), I need the last index of a particular element. If array is 1 2 2 2 2 5, last index of 2 is 5.

My question is how can I find the last index of a particular element using binary search in the above segment tree (where internal nodes have max of left and right child) in O(logn) time instead of O(log²n)?

Thanks.

I am getting TLE in this problem. I used lazy propagation with co-ordinate compression.

Link of the problem:- http://www.spoj.com/problems/POSTERS/

Code:- https://pastebin.com/cy0Zvx0Q

How do I apply co-ordinate compression here ?

If points (1,4), (2,6), (8,10), (3,4), (7,10). If I sort it and stor the indices in hashmap, then (1,2,3,4,6,7,8,10) will be compressed to (1,2,3,4,5,6,7,8).If I compress it this way then it fails for this test case.

6

1 3

4 6

6 7

8 1

1 2

3 4

I get answer as 4 because poster 2 at point (5,5) is not stored here as we have no index for 5.

I am newbie to this topic. Any help would be appreciated.

I am getting TLE with java on this problem http://www.spoj.com/problems/GSS3/ . I checked all testcases and it seems to be running fine. Any help would be appreciated.

Code :- https://ideone.com/lFTHXl

A program to find the processes which utilize the memory optimally, given the list of the processes with their memory usage and the total memory available.

Example:- Total memory :- 10

Processes:- 1 2 3 4 Memory usage:- 2 3 4 5

Answer should be processes {1,2,4} with memory consumption {2,3,5} as 2+3+5=10