rr459595's blog

By rr459595, history, 46 hours ago, In English,

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

Thanks.

Read more »

 
 
 
 

By rr459595, history, 6 days 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, 4 weeks 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, 7 weeks 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, 2 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, 2 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, 3 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