# RE in B. K-th beautiful string - codeforces

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?

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