ZOMCAV - Editorial

editorial
, , , ,
10

The answer of the test case you have mentioned will be “NO”. You got an AC because of weak test data.

2 Likes
11

This problem having very weak TC.

There are many solution which should not pass the TC.

3 Likes
12

It’s a pretty tough one to write good testcases for because the output is just one of YES or NO :confused:

Perhaps it would have been better to ask for the maximum number of Zombies that would be killed, or somesuch. Would make for a slightly more interesting problem, too. Another approach would have been to allow 1000’s of testcases, but restrict the total N across all testcases to 100’000 - I have a suite of tiny, randomly-generated testcases that have exposed the errors in other people’s code after checking just a few hundred(!) testcases.

Edit:

Since people are posting solutions, here’s mine - fully commented and documented.

Edit2:

With a little bit of cunning, you can drop the need for sorting and end up with a O(N) time, O(N) space solution:

https://www.codechef.com/viewsolution/25928285

1 Like
13

thanks for your solution, it is very helpful.

15

You’re welcome! :grin:

16

My solution CodeChef: Practical coding for everyone

17

My solution, same approach as described above, without segment tree.Made an array of n+2. First I calculated the ranges and added one at starting index and subtracted one at element next to ending index.
After this, just did the prefix sum, sorted the array and got AC.

19

I have also used the same approach (Segment Tree + Lazy). But later I clicked that it can be done with by difference array. Here is my solution Zomcav solution

20

The editorial mentions it clearly that when you increment an index in difference array by 1, you are increasing all values in range [i,N] by 1. So we increase at index i-C_i and then decrease at i+C_i+1 so that it effectively becomes -

Increase all values in range [i-C_i,N] \cup Decrease all values in range [i+C_i+1,N] effectively becoming increase all values in range [i-C_i,i+C_i]

21

i got it already thanks for help

1 Like
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