11171 - SMS

[Hadi]

I build two tries (one is digit based, the other is letter based) and find minimum key sequence for each word using these tries. Then, I use dynamic programming to find the minimum sequence for typing the given query. But It seems that my solution cannot find any key seqeunce for some queries.

Some tricky I/O please!

[rio]

I think there is no tricky case. I took almost same approach as you did and got AC.
Maybe some flaw in your trie implementation.

[mf]

<s>Number of keypresses doesn't fit in an 'int' in some test cases.</s>

Ok, sorry. I've used an 'int' and quite a low value to indicate +infinity, that got WA. Swithcing to long long made it accepted, that's why I said that, but now I see it's not really the case.

[sclo]

Number of keypresses doesn't fit in an 'int' in some test cases.

How is that possible?

[rio]

I think this is the worst (most key pushed) case.

Code: Select all

10000  // dictionary has words only with length 3.
abc
cba
...
zzz  // U(5000)
...
1
zzzzzz....  // length 3 * 83333 = 249999

So the key press is 249999 + 83333*(1 + 5000) - 1 = 416998331.
And it fits in int.

ADD : Oops. I noticed that this is wrong. The maximum key push is more smaller.

[Hadi]

I got Accepted using int as data type and 999999999 as infinity value.

[lolpilla]

Hi.

What do you mean by two tries, one digit based and the other letter based?

I was using a vector for the full word, and see where can I get with from a possible sub-word (where possible means that the sub-word that comes before this letters is a possible word, with a minimum number of keypresses). I end up comparing strings and using maps.

I get the correct answer for the examples in the problem's webpage, but I get time limit exceeded when submiting. Any tips or ideas why I'm getting this? Any ideas of usable data structures for this problem so that I can get a better performance? Or will I have to think in another way to solve this problem?

[brianfry713]

http://en.wikipedia.org/wiki/Trie

The digit based trie keeps track of how many words in the dictionary read so far map to that sequence of button presses.

The letter based trie stores the dictionary and also stores the position in the common sequence for each word.

My AC code doesn't use any maps and only compares strings using the letter based trie.

Some random input:

Code: Select all

39
r
qsivciw
aewbk
jgotyxjgz
sjturlghdo
hwdhziga
elb
ebrqh
hzccvv
be
s
bonjpxrr
vcspjviz
biddkya
afs
owidh
cyr
tuokd
seowmsb
scyuh
oxpx
wzfuqzpm
zratvorji
ibxg
gzmfolik
o
cpvpfwihq
yjngc
jb
jhdvn
gvesl
ubgliduqvy
enwjlik
ruuohowe
oqei
mu
rqtoqj
dieqsqhlke
rsvyll
18
oqeizratvorjielbsjturlghdorsvyllsebrqhelbqsivciwrqtoqj
zratvorjijgotyxjgzvcspjvizbiddkya
sjturlghdocyrjhdvnowidhafsoxpx
ebrqhvcspjvizbiddkyaseowmsbrdieqsqhlkehzccvvgveslruuohowescyuh
dieqsqhlke
rqtoqjelbafscpvpfwihqjgotyxjgzubgliduqvybeelb
zratvorjijbdieqsqhlke
ebrqhjgotyxjgzgveslyjngchzccvvrsvylljbzratvorji
jboxpxsjturlghdo
jgotyxjgzibxgoqeiaewbkjgotyxjgzubgliduqvyrqtoqjtuokd
rs
musjturlghdorsvyllbiddkyagvesl
oxpxzratvorjiebrqhhzccvvubgliduqvyoqeioafsgvesl
ibxgoqeigzmfolikyjngcseowmsbscyuhjhdvn
qsivciwcpvpfwihq
hzccvvowidhyjngcoroxpxbiddkyabiddkya
seowmsbruuohoweoqei
gveslcpvpfwihqs
55
dgoytcgbh
pj
n
xzbebb
uwbwcdigu
oikjm
lvjcesrtr
u
uwoqurmwuw
oivyvfmn
hzw
rohigdfc
vs
mg
jdzxnuykb
atuzsjsgs
owhrx
jtrsncxo
kka
mmxhiwzu
h
qwk
nkeyfy
sanicas
xgruqbsrv
z
yvwzkgg
l
bfgqn
qipnog
gkbyfjxrju
jgwpqkv
pbif
anc
dkxku
kckj
udjd
iubspvhsfo
fb
vh
vtuwdw
oratdde
zhdqemllbs
efoncjgyfl
ozoosru
etghk
t
ywprbwfo
rxz
ivm
jbecx
gqlpcxlz
hqoi
uxnnuol
jyqvbvxya
4
gqlpcxlzjgwpqkvuxnnuolrxzdkxkujgwpqkviubspvhsfo
ozoosrupbifetghkkckjywprbwfogqlpcxlzlvjcesrtrpbifn
hqoiefoncjgyflxzbebbxzbebbnkeyfy
ujdzxnuykboivyvfmnuwoqurmwuwhzwxgruqbsrv
7
mhluetmrr
sm
htg
mgxfygbk
vxdkyprjmx
yqxlj
ys
7
htgsmvxdkyprjmx
vxdkyprjmxmgxfygbk
mhluetmrrvxdkyprjmxmhluetmrrys
yqxljyqxljsmmgxfygbkvxdkyprjmxhtgsm
htgmgxfygbkyqxljsmhtgmgxfygbkmgxfygbkys
smsmhtghtgmgxfygbkmgxfygbkvxdkyprjmx
ysyqxljvxdkyprjmxyqxljvxdkyprjmxvxdkyprjmxmgxfygbkmhluetmrryqxlj
15
dyqqkgbfgv
xwgt
yseccsgne
ew
vplt
bdo
kwzpt
womwgq
jkgyopfmv
biv
lyzokypc
nygbuoruzb
y
sfdp
gxasiatymr
13
ewgxasiatymrlyzokypc
bdoyseccsgneewkwzptbivdyqqkgbfgvgxasiatymry
womwgqsfdp
vpltjkgyopfmvwomwgqnygbuoruzbewbivgxasiatymryseccsgnebdo
dyqqkgbfgvkwzptbdo
vpltjkgyopfmvlyzokypckwzptyseccsgne
xwgtkwzptbdolyzokypcsfdpvpltgxasiatymrgxasiatymr
ywomwgqgxasiatymry
lyzokypcdyqqkgbfgvdyqqkgbfgvyseccsgneew
gxasiatymr
ew
kwzptwomwgq
xwgt
27
ydiseson
bwumuwdgrr
jzqjteg
houhtf
yzpnns
hg
ekmxbahdrs
xaj
rdokiski
xx
jei
kua
wbrbu
xrlg
clpnu
zeqx
sg
dwsx
cv
t
wgvnr
owpdll
kpa
sv
byotxnvt
qrlw
aqqomftzqd
14
xxhouhtfwbrbuxxydisesonhgwgvnrwgvnrjeikua
ekmxbahdrshgsgwbrbuhouhtfzeqxbyotxnvtwbrbu
zeqx
aqqomftzqdrdokiskiwgvnr
dwsxqrlwsgxajsgqrlwaqqomftzqdbwumuwdgrrxaj
ekmxbahdrssgxxekmxbahdrsdwsxhouhtfwbrbukuardokiskixrlg
byotxnvtaqqomftzqdzeqxqrlwclpnujzqjtegbyotxnvt
kpaxrlgbwumuwdgrrwgvnrhouhtfqrlwqrlw
byotxnvtydisesonclpnuxrlgkpatsvbwumuwdgrrqrlw
jzqjtegjeisvsgxrlgxxzeqxcvxaj
wgvnrowpdll
yzpnnssvowpdllxrlgzeqxtwbrbuekmxbahdrssgwbrbu
houhtfsvdwsxzeqx
sghouhtf
0

