FRGTNLNG - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kanstantsin Sokal
Tester: Jingbo Shang
Editorialist: Lalit Kundu

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Programming

PROBLEM:

You have acquired a dictionary of N words of a forgotten language. Meanwhile, you also know K phrases used in modern languages. For each of the words of the forgotten language, your task is to determine whether the word is still in use in any of these K modern phrases or not. Each phrase has L words given in input.

EXPLANATION:

================
First, you just need to store all the N words of the forgotten language and all the phrases. For each each word, then, you can traverse over all phrases and check if its present in any one of them. You can also build a single array of all the words from all phrases and then check for each forgotten language word if its present in the array or not.

If you want it to more efficient you can store all phrase words in a set where insertion is O(\text{log}(\text{size})) and checking if a string is present or not is also O(\text{log}(\text{size})).

For implementation, you need to know basic programming concepts and syntax of a language of your choice. You should know about arrays, conditionals, loops, input/output to solve this problem.

First, we include implementations in three popular programming contest languages.

C++ code

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
	// we use 'cas' because 'case' is a keyword
	int N, K, L;

	// allocate more than necessary
	// note that phrases[i] is a vector of strings.
	vector < string > phrase[55];

	//array of forgotten words
	string forgotten[109];

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
	    cin >> forgotten[i];
	}

	for (int i = 0; i < K; i++) {
	    cin >> L;
	    for (int j = 0; j < L; j++) {
	        string S;
	        cin >> S;
	        phrase[i].push_back(S);
	    }
	}

	for (int i = 0; i < N; i++){
	    string answer = "NO";

	    //traverse over all phrases
	    for(int j = 0; j < K; j++){

	        //traverse over phrase[j]
	        for(int k = 0; k < phrase[j].size(); k++){
	            if(phrase[j][k] == forgotten[i])
	                answer = "YES";
	        }
	    }

	    cout << answer << (i==N-1 ? "\n" : " ");
	}
    }
}

Java Code

Note that java.util.Scanner provides an easy way to tokenize and read the input. However, for problems with huge inputs and strict time limits, it is not recommended because it is slow. Instead, one should use BufferedReader, like so:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static String[] data;

    public static void main(String[] args) throws IOException {
	BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	int testCases = Integer.parseInt(bufferedReader.readLine());

	while (testCases-- > 0) {
	    //get N and K
	    int forgottenLanguageWordsCount, modernLanguagePhrasesCount;
	    data = bufferedReader.readLine().split(" ");
	    forgottenLanguageWordsCount = Integer.parseInt(data[0]);
	    modernLanguagePhrasesCount = Integer.parseInt(data[1]);

	    //build array
	    String[] forgottenWords = bufferedReader.readLine().split(" ");

	    //build a single list with all words from all phrases
	    List<String> modernWordsList = new ArrayList<>();
	    for (int i = 0; i < modernLanguagePhrasesCount; i++) {
	        data = bufferedReader.readLine().split(" ");
	        int totalWordsInPhrase = Integer.parseInt(data[0]);

	        //add to list
	        modernWordsList.addAll(Arrays.asList(data).subList(1, totalWordsInPhrase + 1));
	    }

	    //use .contains method to check if present in list or not
	    for (int i = 0; i < forgottenLanguageWordsCount; i++) {
	        if (modernWordsList.contains(forgottenWords[i])) {
	            System.out.print("YES");
	        } else {
	            System.out.print("NO");
	        }
	        System.out.print((i + 1 == forgottenLanguageWordsCount) ? "\n" : " ");
	    }
	}
    }
}

Python code

T = input()
for cas in xrange(1,T+1):
    N, K = map(int, raw_input().strip().split())

    forgotten = raw_input().split()

    allWordsfromPhrases = []
    for i in xrange(K):
	allWordsfromPhrases += raw_input().split()

    ans = ""
    for i in xrange(N):
	if forgotten[i] in allWordsfromPhrases: ans += "YES "
	else: ans += "NO "

    print ans

Python is ridiculously easy in this problem. Note that the python code has a bit of different flavor, specifically the for…else statement.

Suggestions

I will directly quote kevinsogo from one of his editorials.

Now that you’ve learned that many, many things can go wrong even for such a simple problem, how does one go about preventing it?

Well, for one, it is usually hard to write a completely correct code in the first try. Therefore one should always test the code before submitting it! For example, use the sample data. The sample data is provided for two reasons:

  • To ensure that you are following the input/output format correctly, and
  • To ensure that you at least get some small inputs correctly.

