STEM - Editorial

cook63
easy
editorial
hashmaps
stem
strings

#1

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra

DIFFICULTY:

Easy

PREREQUISITES:

Strings, In-built data structures, Hashmaps

PROBLEM:

Given N words, find the longest such word which is common to all of them.

EXPLANATION:

The first things to note are that the length of all the words is \leq 20 and there can be a maximum of 10 words. Let the longest word in the given set of words be of length L. Thus, the total number of distinct substrings we can get from this word is \mathcal{O}(L^2). Accordingly, the total number of distinct substrings that we can get from the set of words is \mathcal{O}(NL^2).

Once, we have a list of all the distinct substrings, we just need, for each word, the number of words which it appears in. If it appears in all the N words, then it can be a potential candidate for our answer.

How do we implement this? We can use an in-built implementation of hashmap that is available in the language you are using. The hashmap will be organised as map< key,\, list> . The keys here are the distinct substrings from the given set of strings. For each key, we store a list of indices of words which it appears in. We can build this structure by taking one word at a time (say the i^{th} word) examining each its substrings, and putting inserting i in the list associated with the substrings in our map. The word can contain a same substring twice. For example, anan contains an twice. Thus, we have to make sure that we dont insert i twice into the list of a substring which appears twice in it.

Here is the pseudocode:

func get_stem(words [])
{
        for (i = 1 to N in words)
        {
                for (all substrings `subs' of words*)
                {
                        if(map[subs].insert doesn't contain i)
                                map[subs].insert(i);
                }
        }

        for(all keys `k' in the map)
                if(k = longest and lexicographically smallest word with associated list of size = N)
                        return k;
}

COMPLEXITY:

\mathcal{O}(NL^3\log (NL^2)) per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist


#2

Why am I getting WA …my solution is https://www.codechef.com/viewsolution/8583271
please help me.
thanks.


#3

Can someone please help me identify the cases for which my code fails Link


#4

skysarthak fails for the test case

1
3
ab ba b

raj_ankit744 needs a step of the form

if (f[0] == 0 || strcmp(ch,f)<0)
strcpy(f,ch);


#5

Any idea why this https://www.codechef.com/viewsolution/8579208, is giving WA?

Any testcase will be helpful. Have tried out multiple testcases but haven’t found any failure pattern yet.
Thanks


#6

My approach:

  • Pick a reference string. Ideally the shortest but assuming malevolent test cases that’s not too important.
  • Test the single characters for appearance in the other strings.
  • repeat over increasing string lengths until finding no longer strings:
    • where two consecutive positions succeeded in the previous round, test in the other strings for appearance of the one-longer string that they covered together. (e.g. having found asdf and sdfg, test for asdfg)
  • Collect the set of longest strings and sort for the answer.

my submission


#7

I am getting “Access Denied” errors when trying to view solutions. Please make the solutions public as soon as possible. Thanks!