online-judge.uva.es

by **Hadi** » Thu Feb 22, 2007 3:36 pm

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!

by **rio** » Thu Feb 22, 2007 3:51 pm

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.

by mf » Thu Feb 22, 2007 9:43 pm

<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.

by **sclo** » Thu Feb 22, 2007 9:52 pm

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

How is that possible?

by **rio** » Fri Feb 23, 2007 5:28 am

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.

by **Hadi** » Fri Feb 23, 2007 1:21 pm

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

by **lolpilla** » Tue Apr 28, 2009 8:14 pm

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?

by **brianfry713** » Fri Feb 15, 2013 2:42 am

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

online-judge.uva.es

11171 - SMS

11171 - SMS

Re: 11171 - SMS

Re: 11171 - SMS

Who is online