ZOMCAV - Editorial

editorial
, , , ,
26

Yep, you’re right. Let me fix that. Thanks for the reply!

1 Like
27

Here take a look at my solution using Binary Index Tree and HashMap. AC at 0.9sec.

Code

Reply if can be optimized.

Cheers

28

i did the same way :rofl:

29

Can you please explain your approach and why are you using abs(n*n) ?

30

The solution appears to be wrong, and only getting AC due to weak testcases (like quite a few of the solutions that have been submitted ;))

For example, it outputs

YES

for the testcase

1
4
2 1 3 3 
5 1 2 6

@vijju123 - is it possible to get testcases added to Problems in the Practice section? Weak testcases can instill bad habits :slight_smile:

31

I agree. I will ping the contest admin and the setter for it and see what can be done.

1 Like
32

Hey guys!
You are doing great job.
Just one suggestion, you can use more readable/understandable/proper variable names which may leads to understand code from editorials quickly.
I’m referring to ini_C, fin_C

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