Connection Status:
Competition Arena > Stitch
SRM 231 · 2005-02-19 · by lars2520 · Simple Math, String Manipulation
Class Name: Stitch
Return Type: String[]
Method Name: stitch
Arg Types: (vector<string>, vector<string>, int)
Problem Statement

Problem Statement

Many image editing programs have the ability to stitch two images together to form one larger image. In this problem, you will be given two images, represented by String[]'s. Each String[] represents a bitmap, where the ASCII value of character j of element i represents the color of the pixel in row i, column j of the image. Your task is to stitch the two images together. Specifically, image A goes to the left of image B and overlap pixels from the right of A and the left of B overlap. To prevent any obvious artifacts from the stitching, you want to gradually blend the stitched region from image A to image B. The ith pixel (indexed from 1) from the left in the overlapping region should have a value of
((overlap+1-i)*a+(i*b))/(overlap+1)
where a and b are the values of the pixels from A and B, respectively. Hence, the leftmost pixels in the overlapping region should have values of
(overlap*a+b)/(overlap+1).
In all cases, you should round the pixel values to the nearest integer, rounding 0.5 up.

Constraints

  • A will contain between 1 and 50 elements, inclusive.
  • B will contain the same number of elements as A.
  • Each element of A will contain the same number of characters.
  • Each element of B will contain the same number of characters.
  • Each element of A and B will contain between overlap+1 and 50 characters, inclusive.
  • overlap will be between 0 and 49, inclusive.
  • Each character in A and B will have ASCII value between 32 and 126, inclusive.
Examples
0)
{"AAAAAA"}
{"JJJJJ"}
4
Returns: { "AACEFHJ" }

First, line up the two images: AAAAAA JJJJJ Then, blend the overlapping region: AACEFHJ

1)
{"14ABCD",
 "25EFGH",
 "36IJKL"}
{"ABCD14",
 "EFGH25",
 "IJKL36"}
4
Returns: { "14ABCD14",  "25EFGH25",  "36IJKL36" }
2)
{" 32ygfd",
 "3uh53G:",
 ")O83gh3"}
{"hsd$*(PH",
 "3G:$)(*P",
 "gh86$PBB"}
