CAB - Editorial

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);
}  
6 Likes

Can this problem be solved using DP?

This Problem (CAB) can be boiled down as : Find a subset of size k whose sum of elements is n.

I couldn’t implement it.Can anyone tell how can this be solved using DP?

its like coin exchange probm. varation have infinity of all denomnations at array and choose exact n of sum k.

1 more varation: use 2d matrix mat[n][26] create table. find a path in matrix of sum k and exact n elemnt

Yeah!
The link you gave is a different problem than what i am asking.

This is the problem - Find a subset of size k whose sum of elements is n.

Do you know how to solve this using DP?

Find a subset of size k whose sum of elements is n
this look like knapsack prob.
bag size k
capacity n

Yeah this is an Unbounded knapsack problem with a variation that subset should be of size ‘k’.

This problem was already available on gfg.
(Represent n as the sum of exactly k powers of two | Set 2 - GeeksforGeeks)

4 Likes

I made a small testing code, to check whether what your program outputs as the result of a large test case is correct. Posting it here as it may be helpful to some in debugging.

alpha = "abcdefghijklmnopqrstuvwxyz"
s = "uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuttttttttttttttttttttttttuuutrponmh"
the_sum = 0

for el in s:
    x = 1<<alpha.index(el)
    the_sum += x
    
print(len(s), the_sum)

The above string is an answer for the test case: 66 50000000

The underlying concept is same but there is limit to exponent of 2 i.e 26 which needs to handle some edge cases as well I don’t think someone would have been benefited much from any code available online as it was an easy problem and case handling was the main crux of the problem :slight_smile: