PROBLEM LINK:
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}).