487 - Boggle Blitz

[thurbo]

Hi,

I am getting WA for problem 487 (Boggle Blitz).
Not sure if it depends on reading the input incorrectly or just computing wrong results.
Anyway, here is my test input and test output (other examples would be appreciated as well).

Input:
10

3
one
top
dog

4
abcd
bcda
cdab
dabc

1
c

2
ab
cd

4
abba
abba
abba
abba

20
abcdabcdbcdacdabdabc
bcdacdabdabccdababcd
cdabcdabcdabdabcdabc
dabcdabcbcdacdabdcca
abcdeecdbcdacdabdabc
bcdacdabdabccdababcd
cdabcdabeeabdabcdabc
bcdacdabdabccdababcd
cdabcdabcdabdabcdabc
daecdabcbedacdabdcca
abcdabcdbcdacdabdabc
bcdacdabdabccdababcd
cdabcdabcdabdabcdabc
dabcdfbcbghicdabdcca
abcdabcdbcdacdabdabc
bcdacdabdabccdababcd
cdabcdabcjkmdabcdabc
abcdabqqdbcncdabdabc
abcdabcdbcdacdabdabc
abcdabcdbcrrcdabdabc

3
#$.
*#@
+#!

3
ONE
TOP
DOG

2
01
23

2
aA
bB

Output:
dop
dot
eno
enp
ent
eop
eot
gop
got
nop
not
enop
enot

abc
abd
acd
bcd
abcd


abc
abd
acd
bcd
abcd


abc
abd
abe
abf
abg
abh
abi
abj
abk
abm
abq
acd
ace
acf
acg
ach
aci
acj
ack
acm
acn
acq
acr
ade
adf
adg
adh
adi
adj
adm
adn
adq
adr
agh
ahi
ajk
akm
akn
bcd
bce
bcf
bcg
bch
bci
bcj
bck
bcm
bcn
bcq
bcr
bde
bdf
bdg
bdh
bdi
bdj
bdn
bdq
bdr
bgh
bhi
bjk
bkm
bkn
bmn
cde
cdf
cdg
cdh
cdi
cdj
cdm
cdn
cdq
cdr
cgh
chi
cjk
ckm
ckn
cmn
dgh
dhi
djk
dmn
ghi
jkm
jkn
kmn
abcd
abce
abcf
abcg
abch
abci
abcj
abck
abcm
abcq
abde
abdf
abdg
abdh
abdi
abdj
abdq
abgh
abhi
abjk
abkm
abkn
abmn
acde
acdf
acdg
acdh
acdi
acdj
acdm
acdn
acdq
acdr
acgh
achi
acjk
ackm
ackn
acmn
adgh
adhi
adjk
admn
aghi
ajkm
ajkn
akmn
bcde
bcdf
bcdg
bcdh
bcdi
bcdj
bcdm
bcdn
bcdq
bcdr
bcgh
bchi
bcjk
bckm
bckn
bcmn
bdgh
bdhi
bdjk
bghi
bjkm
bjkn
bkmn
cdgh
cdhi
cdjk
cdmn
cghi
cjkm
cjkn
ckmn
dghi
djkm
djkn
jkmn
abcde
abcdf
abcdg
abcdh
abcdi
abcdj
abcdm
abcdn
abcdq
abcgh
abchi
abcjk
abckm
abckn
abcmn
abdgh
abdhi
abdjk
abghi
abjkm
abjkn
abkmn
acdgh
acdhi
acdjk
acdmn
acghi
acjkm
acjkn
ackmn
adghi
adjkm
adjkn
ajkmn
bcdgh
bcdhi
bcdjk
bcdmn
bcghi
bcjkm
bcjkn
bckmn
bdghi
bdjkm
bdjkn
bjkmn
cdghi
cdjkm
cdjkn
cjkmn
djkmn
abcdgh
abcdhi
abcdjk
abcdmn
abcghi
abcjkm
abcjkn
abckmn
abdghi
abdjkm
abdjkn
abjkmn
acdghi
acdjkm
acdjkn
acjkmn
adjkmn
bcdghi
bcdjkm
bcdjkn
bcjkmn
bdjkmn
cdjkmn
abcdghi
abcdjkm
abcdjkn
abcjkmn
abdjkmn
acdjkmn
bcdjkmn
abcdjkmn

!#$
!#*
!#+
!#.
!#@
#$*
#$.
#$@
#*+
#.@
$*+
$.@
!#$*
!#$.
!#$@
!#*+
!#.@
#$*+
#$.@
!#$*+
!#$.@

DOP
DOT
ENO
ENP
ENT
EOP
EOT
GOP
GOT
NOP
NOT
ENOP
ENOT

012
013
023
123
0123

ABa
ABb
Aab
Bab
ABab


Greetings,

Jeroen

[serur]

My AC program would output:

dop
dot
eno
enp
ent
eop
eot
gop
got
nop
not
enop
enot

abc
abd
acd
bcd
abcd


abc
abd
acd
bcd
abcd


