ZOMCAV - Editorial

editorial
, , , ,
22

Can somebody tell how we can use stack to solve the problem?

23

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. :stuck_out_tongue:

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

24

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"
25

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)

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