11602 - SMS for Blind

[Chirag Chheda]

Can someone please help me how to proceed with this problem.
Thanx in advance

[Jan]

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.

[qoo90]

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]

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
_gshdctlcusderlf_fbsnlghnmdfa_oesefglclpmrtdmaaebsopiumengmdmgnhrehp_umgp_lidsdrmaeanncfthmgaprflfep__totgbeibdahdhfpubnubeiltbifmuoohbhmeus_rpoisnppalauncegsgbnrr_sclpngatcdchocdatulsefcpgesahmfc_urerrtomsubpietcifloploigmr_pdnnnsmocirhbfhrtgcnruutabddooadguoopunactpomuorpbnotecatlsaulcfnf__digfispedlhdtdhtr_flmtdl_psgtlphmmlchstrldbtrlcllhppoemabemddroerrsheeainbnmhalll_fbmfsglpmstecchnreioefgtgnulaohlanghllhinifeehccmmntbseobltp_msfpnnfbtuceiibrn_g_bunh_rdsicgogmcrdrnsusrttetibusphn_pnaasdta_iugafecclshetalmdfcpdati_eudtlgtalsemchctoedunreatttmngu_plmtslmgh_bnpimisneh_firalhbc_pffg_rghitmffrrudm_drggedlimtigcelr_uiduocsiahnaeburpfos_h_p_ctmeitlparahmdfhbuogfrbicfocscedogs_sui_heooaghdhf_madbghsonntgrlchguasngfcsepouahrherrncamatlrshdlolaa_plblcaeunsltlcchibr_eocroergsant_osrshlpnfnfpuf_fgoeesoiptgubblibrpbi_utonsbmufgcpsoocuiipmischbc_mhn_ehngulelcreartheugedtustetbptfsseaifnibslgsestbsloonatbpufogoohuhmehrnpicngbsmdebculaalrdaorrhhhardd_hnuaisaofgrboha_lraamls_urip_ocoretufemhsnhhp
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
mmnrpsccfma_phmntdfsooeupdgnadarrc_eminallumdmreplnobntcduoiufnhfsn_aig_hnioapdfatsata_dndipabommtacesonrnftbpmmlrbstdutubntguhsldmdhmfinuadupb_nntce_epdbddgrfrdulbmhrlnsnuugghrhnhlcce_lcgprt_putgemuhimfuc_iphlapllblcefibfu_uahshfggmstusnsua_tbdmfbbcgmdedmhrm_inigusbht_aafeau_rnldghcgsbcladbpudlfuhalupprnriptdtebdihrdtbbttoucbbuoducrchgtrpfatltercdpeulufbohronahuerlfbdstalbsacnfacnpbsu_sndriin_ncdcrlnmsadgrebeiannogtghuuohsmisbmmippfgsogbreceicbtg_rr_uilord_cribtrgamldbdcgnbcmsrddgpcme_uinp_elsgoiorrnptcfi_etelplbprfcemogogscos_cnhuhdsiblsioieeiospufampshdlrcfgmbmhnagnsfpiibltmnp_codoicmonlndnf_fdruhcmdnecaprbd_non_lobettlbmlglnfrpliufemlluogagodefr__ldhhaeboipf_hfeifusauhapglmpgrilprltipdbecinbnnflasicitpculhmrutbnrsbpobnmbrnbifmdgfbatftaidantrcobr_nmmimc_fllsplpmndecmsom_mioarfuruigultaoftttdntpgpgmpocdorsbgfdsbfoggemfioortfrdbuisrd_haomuhsdaeiuscmipcrngrltctpaemcglgmatcmueaasaudphuhu_sfieputrfdbogoaltl_iuubnllcnaus_miac_s_ma_ubfs_mg_a_eigcptnl_lsprbigiagd_edipsuspliucuhtldopiesehitu
9813
lpogsfl_fsgfftpsg__nmhldtlcics_tcrouhtfroaric_nlrsdimcmcap_lptmbm_ndngcbfreuncuoo_dn_ccebouiifeenbmfeenidd_cag_ncfae_eohsmhmstnnrudh_btnrmclpacsurtclnrgaaansbrhnbctnfpbs_aaud_ebtaupbpc_anbrte_cmrrhhirputfieuotihmhncllubfrimpbpmminphp_hbutedslsoumb_cdahmabhu_urgaargcodgfumcrocdnbaesieamabhrcefodmoah_nsmpmpgtdiidbfldpnulhroome_nhrflnph_rdcfeuoebgeicitnfu_aeodabcfgblgro_bumabnathnsihnfueficcgsnclmrsms_p_limm__pahalih_rculabsraepfrhiclbecpm_en_lhcmo_rnffptromcugardassob_meubesfroibnl_nrfitegblgull_cudohtudt_u_bhgueoleucrdoseidmftibmbhesmaddsubenrlitdooaufana_uihbuoon_shdh_gnsttndaiatmsitotncefeu_cbdhgtuptalncolfcuoedmucdgiculupenhtedfsplhim_duethfeefugfiu_ocbhruhrlbndfadatptd_hdntcd_leehahrsdbfhfmbil_ldbcsgccupiceirdglmusrabssrblhminlsigumcodoehp_o_cgargofrldmfmcepnercm_prlucmoedeusphhdpmibcptgurahmsldlpupcrppmbtmatdultbiaempfadldcspaflenmhibnmbdngpgaitsesrhibmecssmimgdnseobsipfrilisatcemtgnnnlgdicncp_cgtnnc_ufrntscisualo_oisrodospddacsnru_rhnbtgai_lrabgnuahmtgmlososo_lebsbnbdrrueccgn_astg
9911
olshhhmoegnpfp_ssuphmr_mrblnduouprfneseff_ddcnfrnfdltephcgrnaocicpmrlbinenaiip_ughsedndu_dghsrohbs_mlalepfpbctchtstpfphcbdsibbimuduts_pdu_luomaighgnrfmtcmcnnfb__ngigprddmnucfrncohbritsbmmocldgpsrraun_hhtltlcrlbsucecpnbapausci_lguocsfoe_niam_ugtadhecnmrgethohrofpc_prngchpsaphuu_embuidaedoabsmslmbtmnoooobhhncflohircah_otprbphtbgca_uatumrsfsbbfireuhagopemuiiclftaumlcusn_rlngtillfclrohpt_ncudntcbl_lgdmcennutabpceaussph_uhtpuuaengrfietditiftnihfbafomgeormsdgdpffrtpfr_rcmaddie_bctgedfudhirurgoac_g_e__nssmboc_cntpfnlogibomrdruriinmusuuiucotmicgdodisapsoaetmhlsinbtffbb_gs__gaacblfrgdntrchsrnprih_emihlbaemfdbmuitcicici_duemfercsspgppupspdmdnegcdgompta_sltpthnscuasmihabmgf_btghhdmdtefti_roprmfuoorurpu_fm___thiicgueul_irfmbtfbaapbngfgsfbuipfhlliilaambuoohibghomufitrguuoafpufcgil_upibeee_bael_boassngnmanaub_imuagtmn_shfrmbrorl_uodmbimbpshcronimses_rphhnoporfgunars_cncbp_tonptnncttpcbafaluor_p_hidrsu___ootbeebpfopiommpnogeupbalnnlismiobitrdlrceois_entetfpnfhhphgonhcbb_o_bntatec_bdiulcegg_ugeogcacea
10089
mnfrbatiosrchmbucbb_husagl_peudiuppseueocpdods_alaeua_rednlcstroornmlscnttimlgiuadllrmntlpf_egtpp_bmmlnspm_loribel_mmlbs_unlongnlbpgcflgrmunaengtcp_emnbpbu_trcpslruheolbtifhgsh_hsgaaongl_stghah_ilemscschrdngnimfig_matmcpungcemlbdphafcurfflpushtnandombnpbtodfdgsaiuorhmceuiecddafpscpesatbiabmpgtbragfghhfpocodss_rglmuribdodfmhrtmgflisucmtdpltacnhmcrigpsdesmfcntcgrnmdotoheofnmedutem_hu_endepigfcilcluroeuphpddbrmofulbeeibfnibmgftlgmsesubdugtuu_moi_mnocofabplgrufagaltdlroetuinagpomo_oobftnpbtmdihgdruhiptrosroblhbffganitoaetfeeuftlfebegbcgdrugbffinbeoelfhrldctafapadcfco_fiedsddbmhngotgusabnemnibltrsmhno_ucetsuenmorlrpdpcm_dbnhnm_brmbduibsurhiusrddnnrh_mcclhabftfuctgfaesansrfdrmhrdmuelnlatntcclmdrhuitnnhe_unohcepnmaimacilmaiubeglarpnbsrlamguhgsdl_strphsolnhuotlgl_am_hotdmol_napludplllles_drardpuogottubceplf___mtgaoad_casublahmoggheclcilrnfatr_hhuehols__nupaotstnldaneo_pfogdelanoei_obgialrtscfdssplltiasmmennmtuiaspsptihunnbhibeabs_pfiouihcus_soommssrmchgftsdissfligegasbuiebdssi_fdgifh_intumlgms
9941
fg_gn_iadcalorlmidiir_luddumfutrnrbdnio_tm_duhpuphcaglgeohbc_mulugsdthggrnmcdgrmcldnaahmacfsptpgcpdebbpudglrdtocrhhhntseemcmuplbnmserfcultphl_ssfmarclhslt_esunuccdm_t_eftmntinmdaeoa_ta_gt_risdn_ggcmtdsnrilfilmsureucrdthnh_cd_lputisbpelbhaopisrgaubtlgsmmgetonfpci_rsbhgepcfnfsrpstpaanehpsuiu_ilpgelirubmoumugnrdaddhtes_lthnsplecafnslocmgmt_ddfrctaacmg_mbcsl_ulnhlaguhdfirpsilmidmpdangdimfeir_pdbrritdaucgutofglomnhi_fdgnscnegapdblrtpobhopeifohhgorhronpeutbgpnnhusphaaihpbthhapppfcpmc_iopedodie_miffcmmonhcllrahnctirocom_acd_ideactsetuhaargiermnatbsneiplapdmfhsrtemdrtucbpbfmrfh_icssnmcrlpid_pbc_ghmpslsmmbpudfebgmpehosiea_olgtsoatctgocofineiluhoclonpefoahgsocogurdnsbdlufueunepltdseeebnlbftruedpdiaorfgtsnfaibr_grudcguofnoffsitsfrdldnnomeuubcl_ahoafglmrplpbchshhfoapascgbscdlfpunbdscguhbbolobfg_elpurnbh_u_os_naefeammdgtsrglrlref_gorirubemphfgsuchsohmoeiteutr_ifbhg_abftogld_sbapcbblcluelgroctgilatgsehmufbpgelpafhroansfcpttgloeushitbantcmucpf_eesontnalasirprsr_epbgnbafpgcbrtifethuipfigfdbacsauoehnpr
9980
lerioounonsadguhhnhisfgegousplrfodnbrelpdsaeulgsgddbddcfdbcnilsuupnogbafrdiss_pl_htebsnaaacimathmghmtpp_cufgdtdoaemtibopi_gbpsnsutlmmedsguinlunp_muddheudtnnigirsngclihgett_shpedmsfmb_nolut_ldf_ntmbmasrihrrpbe_dhheiaonstpdopludhgudhlccdtndhgpbditdsptlgnoputnhintulandccadirdrbdonndsclhicihcnproua_i_fbonlgiuouheluhptpmphoarilpudfmrsnu_omb_mohebedeafsmucspihbdfhth_bmssunlifitdrsrmc_spneleclhbg_dfobhsgnihcfitgodhbcls_eoesfp_gubgbdbogtmtd_ugpeipfsnsep_dil_tiffhmlbrdpfmutfiliaagfbfhaguhpdmdbofogacedbigfgbtbnpfansuhdbuuhnb_rdtahbolsncioobnsddilieb_pdpumblilolfgcchaptupmutohepdgilrcgmchabdtpuppihhosfspeoh_aafhadgpbfsesuuhihfbnboulfpgfm_rbnbrbnaepdmtg_gbgnhuddgarmluoomnflcgeoaubosinibgncfmislhiiaihfirhbnfoegmclbstlmlgmlrpcnodl_nfsruefcumftuuguhafmpan_rutpfplrautmibunuflusutmuorlbutboegp_obccbnnmulb_snrlmtrpggdgugsbacebil_utlcsusg_dlrshidocumdpgnstcgatcmcsepousgarr_hooelcecih__omitufinpdfcnlufugtptlhgb_nr_p_hhtbbtpmaponelhocnuflusf_c_bsnodrntdofon_hubpnilohiullgn__pcpadrfhgbgcbt_epssi_uafb_bgbhge
10006
irhedimniefcl_imh_gblnnc_cbomimuuhusunne_eiubhpeumapnbuhaforiogbdsptiftlaiddt_abrsehdissfpaicfuua_rnafpheerritsucttnpmina_midha_cpghelcnbpobabctgupoedb_lsalfpnfhncp_ontgnid_dnmadhatummcguo_lil_mugpcoapgce_gd_i_brdiscaphuurtlaistcsir_caopcfrgafdeupmhheoutmfulbigbff_flilcieognimbpsadgnpmmshoobnhhodpnhe_onmbndsgmimilgcgiflmrcuoeotsluurfeuestdpemhcircgu_tmlnrlbfsnfochpladodfaoc_sserbuhmceuulegpaahotemmgoahtusisplgntlgsbgfpd_rtofofgubpog_llgrc_hpfae_arfsbmbmssplnmoiuonhedt_iacoptosnafilgacptmgaioaemmihghicgs_bplngrd_uecnalmrcfiotouam_ibcoirrporfleulargoso_ffacaeptridc_oiteittsfprtcidgeninogiscnluofocosdlehgictmfdccerfn_srmcabsamheocaogcuaubptuclmc_goiedthfrhaitbehmgtsnlbmdncdtcaillfontgtfel_mhhsuluhtucrfttoa_reuistlpoebgmgmiaeelgmlmt_oecctcecohmrlopchfnie_gprclt_eupcrcscof_rbamcg_ufsupetfrndbusd_rinptrug_pucgesimr_pfrthbhfdaioemgcgbmdnptmfulebbgbpoofauafhgmpttbopfefmhhdannl_midossrofubudbarteateagmnghtrplfhc_rrtnohhd__rsdenfbcaif_petutc_sgifedfmnfsbafdlihnmfloituuo__ffgahrbegoihtmildosrnncl
10182
*

output

Code: Select all

f_umhrndsabogtiecpl
mnltifsgeuadbh_oprc
gsdbuactel_phmorfni
_nrpfsmtliagbudceoh
iabhrtlceomn_pfdgsu
nefl_tarcophigmdsub
pomdscngb_uhlrtifae
chosu_pdemnrtbgilfa
prcs_glntfudiombhea
nfmdpalirb_ueshtcog