HOWMANYMAX-Editorial

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();
}

Can someone tell me what is wrong with this code, it has one wrong answers others all correct :frowning:
https://www.codechef.com/viewsolution/66459168

Input:
2
1
1
1
0

Your Output:
0
1

Correct Output:
1
1

1 Like

The answer can never be ‘0’. Check line 29.

1 Like

yoo thanks

so basically for l==1 it will be 1, damm such a small mistake :frowning: because of this i got WA in the contest :frowning:

edge cases are always very important. You will get a feeling for them over time.

1 Like

ok :frowning: