PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author:Saurabh Singh
Tester: Daanish Mahajan
Editorialist: Saurabh Singh
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
Each letter from ‘a’ to ‘z’ is given a score.‘a’ - 2^0,b - 2^1 and so on.
You have to construct a string of n length consisting only of lowercase alphabets such that the sum of score of the characters it contains is k.
QUICK EXPLANATION:
It can be shown that a solution exists only when bitcount(k) \le n \le k .If this criteria is satisfied,we can construct a solution.One way can be to initially take alphabets corresponding to ON bits in k.This string will have length bitcount(k).Now,keep dividing each alphabet of this string into two alphabets that come just before it,till the length of the string becomes n.
EXPLANATION:
Observe the constraints on k, k \le 5*{10}^7 \lt 2^{26} . So,in the binary representation of k,the most significant bit is the 25th bit.
For a given k,let’s try to find the minimum and maximum length of the string that can be constructed having total score k,i.e. the minimum and maximum value of n for which an answer will exist:-
Minimum length :- The min. length of string possible is equal to the number of ON bits in the binary representation of k.For each ON bit in k,select a corresponding alphabet(i.e. ‘a’ for 0th bit,‘b’ for the 1st bit and so on) and add it to your string.This string is the minimum length string.We can easily see that we cannot have a string shorter than this because each new character in the string can increase the number of ON bits in the total score by at most one.So,a string of length n(n \le 26) can have a total score having at most n ON bits.
Maximum length :- It can be easily seen that the maximum length of string possible is equal to k ,because a string of length more than k will always have a score more than k.
Also,for a given k,answer will exist for all n in the range [bitcount(k),k],since once we have the string of minimum length,we can have keep dividing any alphabet in this string into two alphabets that come just before it (for e.g,1 ‘c’ can be replaced by 2 'b’s),till we have a string of desired length.
One way to do this can be to make an array of length 26.Initially,fill 1 in those indexes which have a corresponding ON bit in k and 0 in other indexes.This array corresponds to which characters and how many of them we will take in the final string.Right now,the length of string is bitcount(k).
Now,iterate from the right,and for any index ,for the value you subtract from that position ,add twice its value to the index just smaller than it.Continue this till the sum of elements of array (i.e the length of string) becomes n.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,k;
cin>>n>>k;
int cnt[26];
int curl=0;
for(int i=0;i<26;i++)
{
if(k&1<<i)
{
cnt[i]=1;
curl++;
}
else
cnt[i]=0;
}
if(curl>n||k<n)
{
cout<<-1;
return;
}
for(int i=25;i>0;i--)
{
if(n-curl<=cnt[i])
{
cnt[i]-=n-curl;
cnt[i-1]+=2*(n-curl);
break;
}
curl+=cnt[i];
cnt[i-1]+=2*cnt[i];
cnt[i]=0;
}
for(int i=0;i<26;i++)
{
while(cnt[i]--)
cout<<(char)('a'+i);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
cout<<"\n";
}
}
Tester's Solution
# include <bits/stdc++.h>
# define pb push_back
# define ll long long int
using namespace std;
FILE *fp;
ofstream outfile;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int maxt = 1e5;
const int maxn = 1e5;
const int maxk = 5e7;
ll val[26];
vector<char> ans;
int main()
{
int t;
cin >> t;
// int t = readIntLn(1, maxt);
val[0] = 1;
for(int i = 1; i < 26; i++)val[i] = 2 * val[i - 1];
while(t--){
ans.clear();
// int n = readIntSp(1, maxn), k = readIntLn(1, maxk);
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++){
for(int j = 25; j >= 0; j--){
if(k - val[j] >= n - i - 1){
ans.pb(char('a' + j));
k -= val[j];
break;
}
}
}
if(k > 0 || ans.size() < n){
cout << "-1";
}else{
for(char a : ans){
cout << a;
}
}
cout << endl;
}
// assert(getchar()==-1);
// assert(getc(fp)==-1);
}
