if someone has solved recent july long challenge MCHEF question using lazy propogation , then plz share it’s solution here . I am solving lazypropogation question first time, so i have to clear some things about it.
Question link-> http://www.codechef.com/problems/MCHEF
You don’t need lazy for this … It can simply be done by updating those nodes for which segment range lies inside query range !
For index query go to the depth by taking minimum of all the nodes through which you are traversing !
Both update and query can be done in O(logn) !
My solution link -> link text
2 Likes
Here is the link to my solution, which i solved using lazy. http://www.codechef.com/viewsolution/7455248
Hope you understand it. If you have any problems, you can ask me.
@likecs , plz have a look on my code
http://www.codechef.com/viewsolution/7482149
My solution is running fine on my machine , but giving wrong ans on codechef.
See the figure for a segment tree with 10 nodes labelled from 0-9 (0 based array indexing) on this link
Now, there is basically 2 major faults in your solution. First the number of nodes in a segment tree is 2n-1 but the value of t for a segment tree is less then 2(2^(ceil(log2(n)))-1. For example in the above figure, the value of t for range 7-7 is not 15, but 19. So, in case of large values of n, your program is trying to access a memory location which is not available(see segmentation fault is the last 2 cases). Also, you must initially set the tree values to 501, the maximum sum of the cost which can be there. You have initialized it with 201, the maximum possible cost one item can take. This is wrong as your segment tree is responsible for storing the value of sum of costs in the interval. By storing 201, your basic purpose of segment tree is lost. Also, to optimize your solution, first store the minimum cost of every element in separate array. You are calling the same range query again and again in the knapsack dp, which increase the time taken by your solution.
If it was the first time you are attempting segment trees question, first have a look at se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html and www.spoj.pl/forum/viewtopic.php?f=27&t=8296 to underatnd segment trees and lazy propagation. then Attempt some basic questions lake range minimum query with range updates, Flipcoin and Multiples on 3 (on Codechef Medium level) etc. and then try the questions like MCHEF, ADDMUL, CHEFCK etc on codechef.
May be this helps…
You can just use an array instead of segment tree for updation.
Any cell of above mentioned array tells you which index to go next.Let me give you an example.
Let the Array be : Wheretogonext[1…N] and initially it contains {2,3,4,5,6…N} and another array that contains data which need to be updated and let it be cost[1…N] initialized to INTMAX.
Declare a structure that has left index,right index and cost as follows.
struct query{
int left,right,bribe;
};
Declare an array of queries of above type and input all the query data.Next thing is to sort this query array in increasing order of bribe amount.Eg let there be 4 judges ie, M=5.
query Q[1…M] has–> {left right bribe}
Q[1]–> 3 4 2
Q[2]–> 1 3 4
Q[3]–> 6 6 5
Q[4]–> 4 5 8
now update the cost[Q[1].left…Q[1].right] to Q[1].bribe.This can be done using simple ‘for loop’.While updating you also need to update Wheretogo_next[Q[1].left…Q[1].right] to Q[1].right+1 in parallel so that you don’t need to process the same sub array again.
After processing Q[1] Wheretogonext[1…N] has {2,3,5,5,6,7}, and after processing Q[2] Wheretogonext[1…N] will contain {4,4,5,5,6,7} .Here 3rd index will not be updated as cost[3] is !=INT_MAX which tells you that is has already been updated with a minimum value.Try iterating following loop manually for better understanding.
for(i=1;i<=M;i++)
{
j=A[i].left;
while(j<=A[i].right&&j<=N)
{
if(cost[j]==maxx) //maxx = INT_MAX
{
cost[j]=A[i].bribe;
}
k=j;
j=next_idx[j]; //nxt_idx is same as Where to go next
next_idx[k]=A[i].right+1;
}
}
@likecs, thanks for correcting my segmentation error. but my idea of creating segmentation tree is to store minimum cost for a node instead of storing sum of costs for the node. Also now i am calculating and storing minimum value seperately as u suggested in cost[] array.Can you still help me why am i getting the WA now ??
my new solution -> http://www.codechef.com/viewsolution/7483903
This is one of the similar code which i used before. I was facing the same problem. I am providing you with a test case which you should solve on your own and then check what solution your gives. You should try to solve it own your own. This will improve your skills on laziness which can be understood on our own only. Every time, new concept on laziness can occurs. Just to give a hint, do not reset the value of lazy in this question. If you still have problem, you can ask me. I will explain the full concept in detail. The test case is (just the range updates ones)
1 6 64,
2 7 65,
3 8 75,
4 6 72,
3 3 57,
3 4 61,
1 10 78,
9 9 12,
To understand the concept well draw lazy and segment trees and think what values you will assign them after update operations.
i don’t understand ur hint…??
but i tried to draw segment tree with my solution for ur test case and it is gives right value corresponding to every leaf node after applying update and query operation