How to solve "Henry and Lost Ranges" of thrid ACM ICPC Preparatory Series?

general
1

**Can anyone share their approach who had solved the problem?
**

PROBLEM STATEMENT:

Henry is a curious little boy. He likes to play around with numbers.One day, he defined a
function ​f for natural numbers such that:

f(X)​ = largest prime factor of X , where X > 1

For example: f(2) = 2

f(3) = 3

f(75) = 5

Now, Henry selected two integers A​ and B​ (A ​≤ B​) and counted all numbers X​ between A​ and B (both inclusive) such that f(X) = K​. He found out that there are N​ such numbers.

After that Henry went for playing. When he returned home, he found out that he had forgotten
the upper limit of range i.e. the integer B​. However, he remembers all other numbers i.e. A​, K
and N​.

Henry wants to find out B​ as soon as possible. Can you help him finding it?
Note:

  1. If there are multiple possible values of B​, output the least​ value out of those.

  2. It is assured that the input will be in such a way that final value of B​ will be within the
    range of long long int​.

Input

First line of input contains T,​ the number of test cases.

The only line of each test case contains three integers A​, K​ and N​.

Output

For each test case, output a single line containing the integer B​.

Constraints

● 1 ​≤ T ≤ 5

● 2 ≤ A ≤ 10​

● 2 ≤ K ≤ 11​ and K​ is a prime​ number

● 0 ≤ N ≤ 152319

2

@srd091 i was getting runtime error in chefandsister while my code was running without error on my machine
my code###
#include
#include
#include<string.h>
using namespace std;
//long long int sum,t,a[100005],n,i,j,c;
long long int a[27],i,t,k,ans,n;
//char m1[100005],m2[100005],a[100005];
int main()
{
char str[27];
cin>>t;
while(t–)
{
cin>>str;
cin>>k;

i=0;
ans=0;
//memset(a,0,sizeof(a));
for(i=0;i<26;i++)
    a[i]=0;
while(str[i]!='\0')
{
    n=str[i]-'a';
    a[n]++;
    i++;
}
for(i=0;i<26;i++)
{   
    if(a[i]>=k)
    {    a[i]-=k; ans++;}
        
}
/*for(i=0;i<26;i++)
        cout<<a[i]<<" ";
    cout<<"\n";*/
//n=strlen(str);
sort(a,a+26);
//int flag=1;
while(a[25]!=0)
{
    //cout<<"hello";
    for(i=0;i<26;i++)
    {
        if(a[i]!=0)
            break;
    }
    int j=i;
    ans+=a[i];
    //cout<<j;
    int x=0;
    int temp=a[j];
    for(i=j;(i<26)&&(x<=k);i++)
    {   
        //if(a[i]!=0)
            a[i]=a[i]-temp;
            //cout<<a[i]<<
            x++;
       
    }

/* for(i=0;i<26;i++)
cout<<a[i]<<" “;
cout<<”\n";
*/
}
for(i=0;i<26;i++)
{
if(a[i]!=0)
ans++;
}
cout<<ans<<"\n";

}

return 0;
}

thanks in advance

3

@srd091 would you care to share the approach for chefandsister?

4

@srd091
Let’s say the input is aaaabbbb and K=5.
According to your code the answer is 4,but the correct answer will be 2.

5

what will be the correct output when input is aaaabbbbc and k=5 in chefsister?

6

For Henry, just generate all possible numbers whose Greatest Prime Factor is K using dfs and are less then (1 << 63)- 1, and store them in a array, then using binary search we can easily find the answer.
The total count of numbers whose prime factor is K would be quite low as for K = 11, it’d be around (200000), so it won’t result in TLE at all.

1 Like
7

Is anything wrong in thin code for CHEFSIS ?

#include
#include
using namespace std;
int main()
{
int e;
cin>>e;
for (int j = 0; j < e; ++j)
{
short int count[30];

	for (int i = 0; i < 30; ++i)
	{
		count[i]=0;
	}
	string s;
	cin>>s;
	for (int i = 0; i < s.length(); ++i)
	{
		int x = s[i];
		x=x-97;
		count[x]++;
	}
	int k;
	cin>>k;
	int cnt=0;
	short int r[30];
	int sum=0;
	for(int i=0; i<30;++i)
	{
		r[i]=count[i]%k;
		sum+=r[i];
	}
	for(int i=0; i<30;++i)
	{
		cnt+=(count[i]-r[i])/k;
	}
	while(sum>0)
	{	int t=0;
		int max=0;
		int mi=0;
		for(int i=0; i<30;++i)
		{
			if(r[i]>max)
				{max=r[i];
					mi=i;}
		}

		for(int i=0;i<26;i++)
		{
			if(t<k&&r[i]>0)
			{
				t++;
			}
		}
		if(t<=max)
		{
			r[mi]-=max;
			sum-=max;
		}
		else
		{
			t=0;
			for(int i=0;i<26;i++)
			{
				if(t<k&&r[i]>0)
				{
					t++;
					r[i]--;
					sum--;
				}
			}
		}
		cnt++;
	}
	cout<<cnt<<endl;
}

}

1 Like
8

@vardhi you have specified length of char array str as 27 but input can be upto 50 char long, that may be the reason the you are getting run time error.

9

@vardhi and in second while loop where you are filling values in array a you haven’t initialized i, as after for loop value of i would become 27.

10

@novice_612 I wasn’t able to solve that problem correctly.

11

@jainy6 Look carefully, that wasn’t my code.

12

according to the question, 3 as you can either take {abc,aaa,bbb} or {aaaa,bbbb,c}.

13

@bhavit_sharma Can you elaborate your approach, I didn’t get the point of using dfs to store all numbers.

14

The point is to quickly calculate all the numbers that have greatest prime factor = K, and then to quickly answer the queries. For example If I have all the numbers for K = 11, and the A = 1e9 and N = 9999, then using binary search, I can find the lower bound for A in those numbers, suppose the index of lowerBound for A in the list of numbers is idx, then the lowest B’s index would be idx + n - 1 in the array.

15

@bhavit_sharma how will you calculate the numbers quickly that have greatest prime factor = K?

16

-Could not submit it due to lack of time :frowning:

17

@patoliyam you have taken t as number of test cases and in while loop you have also declared t.

18

the lowest number who greatest prime factor is K is K itself. So run dfs from K. Now all the other numbers would be it’s multiple from (2K, 3K, …(K^2)), so now number run dfs from the following numbers. Use map to keep track of the visited ones. Just be careful to check the overflow cases.

1 Like
19

@srd091 I made it correct, Anything else?