SCMNDS - Editorial

editorial
1

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

Author: jenil1999

Tester: karthikeya619

Editorialist: jenil1999

DIFFICULTY:

EASY

PREREQUISITES:

Greedy,Graph Theory,GCD

PROBLEM:

Apart from the story, Problem can be summarized as follows:

You have given a string S of length N. You have to make longest possible K-strong string by choosing any character at most once from S in any order. Any M-length string is K- strong if a character at index i is equal to character at (i+k)%M for 0 \le i \lt M.

QUICK EXPLANATION:

Bruteforce Solution would work for this problem. Iterate length L over [1,n] and check whether assignment exists or not for each length L. To check that, you need to make a graph of L nodes where any node i is connected to (i+K)%L (0 \le i \lt L). Find all connected components of the graph. Assignment is possible only if every node of a connected component have same character. The last part can be verified by maintaining count of all unique characters and assign characters in any order as length of the all connected components will be the same. The answer will be maximum L for which assignment is possible.

EXPLANATION:

it is obvious that answer is in range of [1,n] so bruteforce solution can be iterating L over 1 to n and check if it possible to make string for every L .

We precalculate count of the unique characters of string S given in input.

How to check that assignment exist for K-strong string of length L ?

There are two parts. Let’s go through each one by one.

Part 1: First part can be done in O(L). Assume L Length string as a graph where node i and node (i+k)%L is connected. Calculate connected components and length of connected components of this graph using DFS.

Part 2: After Part1, We will have the length of all connected components. If all nodes of a connected component are equal, then only assignment is possible. So we need to assign a character to every connected component. i.e., suppose there are 2 components of length 4 then there should exist two characters with at least count 4 or one with count at least 8 in string S then only assignment is possible. The last part can be done greedily.

Pseudo Code:

Inputs: n,k, String S
c=calculate_counts(S)
for i in range(1,n):
	lengths=calculate_connected_components(i,k)
	Assign characters to components in any order
	if assignment is possible then update the answer.
end for	
print ans

Bruteforce Solution takes O(N^2) . If you had submitted solution of this Complexity, it would have get you AC.

Can we do something better?

Claim:- For Any string of Length L and K, There will be gcd(L,K) connected components of L/gcd(L,K) length.

You can solve this problem in O(N*log(N)) using above claim.

Pseudo Code:

Inputs: n,k, String S
c=calculate_counts(S)
for L in range(1,n):
	g=gcd(L,k)
	cnt=count number of characters we can assign to component of length L/g
	if cnt>=g
		assignment exists
		update answer
     
end for	
print ans

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
const int mxn=100001;
 
int gcd(int a,int b)
{
    if(a==0)
    return b;
    else
    return gcd(b%a,a);
}
 
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int a[26];
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        a[s[i]-'a']++;
        int ans=0;
        for(int L=n;L>0;L--)
        {
        
            int g=gcd(L,k);
            int count=L/g;
            int pos=1,c=0;
            for(int i=0;i<26;i++)
            {
                c+=a[i]/count;
            }
            
            if(c>=g)
            {
               cout<<L<<endl;
               break;
            }
        }
    }
    }
Tester's Solution 
from collections import  Counter
import bisect
for _ in range(int(input())):
    n,k =  [int(j)  for j in input().split()]
    s = input()
    c =  Counter(s)
    l = sorted([c[i]  for i in c])[::-1]
    d =  []
    for i in range(1,k+1):
	    if k%i==0:
		    d.append(i)
	ans =  0
	for i in d:
		for j in range(i,n+1,i):
			c=0
			for k in l:
				if k>=(j//i):
					c += k//(j//i)
				else:
					break
			if c>=i:
				ans = max(j,ans)
			else:
				break
    print(ans)

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

1 Like