Separate the Numbers

  • + 12 comments

    This challenge looks difficult (medium difficulty, as many pointed out) unless you know the right way to handle it, then it becomes almost trivial. I'm sharing this in hopes that you'll not waste hours of your time (like I did) on a 15-minutes problem.

    Instead of performing laborious operations on each input string s, you should extract from its beginning a number a of length l (1 ≤ l ≤ s.size()/2), and by concatenating (appending) its subsequent numbers you build a new string t from scratch. Once it's done, compare t to s: if there's a match, print the result and move on to the next string, otherwise keep comparing strings built from numbers of different l until you either find a solution or finish checking all possible cases for s.

    My C++ solution:

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        string s, t, a;
        cin.ignore(256, '\n');
        while(cin >> s){
            for(int l = 1; l <= s.size()/2 && s != t; l++){
                a = t = s.substr(0, l);
                for(int i = 1; t.size() < s.size(); i++)
                    t += to_string(stoll(a) + i);
            }
            cout << (s == t ? "YES " + a : "NO") << endl;
        }
        return 0;
    }