My AC output:

Code: Select all

6734R972886754R352R7588754436R778955R7U(1)R32774R352R7748249R778675
972886754R546899549R82775849R2433592
7588754436R297R54386R69434R237R6979
32774R82775849R2433592R7369672R7R3437774553R492288R48375R78864693R72984
3437774553
778675R352R237R278739447R546899549R8245438789R23R352
972886754R52R3437774553
32774R546899549R48375R95642R492288R778955R52R972886754
52R6979R7588754436
546899549R4294R6734R23925R546899549R8245438789R778675R88653
7R7U(1)
68R7588754436R778955R2433592R48375
6979R972886754R32774R492288R8245438789R6734R6R237R48375
4294R6734R49636545R95642R7369672R72984R54386
7748249R278739447
492288R69434R95642R6R7R6979R2433592R2433592
7369672R78864693R6734
48375R278739447R7U(1)
47572959R5497758R8966865R799R35958R5497758R4827784736
6966778R7243R38445R5255R99772936R47572959R585237787R7243R6
4764R3366254935R992322R992322R653939
8R539968952R64898366R8967876989R499R947872778
484R76R8935977569
8935977569R64939425
645838677R8935977569R645838677R97
97955R97955R76R64939425R8935977569R484R76
484R64939425R97955R76R484R64939425R64939425R97
76R76R484R484R64939425R64939425R8935977569
97R97955R8935977569R97955R8935977569R8935977569R64939425R645838677R97955
39R4927428967R59965972
236R973227463R39R59978R248R3977542348R4927428967R9
966947R7337
8758R554967368R966947R6942867892R39R248R4927428967R973227463R236
3977542348R59978R236
8758R554967368R59965972R59978R973227463
9948R59978R236R59965972R7337R8758R4927428967R4927428967
9R966947R4927428967R9
59965972R3977542348R3977542348R973227463R39
4927428967
39
59978R966947
9948
99R468483R92728R99R93473766R44R94867R94867R534R582
3569224377R44R74R92728R468483R9379R29689688R92728
9379
2776638973R73654754R94867
3979R7759R74R925R74R7759R2776638973R2986893477R925
3569224377R74R99R3569224377R3979R468483R92728R582R73654754R9754
29689688R2776638973R9379R7759R25768R5975834R29689688
572R9754R2986893477R94867R468483R7759R7759
29689688R93473766R25768R9754R572R8R78R2986893477R7759
5975834R534R78R74R9754R99R9379R28R925
94867R697355
997667R78R697355R9754R9379R8R92728R3569224377R74R92728
468483R78R3979R9379
74R468483

Note that your output may be different but should have these total number of button presses:

Code: Select all

64
36
35
71
10
52
23
54
18
59
4
34
55
44
17
43
21
18
53
58
36
45
17
19
33
41
46
42
72
22
50
11
64
20
39
55
21
43
10
2
12
4
50
49
4
25
50
63
52
42
53
37
12
54
19
9

[@li_kuet]

Why am i getting WA ?
It's okay with brianfry713 testcases. What am i missing

Code: Select all

AC :)