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. :slight_smile:

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

@everule1 @paradox64ce , THANKS!!!

1 Like

Glad I could helpā€¦ :smiley:

1 Like