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ā¦ 