CROSSWORD EDITORIAL

PROBLEM LINK:

Practice

Author: Pratima Singh
Tester: Prasoon Jain
Editorialist: Pratima Singh

DIFFICULTY:

CAKEWALK, EASY

PREREQUISITES:

Implementation

PROBLEM:

Given a binary string of length y and an array of size n, where n is the number of partitions formed of only O in that string, and each element of this array represents the length of i-th partition. No two partitions can touch or overlap.
For example-

  • If y=6 and the word is OOXOOOOOXOOO, then its encrypted array is {2, 3}
  • If y=3 and the word is XXXXXX, then its encrypted array is empty

Let’s assume length y for string and n for array. If the array is also given to us, we need to check if there is exactly one string such that it’s length and array size is equal to what we opted.

EXPLANATION:

The only answer is when no segment(i.e. partition of the string) can be moved one cell either to the left or to the right. So there should be exactly one cell between two consecutive segments, and the first and the last segments should touch the borders.

Thus total count of cells needed is y = \sum_{i = 1}^{N} a_i +n-1

SOLUTIONS:

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void solve();

int main() {
	 solve();
	return 0;
}
void solve(){
    int n,y;
    cin>>n>>y;
    int s=0;
    for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        s+=x;
    }
    if(y==s+n-1){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}```
Editorialist's Solution
 n, y = list(map(int, input().split()))
 a = list(map(int, input().split()))
 if sum(a)+n-1 == y:
     print("YES")
 else:
     print("NO")

Feel free to share your approach, if you want to. Suggestions are welcomed.