ZOMCAV - Editorial

editorial
, , , ,
33

Yeah. Thats not exactly in my bounds to control the variable names used by setter or tester. But I will take this feedback to keep better names in editorialist solution :slight_smile:

1 Like
34

because maximum possible radiation in any cave is n and there are n caves so sum of all elements of H array should be less than (n*n)

35

Here is my solution its almost same as the editorial but not as efficient as other codes.
https://www.codechef.com/viewsolution/25893694

1 Like
36

I’m starting to sound like a jerk, here, but this is also incorrect :frowning: Consider:

1
5
1 2 1 2 1 
2 3 4 3 3

(I should probably point out that I have a long, long history of whining about weak testcases, so none of this is personal - it’s just one of my bugbears :slight_smile: :

)

1 Like
37

This is my solution CodeChef: Practical coding for everyone
It takes 0.42 sec.

38

i am not able to understand why this line?

39

What do you think should be the leftmost index in case i-C_i is negative (in 0-based indexing) or 0 (in 1-based indexing)?

40

value of i-ini_c[i] might be <1 then we can’t update indexes that are less than 1
so we still need to update from index 1
so left bound=max(1,i-ini_c[i])

similarly the value of i+ini_c[i] might be >n then we can update only upto n
so right bound=min(n,i+ini_c[i])

1 Like
41

My approach using segment tree and lazy propagation. Here. Execution time(1.51).

1 Like
42

i got TLE error on my segmented tree with lazy propogation link
@vijju123 @kamesh_11 help me this

44 
 if l <= start and end <= r:
        SegTree[pos] += (end - start +1) * val
        if start != end:
            lazy[2*pos +1] += val
            lazy[2*pos + 2] += val
        return 
    
    mid = (start + end)//2
    range_update(SegTree, arr, lazy, start, mid, l, r, val, 2*pos+1)
    range_update(SegTree, arr, lazy, mid+1, end, l, r, val, 2*pos+2)
    SegTree[pos] = SegTree[2*pos+1] + SegTree[2*pos+2]
    return

Correct me if I got it wrong, but afaik lazy propagation states that once you store things in lazy array, you do not go on to update the children unless required by the query.

45 
void update(ll segTree[],ll lazy[],ll qlow,ll qhigh,ll low,ll high,ll val,ll pos)
{
   if(lazy[pos]!=0)
   {
       segTree[pos]+=(high-low+1)*lazy[pos];
       if(low!=high)
       {
           lazy[2*pos+1]+=lazy[pos];
           lazy[2*pos+2]+=lazy[pos];
       }
       lazy[pos]=0;
   }
   if(low>high or qlow>high or qhigh<low)
       return;
   if(qlow<=low and qhigh>=high)
   {
       segTree[pos]+=(high-low+1)*val;
       if(low!=high)
       {
           lazy[2*pos+1]+=val;
           lazy[2*pos+2]+=val;
       }
       return;
   }
   int mid=low+(high-low)/2;
   update(segTree,lazy,qlow,qhigh,low,mid,val,2*pos+1);
   update(segTree,lazy,qlow,qhigh,mid+1,high,val,2*pos+2);
   segTree[pos]=segTree[2*pos+1]+segTree[2*pos+2];
}

@vijju123
i check @kamesh_11 soltion it same as mine

46

It only cover partially range

47

CodeChef: Practical coding for everyone can anyone help me this?

48

Here’s a small testcase for which it fails, to help you debug:

1
5
4 2 2 3 1 
4 5 4 4 4

but more than that, your solution appears to be O(N^2), and so too slow to pass the larger testcases - you’ll get a TLE.

1 Like
49

it should show “NO” for that test case right?

50

No, it should be YES - what are the radiation levels for that testcase?

51

5 5 5 5 4 is this right?

52

I get:

4 4 4 5 4

After processing the first cave (radiation power: 4)

1 1 1 1 1

After processing the second cave (radiation power: 2)

2 2 2 2 1

After processing the third cave (radiation power: 2)

3 3 3 3 2

After processing the fourth cave (radiation power: 3)

4 4 4 4 3

After processing the fifth cave (radiation power: 1)

4 4 4 5 4
1 Like
53

yeah,for the fifth cave I took Ci - i instead of i - Ci.
thanks