MATPAN - Editorial

editorial
, , , ,
1

Problem Link

Practice
Contest

Author: Alexandru Valeanu
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Looping Techniques

Problem

You are given a string consisting of letters and the cost of adding a specific character to it. You need to convert the string into a pangram, i.e. it contains all the lower case alphabets (a-z) in it. The cost of above operation is to be minimised.

Explanation

Subtask - 1

For this subtask, N = 1. This means the string contains only 1 lower case character. So, we would need to add all the remaining characters so that it becomes pangram. To minimise the cost, it is easy to see that we would add each character only once.

Subtask - 2

Similar to above solution, we would like to only add those characters which are missing in the substring so that it becomes a pangram. Also, each character should be added only once to minimise the cost.

Thus, we need to find efficiently which characters occur in the string and which do not. To do this, we just maintain an array, of size equal to the alphabet size (in this case 26), such that all of it’s value are initialised to 0. Now, we simply traverse the array from left to right and set the corresponding character to 1 in the array. Thus, at the end of the loop, we just need to find the location of 0 in the above array and add the corresponding cost of the character to the answer.

Time Complexity

O(n)

Space Complexity

O(n + ALPHABET), where ALPHABET = number of lowercase characters (here 26)

Solution Links

Setter’s solution
Tester’s solution
Editorialist solution

1 Like
2

import java.util.Scanner;

class pangram {
	public static void main(String[] args)throws Exception {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		while(T--!=0) {
			int[]arr=new int[26];
			int[]brr=new int[26];
			for (int i = 0; i < arr.length; i++) {
				arr[i]=sc.nextInt();
			}
			String str=sc.next();
			for(int j=0;j<str.length();j++) {
				char ch=str.charAt(j);
				brr[(int)ch-97]++;
			}
			int sum=0;
			for(int i=0;i<arr.length;i++) {
				if(brr[i]==0)
					sum=sum+arr[i];
			}
			System.out.println(sum);
			
			
		}
		
	}
 
}
3

Cant i initialize has[26]={0} like this instead of using for loop …
when i am using for loop its accepted but when doing like hash[26]={0},getting WA

My code :https://ideone.com/41po2B
plzz explain …

4

Yes, you can do that, but in your case you are assigning particular index (26) to 0, which could have also lead to runtime error as size of array you declared is also 26. I have modified the code, which can can see here. Btw, i would suggest you to use memset or fill in C++.

5

import java.util.Scanner;

class pangram {
public static void main(String[] args)throws Exception {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T–!=0) {
int[]arr=new int[26];
int[]brr=new int[26];
for (int i = 0; i < arr.length; i++) {
arr[i]=sc.nextInt();
}
String str=sc.next();
for(int j=0;j<str.length();j++) {
char ch=str.charAt(j);
brr[(int)ch-97]++;
}
int sum=0;
for(int i=0;i<arr.length;i++) {
if(brr[i]==0)
sum=sum+arr[i];
}
System.out.println(sum);

    }

}

}

6

int main()
{
int t;
cin>>t;
while(t–)
{int a[26];
string s;
for(int i=0;i<26;i++)
cin>>a[i];
cin>>s;

	int sum=0; 
	for(int j=0;j<26;j++)
	{int f=0;
		for(int k=0;k<s.size();k++)
		{
			if(s[k]==(97+j))
            {cout<<s[k]<<"+_";
             f=1;
		      }
            
              if(f==1)
               break;
            
        }
            if(f==0)
            
                sum=sum+a[j];
		
    }
      
		
			cout<<sum<<endl;
}

}

7

Using set operations in Python.

8

I’m getting a weird problem with this problem. The same program, when the strings,vectors are defined as global outside any function, I get wrong answer but when I put them inside the main() function I get correct answer.
Language:c++14
Just put outside main function and you get WA. HOW AND WHY?

vector<int> price(26);
		vector<int> flag(26, 0);
		string str;