abc
abd
abe
abf
abg
abh
abi
abj
abk
abm
abq
acd
ace
acf
acg
ach
aci
acj
ack
acm
acn
acq
acr
ade
adf
adg
adh
adi
adj
adm
adn
adq
adr
agh
ahi
ajk
akm
akn
bcd
bce
bcf
bcg
bch
bci
bcj
bck
bcm
bcn
bcq
bcr
bde
bdf
bdg
bdh
bdi
bdj
bdn
bdq
bdr
bgh
bhi
bjk
bkm
bkn
bmn
cde
cdf
cdg
cdh
cdi
cdj
cdm
cdn
cdq
cdr
cgh
chi
cjk
ckm
ckn
cmn
dgh
dhi
djk
dmn
ghi
jkm
jkn
kmn
abcd
abce
abcf
abcg
abch
abci
abcj
abck
abcm
abcq
abde
abdf
abdg
abdh
abdi
abdj
abdq
abgh
abhi
abjk
abkm
abkn
abmn
acde
acdf
acdg
acdh
acdi
acdj
acdm
acdn
acdq
acdr
acgh
achi
acjk
ackm
ackn
acmn
adgh
adhi
adjk
admn
aghi
ajkm
ajkn
akmn
bcde
bcdf
bcdg
bcdh
bcdi
bcdj
bcdm
bcdn
bcdq
bcdr
bcgh
bchi
bcjk
bckm
bckn
bcmn
bdgh
bdhi
bdjk
bghi
bjkm
bjkn
bkmn
cdgh
cdhi
cdjk
cdmn
cghi
cjkm
cjkn
ckmn
dghi
djkm
djkn
jkmn
abcde
abcdf
abcdg
abcdh
abcdi
abcdj
abcdm
abcdn
abcdq
abcgh
abchi
abcjk
abckm
abckn
abcmn
abdgh
abdhi
abdjk
abghi
abjkm
abjkn
abkmn
acdgh
acdhi
acdjk
acdmn
acghi
acjkm
acjkn
ackmn
adghi
adjkm
adjkn
ajkmn
bcdgh
bcdhi
bcdjk
bcdmn
bcghi
bcjkm
bcjkn
bckmn
bdghi
bdjkm
bdjkn
bjkmn
cdghi
cdjkm
cdjkn
cjkmn
djkmn
abcdgh
abcdhi
abcdjk
abcdmn
abcghi
abcjkm
abcjkn
abckmn
abdghi
abdjkm
abdjkn
abjkmn
acdghi
acdjkm
acdjkn
acjkmn
adjkmn
bcdghi
bcdjkm
bcdjkn
bcjkmn
bdjkmn
cdjkmn
abcdghi
abcdjkm
abcdjkn
abcjkmn
abdjkmn
acdjkmn
bcdjkmn
abcdjkmn

!#$
!#*
!#+
!#.
!#@
#$*
#$.
#$@
#*+
#.@
$*+
$.@
!#$*
!#$.
!#$@
!#*+
!#.@
#$*+
#$.@
!#$*+
!#$.@

DOP
DOT
ENO
ENP
ENT
EOP
EOT
GOP
GOT
NOP
NOT
ENOP
ENOT

012
013
023
123
0123

ABa
ABb
Aab
Bab
ABab


Goo luck![/list]

[thurbo]

Mmmm, run diff to check for differences but couldn't find any. Guess I am missing something but what?
As it seems that both our programs generate the same output, I assume it has something to do with special cases but I am completely blank. Do you have any ideas?
Thanks,

Jeroen

[daveon]

Hi,

I don't think that there are any tricky cases. Perhaps if you explained your logic or post the main parts of your code, then I can be of more help.

[thurbo]

Hi,

It has been a while so I had to search for things :-).

First I build up a collection of all possible edges.
For every edge I will add the corresponding word to the collection of words for the tail of the edge.
For every word in the collection, remove it (after storing if length >= 3) and for every edge starting from the corresponding node, add a new word to the collection consisting of the old word suffixed with the letter matching the tail of the edge.
Example:
one 123
top 456
dog 789

Possible edges:
1 -> 4
2 -> 1, 4, 5, 6
3 -> 2, 5, 6
5 -> 4, 6
7 -> 4, 5, 8
8 -> 4, 6
9 -> 5, 6, 8

Word collection (init):
1 -> no
2 -> en
4 -> ot, nt, dt
5 -> no, eo, do, go
6 -> np, ep, op, gp
8 -> do, go

Word collection (iteration 1):
1 -> eno
4 -> not, ent, eot, dot, got
5 -> eno
6 -> enp, nop, eop, dop, gop

Word collection (iteration 2):
4 -> enot
6 -> enop

Found words are: dop, dot, enp, ent, eop, eot, gop, got, nop, not, enop, enot.

[daveon]

If you give me your email, I could send you some more IO.

[rammestain]

I got TLE, please give me idea.

[sclo]

backtracking + trie is enough to get AC.

[DD]

I use backtracking to find all possible answers, then store desired answers by map in C++.
And my program ran about 0.30 secs to get A.C., if you still struck in T.L.E, please try this method.

[Shafaet_du]

Trie may make the code run faster but map is enough to get ac. The condition "increasing chain of characters" ensured that the number of words wont be very large.

[brianfry713]

Input:

Code: Select all

1

8
ABCDEFGH
BCDEFGHI
CDEFGHIJ
DEFGHIJK
EFGHIJKL
FGHIJKLM
GHIJKLMN
HIJKLMNO

My AC JAVA code handles this case quickly. ooroni, this gave a RE for input #5 at http://ideone.com/MfA62