{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLet \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e be two strings over some finite alphabet \u003ci\u003eA\u003c/i\u003e. We would like to transform \u003ci\u003ex\u003c/i\u003e into \u003ci\u003ey\u003c/i\u003e allowing only operations given below:\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cb\u003eDeletion:\u003c/b\u003e a letter in \u003ci\u003ex\u003c/i\u003e is missing in \u003ci\u003ey\u003c/i\u003e at a corresponding position.\u003c/li\u003e\u003cli\u003e\u003cb\u003eInsertion:\u003c/b\u003e a letter in \u003ci\u003ey\u003c/i\u003e is missing in \u003ci\u003ex\u003c/i\u003e at a corresponding position.\u003c/li\u003e\u003cli\u003e\u003cb\u003eChange:\u003c/b\u003e letters at corresponding positions are distinct\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eCertainly, we would like to minimize the number of all possible operations.\u003c/p\u003e\u003cblockquote\u003e\u003cb\u003eIllustration\u003c/b\u003e\u003cp\u003e\u003c/p\u003e\u003cpre\u003e\u003ctt\u003eA G T A A G T * A G G C\r\u003cbr\u003e| | | | | | |\r\u003cbr\u003eA G T * C * T G A C G C\u003c/tt\u003e\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\u003cb\u003eDeletion:\u003c/b\u003e * in the bottom line\u003cbr\u003e\u003cb\u003eInsertion:\u003c/b\u003e * in the top line\u003cbr\u003e\u003cb\u003eChange:\u003c/b\u003e when the letters at the top and bottom are distinct\u003c/blockquote\u003e\u003cp\u003eThis tells us that to transform \u003ci\u003ex\u003c/i\u003e \u003d AGTCTGACGC into \u003ci\u003ey\u003c/i\u003e \u003d AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003cpre\u003e\u003ctt\u003eA G T A A G T A G G C\r\u003cbr\u003e| | | | | | |\r\u003cbr\u003eA G T C T G * A C G C\u003c/tt\u003e\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eand 4 moves would be required (3 changes and 1 deletion).\u003c/p\u003e\u003cp\u003eIn this problem we would always consider strings \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e to be fixed, such that the number of letters in \u003ci\u003ex\u003c/i\u003e is \u003ci\u003em\u003c/i\u003e and the number of letters in \u003ci\u003ey\u003c/i\u003e is \u003ci\u003en\u003c/i\u003e where \u003ci\u003en\u003c/i\u003e ≥ \u003ci\u003em\u003c/i\u003e.\u003c/p\u003e\u003cp\u003eAssign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.\u003c/p\u003e\u003cp\u003eWrite a program that would minimize the number of possible operations to transform any string \u003ci\u003ex\u003c/i\u003e into a string \u003ci\u003ey\u003c/i\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input consists of the strings \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e prefixed by their respective lengths, which are within 1000.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eAn integer representing the minimum number of possible operations to transform any string \u003ci\u003ex\u003c/i\u003e into a string \u003ci\u003ey\u003c/i\u003e.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10 AGTCTGACGC\r\n11 AGTAAGTAGGC\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}