RE in B. K-th beautiful string - codeforces

help
1

I got a runtime error in this problem.
My code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        long long n, k, x, y;
        cin >> n >> k;
        string ans(n, 'a');
        x = (ceil(sqrt(1+8*k))-1)/2;
        ans[n-x-1] = 'b';
        y = k-((x*(x-1))/2);
        ans[n-y] = 'b';
        cout << ans << '\n';
    }
}

My approach:
Let’s say the first ‘b’ is at a position x from the last character.
I used the quadratic formula to find x.
\dfrac{x(x+1)}{2} = k if you see the pattern.
x^2 + x - 2k = 0
x_+ = \dfrac{-1 + \lceil \sqrt{1 + 8k} \rceil}{2}
I neglect the negative value and take the ceil of the square root because floor gives x-1.
So we can say that b_1 is at index n-x-1.
Let’s say that b_2 is at the y-th position from the last.
There are \dfrac{x(x-1)}{2} permutations (sum of first x-1 numbers) before b_1 is at x.
So y = k - \dfrac{x(x-1)}{2}.
And b_2 = n-y.
Error:

Diagnostics detected issues [cpp.clang++-diagnose]: C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\xstring:2970:20: runtime error: addition of unsigned offset to 0x108dfa00 overflowed to 0x108df9ff
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\xstring:2970:20 in

Can you please let me know what went wrong?

2

Here is the updated code

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        long long n, k, x, y;
        cin >> n >> k;
        string ans(n, 'a');
        x = (ceil(sqrt(1+8*k))-1)/2;
        assert(n-x-1 >= 0);    // =========== added new ===========
        ans[n-x-1] = 'b';
        y = k-((x*(x-1))/2);
        assert(n-y >= 0);    // ============ added new ============
        ans[n-y] = 'b';
        cout << ans << '\n';
    }
    
    return 0;
}

and here is the output on submitting the code on test-case 2

Checker Log
Exit code is 3

Diagnostics
Diagnostics detected issues [cpp.clang++-diagnose]: Assertion failed: n-y >= 0, file p71.cpp, line 23

Short summary: You are accessing -ve index of string resulting in runtime error.

1 Like