604 - The Boggle Game

[Dominik Michniewski]

Could anyone tell me: Does it exist some special cases for this problem?
I try to solve it in this way:
1. Generate all possible words (which have exactly 2 vowels - AEIOUY)
2. Sort this words and remove duplicates
3. Generate all possible words for second board (in the same way) and using bsearch try to find it in first words - in success add such word to table with common words.
4. Sort common part and remove duplicates, and print it.

Is this way incorrect ? I always got WA

Best regards
DM

[the LA-Z-BOy]

Is this way incorrect ? I always got WA

I got accepted with quite similar method as you. May be you are missing something else somewhere.
This test case may or may not help you
Input

Code: Select all

A A B B    A A B B    
A B A B    A B A B
A B C A    A B C A
B C A D    B C A D

#

Output

Code: Select all

AABB
AABC
AACB
AACC
AACD
AADC
ABAB
ABAC
ABAD
ABBA
ABCA
ACAB
ACAC
ACAD
ACBA
ACCA
ACDA
ADAB
ADAC
ADCA
BAAB
BAAC
BAAD
BABA
BACA
BADA
BBAA
BCAA
CAAB
CAAC
CAAD
CABA
CACA
CADA
CBAA
CCAA
CDAA
DAAB
DAAC
DABA
DACA
DCAA

thanks...
Istiaque Ahmed

[little joey]

Hi Dominik,

It's been a while since you wrote your message, but according to the list you still are WA on this problem (if I looked correctly). I had a long standing WA on this one too, but fixed it finaly today. I use a similar method as you (I use a binary tree to store the generated words, but that's just a minor difference).

My mistake was: I didn't re-initialise the word list inbetween two cases . Maybe you should check your code for this kind of errors too, because your method is OK.

My ultimate input was:

Code: Select all

A B B A    A B B A
E D D E    E D D E
E F F A    E F F A
A E F G    A E F G

X X X X    A B B A
X X X X    E D D E
X X X X    E F F A
X X X X    A E F G

#

Which produced the same list of words twice!

It's just a thought, but maybe it helps.

-little joey

[Dominik Michniewski]

Description says:

Code: Select all

Two consecutive entries on same board will be separated by one blank.

so I think that your input is incorrect .... but I don't make such mistake as you write. Everything looks OK. On both outputs - yours and LA-Z-BOy's ...
I try to make this problem again using my algorithm, but storing words in other way ...

Best regards
DM

[little joey]

Oops, you're right about the spaces . I editted my previous message. My program removes everything that's not an uppercase letter from the input, so it workes fine on this and I didn't notice.

[Dominik Michniewski]

After all, I've got Acc on this - I change code to use binary trees and got Acc with 1.5 sec time ....

Best regards
DM

[valderrama]

Hello!!!!

I'm trying to solve to 604 proble. It runs correctly, but it is using to much time. Does anybody know any method to be faster?? Here goes my method:

1. Generate all possible words of 4 letters from the first square.

2. Look if each letter of each word have a corner or edge in common in the squares (both).

3. Push the words in a vector, sort it, and print the words.


Please, I need help!!!!

Lots of thanks.

[sohel]

How did you generate all the four letter words?

I used dfs to generate all the legal words and used mapping to store it.

Then I did the same thing with the second grid and if it maps with that of previous then I inserted it in a vector.
Sort the vector.... and thats it.

[valderrama]

I generate all word just iterating (I think I used four ar five iterators one "inside" the other).

Please, could anybody tell me some method (that I were able to understand... it's so difficult) to generate the words faster???


Thanks!!!!

[Dominik Michniewski]

try to avoid letters, which not exist in second table. with this backtracking is fast enough.

Best regards
DM

[valderrama]

Hello!!!

I'm not able to solve this problem, because I get "Time Limit Exceeded" all time. Is there any method to solve the problem more quickly?

My algo is:

- Generate all possible words of the first board with two vowels and with its letters one on side the other in the board, and store it in a BST.

- The same with the other board

-Store in anther BST the common words.

-Print the common words.

Do you know any fastest method????

Thanks!!!

[sohel]

Hi Velderama,

Generating all the words using DFS should work.

First for the 1st grid:
-generate all the words and store the ones that contain two vowels ( remember y is a vowel in this problem).
- I used map to flag the valid ones. (M)

Then for the 2nd grid:
-generate all the words and if it contains two vowels look whether it is in M;
if yes( push it in a vector and mark this visited using another map M2 )
-repeat the steps and if (a valid word is formed in 2nd which is also contained in 1st but it is already mapped in M2 then do not push it in ).

In this way the final vector size is greatly reduced and helps avoid TLE.

Hope it helps.

[Larry]

Keep in mind that TLE doesn't always mean there's a problem with your algorithm. Maybe you're taking input wrong..

[valderrama]

DFS???? Map???

What is it????

I just know basic structures such as BST, TST...

[Dominik Michniewski]

DFS - Depth First Search

Best regards
DM