# https://codeforces.com/contest/1328/problem/B

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();
}
}
``````
5 Likes
``````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.

1 Like

Glad I could help… 