rr459595's blog

By rr459595, history, 2 days 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, 5 days 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 weeks 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, 22 months 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