BLONDIE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice Link

Contest Link

Author: Ankush Khanna

DIFFICULTY:

Cakewalk

PREREQUISITES:

Prefix sum

PROBLEM:

Given an array with some elements missing, you have to find the missing elements. The missing elements can be found by taking the rounded down average of all the elements traversed before it. The first element is always known.

QUICK EXPLANATION:

Key to AC: Build a prefix sum of the elements traversed so far, whenever we encounter a missing element, take the rounded down average of the current prefix built (till the previous element), update the array element and also the prefix sum. That’s it!

EXPLANATION:

There are two ways of solving this problem. The first one is to just follow what is written in the problem statement (the steps) and solve the sub-task 1 for 30 points. Because it will be a brute force solution working in O(N^2) time, and would certainly fail to pass sub-task 2 within the given time constraint.

The other way is to simply keep a track of the accumulated sum by using prefix sum technique. As mentioned in the quick explanation part, the solution just needs to do the same.

Actually, the quick explanation is the real explanation for this problem. My solution for this problem works in O(N) time per test case, and I have used O(1) auxiliary space for my solution.

COMPLEXITY:

Being a regular cakewalk problem, this problem is also solved in O(N) time per test case. The regular solutions that I have seen have taken O(N) auxiliary space for building the prefix sum, but it can also be done using just constant O(1) auxiliary space.

SOLUTION:

Setter’s Solution [Plain Text]

Feel free to share your approach. If you have any queries, they are always welcome.

2

#include<bits/stdc++.h>

using namespace std;

int main(){

int T;

cin>>T;

while(T–){

long long n;

cin>>n;

long long arr[n]; long long p[n];

for(int i=0;i<n;i++){

cin>>arr[i];



if(arr[i]==-1)

arr[i]=p[i-1]/i;



else if(i==0)

p[0]=arr[0];



else

p[i]=p[i-1]+arr[i];

}



for(int i=0;i<n;i++){

    cout<<arr[i]<<" ";

}

}

return 0;

}

what is error in this???

3

Try changing this to

else if(i == 0) {
    p[0] = arr[0];
}

if(i > 0) {
    p[i] = p[i - 1] + arr[i];
}
2 Likes
4

thank u