ZOMCAV - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Sayantan Das
Tester- Suchan Park
Editorialist- Abhishek Pandey

DIFFICULTY:

Simple

PRE-REQUISITES:

Difference Array

PROBLEM:

Given N caves, and an array C of same size where C_i denotes that all caves in range [i-C_i,i+C_i] have their radiation level increased by 1. There are also N zombies, with i'th zombie having health H_i. A zombie dies iff it goes into the cave with radiation level (and NOT radiation power C_i) equal to H_i. find if all zombies can be killed or not.

QUICK-EXPLANATION:

Key to AC- Use difference array to do the updates and then check if sorted arrays are same or not!

Let the final array, containing the radiation level of all caves be A. We need to find out a way to calculate A. We will do that via the technique of difference array!

Create an array D[N] where D[i] is defined as D[i]=A[i]-A[i-1] and D[0]=A[0]. Note that since this array D stores the difference between consecutive elements, it is possible to find array A in O(N).

We can now update the radiation levels due to radiation power of a cave in O(1). Say our current index is i. All we need to do is that D[i-C_i]+=1 and D[i+C_i+1]-=1, as starting from index i-C_i, the radiation level of caves upto i+C_i is increased by 1. The D[i-C_i]+=1 means that starting from this index, the radiation level of caves upto the last cave is increased by 1. And D[i+C_i+1]-=1 denotes that starting from this cave, the radiation level of caves, upto the last cave, is decreased by 1.

Prefix summing the array D gives us the array A. Now, all we need to check is if for every element in A, there is an element in array H. For this, simply sort both the arrays A and H and see if they are equal or not.

EXPLANATION:

The editorial will consist of following sections-

  • What is a difference array? What is its use?
  • How to use difference array in our given problem.
What is Difference Array and its Use

I’d first ask you to give the pre-requisite link a read before proceeding here.

Essentially, what difference array concept says is-

Say you have an array A on which you are doing range updates, i.e. updating an interval [L,R] with some constant value. Define an array D which stores D[i]=A[i]-A[i-1] and D[0]=A[0]. Its clear that doing the prefix sum of D will give us the final array A after the update.

Now, say if I have to update values in an interval [L,R] by some constant K, I simply update the difference array. What happens to D if I add K in range [L,R] ? The difference between A[L] and A[L-1] increases by K, which is captured by D[L]=D[L]+K. And the difference between A[R+1] and A[R] decreases by K , hence D[R+1]=D[R+1]-K.

Essentially, what D[L]=D[L]+K denotes is that “I am add K to all elements in range [L,N]” and D[R+1]-=K denotes that "I am subtracting K from all elements in range [R+1,N]. These both operations, which can be done in O(1), capture the essence of updating the difference array if elements of A in range [L,R] are increased by K. Note that, we do not care for any intermediate element, in range [L+1,R-1], because if all elements in range [L,R] are increased, then their relative difference remains same! This is why we only needed to update difference array at endpoints.

By definition now, D[0]=A[0]. What happens if I do prefix sum of it?

D[1]+D[0] = (A[1]-A[0])+A[0]=A[1]
D[2]+D[1]= (A[2]-A[1])+A[1] = A[2]
.
.
.
D[i]+D[i-1]= (A[i]-A[i-1])+A[i-1]=A[i]

Hence, the final array A is restored after we do prefix sum of D - which is usually done after all updates are applied.

Using Difference Array in this Problem

If the above is clear to you, you’ll realize that this question screams of difference array!

Make a difference array D.Let us then iterate through the array C. Lets denote its i'th element by C_i. Calculate the range in which we have to update the values by finding L=max(0,i-C_i) and R=min(N-1,i+C_i). Note that we follow 0-based indexing here. The min and max stuff is done only to make sure that 0 \leq L \leq R \leq N holds, else we may get a runtime error if we access an index out of bounds of the array!

We simply do a D[L]+=1 and a D[R+1]-=1 for the particular [L,R] we found above. Then we iterate to next value of C, i.e. C_{i+1} and repeat the story there. Note that initially the radiation level everywhere was 0, and hence D[0]=A[0] holds.

Simply doing a prefix sum of D now gives us the final array A, which has the radiation level of call caves. Now we need to see if for each element of H, i.e. the array with health of a zombie, can we find an element in A or not. The simplest way is to simply sort both the arrays, and then check for equality of elements at each index. If the equality holds, then the answer is YES , else the answer is NO.

SOLUTION

