PGRID1 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Nandini Kapoor

DIFFICULTY:

Easy

PREREQUISITES:

Implementation, Running Sum

PROBLEM:

Suppose we have a 2D grid A of infinite width and height of N units. Each row of the grid can be represented in the form of 111…(x times)00…∞ where x\gt 0, implying the row starts with consecutive 1'_{s} followed by all 0'_{s}.

Now you do the following in each step.

Choose an unmarked cell having 1. Let it be (i, j).
while((i,j) lies in the grid boundaries && A[i][j] == 1){
    mark[i][j] = true; i--; j--;
}

How many minimum number of steps are required to cover all the cells containing 1.

Note: The number of consecutive 1'_{s} at each height is given by the array W where W_i represents the same at i_{th} height.

QUICK EXPLANATION:

We will apply the step on all the 1's in the first row. Then we move down the rows and check how many set bits are to the bottom left of set bits of the row above it, and apply no extra steps to make these 0. For the 1's in a row that have no 1 to the top right of themselves, extra step must be applied. Maintain this running sum of needed number of steps to make all set bits unset from the top to the current row of the matrix in order to obtain the final answer.

EXPLANATION:

Claim: If the number of 1's (say L) in a row are less than the number of 1's (say U) in the row above it, then the row above can engulf all the 1's of the row below it without using any extra step.

Proof

Assuming U and L as above, we are working on the implications of the relation L\lt U.

Consider the topmost row consisting of x+1 number of 1's: 1_01_11_2...1_x000...
For the first 1 in the row i.e. at A[0][y], there is no element A[i-1][j-1]=A[-1][y] (to its bottom left as per the diagram in the problem statement itself) that can be engulfed in a single step along with A[0][0]. The same is also true for every first element in every row no matter what height it recides at (i.e. value of y is of no consequence). Thus the first element of none of the rows can engulf any of the elements in the lower row in a single step but the next x number of 1's can. Thus a row with x+1 number of 1's can engulf x number of 1's from the row below it.

The second 1 of the upper row at A[1][y] can engulf the 1 at A[0][y-1].
The third 1 of the upper row at A[2][y] can engulf the 1 at A[1][y-1].
Each 1 can engulf the 1 diagonally to the bottom left of itself, thus the last 1 in a row A[x][y] can engulf A[x-1][y-1]. If the 1 engulfed by any of the 1's of the upper row was the last 1 of the lower row, then no extra step is needed to be performed on this lower row as all its 1's became 0's when we selected each of the 1's of the upper row and went diagonally bottom left in each step.

As the topmost row has no other row above it, we apply the step on all of its 1's as they can’t depend on a higher row element to engulf them. Then we move to the next row and check whether the 1's can be engulfed or not. The ones that can’t be engulfed need to become the starting points of newer steps and thus will be able to engulf diagonally bottom left positioned 1's without extra steps and so on.

Before proceeding to a lower row, the number of steps needed to flip all the 1's above that row have been added to the answer. Thus on reaching such a row all whose 1's can be engulfed by the row above it, no extra step would be needed to flip all the 1's as they are reachable from the indices to the top right of themselves containing 1.

If this engulfing of the 1's of a lower row is not possible by the higher row, i.e. the number of 1's in the row below is greater than or equal to the number of 1's in the row above, then the 1's starting from U_{th} to the end of the lower row can not be engulfed. An extra L-(U-1) steps would be needed so that these ungulfable 1's can be flipped and the matrix from top row to the current row can be all unset bits.

We keep maintaining this running sum in a variable starting from the first row until the last row and obtain the final answer.

TIME COMPLEXITY:

O(N)

SOLUTIONS:

Setter
    #include <bits/stdc++.h>
     
    #define pb push_back 
     
    using namespace std;
     
    const int maxn = 1e5;
    const int maxtn = 1e6;
    const int minv = 1;
    const int maxv = 1e9;
    const int maxt = 10;
     
    int main()
    {   
        int t; cin >> t; 
        int tot = 0;
        while(t--){
            int n; cin >> n; tot += n;
            vector<int> v;
            for(int i = 0; i < n; i++){
                int x; cin >> x;
                v.pb(x);
            }
            int prv = 1; long long ans = 0;
            for(int i = n - 1; i >= 0; i--){
                ans += max(0, v[i] - prv + 1);
                prv = v[i];
            }
            cout << ans << endl;
        }
        assert(tot <= maxtn);
    } 
Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef double f80;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
#define double long double
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b>0) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
 
int w[100005];
void solve() {
	int n=readIntLn(1,100000),ans=0;
	fr(i,1,n) {
		if(i!=n)
			w[i]=readIntSp(1,1000'000'000);
		else
			w[i]=readIntLn(1,1000'000'000);
		ans++;
		if(w[i]>w[i-1])
			ans+=w[i]-1-w[i-1];
	}
	cout<<ans<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(1);
	int t=readIntLn(1,10);
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist
    #include<bits/stdc++.h>
    using namespace std;
     
    #define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
    #define int long long int
    #define endl "\n"
    #define mod 1000000007
    #define pb_ push_back
    #define mp_ make_pair
    //____z___
     
    void solve()
    {
        int n, ans=0;
        cin>>n;
        int a[n];
        for(int i=0; i<n; i++) {
            cin>>a[i];
            if(i==n-1) ans=a[i];
        }
        reverse(a, a+n);
        for(int i=1; i<n; i++) if(a[i]>=a[i-1]) ans+=(a[i]-a[i-1]+1);
        cout<<ans<<endl;
    }
     
    int32_t main()
    {
        _z;
        int t=1;
        cin>>t;
        while(t--)
        {
            solve();
        }
    }

4 Likes

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

Please help! I’m getting wrong answer… What’s wrong in my solution/approach,I think it’s very correct…