PROBLEM LINK:
Author: arnie8991
Tester: sandeep1103
Editorialist: arnie8991
DIFFICULTY:
MEDIUM
PREREQUISITES:
Problem
Indiana Jones has finally found Atlantis and he also discovered some manuscripts that can decipher Atlantean language. Strangely Atlantean language alphabets are the same as English language alphabets. The Atlantean manuscript contains N unique words. (numbered from 1).
Indiana has also discovered a device that displays a single alphabet per second for a total of Q seconds. At each second, Indiana tries to figure out if the string formed by some of the consecutive alphabets shown by the device until then, spell any of the word present in the list. In case he finds a word, he prints F(String)
where,
F(String) is 0, if the position(string) in manuscript is odd, and it is 1, if the position(string) in manuscript is even.
at each second Indiana can find multiple words from the list in which case, shorter words get their F(string) calculated first.
Note: a word consisting of q(i.j) can be taken only once. If the same word is found in another position, then it can be added to output again.
EXPLANATION:
The brute force approach to solve this problem is to simulate the procedure of the way that Indiana tries to find the words from the sequence of letters coming in per seconds. SO for example, if Indiana gets letter āaā at qth second, he will consider all the letters in the last 100 seconds that he has received and if he finds, any word, he would add their position%2 in the output string. We can use a HashMap to store the words and the indexes. This solution although quite fast is not efficient enough to pass the given constraints. Thus this would give use TLE.
In the intended solution, we need to search the word faster and since we get the letters one by one, we can use a Trie data structure to efficiently determine if a word is valid or not and thus we can build a trie with the inverse of the words and as we get the letters one by one, we can search in the trie if the prefix is valid or not, until we get a word.
Time Complexity: O((N * 100 + Q * 100))
SOLUTIONS:
Setter's Solution
// All imports here
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
// Template code starts here //
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Debugger debug = new Debugger(out);
Objectify objectify = new Objectify(debug);
Task solver = new Task();
int test = 1;
while(test-->0){
solver.solve(1, in, out, debug, objectify);
}
out.close();
}
}
class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
public float nextFloat() {
return Float.parseFloat(next());
}
}
class Debugger{
PrintWriter out;
Debugger(PrintWriter out){
this.out = out;
}
public <T> void printList(List<T> arrayList){
for( Object ob: arrayList){
out.print(ob+" ");
}
out.println();
}
public <T> void printSet(Set<T> set){
for(Object ob: set){
out.print(ob+" ");
}
out.println();
}
public <T> void printMap(Map<?,?> map){
for(Object ob: map.keySet()){
System.out.println(ob+" : "+map.get(ob));
}
}
}
class Objectify{
Debugger debug;
Objectify(Debugger ob){ debug = ob; }
public void printArr(int[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
public void printArr(double[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
public void printArr(long[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
public void printArr(char[] arr){ debug.printList( String.valueOf(arr).chars().mapToObj(c -> (char) c).collect(Collectors.toList())); }
public void printArr(String[] arr){ debug.printList(Arrays.asList(arr)); }
public void printMatrix(int[][] arr){ for(int a[]:arr) printArr(a); }
public void printMatrix(double[][] arr){ for(double a[]:arr) printArr(a); }
public void printMatrix(long[][] arr){ for(long a[]:arr) printArr(a); }
public void printMatrix(char[][] arr){ for(char a[]:arr) printArr(a); }
public void printMatrix(String[][] arr){ for(String a[]:arr) printArr(a); }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Template code ends here
class Task {
final long MOD = (int)Math.pow(10,9)+7;
public void solve(int testNumber, InputReader sc, PrintWriter out, Debugger debug, Objectify objectify) {
// write your code here
int n = sc.nextInt();
String[] list = new String[n];
for(int i = 0; i < n; i++){
list[i] = sc.next();
}
TrieNode root = new TrieNode();
createTrie(root, list);
// out.println("Root num is: "+root.num);
int q = sc.nextInt();
StringBuffer resString = new StringBuffer("");
List<Character> list2 = new ArrayList<>();
for(int i = 0; i < q; i++){
String s = sc.next();
char c = s.charAt(0);
list2.add(c);
TrieNode temp = root;
int k = list2.size() - 1;
int cnt = 0;
//searching the trie
while(k >= 0 && cnt < 100){
int c2 = list2.get(k) - 'a';
if (temp.ch[c2] == null){
break;
}
else{
temp = temp.ch[c2];
}
if (temp.num != -1){
resString.append(temp.num);
}
k--;
cnt++;
}
}
out.println(resString);
}
public void createTrie(TrieNode root, String[] list){
int k = 1;
for(String word: list){
TrieNode temp = root;
for(int i = word.length()-1; i >= 0; i--){
int pos = word.charAt(i) - 'a';
if (temp.ch[pos] == null){
temp.ch[pos] = new TrieNode();
}
temp = temp.ch[pos];
}
temp.num = 1 - k;
k = 1 - k;
}
}
class TrieNode{
int num = -1;
TrieNode ch[] = new TrieNode[26];
}
}
Tester Solution
#include <bits/stdc++.h>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << ā\nā
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;
class Trie{
public:
Trie* next[26] = {};
int isEnd = -1;
Trie(){
}
void insert(string& word, int p){
Trie* node = this;
for(int i = word.size() - 1; i >= 0; --i){
char ch = word[i];
if(!node->next[ch - 'a'])
node->next[ch -'a'] = new Trie();
node = node->next[ch - 'a'];
}
node->isEnd = p;
}
void search(string& word) {
Trie* node = this;
int n = word.size();
for(int i = n - 1; i >= 0 && n - i <= 100 ; --i){
char ch = word[i];
if(!node->next[ch-'a'])
return;
node = node->next[ch-'a'];
if(node->isEnd != -1)
cout << node->isEnd;
}
}
};
void solve(){
int i, j, n, q;
cin >> n;
string st;
Trie* tt = new Trie();
for(i = 1 ; i <= n; ++i){
cin >> st;
tt->insert(st, i % 2 == 0);
}
cin >> q;
string tmp = "";
while(q--){
char ch;
cin >> ch;
tmp += ch;
tt->search(tmp);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t = 1;
//cin >> t;
while(t--)
solve();
}