11418 - Clever Naming Patterns

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
mike21
New poster
Posts: 5
Joined: Sat Jun 15, 2013 3:25 am

11418 - Clever Naming Patterns

Post by mike21 » Thu Oct 24, 2013 12:08 am

Hello,

Can someone explain to me, why in the last test case (4) of the provided input, "Ad" is listed as the name for the first test case?
How I understant it, the only set of words for the first problem in the fourth test case is "Aa Ba Ca Da", so no "Ad" in that set.

Many thanks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11418 - Clever Naming Patterns

Post by brianfry713 » Thu Oct 24, 2013 9:03 pm

For the 4th test case of the sample input, there are 4 problems. You have to choose one from each of these 4 sets:
Aa Ba Ca Da
Ab Bb Cb
Ac Bc
Ad
Check input and AC output for thousands of problems on uDebug!

mike21
New poster
Posts: 5
Joined: Sat Jun 15, 2013 3:25 am

Re: 11418 - Clever Naming Patterns

Post by mike21 » Fri Oct 25, 2013 12:39 am

Yes you are right but in the sample output for test 4, the name of the first problem is "Ad".
I thought that the set of possible values for the first problem, in test 4, are "Aa Ba Ca Da". How come that "Ad" is selected? shouldn't "Ad" be allowed as a name only for the fourth problem?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11418 - Clever Naming Patterns

Post by brianfry713 » Fri Oct 25, 2013 9:41 pm

The order of the sets in the input doesn't matter, you just have to choose one starting with A, one starting with B, and so on.
The only solution for this input is:
Ad - choose Ad
Ac Bc - choose Bc
Ab Bb Cb - choose Cb
Aa Ba Ca Da - choose Da
Check input and AC output for thousands of problems on uDebug!

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 11418 - Clever Naming Patterns

Post by vsha041 » Tue Apr 08, 2014 1:19 pm

This is a standard Maximum Flow problem and you can get AC in 1/10th of a second with Edmond - Karp algorithm (augumenting path by BFS). Main thing is to build the graph correctly. Attached is an image of what the graph will look for the first case. All edge weights are 1. You will also need to add residual edges (not shown in the graph). Once you get the flow (3 in above case) just check which residual edge from X', Y' and Z' have weight 1. Most important thing is to note that you can have two words that differ in cases but they should be treated same. For example: fatcow and FATcow are same. I converted all words to lowercase straightaway before creating the graph. If you don't do that then you will get WA.
Attachments
Untitled.png
Untitled.png (193.63 KiB) Viewed 4076 times

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 11418 - Clever Naming Patterns

Post by nbacool2 » Sun Dec 07, 2014 4:07 pm

