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

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