PROBLEM LINK:
Setter- Sayantan Das
Tester- Suchan Park
Editorialist- Abhishek Pandey
DIFFICULTY:
Simple
PRE-REQUISITES:
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
- 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
?
- Lower bound on H_i (say K) such that if H_i \geq K then answer is always
- 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.