Could I get help for my code? I keep getting WA when everything appears to be correct :(
GOT AC AND CODE REMOVED
Last edited by nbacool2 on Fri Dec 12, 2014 12:26 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11418 - Clever Naming Patterns

Post by brianfry713 » Mon Dec 08, 2014 11:24 pm

Try this random input:

Code: Select all

30
21
9 UBj iVcVr eJv jbz f XH qiV BcetJ lmIV
7 K jBUWr eNA Y n V zwHOR
13 T sP WKf FX Ju EeVxo lWpl oiNi xC Yi NZtT V ZfWPk
4 hPX W VRs Y
17 Mh KckbF HfuAK av Yhqd LRf e qb jL VjY WL fS tfWh BZd xLPP O nC
10 im ZtQ JeV NAXMI sL Qp k eTWn y bzfR
9 cFUs L vxuq wf y ANxZW Xz E qENd
11 qp wdA YoCp Vna lAGx Jl slxIW nF kmvv OXe xYeCU
17 rvyxz s BS GluZS wknq ey KQaX uai cWfMP JmIrv V QrU YqLv tKH fVHnx OjzPH XtLAU
3 oJdyz nJWy Y
1 s
5 ExPw vwNG zpic yFmJ x
1 axf
5 fq EEOdh KcKO wUz VhLQ
12 dA Gr HBnb sE Zgl yHTX Tb oJzTp F wiRNI LSk xgjtn
4 b n ZMS yPzL
6 NpQJP zV VUK exA W XU
1 jo
6 lRz xD EanTc JgGEn YVHFc WNFc
2 GyAi BBm
23 phwr ozM u Im MV llSKu w gxM yKM bbVd EmD K VG T Nbd jKrRM sonj AoZa Xa ZesR CHkVN qXCrO H
16
11 dvRs gqOyw oqfDL ybi PNze Bv SX Ajdj KZbT vCrF eYw
4 aLKl WjiRB R gNWEC
1 bvCG
24 f UIKPL cxpx PiB aiei Dm sl b XR if Rc nwlj KN euzt wE H yc mgkT T oMQz GZgB JFVH VxN Zpt
16 LnwX S PcId DNnb m nK IbiE xmZC a WpKdU yL zxO OFO vgQJ TYwmz EpRS
6 Oe ma YTSP rQo NBVw juWD
7 jGQ tf bVs wZD RA ez zJa
5 Ks G m jZUiR YO
15 PQ hYG mEbja T Qxsw RgQy B eRFn So xCtjV y JaXV kri CVHxZ akOjg
11 EuQq r X V zVah tB yPy ss WLAeb Qj U
6 nQa XD M ge RC Wcc
7 c MN Ggl YHTV RJls T Q
12 It MQw zfWb xssIA QxYM Gdn V jS T Wd RaJP eKAb
12 hJqf Upnx wzaH s MRZK ENXL trEL CZ Ay iR X rFCr
6 MbBMG TWX z Vpnxp xdV Y
6 gkg vWK tBRf mVqdH r Wsum
12
13 B oDVau wr F dA KkQe v qb RlSH y zN EMDw AJ
21 euRxa sUqOI f gHAp WHmi YLwK vbRZD pO RS Of tLx NVIc XQN ZgjHF UMh q DiX kPYO aytWY CWVHw ME
15 gsx qaZOs tiNn MzkY uyG zWkma SSfR K X rgFmJ oQR W N vQ pZaYa
3 CJc U QEB
24 L PQeVr R Gfijf t ucL DWTGL XZney W QNB CTcTS V SZl nOih EK I YBx f M a O zkZ BTaJ kad
13 DsEb uhJ QiYkr VwJ nD zQPxT FjgQv Plys KFmJm WQG Rkc tsErT CvURo
7 JaSpT wybGh RssW NTuJC ei pQ FX
2 hGj E
19 atH Xssc vF sE Fhh zmCR McEnv YdZ DsQ UDi NhyVh cfH kuihP GUCL QWrpk wH PZpL oztwp T
9 k RH xytsA WAfLU u Zv NN sAr PTWO
11 f XDN W QOhL n oTs VU s kp Te GDpl
19 iX ruu Kuoqm z F o SkAm E WPq PJRLN Ydczn TDgBF m v DafT Cqu QsLBq AxcfE u
22
13 TP pJwDL qZyo Sr yHs FdK E jdGIL UqmQc aHnB ZHxw dlNRj HO
8 Ns JLkc Hr GsBhC WgcwU sIBaJ q E
24 K vL n Yre tQNc LFts I DSA ffQR g BxhEk CfrC Xx wf aW Prvd ZARN eRtC HfL sY U QWwD ryGtJ jiqC
10 aj j XvGlf qdQ Hzez S zwBvb cqvp yDcmu Wu
6 fb z vSZE iSV H cuLCk
3 ck xoUWm h
1 jvrR
10 iPp zUvWY D yOqpg aci x S HPIAc VoqBV QVLmz
5 uo YV WOim Z XeOcc
7 DRyRH Ed HmqpJ zFzYN nE XP Suoe
4 qCoTZ CAKev hIAk wFWG
8 ELaiQ pWzKK CIH qjYeQ VOhNh xJ WKE Gkhb
2 pB YbJBk
6 sR w vX pCP h eJEAH
3 l eATc AeN
2 VHM HJs
12 RHk SmVB QgXoG FXR JB tXDW Ci HmT uJoPg VJ Wv gT
24 O NZ El Jh F r PuHf dQ cS u Irwr Bcxg WVV HXbK LM gg XzI tuFQa yo Z q vgurh sQI a
6 BW nqB jot Qzsw GDWJ Y
5 hre Wb ySS Ps ZGr
11 geQ WdTgV p uAh yR V cgZq hjs X QT zz
12 mYy eAo QB WQAj FkX Ghyq jd RiVY nAs O h SR
2
3 AHTfz CvdWt LMYoD
22 bmy oDhKL h X ZeaM KStrp PvV DZI FNKs vtYn Lcw S c MH Iwdc YDwP gq E UjRnv rWA WSjYd JQ
9
2 DLIfI tqXV
11 gk O lIXR J rbXND Mx yrN Ncep SbEVM w UJC
25 a K o G DZ F Xm SGfAR Vk lN Ezdz te Usot PW znl maiO WBEMR qtx HySLr IOI CfD NvETe Rz Y jYN
5 E Nl q Wpg z
7 cIHc X nh tUC u Y El
2 FB wVEkB
10 iBxJZ NZ GAmXB Sn uXco mgFGs Tfu zT qqD R
22 b VAHNd nQurU XJ JScRC QnetH ULGu eEr hX awmAd Fh Lya pyMZ OeA ylfj r wlL Mr gldKX Szymz C d
6 Hblq zDzo PxLo x gypMa JgSH
16
3 MJdX Xstba s
6 g TDWDb CP VVjg SIF uvafv
5 dPS X T YvzOn Wfr
13 NyF sASkc caP y grxjj q tlXhm W vvh DhaUh rYJ ZRPMJ EQkK
2 cb rdum
8 PDB XxPe fdLl YEEw tTqQ qJjE Le gmzzW
5 fZX S GVG zVs et
3 l Trd BBjrV
6 e dKwy KVJzJ W SCJGF zpG
22 Jp eu ALU ujzHD cL B DGl mBRI F ODEs wbB nV pgo g Sudn lsAb Ql xdo Yvjy vGloH zRPm TBCfu
13 HxXYp GRFo x F CIMs MR ntO Ltjsg P urD iPM jAU TZzg
11 Illv qGWAV WNnnw NelGq EdjHS XYOBQ BfZ pV lCSW Ze Mxo
18 BnmNN kexp zzW uYR V nuon riYJ e tfmDV gZ qEDf fZX SvP yA XIOV DZVi cFUn WsIp
7 AxqNh euKYT UVYtt fBmu lBhBI CeV DCnQG
3 kJMmQ tHggs qbSzY
12 oaq D WPLn MbC s Qsy lKUq N Y iBuIr r G
17
20 kbIJ DQTW cb yyad v ToTZ ju XIf UzOLz pVD L OdAW R ePXE sC zPBq wQVuV QY BgM FluhW
14 C utVP ZNuz SE pKv XNbX Te y Whi B lulcp q DIeSL eOlV
20 Mt EZ kmO BXI qU Y VKa ZS XsQln TpSOg o pgVv RhhS dStA Lat UnE w FZZf CaTG JhC
1 d
11 oMEn L p YQE q ZTmJN ucIp Wdk Xjc RIptR sz
19 GnwKD bqDr zOs fWk LrCQ qS W O Y ch Uvpw PJYq e AQgxC Nu HjM JIscb sZPA rdMeu
2 lUiO zS
20 ah dyC qUDrP Ck bwhw iYPbE WB NwFJL rKLpT J lzt Ez POGKj vb Xuh MT tFJ kexa uM fXh
5 Hb fw M QTbUy WR
9 PoHLQ wb ux YaO TR xChHe RraaA QYV bmQKW
2 fS tBb
6 e ZCX lvy oM seSB wg
15 J xjisn pKtdn b SFlJJ Zr EFny YVQ vhUe WOEB Ugd T RwNx qqUy lz
8 q BX Zsgrn TgE weS R XvP vtf
10 bKvO WjHC uad SnRz vSfTr rdBUP ybQyx tBra X ZtO
5 I Jr OmYP K zZppP
10 nBy Pg SYr JpB zuac kq WRDS rM QV e
11
3 cgOu rCL zfsEF
2 ft u
14 Ba Pp mZy i DSD qp NNq yX Vvl Rbpx Sp Uey lar oMAk
13 KjXo gcvU DkpDX HOHk VXto l O rNGoD CZzp X FAhy b W
1 iWw
21 HF bL rUq wy ypC CIdNU TL VMNq q u iVP lCE G nXKTE fqky SGDqT xurwj D Pkgcp oTj MDNk
7 djXHc WsI iNfF OANIR VkNq UI qZ
6 J NxLkb A wt ZnV b
19 ENjt u q AiJXF YIiYu PSq cHlmW WNS tE MyF O Kp doR jWkE BG L vl zRes xTj
18 ACCkF sWUhF VYQ bpGB x fXtM cw UHK MjPc La PoWe iQmZB R WD kAPuW DvFG GLqf Tkvu
2 GJ s
11
5 D xB pslS qDjbG LPO
11 Gv lAZU pxf QvVr W ZDC NYS KNbcf ov Sgp uPM
2 F dA
20 aLk XU mLi oWkIb KYD RCo Gf ILt UXM lVj Sa pSmD J Whh dnqd VhD CQxca z t yMgSe
9 iI C QKNTH WKXz nzmrk PYwq gJWO MV tMFr
3 EFqP ve kBsYD
6 B J fYIi r qI L
12 j MI zsdS vOyAy K yL D LnKf NoG Rrle xohV GntI
8 KGs vqv MEV UJg Sc oxfO YtC pj
24 hiWon qLt JuwH sPJt Xu AaPex w c DCp Pu RE IfF Vh Ll ZV fQUFk TZt ulu obstS k nFX yJRrD mZq guZr
16 cvJQ D MpKyR kH YysC qMQc uAuwh GvHB Vd RtyS xVzDJ wPOeg nL sqSgx LtT pCN
7
3 eC TL mf
25 gVHtr js PGl QuPL b oMBY mCfa N z XlP ttF k IIcpv uB L YvzUN HloC ffk rX EfWx WAF A cLMj S vjq
6 BIxak YyEz wj nj ZuOB kJ
11 dNx qTM V CRYQm LCnV znCe xDU oc t s I
1 Cp
3 A pCxO R
16 Fd eY R L y OiyU wLkeB hWkBy B viA shay jhl UZGh mssfj Zs p
5
16 dUR OJ iK nk p gG Uae aln hxB vW qGft LsUx K Bz m fCChh
14 Cqc vB PKZY TZE sFr X HjCf WiOBa Rg GmZ y aGcc DChi k
2 auh vkSm
5 BFPFA qrz L UwTnZ aw
8 eIBiL T HLcH Q kZ UQHM MPEo W
8
1 BNQXG
20 aCc MIOe LH pr NqjXW R t qRBU I J Ym zIj U krQ wfp vMcqT cxwzo oVvy sh xHj
13 dmAYC NPRN LWU WuQTf AyXiX HwW rdL p CTC kbnr F v TNDX
15 h Te Yzvl xd UBf c ei LYHiD ry Mdy NBuKq ipkcs A vp ZbFoo
2 fh CdxDn
8 EbR aKqUC QB Ix rw pUPG wTBu TJGam
19 gXqXz B H d kSIRe CHEzr IbwI yNO Q x ZZO p eIceD mZ whvq a FyNv rOKn OAjm
13 CaN JR x RTmo njq q U liO wJ m sP zG oY
22
11 bcE DQ O Y wpvqq xpeY UeV KkZb SZ QVLI ZiN
7 VuDY U z wFES rIYP dI ozZO
8 KIXY xigpM zHuoA OvDMX yUpgp WEx d QjGn
7 QOSFK Xb ZB DWck Wjlbm yiInH OKeL
17 mUZL w Xdboy GeOq BlDh D oIrU sytGA Kc Racs zrqq uuk H yN Tw Q J
11 N TP F ZVEu h M U O s P VzDEd
9 sPdNi O qu zQLFC dq Wl yasLq X kP
10 iP hMYkG OZgKJ ZZxo DXWW gPcl T W X RKLJ
7 CYy ungJN G kGT sZNoj Bfo whQDj
2 Pd aqypA
1 rVKX
7 JIHO KGF XYkF yIGy RRVL qu sOMh
17 l QtDhJ OYVjY rLnY vGbR svLMJ jr kBNl ICN C ag M Dbq H wRmLS zXe Xs
8 UaT We d OD qA xE ZEVO yOK
10 tTaVf BfTSR R Z JsRCh YUt Udlw oNgO whsuZ dH
2 OHM wxMt
7 H qaON vnIw wyNbi RLjCI bEPS Z
22 E LwBkb MAYs vl tvYzb pTnC Rae Uxg ycz wQxPl AWx o HDh JymM fQ ZrLU XFXRd cyujJ kN iL dBY SOY
17 aTkrB VfgI o yDuxx bOZ wCrK qPr Rugk TVd zehgu djCeC MpLsX CbQ UlPnz ifFsn XO g
2 dAy OMC
21 FkRxB HlpY ql inYV ocpSW xKWBy mQlFi s R w dN BWNhq YQnxq To gAKgj vbmBu z A Ko Jrh U
16 G oudrt SAfMr U VxjYD d KzOG BO ji xVW WUpez hF ZZ qM RJab yE
22
4 iNju wwmH X ym
14 n bpa Re d g wfvrW Ewuk j T MxKJ I se FaZLN VNz
6 byhB jaUjz odzdv ZMT m IliQ
23 p JICY neN KVs xrsH mm omBri RUi y BxXC huYP cyp fipu Zok WtQ IGb diIcs V g td sthL e As
4 jKZv ty xX ohSZ
18 hq fEaus Vte MSZG BE d wFfgG s ycBiY Z o Kt i aWV Nd Xvz cU tdawX
13 qwqft E D ktlua vmc RFs iS AoO cQyW xoKi gM ySdR OMRcP
5 UhB ICC ALpYf FBMK NfgR
20 l DMCr o C rZ f gH pX MYvk XluZ V nVJSf AkdAn jyYRq IY BKBW wGSz TTFQt ZkV KtZRA
3 tiFKS ws OMfiP
7 rqmth Xm Z WW yugSX v md
6 GEVM tUdN s rFg wrY Y
1 ewpyb
1 M
6 KfJUs CzSQw ITFl MWW RlbtI Vinfs
3 aoU ZQ Edp
6 cS VZcQI wtFMN z xCa mRgim
16 fc MlYa IZk R TkHD cYTFr oGeV EQO Ymw K zlYiG sUU AYXi wroE d vifW
1 VaizS
16 d SMKpC v cWTS ohc jN rb tEK Kf wX e MiQo ZNhS GFIL YvF IK
8 s y c OE MYLO xYS IFpOr WMALE
2 oV IO
4
7 BPA J GLMUh Nm RuLC U eBYJ
8 cScI jucz fM rlVj ZNmjZ X ywUGm oyVtd
16 AXI WL m JrE FH Xs om dcaq tIYHM LQM B zyHFX uMs hfhbN NWhR KkJr
7 DwHzP mYz ROeS Z n XHlo jj
19
17 DpCI XaX Zkw PuqQ ouXHX tI aARz UjxxI IrHac NlRG fAKFN SU VEN HA WMz rAC q
8 i VXhju W UB Zy Yp TEgJ xqKTo
6 Pi aRu KW yuuv I vWz
17 SlL v HFzp pKJmX xOMB fCL Unw Agg Yywv tBF ZoVxw ISDmu raCnf n K QJkc Wv
4 K ydkC xmQS iOJ
1 FQ
18 bpHW xunx ygLZ qk P WHVp ORV r hEoi AGbD n KLi vH foWWl tFlz i utQb zkQOu
13 lsA Xc OpbA Itj hDy K VN N DEzK wNrxs Sc efWx TwpE
1 QShU
17 oFuG uxr Ta xuLFZ ZMt vMXFt sbeK YIqX a QvBR Nx rQkxx h WnYEN F I KORHJ
11 HAW irsg T UZ RCzQ VkpQ zqRLO X ybH qd wwLL
11 eS oVEVY qq Tx f ni Dc WF rhTaS uvn ym
2 nGCK taJ
4 RYZdM tpJqS vKvT x
20 MOD tvJoU xfAFd kCtm qsf aad h IC Eja OdKL yeUt zSs bbE SqL pN F U dMzn VSdJg RQV
11 jlyUy nQ lpp Z ylv U byDhm s fydEc RPJ HbGlE
14 cTzVV zFJjg QRn HIMlV wuF u t Mb S VbUw ro i N j
13 ayq Y vfodp XDDq QdbOZ rAb I ku TMeoB W zh uozg hSFCa
21 GdDx vT x H N UUGu Oq DV TAiyK rjT ftSQ PsW efV J LlgD wspzT bnaeZ Qui zFT iIZJr YJnQ
4
15 CKT uM DFO OD T IMkr EGh RWIW xnHwi Zf PvSDS wFM Aptv vZb JfZSZ
9 DyzR a xbLfP m jXh i qnen s WUkWz
8 AqK OkY pfL y r Xy mAa Vtm
16 BXe D oKSf RXmE vJuds TjAOq SUY e W jhw hMXC kdTcR n iDdmH P zHNR
3
18 ANx uRSo savgB ves jUg oQqgc zWp PryAZ XJp G F WqmX bpDlF H rDL NCmup dt KkvJm
4 bKhQx rcodo mG vd
4 CnR U hrog idE
14
11 bOJOb SxxJ Oi UCK dtir PePvQ zf FXBP XXDHv tXs WnKZ
14 LK bLB uU o f SJfZN D Tz xLaoQ czDT R wDF jh qNxI
17 iEe qR WV SxO Ps ksQHI UWq XsJBK A C E t RUBi vgwYa yTsZo ofXa fO
9 F zK VVHt XJL Wmv Th y pW uVb
2 MArqd XdGIC
19 Azxch rbq V oxlG Cxu s j QgAC N pIFJi U ylBm Wvitx KwltU zcaJ BEue t xVa FVI
20 hnOG E S oTeA qO ACP iEQIS BFD vT rJS uj yBSM tbWy Dkw JShE zHrsE XosHJ FO Kb WpbTd
18 e Ogdx jH u rg vdK WkIss AF y T qg ZS cEoAv FBq pS NW XbVU SjrH
15 GsXc Yokkg sE w kV VXdh qj TtqDV rQYq ICxO azN Diq C ONUQ j
1 nWiSW
9 J qOn Y ZZV xywTg FGX sRx WSeDv VHtkG
6 CgV YTtta Qop kL wDg uWUwU
6 kj Q ZyxY sa UWlIK w
12 DonQX T SDAlE USST wC on XODD rE vhDKQ Z Pdw YcbMq
5
9 cOx uubDF sTh iE byJC kIPOk JFc xCfkP TmCe
13 bSfa v JVqKf Lb uleuB FBT oAN gE p ky I R wsb
12 Dn rlPpA I xoczn qWSvE mZeN leysg GfJ fU y tQn n
5 aC BCks nTgJ SPPa xlrP
9 e padl H dERgZ znuCR gG WK otD J
22
5 Fi wvp DTdqX UrL J
17 CaUoJ zanCm KGncu dPryv tm bxaq v giO aFV hk ML LV YVpq stEmB WFQs Nun ooS
5 dgHY Mbe uxey Xr Y
1 H
12 LUsU h zhk eOh YqZAC pSt xLyjo AxxY MWHj sH fhU OQBRq
5 T ZFtIH HTEyp AB DRQ
8 STR d MHgD uxLW XGBN ytojZ WMp zz
21 kaz PhCpF Ey GNfs mb ZtF TM FnpQ JC hEB iZ XbV uSL YuRNn vw LKR Oka wvZji AVPpH NKbSP snTi
6 nChn SBii X M wc u
2 mKHK ubiY
7 VmDkA PN gS Xr og adJw wCUo
3 UH zo yAJU
5 joG aWeLv xMZY WbsW DEeD
18 Bgp Xjs SQcyN RgYE AH ZayBn nE VjF KQ iGSQd gBvqw W hp J E fPw Ueg DLy
14 ifO FK Sr px M OpM D xgX HmR wBp jd eYCMt A N
4 aJHRe WYIIV yq UWON
5 q VnpgX XI IO y
19 rqvz jSb HgFy M I Ababy TlB srGY O pkDND E FwCP DHukb le nfRG yw wxDO Zb Xda
3 PkAA MXzip xl
9 oPO yMVAv wN N dM UWW XqFE AJ mmvDy
6 e WPo uKT NrjqF xMr ZYbk
10 gutL rW ldf zSVD Wpv jsV NKfKd urIa EG AX
7
3 Fc Mtl IAr
20 dgi vSUR UNu RCzNo STR wRbVu tH lDFSF yH PjkbS iz oytb xXf KBn qPI JTG NoiUP mjJ zZwp HU
13 EbM WluGU OMV T QVL PxUkV RWKmU lJwe ZTDe VSm JM UoA k
17 akJn iC YdMsa T zO S p HZoeA lt vGL M uPIJN d oB q JVz xtPlm
7 BJF zw CtO hk VqbNj PEeQh trlQl
18 cJxA VI NFpU w qYBS P FWy DG I HJI MKio sjV a YrJ R Ta X kR
13 g Redy vCxW WdBQ N TDAVw S kTFa As IKjj q pyL ls
18
12 P dRmgA zAGat tiIf ful qUHBK Lcb J GJDpp yacb R EIws
3 kHr uRhfW gvY
10 grYoy ZoX tw u hA rcDC qi YI jdp X
9 qY JFF WWi XiFj oqVXh VAC zH S U
3 M NDAb vofhm
4 BJd Zikz YoSR gt
15 IsGm uRl nOch f TQRr Yobk x zSVz WhE O qt JyAK V rvHsp s
7 LN axSlF XINd eSkQS rSJIF u OS
11 nzY jbuPC x tTM Qjt WnjE f OX yQU ZQGz Upqw
8 r oe Nwcfh Y TfQTw JU f z
7 DVqpl zOmyI XAwH EwwH K LH yzCGb
3 FklDT Vw tGhd
14 Hgr Z s F nC IEs QdstZ vrxN YNSiT jFtIX Wdb tbc xB uR
4 oaSCV Z TeQHr XTZhi
8 j zNG XJei v Yl sS trqAy WYi
9 A Ulz JajJP NeInd vFay Zzi WRef q YupQb
18 cE tNI nnS qEOAJ EPIGn o sr Ykef VctpZ x RRVY LKX uUMhQ jUoLq M FCMk HP AJU
4 E qEAyI XEN T
19
13 MRe d ymJVQ xwv ueO kFjRS oaZGQ FdMv Vv wy CUma njtRQ ThV
4 GC D uzGpZ o
9 d uy TZBu FaGgT x vfqX yFa wXOa zrRjg
21 Q LLI gdQh Hwj CQCVB Tqz msnkf Zi Sm KWsN ARdA WFLXr O yljs Re JZD et xHXo uU VBJP N
8 n vW YMol dadfW OnNP z xOels ws
2 oCN UNBDD
10 h xjtJ Fhj tPeaA a vk uQxL ZRtMA Ko duqr
8 cwupC WGVc Y O T k usdbC zj
20 Jth hq S NzR idES t vqr dsoDE F zK u McMD GZE CnJQ ru aqvEU XQvv WbnFb YZ oSyXs
19 E fYeO hsd KxU ZyB gJN jcJp iGZe v aQnYF RnGF Upe WJDIO mSO TR yiPY D oJ cjl
14 LdYO YSc d gwhG ZEvnS TvFtS FOj v mYy cKUtW uudh JDHpR I KLtIt
18 S o WG R CSTQ MaCX KqrjL XwB Z DLcP a YqP vbZ fi ur t no hO
13 r yH TUaAF DenbD W ofQ c aXJ K FjEXY XQf VmYtn UQk
6 IhAxd RaUg w UIMKw Auzsd Fbns
1 Fc
4 PUj ML As LyG
7 KaZuR YgiOf T wL zAg FvLl XBIM
9 aFK dQVU Xuh wrZ vXC TK FO ZGMj uGlly
1 BX
1
25 aZvo Cwe dwAMU WNs NBiRM P sHHAL gQs L me ykH uJ XmxT kqH rVbU V qhnf byJS egU TBqN OiAF jAYFx FY Hq ZLsWe
23
11 ncC wS D gKDMs jt ZGGOw VupmJ I XTz y c
3 Je gMhA yp
5 EEVkU mZtVE Xig nBgu wAjcf
1 L
1 d
1 V
13 kyqS bjNXH wPTGF hqt ge fFEu LQuZQ DK j uQ Nla imk Qp
1 ge
18 aUhpr Sy nIfSQ Qg yYAB DYP vKmR FMg lgxLa JC BXIV Zo iOJU wXrP gv xvc hfLk Ca
3 ONVRW nxkTy Qoo
6 If dqP w xy jMyfS YL
3 WUZC G dM
4 R Hvba J LU
9 pagk YWf mnNjO gEZJK SO wXhUp Nv hE dPsN
7 szX Q w iQcCs YETA DMq bzfQm
2 BenYK wdb
15 uVSK gqM xnz Wn QgPSv nDd i DXRc j vnrfp zE ye LSH Fbr hp
14 fH YcJs SVdrk Dwg CHLQ wVjLI bpW Ln V xjHga Jfn n i zn
9 m X C Vtmf bqOO Qd w lDgJ Zn
5 qG wU dR jecMF g
4 h z lnShc xZw
13 TMs Lj X HFdO ngrh ay MXYKE vn qJh p cw SNmNN Z
1 CUgcl
18
7 aDD XC Z U TlSul PW VWvJ
3 Gy fS QFxv
10 l vaNc X yAerj PQRI TNN UjBD q AC kVaJ
18 mg Xq kvQP iUos qo zLR cSvu Py ddca aGIM Yzdm lr TR sk VvQIt wAoOg nHPk uo
10 Kxqrj wcvfh t Vz sey Afl u PzKf Z qTUH
6 RG wEc LiAS VeoQO SPqnZ Ps
22 b czlK oJfa Nv gx X DWsiY VM PRPI z SlTK Rpjv M AAeQL fiZ W qLRNd JkgVe KP LX YBC UswFt
5 DBKiW Po SjUg yPQSu VEHa
20 JnlNG wn mi rvOhM DPsg ao n qc keaqk LqfeO Tlqc iK UNpI Xa SBH PHrA vBkh Z yZd Fj
8 C pu zyl W QG UaFh TnL AHX
20 OLYj taXf Qq P JhoF uFc L x vNNc S DU RDe wJ Ze kydz IiB gFx aV mr ymqKZ
24 EhSc i BmC HPhl kIg tbOE q zX fZF ma jNBr PijG ctwM o XfFEm uz sEw Ghy redr nesy WNGrF V lSC yT
1 F
16 iWsrt uxdJr lDdC THD qYe PN xcsYd d cb SWPD YUO WZY Vhc kKZm ZrTYk ACLsb
5 pcNu Zbff xWBC tqYy u
4 nUp Cikc Qp dd
9 Q za ACwSY Slt Ds UiqT yQum t w
24 HCoX dojKC ZcV v AaWEJ TAjkc xdUF MKcBo Kch wt jADJ Gqzs BEci NLjaD oh R fHEK L yUEcs Ci iKmav UJXg pob qEoyj
8
20 DOku vb QFy P wMzE O K lLiIU TbYOv bw j yOXCt M XO nJS Z s RvKA uNhxJ Ahpv
23 cmi LH sCbR Mlx KZ pGZdH YR iE txguv zesi WOe GHsY xMg hLA Nc BK R qLT J UoYo dRqY vF OBIU
21 EUwx UrJoF OQ l QHCr jKMlS h P DGn KerhQ zPRBm N SGY xNf fk wk Yy t c mTg Ip
10 gY Tt rHDj P bTt IuYBn Kw sdxul qpG j
19 fZQ Vrl At jHH rE tT Y isnmP QdTZo kgda zlMZ bJMN lfI Dcb SFtb X gpp wunJU UpFqA
12 Hq j k QMR sEVwW rmpOO GcY tp Y p ddiD fC
6 A nP vsqz Mo StKgG QXA
13 BwPPX plgFI vjAl XHTv i MX tq oSrO n sNV jxl Kns Qx
25
7 TPd RPrq YN z EcDEQ pZZKK NjXIb
2 Ys zqnit
3 U iKDl Ea
1 gL
1 rZkOP
1 ALl
10 IRexQ R qQyp AoyiT E nISC trPDN ygxI ZGbsz pTtt
12 FUkD B U N qG Ep XiKs AhjZ ZUqw JKHKX IPd y
4 ntEb BlaK RQQjm e
11 vcn IlAIh UOdxR QL LiP BlTG Z TleyV gvdg YGV E
5 jO eAV XghtB Z BC
17 o u JeZ t BLGGx ZAC F Rdx y Qwb C gnzu P mjmm XINjI hyNd vZ
1 EEfJ
13 dVLIt WT IoNVZ Lv BAQcT jDYey EA FJtt QK rxqP tSgRe nT zXkA
2 cFPt nlIv
4 xgPE t ue Ypw
5 lpHUc y Aas TpG W
23 Kltpa EoN SFNu P h Vc GyhWm Q UEOY ffH Tb mVHs dl BwZA nWm XzR j rOLcF Zb yU iKWml W AqZ
4 PGZM Eb y zBe
3 Btn ZA p
6 HwbT r nQ zNNnh tm Wa
2 qKw nZ
19 mt q nv Aqt xJzY dEva ewGSm J TVyU ZNe iOZNE BxiN UGUzv wIE YOAwr rX gfaVO fuhz PUhDp
13 SS bhvwP jsv nIH u poKR YDX Tsys v fZHRh AiF gdjMF QJ
8 wrvMR IF NO u eOdX bKt y ztG
Last edited by brianfry713 on Thu Dec 11, 2014 1:00 am, edited 2 times in total.
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 11418 - Clever Naming Patterns

Post by nbacool2 » Tue Dec 09, 2014 1:09 pm

Thank you, brianfry713!. I changed my code and got AC :) It appears that I had sorted the strings in their raw unformatted state rather than with first char uppercase and the rest lowercase .

