Any approach to solve this question

Letās look at the pattern

```
aaabb
aabab
aabba
abaab
ababa
abbaa
baaab
baaba
babaa
bbaaa
```

Now notice that

There is one case where the first b is at index 4

There are two cases where the first b is at index 3

There are 3 cases where the first b is at index 2 and so on.

for k=1 itās obvious.

for k=2, We can remove the case where first b is index 4 by subtracting 1 from k.

Now the second b is at index n-k.

for k=3, we can remove the case where first b is at index 4 by subtracting 1 from k.

Now the second b is index n-k.

If you notice we can subtract 1 then 2 and so on, as long k remains positive. If the largest number we subtracted was i, Then the first b is at index n-i-1, and the second is at index n-k.

```
//https://codeforces.com/contest/1328/problem/B
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
ll solve(){
int n;
ll k;
cin>>n>>k;
char s[n];
for(int i=0;i<n;i++){
s[i]='a';
}
int pos1=n-1;
for(int i=1;i<n;i++){
if(k>i){
k-=i;
}
else{
pos1=n-i-1;
break;
}
}
int pos2=n-k;
s[pos1]='b';
s[pos2]='b';
for(int i=0;i<n;i++){
cout<<s[i];
}
cout<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
solve();
}
}
```

```
Looking at pattern:
aaabb //1st 'b' takes 1-1=0 steps
aabab //1st 'b' takes 2-1=1 step and 2nd 'b' has taken 0 steps
aabba //1st 'b' takes 2-1=1 step and 2nd 'b' has taken 1 step
abaab //1st 'b' takes 3-1=2 steps and 2nd 'b' has taken 0 step
ababa //1st 'b' takes 3-1=2 steps and 2nd 'b' has taken 1 step
abbaa //1st 'b' takes 3-1=2 steps and 2nd 'b' has taken 2 steps
baaab
baaba
babaa
bbaaa
```

Notice how the series progresses 1 0s ,2 1s,3 2s,4 3s and so on.

Using this we can estimate the āsegmentā in which ākā will fall.

By segment i mean will it fall in 1 0s or 2 1s or 3 2s and so onā¦

For example if n=5 and k=8, k falls in the segment of 4 3s i.e. the group of strings where 1st ābā has taken 4-1=3 steps (to left).

So how do we find this segment ?

For this we need to find the minimum m which satisfies the following equation:

`2*k<m(m+1)`

because the series is progressing as sum of 1st m natural numbers.

Now we can estimate m to be approx floor(sqrt(2k))

`m= floor(sqrt(2k))`

if still m(m+ 1)<2k

{

increment m.

}

now let i1 and i2 be the indices of bs in the final string.

i1=n-m-1.

and i2= n-k+ m*(m-1)/2.

Thats it.

We can can get the indices of both bs in constant time.

Hereās my AC solution:

```
#include <bits/stdc++.h>
#include<cmath>
using namespace std;
#define ll long long
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
//k--;
ll k1=sqrt(2*k);
if(k1*(k1+1)<2*k)
k1++;
ll i1=n-k1-1;
ll k2=k1*(k1-1)/2;
ll i2=n-k+k2;
//cout<<"deb:"<<i1<<" "<<i2;
//cout<<"deb:"<<k1<<" "<<k2;
for(ll i=0;i<n;i++)
{
if(i==i1 or i==i2)
cout<<"b";
else
cout<<"a";
}
cout<<"\n";
}
return 0;
}
```

PS:By steps I mean steps to left of course.

Glad I could helpā¦