Split#12368

Split (Editorial)

Problem Author:	Andriy Kholod (Connect)
Prepared by:	Andriy Kholod (Connect)
Analysis:	Andriy Kholod (Connect)

Idea

Let the number be given as a string $s$ .

Since the length of the number can reach $2 \cdot 1 0^{5}$ 2 \cdot 10^5, working with standard integer types will not work. Therefore, all arithmetic in the solution is done over strings.

Key Observation

In fact, it is sufficient to check only two cuts:

after the first digit;
before the last digit.

That is, the candidates are:

$s_{0} + value (s [1.. n - 1])$ s_0 + \text{value}(s[1..n-1]) and $value (s [0.. n - 2]) + s_{n - 1}$ \text{value}(s[0..n-2]) + s_{n-1}

In other words:

either the left part consists only of the first digit;
or the right part consists only of the last digit.

Why is this sufficient? If we cut somewhere in the middle, both parts lose some of the "weight" of the higher digits. In decimal notation, higher digits are significantly more important than lower ones, so the optimum is achieved when one of the parts has a length of 1, and the other contains almost the entire number.

Thus, the problem reduces to comparing only two options. The sum and comparison of two large numbers can be implemented using long arithmetic, which is the solution.

Asymptotics

Each of the two candidates is constructed in $O (n)$ , where $n$ is the length of the string. The comparison also works in $O (n)$ .

Thus, we have $O (n)$ .

#include <bits/stdc++.h>
#include <random>
// fast_pragmas

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")

// fast_pragmas ended

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

#define ull unsigned long long
#define ll long long
#define ld long double
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define ln log
#define lg log10
#define log log2
#define here cout<<"HERE"<<endl

const ll clasik = 5e5 + 7;
const ll mln = 1e6 + 7;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const ll block_size = 450;
const ll INF = 1e17;

ll df[clasik];

string normalize(string s) {
    int i = 0;
    while (i + 1 < (int)s.size() && s[i] == '0') i++;
    return s.substr(i);
}

string addDigit(string num, int d) {
    int carry = d;
    for (int i = (int)num.size() - 1; i >= 0 && carry > 0; i--) {
        int cur = (num[i] - '0') + carry;
        num[i] = char('0' + (cur % 10));
        carry = cur / 10;
    }
    if (carry > 0) num.insert(num.begin(), char('0' + carry));
    return normalize(num);
}

bool greaterNumber(string a, string b) {
    if ((int)a.size() != (int)b.size()) return (int)a.size() > (int)b.size();
    return a > b;
}

void solve() {
    string s;
    cin >> s;

    int n = (int)s.size();

    if (n == 2) {
        int ans = (s[0] - '0') + (s[1] - '0');
        cout << ans << endl;
        return;
    }

    string option1 = addDigit(s.substr(1), s[0] - '0');
    string option2 = addDigit(s.substr(0, n - 1), s[n - 1] - '0');

    if (greaterNumber(option1, option2)) cout << option1 << endl;
    else cout << option2 << endl;
}

signed main() {

    //freopen("deciding_points_input.txt" , "r" , stdin);
    //freopen("outputA.txt" , "w" , stdout);

    speed;
    int test;
    test = 1;
    //precalc();
    //cin >> test;
    for (int tt = 1; tt <= test; tt++) {
        //cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

C++