rr459595's blog

By rr459595, history, 7 weeks ago, In English,

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

Read more »

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

By rr459595, history, 2 months ago, In English,

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?

Read more »

 
 
 
 

By rr459595, history, 2 months ago, In English,

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.

Read more »

 
 
 
 

By rr459595, history, 2 months ago, In English,

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

Thanks.

Read more »

 
 
 
 

By rr459595, history, 2 months ago, In English,

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.

Read more »

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

By rr459595, history, 3 months ago, In English,

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.

Read more »

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

By rr459595, history, 4 months ago, In English,

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 ?

Read more »

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

By rr459595, history, 4 months ago, In English,

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.

Read more »

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

By rr459595, history, 4 months ago, In English,

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.

Read more »

 
 
 
 

By rr459595, history, 6 months ago, In English,

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

Read more »

 
 
 
 

By rr459595, history, 2 years ago, In English,

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

Read more »

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