malioboro
New poster
Posts: 4
Joined: Sun Oct 05, 2014 10:52 am

Re: 11418 - Clever Naming Patterns

Post by malioboro » Sun May 17, 2015 7:06 pm

Hi, I'm sorry, may be my question is little bit out of topic

this is my code so far for this problem

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <ctime>
#include <sstream>
using namespace std;
#define ot(x) cout<<x<<"\n"
#define cen cout<<"\n"
#define EPS 1e-10
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define DFS_GRAY 2
#define DFS_WHITE -1
#define DFS_BLACK 1
#define fi first
#define sc second
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
vector<vi> AdjList;
priority_queue< pair<int, ii> > EdgeList;
ll n,t,j,k,i,m,l;
string s[50][50],ss;
vi match, vis;

int Aug(int l)
{
    if (vis[l]) return 0;
    vis[l] = 1;
    for (int j = 0; j < (int)AdjList[l].size(); j++)
    {
        int r = AdjList[l][j];
        if (match[r] == -1 || Aug(match[r]))
        {
            match[r] = l;
            return 1;
        }
    }
    return 0;
}

int main ()
{
    ios_base::sync_with_stdio(0);

    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>m; 

        AdjList.clear();
        for(j=0;j<50;j++)for(k=0;k<50;k++)s[j][k]="";

        AdjList.assign(100,vi());  // 0..25 then 50..75

        for(j=0; j<m; j++)
        {
            cin>>t;  // name
            for(k=0; k<t; k++)
            {
                ss="";
                cin>>ss;
                ot(ss<<" DEBUG");
                if(ss[0]>=97)
                    ss[0]-=32;  // first Caps
                s[j][ss[0]-65]=ss;
                AdjList[j].pb(50+(ss[0]-65));
            }
        }

        int MCBM = 0;
        match.assign(80, -1);
        for (l = 0; l < 31; l++)
        {
            vis.assign(31, 0);
            MCBM += Aug(l);
        }

        cout<<"Case #"<<i+1<<":\n";
        for (j=50;j<50+m;j++){

            ss = s[match[j]][j-50];
            for(l=1;l<ss.length();l++)
                if(ss[l]<97)ss[l]+=32;

            ot(ss);
        }

    }
    return 0;
}
but, I have a problem when I try to input this case:

