PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Jeevan Jyot Singh
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh
DIFFICULTY:
1202
PREREQUISITES:
None
PROBLEM:
You have an array A containing N integers which are not known to you. You are also given a binary string S of length n - 1. For each 1 \le i \le N - 1, S_i denotes the following:
- If S_i = 0, then A_i < A_{i+1}
- If S_i = 1, then A_i > A_{i+1}
For how many values of i (1 \le i \le N) is it possible that A_i is the maximum element of the array A.
EXPLANATION:
Insert 0 in the beginning of the string and 1 to the end the string. The number of substring 01 in this modified string is the answer to the problem.
How? For every substring of all 1s which have 0 on both there sides(if they exist), only the first number can be assigned the maximum value as this substring represents a strictly decreasing subarray. Thus, the number of 01 in the modified string is the answer to the problem
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's Solution
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 1e18;
const int N = 1e6 + 5;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
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, ' '); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int sumN = 0;
void solve()
{
int n = readIntLn(2, 1e5);
sumN += n;
string s = readStringLn(n - 1, n - 1);
assert(*min_element(s.begin(), s.end()) >= '0' and *max_element(s.begin(), s.end()) <= '1');
s = '0' + s + '1';
int ans = 0;
for(int i = 0; i + 1 < sz(s); i++)
{
if(s[i] == '0' and s[i + 1] == '1')
ans++;
}
cout << ans << endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
assert(sumN <= 1e5);
readEOF();
return 0;
}
Tester-1's Solution(Python)
for _ in range(int(input())):
n = int(input())
s = '0' + input() + '1'
print(s.count('01'))
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, ans = 0;
cin >> n;
string s;
cin >> s;
for (int i = 0; i < n - 1; i++)
{
if (s[i] == '1' && (i == 0 || s[i - 1] == '0'))
ans++;
}
if (s.back() == '0')
ans++;
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
**