HR Bear and Steady Gene ( Binary Search )
https://www.hackerrank.com/challenges/bear-and-steady-gene
I knew it can be solved with crawling, but writing binary search was easier, and worked fine as well.
Try removing ( int ) before s.size() in the function ok(), and call ok() with parameter len = 0. You might find it surprising as I did, that it will show -1 > some positive value. This happens because it is integer compared against size_t ( which is unsigned ), and -1 will be converted into MAX_UNSIGNED_INT - 1 before comparison ( which I though size_t was the one that will be casted ). Anyways, I'll try to avoid implicit casting from now on. Here is a site that might be useful reading about.
c++ - Why does this if condition fail for comparison of negative and positive integers - Stack Overflow
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair< int, int > pii; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< pii > vpii; typedef vector< char > vch; const int INF = 0x3f3f3f3f; // #define MULTIPLE_CASES bool ok( int len, const string &s, const vvi &pcnt, const vch &gen ){ // cout << len - 1 << ( len - 1 < ( int )s.size() ? "<" : ">" ) << s.size() << endl; for( int i = 0; i + len - 1 < ( int )s.size(); ++i ){ bool fail = false; for( int j = 0; j < 4; ++j ){ int cnt = pcnt[ gen[ j ] ][ i + len ] - pcnt[ gen[ j ] ][ i ]; int remain = pcnt[ gen[ j ] ][ s.size() ] - cnt; if( remain > s.size() / 4 ) fail = true; } if( !fail ) return true; } return false; } void solve(){ int N; cin >> N; string s; cin >> s; const vch gen = { 'A', 'C', 'T', 'G' }; vvi pcnt( 256, vi( N + 1 ) ); // 1 idx for( int i = 0; i < s.size(); ++i ) for( int j = 0; j < 4; ++j ) pcnt[ gen[ j ] ][ i + 1 ] = pcnt[ gen[ j ] ][ i ] + ( s[ i ] == gen[ j ] ); int lb = 0, rb = N; int ans = -1; while( lb <= rb ){ int mid = lb + rb >> 1; if( ok( mid, s, pcnt, gen ) ) ans = mid, rb = mid - 1; else lb = mid + 1; } cout << ans << "\n"; } int main(){ ios::sync_with_stdio( false ); cin.tie( 0 ); cout.tie( 0 ); #ifdef MULTIPLE_CASES int T; cin >> T; while( T-- ) solve(); #endif #ifndef MULTIPLE_CASES solve(); #endif return 0; }