Code: Select all

1
3
2 a o
2 d c
1 b
in my IDE (Codeblocks 13.12) and I have try it in codechef.com/ide too, my code get runtime error in the last input (1 b). When I try it in Ideone.com my code didn't give any output (http://ideone.com/hpNk5T). Anybody here know what's happen with my code?

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11418 - Clever Naming Patterns

Post by jddantes » Fri Sep 11, 2015 6:36 am

Why TLE?

Code: Select all

#include <bits/stdc++.h>

using namespace std;


vector<vector<string>> input;
vector<int> sz;

int N;
int totalNodes;

bool hasLetter(int index, char letter){
	int num = sz[index];
	for(int i = 0; i<num; i++){
		if(letter == toupper(input[index][i][0])){
			return true;
		}
	}
	return false;
}

int getIndex(int index, char letter){
	for(int j = 0; j<sz[index]; j++){
		if(toupper(input[index][j][0]) == letter) {
			return j;
		}
	}
	return -1;
}

int graph[56][56];

vector<int> pred;
vector<bool> visited(56, false);
void printCap(string &str){
	// cout << "Printing " << str << endl;

	for(int i = 0; str[i]; i++){
		// printf("Printing index %d [%c]\n", index, )
		if(i){
			printf("%c", tolower(str[i]));
		} else {
			printf("%c", toupper(str[i]));
		}
	}
	printf("\n");
	// printf("Done printing it\n");
}