3
Returns: { " 32ygmd$*(PH",  "3uh53G:$)(*P",  ")O83gh76$PBB" }
3)
{"A"}
{"A"}
0
Returns: { "AA" }
4)
{"  "}
{"~~"}
1
Returns: { " O~" }
41)
{"xe|G>JGQ(v'&Ph4uZVMwC~+fGn<.}-J*GWYN*u8#.iBTNj,{@o",">)9<^#hQq8p4U]j$nP9UTL1Obec~7&->6bkQ+cy}N6O!cPK|~r","lzmbQs/mUvZAI fx!s[h\"[v2d&oiJ?8A(Xm6K)&75bVB_IC5d(","9RH%iEfe\"s_1/!*R`JR~\\lW.}&uO.(4HW*wHk8Vy-Di~Cf9_H=","AA9pb0~pGl P/.7-.+0;.@6LB)/;e:1eD*IHXP<]h)_Y/~;!h_","\"c C`'_sn>XEVl[Q\\T_xPh]=0]K0B&'eawp]tqZD{fC7Fk]4}O","?fXx3L~`#D]a-<$by1te4ifq6[*\"++@#]f-:=D#?'0d4N6,\"h.","G7Rwn/~BJv?X`edDQt>\"LfZ'WD1\\%4zRTwStfC4K;aK","=n4CFj*Ug9[<@bOxE_W.xtlixEI;DT]V @HdIfm\"}^*ro`pYl@","B.m/'Y%!:Ie(k@PPL|/R,mO+dxq)Ob|~!DTb8\\O+>w%'XcU_e1","8bntJZ,4TJmuv","*|54]SLu5ph3wNC_uxD-aUdO^PF_f4JvsAYYaDIFZ<8|mXT133","y!~n9~n'uJ&Dc:zREu*\"jlw8f/KDD;F gvnQ+EhTF&","Vz\"+%1d!lh5dt5qL )W1YH6hp*1","T>U^\\QWm`p?y#Z[?JSVQR|ATE6;(M1ERgX8v&m5-Js|&JTCum!","\\L17]u1QTCTJTGDsgUVIYelki;sIj=+M#&<+_a+56~FR]_w(A;0#O2pExT-$-k|  [m,N^","?~_/qo&1qBrtc$pog2aynnab\"W N;*3k8L|D","o:Kw{'fTqe1JosmUz_3xSd'R1 .Bz%Uo}>r6,dLSTe;Cm&0[*<",">-CFRC+){oPL1-8%jh(-d>/y6!={0*Dm%)C>@hj'jFZR$}3-7'","zKW}4En_B@P_Ro)zEh\"4&(#8kX|>PPj/lOih9;CK7)tQzb~1KB","(';2%R$ 5;&zq|bI2$%KGGaQzzW:^']RLKO#`U&:*nhg@L $/J{elO. 6m}~j]a","yySRQd8BBvWVA[<~ey=64Y({$a0cOd2g7,Kw?2{87Y(t=!GwM;","t`V0UuJ%\"tOKQS[mk<:$F_UP~T&a:aMRT8bD}P1gO'X>O{*'>2","I9&$;8<@90iVf}%oLRpn!]od]f1pKk'\"\\4*TN)1 XV2kMfy_;p","Ks`T/{N3Df;SU&Dslaqsr[ZvY0&Z@EUT5J+DY}EI=o{OtUk*aN|b-El*8$X#(c4N+&RI8s-&)-","3JZTZD7Ftw[?wmgJR]3HTjY]+9uS`KNFa=3FcaVr2(TSh%-9O:HJxQa8^X38o3u4xO&aVyb\\BhA hnOwK|DLwar^mE]S`",".6~)_pA~BTB =Ko#X}Me'FFM%@\\3xH!`T-[bpFQ`uXJPl?FpU%","`1/&z_gm6R>mA?A_KG4QIva1*e4j1P%6\"\\(XF~c`<8VO#IB;Y*","'MB3T[mAtHqXxZ@OmPBO*VR9pneo/6lv
{"4o4gd;_gIKl6}tJ1v_nc4|1`phfKJA{I7","q.e}>PIt[m|GRZ2~G%YWmT`.U`sjnJ@S7][e,vzo[s~q>)ijLs",">@dhe4NOf FT3+H.}R#uJHUF U\"O1` }_Yvz <3wPz+mxU}1eY","*f`~_`({To^o.fpc-v{~:xe,iY|O\\moM+BE%O5}Yp_9pK()9DQ","4dj>:-ye;:vnCD!hAo&pE1L)Zwyd-L#6w2ewt\"LM?t!Ln.vK*m","H\\e5D\\%#B>boC>VrL_oS^@Uo%91a_6LK$l9=):O~Pc\\6F<1-,'","].4WDQOM@K{Gh+a_c,=tuNaVw_^699p.(_]\\4v2X=?l(j}=-8U","{WFCt^D%bEu^0\\C#Dq, 6H`D\\dQ$J6qpI*mUbUMg>N^E#-OWZW","]4q?s\"y4IQ;dByU}.;V67S_EY.5\"OFOM1Lr!i::~p~Z==bUp1*","istixM9Z?bJ1Q^Qm;>%;yOS~.^'E\\~5$rfH4(4U(f@ 7dbj*1e","fu*z[J#nX}y1}]f-\\1yo[es~N$E`u+-}wO?IZTPz+ev*P(I>F*","Hlob~I!ejv%il'-&w#oBi)xYh{200n1lEWV=)+m9hg!_qa7IAb","l{ 2q&oy|Z8O~T'05vswm[\"5@m4l|J^i5:hEwW{$Sk?rUG]ykf","I')\\uY%ccmchsElPES[H/0f*UT];2+sO5juctr%J#lGLIgX/^o",">D.|-xrmxrbmO!O+V-gz4KnB4*lyQi_hX`lAB[6u\"h_Rc\\1b_c","99VyQ[Lc_bw+~=;h/[#\\<$i+J+NH@68XcR&-vXZ'Zu[2q&aGy7","F\\RsqoQWFHw=Y9b*RITz*?Vu&bT'OX9M:@4TitAoE` |]I'k3o","@-N_7K[4;Eqaj0'o`K'F/gI(M-o?)o4c;cAxh^D#x,'G:koE8H","_(:r-/@A<6EK#sc*Ox!QpH*_P6ddN\\(cylNHXo)(hRM{IXkq}O","EA+kI20O@=6Pn9Q)oAn`%C)d2irhO1@o1x:9","D~GS%I^0cq;2*DN\\jthA<@1,5:UEnTj,f4Zj^*qnJS[y0;V+%Y","bGQiyFx/r6tw2~0XvB5&3t\"dA+sOgEzJ;tp`9cwBKO|iXt/#@K",">XVi!fh-_VBW*uSA|](}G~Rs{S*K]$8X@qJx","37I2To|O!N_1fafRkRSchi?7#C#JnKNxh|6GnY9sIup,yBo$L'",",{hnx`.An4|Iszuy&8S-B!y!qrVho`#?\"|,Q?S1lpX%L3)\"e!}","_$*\\PXZ`+W(Ey\"nsO\\_6)5PkJDm~~HH+c]w9JOp/uV\"_t!u,U;","&}M-qR$GmR2&&e'-~x_|[CE^21E","Yg95),h*clq\"R!%jdOurr7D-H*-6[W`Ga=7T=!|:4)d@X@y\\2\"","Q/e4EIw$}/\\P$G|L#jrD To\\Av&n]+lp_{5!7s; PWR|$(?ms6","SP,TKk-Ly98w/X34[\"_,0CXH\"6Kmejv8?sALf|,P-%:B*EP\"9v","'f!`rA/W:SFb=_`Icm&QdL5qqc>HSXF4nB+}W!YCn~Qc`t'mau","*Jx2O~w`Tq/d),+IJF[?nnws OG]1/3a}mu;h:[gD;gD_6@8WZ","g-WrSXnZ7SA~A\\Npkm|swjQ&q?9>p?;5 :T^g&X/O2}WunZk>U","t>w-l|cDX25,T++\\w.,mEml\"!2Q\"!@Q{HbpEVHGt6C%AukF 7_","7C\"wBn/-d{'&oQ+&XGuWl,i4/0C_QmW.xeTD|}]eFab-'q7pk1","{dU9UUHPmEOH>BJ>,T0B8YN4i@-'#Qe`WFGuYgop`|!Pg7O!;N","Dp4BqtP/n1ZGQje*zl]Y862)p&0d!P3m3[6J>G#(BA}[82$VD5","^?^%'/2D_wyksPQ3HC-R>H.U^1G:hYnaJUVL`TZ]Pjg*}D*pC,","D,2a.}N75|&Xw*]@M/SLrJ/*owXmT-'w%6N$EKO'tp1ekjD\\h[dRSk\\^fE}","*7]6Qp$^4tm:f,o\\6:R@TUQg$5-M#z1d^29Ct>gXK{,-u`zLv "}
25
Returns: { "xe|G>JGQ(v'&Ph4uZVMwC~+fGl@/z8G8QRT[0yX:0rVg^>p:`phfKJA{I7",  ">)9<^#hQq8p4U]j$nP9UTL1Obe_{B+5AI`lc8[hRlA2JZgSc4V`sjnJ@S7][e,vzo[s~q>)ijLs",  "lzmbQs/mUvZAI fx!s[h\"[v2d'khOF7E4]O=O.)A1tS+pJGQH U\"O1` }_Yvz <3wPz+mxU}1eY",  "9RH%iEfe\"s_1/!*R`JR~\\lW.}&tQ:3>?b9tQm3_tN5r|pBnd.gY|O\\moM+BE%O5}Yp_9pK()9DQ",  "AA9pb0~pGl P/.7-.+0;.@6LB)3@_:0jN0C[bJ@:h9j4aP3G.Zwyd-L#6w2ewt\"LM?t!Ln.vK*m",  "\"c C`'_sn>XEVl[Q\\T_xPh]=0\\L6@,3TNe]_rZKNuUV`PaDQp'91a_6LK$l9=):O~Pc\\6F<1-,'",  "?fXx3L~`#D]a-<$by1te4ifq6[*$20D/XY9VBV'SIQ=;kiIZWt_^699p.(_]\\4v2X=?l(j}=-8U",  "G7Rwn/~BJv?X`edDQt>N^E#-OWZW",  "D$nyyr!kr'gj r6C)qKjn[Y_cqVn7I/u^I8\\WYVXlC5[@:QYGY.5\"OFOM1Lr!i::~p~Z==bUp1*",  "I>\"LfZ'gP^ATGnf_csyN$E`u+-}wO?IZTPz+ev*P(I>F*",  "U^PDWy5,T!ePiJ5-R{\"6\"`RdYbHcLE-SkFe;JV1I.o=mNb)pYi{200n1lEWV=)+m9hg!_qa7IAb",  "-hTG)-`xO8w]^-nx{'MB[Y'5IwtLfV-QYcl@EiLS]S5KRl;rS0p?L8`C0g0J+NH@68XcR&-vXZ'Zu[2q&aGy7",  "B.m/'Y%!:Ie(k@PPL|/R,mO+dvo.Ueyr2EOk:[CK2_>Hr5BWt&bT'OX9M:@4TitAoE` |]I'k3o",  "8bntJZ,4Trc/F*`2irEs.(`kh7\\.hO1@o1x:9",  "Vz\"+%1d!lh5dt5U^\\QWm`p?y#Z[?JSVQR|ATE5>*M9P\\mP=_Mr6QU_GT?lW6Og#!>SA|](}G~Rs{S*K]$8X@qJx",  "\\L17]u1QTCTJTGDsgUVIYelki;nIaA;Z1$CAJdHQJoQKacb>:&C#JnKNxh|6GnY9sIup,yBo$L'",  "bY|D0iuv7VgCJ}Dgz\\sbnf\\JpM\\6:38@+Q^a_Ylpj6CG?L\"o'prVho`#?\"|,Q?S1lpX%L3)\"e!}",  "R_muM{@|S}x*Xwe29j{t&S,T,f-ug",  "Dlln.8rPybpmF2AWLo[9ft/u!4?-I7X5b[b(@M>Sx5gO3m>B8KG5.2w`GVrK=`Xkbrq=xNH!\"`f",  "[]jgDLxwx[kH]%!$(eLOHzA\"6~FR]_q0BCA8J3TMZe>9CVLba31W;|e4g\"

_/qo&1qBrq_(en[EVab]maRe B`Y$Pc9xdaw.nDC]4u!Umkh62<4D.0>21E", "o:Kw{'fTqe1JosmUz_3xSd'R1\"2Ao&LmcKpO'[58bdIhqc6G-H*-6[W`Ga=7T=!|:4)d@X@y\\2\"", ">-CFRC+){oPL1-8%jh(-d>/y6#:LTH#6Kmejv8?sALf|,P-%:B*EP\"9v", "(';2%R$ 5;&zq|bI2$%KGGaQzwX7^5WIOEQ2aIEP=gk8M_E3mnc>HSXF4nB+}W!YCn~Qc`t'mau", "'6yc*\".LVOgkJ?dj-Eqod?#;k,f`qsty4OU,C&72]BM]Jccwt#OG]1/3a}mu;h:[gD;gD_6@8WZ", "Cb,cOke_Q&q`)j=lO.%\"UfE2kN\\fp?;5 :T^g&X/O2}WunZk>U", "G|@a#BwN| Qpr0?WvG#(BA}[82$VD5", "Ks`T/{N3Df;SU&Dslaqsr[ZvY2(ZDY}EI=o{OtUk*aNv\\5Ap48*f$>m/W8@:PGrF.*lwXmT-'w%6N$%-9O:HJxQa8^X38o3u4xO&aVwbU=g>$[X[iBUBX_hwjNnmy)T?YT4rV7DWQrr~S}z5R[XL~!8", ".6~)_pA~BTB =Ko#X}Me'FFM%@\\9oE5RU0^Zp_YjG81E?][email protected],:Il*GlM8x]k=K_.mA?A_KG4QIva1*c4k5R,?%dCMIxUk=ANO6c]WP1JK P>'tp1ekjD\\h[dRSk\\^fE}", "'MB3T[mAtHqXxZ@OmPBO*VR9pkam0;m`FSNsMR)[SI9PFLWLf%5-M#z1d^29Ct>gXK{,-u`zLv " }

Submissions are judged against all 59 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Stitch with a public method vector<string> stitch(vector<string> A, vector<string> B, int overlap) · 59 test cases · 2 s / 256 MB per case

Submitting as anonymous