## 11602 - SMS for Blind

Moderator: Board moderators

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### 11602 - SMS for Blind

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11602 - SMS for Blind

Backtracking with pruning.

1) First, calculate frequencies for each letter.
2) In each position, try to assign a letter with frequency f. And when assigning a different letter in this position, be sure that the frequency is different than f, too.
3) For remaining letters (the ones that are not placed yet) you can find the maximum and minimum keystrokes which can be generated. So, a bound can be placed.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

qoo90
New poster
Posts: 2
Joined: Sun May 10, 2009 10:29 am

### Re: 11602 - SMS for Blind

You can also consider the problem as a local search problem. I had used random hill climbing algorithm and get AC.

First calculate the frequency of all letters, then randomly select a solution (a permutation of 19 letters) and check its distant between the given cost. After that, keep on finding any improvement that decreases the distant of your solution to the given cost. To do that, try exchanging any of two letters in the permutation and see if the new permutation has a cost more close to the given one than the original permutation. If no improvement can be made, then randomly select another starting permutation. You can define a trial bound or try until success. I use 30000 as the bound and get AC.

This method may not guerantee success, but easy to implement and the time complexity will be quiet small.

Hope it works!

allenlam
New poster
Posts: 8
Joined: Tue Jun 09, 2009 6:46 am

### Re: 11602 - SMS for Blind - Why PE?

It is an interesting problem but the judge's behavior is too strange.

I've tried out all possible newline/no-newline options but it is always PE.
I write it in Java and all outputs are done by System.out.println(keyOrder);

It seems there is no tricky output requirement.
Does PE mean something unrelated to presentation, for example...
Does PE mean there are more than 10 solutions with incorrect cost?
Does PE mean some of the output lines are not formatted correctly as defined in the problem?
or the output is just incorrect (WA)?
Does the test cases changed recently that does not match the problem description?

some testing samples:
input

Code: Select all

``````pgibdhtaddrprmeidcrspmniusgctdsfgtta_rpfcercositpocrcon_udagutpemtntouep_ffcsaaucof_rhulsi_bdhacoagutiuopdbgltpraoechhgpcgtrghbai_rgaipmgmttpnugbnspguul_sc_lgnnapcanfepumuhtopstglepeinpelgrplt_gersadcmcepggabgermhhbcltschaudasmmhreummppdnhel_ce_dgcmugamcfdlultimtufunnapsrrnp_m_rctabgimdalheflbrfl_rbt_oetrcmpcebssgmcuntttubmomcfonshi_frrain_igofesehbahccdpnlootutedh_lenrfpmbnbismgi_tog_fgagmhcdnnfuddepuuuabfpngulepdtgaessintelh_dbdecodfsdrsoutactfb_ibcudusthgstilibat_tmbgo_hfbtcnognd_c_ggnpdslerc_gchcntgtmrasccrmcreai__uaihabgspdechtcgtrhsiidrdrepafctgofnsii_asrrrshbruibtpbltefnualptoiaaemmebrurreslcgeismrbnbpcbdfoafbg_mf_rmmabploipbghdtsdhfpnarctsrntnortbrdtarmpuelgmllfofsntpohpilfrsdutpgtahioehoigfoluecoucpsapeorelicccrrhodfsdfdnshriopoi_snanocdurcureduumoiofrsiuituaaiteaedidbh_siucrteugbolncfcsbde_usatgd_iambh_dcnmfs_nmtfist_tgfbmmbicfufteubfmiegtsccgcliuacgnhhgnuarauaomobir_cspapoiau_rilsngmdlcslfbtuasdpcsiaso_gsshg_tmhmcbodnaestdcobidcegfdcimalaefm_pelddbrthhdgcipdidaehhgg_cituoteo
10253
9978
hisu_pbaodo_emiohfcopoofspolthondcslmhahgohmbrlpr_g_olmabapceangnblliopffflnt_ftgfarrcohnohnlrphubhcdpmddipbdcnrugh_aihmestasm_ubsfubpblmebbb_emlb_reghflslnaatgtpbcgaopbfiusb_uofcbhilcsoeeaff_uniht_ugbehdiiiuocsocnb_uhcmchdhdmpsitpmenacrlteohatohncpmutplago_hsueggfeedohob_msppgfllcebmesmduidsnbalnlnesstlgcaeaotcdupar__beruod_fmscn_btrl_euhmfsccpdruepgfpplrtuslr_lrmamluumhcoemcmpsfenahmss_netermhf_escssrmac_mgfnhdfupa_ggimreuhautdhpmstdoghfd_uitmusasulehcsfdrsdaeiopbdnbashcfrtsbnaiglcsseuhpgehhufimt_dahhhbctmonpperllsahdus_t_bmhe_uhtelbmrgaleb_c_tosthmhceaooppnhrgshenphgophlbrlapmthhpuogopefcueel_fsfarcrfbctfl_icpnliebuhbtflurtcui_lfhmpdamaoonuibpelmfibapgiggfgtuec_inuhfmiteitihmganprbmhrrg_r_tcnnesthbtcossiuummamnud_afcohnuttndahlgtpersfndpnogids_iabislblrugfsg_s_cfopigcbprg_bsndipgaerinluasiubtehdcsgogreeoeunfaincbp_mipfeehnneicicdi_puiiouem_sualbhlbfbifi_pffrbesgaoueoseiglialct_dcpg_ecsddsulbtggumdgtubagbmantabcglrogb_aomoanrbdmuesfmhsstifa_olosp_cugarilgabpt_ouccdmbccmirffethdo_agbc
9817
9813
9911
10089
9941
9980
10006
10182
*
``````
output

Code: Select all

``````f_umhrndsabogtiecpl