int tabs = -1;
void printTabs(){ for(int i = 0; i<tabs; i++) printf("\t"); }

vector<vector<int>> adjList;
vector<int> adjSz;

bool dfs(int node){
	tabs++;
	if(node == totalNodes-1){
		// printTabs(); printf("Reached end node %d\n", node);
		tabs--;
		return true;
	}

	if(visited[node]){
		// printTabs(); printf("Reached visited node %d\n", node);
		tabs--;
		return false;
	}
	visited[node] = true;

	// printTabs(); printf("Visiting node %d\n", node);


	bool dfs_ret = false;

	int numAdj = adjSz[node];

	for(int j = 0; j<numAdj; j++){
		int adj = adjList[node][j];
		if(graph[node][adj]){
			bool ret = dfs(adj);
			dfs_ret |= ret;
			if(ret){
				graph[node][adj] = 0;
				graph[adj][node] = 1;
				break;
			}
		}
	}
	visited[node] = false;
	tabs--;
	return dfs_ret;
}

void trace(char letter, int node){
	tabs++;
	// if(node == totalNodes-1){
	// 	return;
	// }

	if(visited[node]){
		tabs--;
		return;
	}
	visited[node] = true;
	// printTabs(); printf("Tracing %c from %d\n", letter, node);
	int numAdj = adjSz[node];
	for(int j = 0; j<numAdj; j++){
		int adj = adjList[node][j];
		if(adj <= node) {
			continue;
		}		
		if(graph[adj][node]){
			if(adj == totalNodes-1 ){
				// printTabs();printf("Printing sol\n");
				int index = getIndex(node-N-1, letter);
				// printTabs();cout << "inspecting " << node-N-1 << ":" << index << "-" << input[node-N-1][index] << endl;
				printCap(input[node-N-1][index]);
				break;
			}
			trace(letter, adj);
		}
	}
	tabs--;
	visited[node] = false;
}

