sanchaythegreat's blog

By sanchaythegreat, history, 2 hours ago, In English

Problem Here's my greedy solution:

void solve(int tt) {

    string db;cin >> db;

    int m;cin >> m;
    string l;cin >> l;
    string r;cin >> r;

    int indMaxRight = -1;
    int left = l[0]-'0';
    int right = r[0] -'0';
    fr(j,left,right+1) {
        int dig = j;

        fr(k,0,db.length()) {
            if(db[k]-'0' == dig) {
                indMaxRight = max(indMaxRight,k);
                break;
            }
        }
    }

    if(indMaxRight==-1) {
        cout << "YES" << endl;
        return;
    }

    fr(i,1,m) {
        int left = l[i]-'0';
        int right = r[i] -'0';
        int ind = -1;
        fr(j,left,right+1) {
            int dig = j;
            bool digExist = false;
            fr(k,indMaxRight+1,db.length()) {
                if(db[k]-'0'==dig) {
                    digExist = true;
                    ind = max(k,ind);
                    break;
                }
            }

            if(!digExist) {
                cout << "YES" << endl;
                return;
            }
        }

        indMaxRight = max(ind,indMaxRight);
    }


    cout << "NO" << endl;

}

For the life of me I can't figure out why it's outputting NO instead of YES in some obscure test case that I can't see. Can someone please help?

  • Vote: I like it
  • 0
  • Vote: I do not like it