rr459595's blog

By rr459595, history, 4 weeks ago, , 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.

By rr459595, history, 2 months ago, , 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

Thanks. #dp,
By rr459595, history, 2 months ago, , 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?

By rr459595, history, 3 months ago, , 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.

By rr459595, history, 4 months ago, , 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.

By rr459595, history, 5 months ago, , 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] = 0 and dp[i][i][m] = infinity.

2) dp[i][j][m] = min(dp[i][mid] + 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. By rr459595, history, 15 months ago, , Algorithm to find diameter of a tree is :-

) Choose random node s and find farthest node u from s.

2) Find farthest node v from u.

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

Can someone please explain why this algorithm works ? I tried searching it on Google but was not able to understand the proof.

Thanks

By rr459595, history, 16 months ago, , 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?

By rr459595, history, 16 months ago, , Link to the problem:- http://codeforces.com/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.

By rr459595, history, 16 months ago, , How to solve this problem ?http://codeforces.com/contest/205/problem/B

Thanks.

By rr459595, history, 16 months ago, , Here is the link to the problem:- http://codeforces.com/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.

By rr459595, history, 17 months ago, , 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.

By rr459595, history, 18 months ago, , 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 ?

By rr459595, history, 18 months ago, , 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(log2n)?

Thanks.

By rr459595, history, 18 months ago, , 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/

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.

By rr459595, history, 19 months ago, , 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

By rr459595, history, 3 years ago, , 