int main(){
	int cases;
	scanf("%d", &cases);

	for(int e = 0; e<cases; e++){
		printf("Case #%d:\n", e+1);
		scanf("%d", &N);
		input.assign(N, vector<string>());
		sz.assign(N, -1);
		for(int i = 0; i<N; i++){
			int k;
			scanf("%d", &k);
			sz[i] = k;
			for(int j = 0; j<k; j++){
				string str;
				cin >> str;
				input[i].push_back(str);
			}
			// sort(input[i].begin(), input[i].end());
		}

		totalNodes = N*2 + 2;
		adjSz.assign(totalNodes, 0);
		adjList.assign(totalNodes, vector<int>());
		for(int i = 0; i<totalNodes; i++){
			for(int j = 0; j<totalNodes; j++){
				graph[i][j] = 0;
			}
		}

		for(int i = 0; i<N; i++){
			char letter = 'A' + i;
			for(int j = 0; j<N; j++){
				if(hasLetter(j, letter)){
					graph[i+1][N+1+j] = 1;
					adjList[i+1].push_back(N+1+j);
					adjSz[i+1]++;
					adjList[N+1+j].push_back(i+1);
					adjSz[N+1+j]++;
				}
			}
		}
		for(int i = 1; i<=N; i++){
			graph[0][i] = 1;
			adjList[0].push_back(i);
			adjSz[0]++;
			adjList[i].push_back(0);
			adjSz[i]++;

			graph[N+i][totalNodes-1] = 1;
			adjList[N+i].push_back(totalNodes-1);
			adjSz[N+i]++;	
			adjList[totalNodes-1].push_back(N+i);
			adjSz[totalNodes-1]++;
		}

		while(dfs(0)){

		}
		// printf("Here\n");
		for(int i = 1; i<=N; i++){
			// trace('A'+i-1, i);
			char letter = 'A'-1+i;
			for(int j = 0; j<N; j++){
				int adj = N+1+j;
				if(graph[adj][i]){
					int index = getIndex(j, letter);
					printCap(input[j][index]);
					break;
				}
			}
		}


	}


	return 0;
}

Post Reply

Return to “Volume 114 (11400-11499)”