PROBLEM LINK:
Setter/Tester/Editorialist: Chandan Boruah
DIFFICULTY:
SIMPLE.
PREREQUISITES:
Brute Force, Mathematics or Graph.
PROBLEM:
Given a string whose value equals the sum of positions of each character in the string, in the English alphabet system (1 based). Also given a number N, find the maximum number of characters that can be changed to make the value of the string equal to N.
QUICK EXPLANATION:
Setters approach:
Take a string that is equal in value to the given number N. Change each character in the string, pushing the new string to a queue, and try each new string that was formed to compare to the string that was equal in value to N. Find how many characters are different.
NOTE: This approach of setter’s is not completely correct cause the string that was taken, might not be optimal. However, the test cases being non exhaustive, somehow worked. Ideally, it is better to take a base string consisting of only 'a’s and keep changing it finding all possible strings that are equal in value to N and then compare it to the given string.
EXPLANATION:
Create a string, consisting of only 'a’s and then keep changing each character pushing it to a queue or a stack, everytime a string is found that is equal in value to N, store it in a list. Then compare each of the strings in the list, to the given string and find which has the most characters different. Print that difference in value.
SOLUTIONS:
Setter's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=int.Parse(Console.ReadLine());
string s=Console.ReadLine();
int val=0;
int[]arr=new int[s.Length];
for(int i=0;i<s.Length;i++)
{
arr[i]=1;val++;
}
int N=n;
for(int i=0;i<N;i++)
{
if(val>=n)break;
arr[i%s.Length]++;
val++;
}
string now="";
for(int i=0;i<s.Length;i++)
{
now+=(char)('a'+(arr[i]-1));
}
List<string>done=new List<string>();
Queue<string>qq=new Queue<string>();
done.Add(now);
qq.Enqueue(now);
while(qq.Count>0)
{
string nn=qq.Dequeue();
char[]dd=nn.ToCharArray();
for(int i=0;i<nn.Length;i++)
{
if(dd[i]=='a')continue;
for(int j=0;j<nn.Length;j++)
{
if(dd[j]=='z')continue;
if(i==j)continue;
dd[i]=(char)('a'+(int)(dd[i]-'a')-1);
dd[j]=(char)('a'+(int)(dd[i]-'a')+1);
string pp=new string(dd);
if(!done.Contains(pp))
{
done.Add(pp);
qq.Enqueue(pp);
}
dd[i]=(char)('a'+(int)(dd[i]-'a')+1);
dd[j]=(char)('a'+(int)(dd[i]-'a')-1);
}
}
}
int max=0;
foreach(string tt in done)
{
int count=0;
int[]comp=new int[tt.Length];
for(int i=0;i<s.Length;i++)
{
for(int j=0;j<tt.Length;j++)
{
if(s[i]==tt[j] && comp[j]!=1)
{
comp[j]=1;count++;
}
}
}
max=Math.Max(max,s.Length-count);
}
Console.WriteLine(max);
}
}