# ZOMCAV - Editorial

I did not said that stack can be used to solve the problem - I asked to explore if its possible to solve it using stack, and if yes then how.

The answer for some data structures can be no because we can’t blindly apply any data structure to any problem.

Here a Pythonized solution without sorting. Fastest solution for Python.

```for _ in xrange(input()):
n = input()
C = [0]+map(int, raw_input().split())
H = [0]+map(int, raw_input().split())
s = sum(min(n, i+c)-max(1, i-c)+1 for i,c in enumerate(C))
print "YES" if s==sum(H) else "NO"
```

That won’t work, alas - it gives YES for the following input, but should give NO:

``````1
4
2 1 3 3
5 1 2 6
``````

(the testcases for ZOMCAV are a little weak, which is why this gets AC)

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

1 Like

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

Code

Cheers

i did the same way

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

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

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

1 Like

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`

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

1 Like

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)

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

I’m starting to sound like a jerk, here, but this is also incorrect 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 :

)

1 Like

This is my solution https://www.codechef.com/viewsolution/25781531
It takes 0.42 sec.

i am not able to understand why this line?

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)?

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

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

1 Like

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