You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 19 Sep '15, 21:52

darkshadows's gravatar image

5★darkshadows ♦
3.0k91161186
accept rate: 12%

edited 09 Feb '16, 17:22

admin's gravatar image

0★admin ♦♦
15.9k347484508


for those who like array of pointers :

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

link

answered 21 Sep '15, 14:32

xariniov9's gravatar image

6★xariniov9
93218
accept rate: 8%

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++)<br> {
cin>>str[i];
}
for(i=0;i<k;i++)<br> {
cin>>m;
for(j=0;j<m;j++)<br> {
cin>>ans[j];
}
for(j=0;j<m;j++)<br> {
for(b=0;b<n;b++)<br> {
if(str[b]==ans[j])
{
arr[b]=1;
}
}
}
}
for(i=0;i<n;i++)<br> {
if(arr[i]==1)cout<<"YES ";
else cout<<"NO ";
}
cout<<endl;<br> }
return 0;
}

link

answered 21 Sep '15, 11:23

rajat_dtc's gravatar image

2★rajat_dtc
1.8k51422
accept rate: 6%

edited 21 Sep '15, 11:35

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

link

answered 21 Sep '15, 17:55

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2781316
accept rate: 10%

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

}

link

answered 22 Sep '15, 05:56

vjmanit's gravatar image

4★vjmanit
2135
accept rate: 0%

edited 22 Sep '15, 06:02

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()
link

answered 26 May '16, 02:35

gaurav123_'s gravatar image

0★gaurav123_
11
accept rate: 0%

edited 26 May '16, 02:38

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--;
    }

}

}

link

answered 17 Sep, 12:20

amitbansal13's gravatar image

0★amitbansal13
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,590
×1,049
×285
×62
×52
×9

question asked: 19 Sep '15, 21:52

question was seen: 4,377 times

last updated: 17 Sep, 12:20