Setter
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
double sum=0;
void solve()
{
	int n;
	cin>>n;
	vector<int> ini_C(n+1),H(n+1),fin_C(n+1,0);
	
	for(int i=1;i<=n;i++)
	 cin>>ini_C[i];
	for(int i=1;i<=n;i++)
	 cin>>H[i];
 
	for(int i=1;i<=n;i++)
	{
		int left=max((int)1,i-ini_C[i]),right=i+1+ini_C[i];
		fin_C[left]++;
		if(right<=n)
			fin_C[right]--;
	}
	for(int i=1;i<=n;i++)
		fin_C[i]+=fin_C[i-1];
	
	sort(fin_C.begin(),fin_C.end());
	sort(H.begin(),H.end());
	
	if(H==fin_C)
		cout<<"YES\n";
	else
		cout<<"NO\n";
 
}
signed main()
{
	FAST;
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
} 
Tester (KOTLIN)
val random = java.util.Random()

fun main(args: Array<String>) {
  val reader = java.io.BufferedReader(System.`in`.reader())
  val T = reader.readLine()!!.toInt()
  require(T in 1..100)
  repeat(T) {
    val N = reader.readLine()!!.toInt()
    val sum = IntArray(N+1) { 0 }
    for((i, c) in reader.readLine()!!.trim().split(" ").map{ it.toInt() }.withIndex()) {
      sum[maxOf(i - c, 0)] += 1
      sum[minOf(i + c + 1, N)] -= 1
    }
    for(i in 1..N) {
      sum[i] += sum[i - 1]
    }
    val H = reader.readLine()!!.trim().split(" ").map{ it.toInt() }.shuffled(random).sorted()
    println(if(H == sum.sliceArray(0 until N).toList().shuffled(random).sorted()) "YES" else "NO")
  }
}

Time Complexity=O(NLogN)
Space Complexity=O(N)

CHEF VIJJU’S CORNER :smiley:

  • Can you give an bounds for-
    • Lower bound on H_i (say K) such that if H_i \geq K then answer is always NO
    • Can similar bounds be given for case YES ?
  • For each of the following data structure, tell if there exists an algorithm which would be able to solve this question using that data structure-
    • Stack
    • Queue
    • Only Segment Tree
    • Segment Tree + Lazy Propagation
    • Fenwick Tree
    • Red Black Tree
    • Sets
    • Hashmaps.
Setter's Notes

Let’s assume an array fin\_C[] that will store the Radiation level of the caves. Initially all the caves have a Radiation level equal to 0.Given Radiation power for each cave C[i], will increase the Radiation level by 1 unit of the caves indexed i-C[i] to i+C[i] in a contiguous manner.

For each i-th cave we can store its radiation range.

fin\_C[i-C[i]]++ will store the left range and fin\_C[i+C[i]+1]-- will store the right range.

Then with one iteration we can get the final Radiation level of the caves.
fin\_C[i]=fin\_C[i]+fin\_C[i-1].

Now we can send one zombie per one cave. If the health of the zombie is strictly equal to the cave’s Radiation level then the zombie dies.So, to kill all zombies their health H[] need to match with the Radiation level fin\_C[].
if sorted array fin\_C[]= sorted \ H[] print YES and NO otherwise.

Related Problems
16 Likes

Here’s my implementation using Segment tree+Lazy propagation
Solution

8 Likes

this my solution using segment trees
https://www.codechef.com/viewsolution/25875881

3 Likes

@vijju123 ,@sayantan_das24,@tncks0121

what about the test cases like mentioned above.

1 Like

@vijju123 My efficient Segment tree solution
link

1 Like

Its :heart: when people already solved the list of questions you prepared in bonus section :smiley:

4 Likes

Not under my jurisdiction :frowning: . I can only tag the contest admin and forward it to him.

2 Likes

My simple approach is take a array to store frequency of first appearances,i.e (i-c[i]) and another array to store frequency of last appearances,i.e ((i+C[i]). now for calculating the final array we need to compare with zombie healths…we can do is… “take the sum of last appearances from i to n and subtract sum of first appearances from i+1 to n”
i.e- f(k) = (last(k) + last(k+1) + … +last(n)) - (first(k+1) + first(k+2) + … + first(n))

link: CodeChef: Practical coding for everyone

3 Likes

My Solution Got AC using simple if statements
and for loop time- 0.29 sec

2 Likes

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

2 Likes

This problem having very weak TC.

There are many solution which should not pass the TC.

3 Likes

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

thanks for your solution, it is very helpful.

You’re welcome! :grin:

My solution CodeChef: Practical coding for everyone

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.

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

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]

i got it already thanks for help

1 Like

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