However, if you pass the sample input, it doesn’t mean you’ll pass the actual input! So it still lies upon the contestant to ensure that their program will pass whatever kind of test case the judge can give to it. So if the judge returns WA, try making some inputs yourself, until you find one where your program fails. Then start debugging from there. In other problems, it is sometimes useful to make random input generators.

Also, there is the occasional problem that tests how well you follow instructions and handle many tricky edge cases. In such problems, speed/minute optimizations are secondary to correctness, so things like readability/modularity more important, at the expense of efficiency. See the sample programs above as examples, which were written partly with readability in mind.

COMPLEXITY

================

If we implement a brute force solution, there are worst case \text{MAXL} * \text{MAXK} words and for each forgotten word, we do a linear search. So total complexity is \text{MAXL} * \text{MAXK} * \text{MAXN}.
Using set, complexity can be reduced to \text{MAXL} * \text{MAXK} + \text{MAXN} * \text{log}(\text{MAXL}*\text{MAXK}).

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

2 Likes

int main()

{

cin>>t;

while(t--)

{

	int b=0;

	for(i=0;i<155;i++)

	{

		arr[i]=0;

	}

	cin>>n>>k;

	for(i=0;i<n;i++)

	{

		cin>>str[i];

	}

	for(i=0;i<k;i++)

	{

		cin>>m;

		for(j=0;j<m;j++)

		{

			cin>>ans[j];

		}

		for(j=0;j<m;j++)

		{

			for(b=0;b<n;b++)

			{

				if(str[b]==ans[j])

				{

					arr[b]=1;

				}

			}

		}

	}

	for(i=0;i<n;i++)

	{

		if(arr[i]==1)cout<<"YES ";

		else cout<<"NO ";

	}

	cout<<endl;

}

return 0;

}

for those who like array of pointers :

https://www.codechef.com/viewsolution/8212713

1 Like

Very simple with maps. Just keep incrementing the input string in the map and check in the end if the frequency of the original word is >1 (that means it has occured more than once, which is only possible that first time it had occured in the forgotten language and rest of the times in the modern phrases).
My solution :
https://www.codechef.com/viewsolution/8211902

// USING map

#include <bits/stdc++.h>

using namespace std;

void ques()
{

  map <string,int> M;

  int n,k,l,i,j;

  string s[105],str[105];

  cin>>n>>k;

  for(i=0;i<n;i++)

    cin>>s[i];
  for(i=0;i<k;i++)
  {
  cin>>l;

  for(j=0;j<l;j++)
  {
	cin>>str[j];

	M[str[j]]++;
  }

 }
 for(i=0;i<n;i++)
 {
if(M.find(s[i])!=M.end())
  cout<<"YES ";

else
  cout<<"NO ";
 
  }

}

int main()
{
// your code goes here
int t;

cin>>t;

while(t--)
{
 ques();
 cout<<endl;

}

return 0;

}

I have the python code here under. It runs well for the sample input but says ‘Wrong answer’ when runs.

t = int(input())
answ = [None] * t #List of answer to each test case

for i in range(0,t,1):
    first = input()
    first = first.split(" ")
    n = int(first[0])
    k = int(first[1])
    org = input() #inputting the original language string
    org = org.split(" ")
    answer = [None] * n #Has answer to each test case in form of list
    for j in range(0,k,1):
        inp = input()
        for k in range(0,n,1):
            if org[k] in inp:
                answer[k] = "YES"
            else:
                answer[k] = "NO"
    answ[i] = answer
#Printing the output
for i in range(0,t,1):
    for j in range(0,len(answ[i]),1):
        if j!=len(answ[i])-1:
            print(answ[i][j]+" ",end='')
        else:
            print(answ[i][j], end='')
    print()

Why the following code shows runtime error please help.

import java.util.Scanner;

public class ForgottenLanguage {

public static void main(String[] args) {
	
	Scanner in =new Scanner(System.in);
	int t=in.nextInt();
	while(t>0)
	{
		int n=in.nextInt();
		int k=in.nextInt();
		in.nextLine();
		String[] dict=new String[n];
		for(int i=0;i<n;i++)
		{
		dict[i]=in.nextLine();
		}
		String[] lines=new String[k];
		for(int i=0;i<k;i++)
		{
			int j=in.nextInt();
			in.nextLine();
			lines[i]=in.nextLine();
		}
		boolean flag;
		for(int i=0;i<n;i++)
		{
			flag=false;
			for(int j=0;j<k;j++)
			{
				if(lines[j].indexOf(dict[i])>=0)
				{
					flag=true;
					break;
				}
				
			}
			if(flag)
				System.out.print("YES"+" ");
			else
				System.out.print("NO"+" ");
			
		}
		System.out.println();
		t--;
	}

}

}