×

FRGTNLNG - Editorial

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

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++){

//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])
}
}

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.util.*;

public class Main {
static String[] data;

public static void main(String[] args) throws IOException {

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

//build array

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

}

//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:

This question is marked "community wiki".

3.0k93161187
accept rate: 12%

18.4k347492528

 1 for those who like array of pointers : https://www.codechef.com/viewsolution/8212713 answered 21 Sep '15, 14:32 932●1●8 accept rate: 8%
 0 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 { cin>>str[i]; } for(i=0;i { cin>>m; for(j=0;j { cin>>ans[j]; } for(j=0;j { for(b=0;b { if(str[b]==ans[j]) { arr[b]=1; } } } } for(i=0;i { if(arr[i]==1)cout<<"YES "; else cout<<"NO "; } cout< } return 0; } answered 21 Sep '15, 11:23 1.8k●5●14●22 accept rate: 6%
 0 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 answered 21 Sep '15, 17:55 279●2●3●19 accept rate: 10%
 0 // USING map #include using namespace std; void ques() {  map M; int n,k,l,i,j; string s[105],str[105]; cin>>n>>k; for(i=0;i>s[i]; for(i=0;i>l; for(j=0;j>str[j]; M[str[j]]++; } } for(i=0;i>t; while(t--) { ques(); cout<
 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()  answered 26 May '16, 02:35 1●1 accept rate: 0%
 0 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=0) { flag=true; break; } } if(flag) System.out.print("YES"+" "); else System.out.print("NO"+" "); } System.out.println(); t--; } }  } answered 17 Sep '17, 12:20 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,777
×1,302
×302
×62
×52
×9

question asked: 19 Sep '15, 21:52

question was seen: 5,154 times

last updated: 17 Sep '17, 12:20