tag:blogger.com,1999:blog-1953325079793449971.post6674296794557717967..comments2024-09-20T21:17:15.980+02:00Comments on Algorithms Weekly by Petr Mitrichev: CodeforcesPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-1953325079793449971.post-73762566288377511762011-01-28T16:14:35.611+01:002011-01-28T16:14:35.611+01:00If we se the classic dp approach with a small twea...If we se the classic dp approach with a small tweak to have an array(from 1 to 9) for every cell(3d table) and store the number with the lest nmber of trailing zeroes that has the x nmber after the zeroes at A[i,j,x].<br />Is this correct?If so are there any optimisations?Kksnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-61653510957959511302010-06-05T18:29:55.365+02:002010-06-05T18:29:55.365+02:00Hi Peter,
I thought about Problem B, and I think ...Hi Peter,<br /><br />I thought about Problem B, and I think I thought of a solution that I would like to check whether it is correct.<br /><br />For each number, we calculate the number of 2s and 5s that make up the number. Then, we know that for there to be K trailing zeroes, there must be at least K 2s and K 5s in prime factorisation of the number. Therefore, I use DP. <br /><br />DP(i,j) store the minimal 2 and 5 that I can get at (i,j). The number of trailing zeroes at (i,j) will be min(no. of 2s, no. of 5s). Then I recursively do this for DP(i+1,j) and DP(i,j+1) and then I will store the value such that when I add the 2s and 5s to dp(i,j), min(no. of 2s, no. of 5s) is minimal. <br /><br />Sorry, my English is not that good. I hope you can understand what I said. Hope for your favourable reply :).<br /><br />If it is wrong, is it okay if you give me a clue?Tuxhttps://www.blogger.com/profile/04471210805354197729noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-33270492207452412692010-06-05T08:57:41.912+02:002010-06-05T08:57:41.912+02:00Hi Petr, Can u recommend me mathematics book for ...Hi Petr, Can u recommend me mathematics book for necessary for programming?Unknownhttps://www.blogger.com/profile/07395058062933291994noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-81421204364539923802010-05-17T13:53:53.443+02:002010-05-17T13:53:53.443+02:00Que te focka, vete al instituto.Que te focka, vete al instituto.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-58613518251316063382010-05-07T11:59:56.119+02:002010-05-07T11:59:56.119+02:00hi peter,
i m new in technolgy of computer and als...hi peter,<br />i m new in technolgy of computer and also new to the tests conducted online. can u suggest some way how to increase the capability of coding.<br />thnxUnknownhttps://www.blogger.com/profile/15154835317485381019noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-72360870602482138992010-03-12T17:12:15.859+01:002010-03-12T17:12:15.859+01:00non-negative - я так понимаю, что ноль может встре...non-negative - я так понимаю, что ноль может встретиться по дороге?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-75145939693902041902010-03-10T21:12:35.910+01:002010-03-10T21:12:35.910+01:00Hi Petr. Im a new member of TopCoder and I must sa...Hi Petr. Im a new member of TopCoder and I must say your work is very impressive. Can you pls tell me what you studied and any books you recommend. ThnksReginaldnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-31787321093708511512010-03-04T03:14:02.776+01:002010-03-04T03:14:02.776+01:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/02784689319173863123noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-5598753052875505682010-03-04T02:40:59.067+01:002010-03-04T02:40:59.067+01:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/02784689319173863123noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-14247251285080676112010-03-02T16:09:10.919+01:002010-03-02T16:09:10.919+01:00hi..peter. can u give me clue about a problem
how...hi..peter. can u give me clue about a problem <br />how to find the first k digit of n^n <br />where 0<n<10^9<br />plz provide a clue...black diamanthttps://www.blogger.com/profile/06960183626493574668noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-34088169912829159932010-02-26T04:11:53.781+01:002010-02-26T04:11:53.781+01:00Never mind, that isn't quite correct. Need to ...Never mind, that isn't quite correct. Need to do something about the non-trailing-zero part of the product for partial paths...back to the drawing board.Abhishekhttps://www.blogger.com/profile/05112275378695185348noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-49162325778045181352010-02-26T03:58:58.690+01:002010-02-26T03:58:58.690+01:00Can't you just use the traditional DP approach...Can't you just use the traditional DP approach for problem B? Store each value as N(i, j) * 10 ^ Z(i, j), where N(i, j) and Z(i, j) are integers. Let M(i, j) be the minimum number of trailing zeros following any path to (i, j). If N(i, j) = 0, then C(i, j) = 1 (total product is 0, i.e. one trailing zero). The number of trailing zeros following any path to C(i - 1, j) and then to C(i, j) is the number of trailing zeros in N(i - 1, j) * N(i, j) + Z(i - 1, j) + Z(i, j). There is an analogous formula for the number of trailing zeros from C(i, j - 1) to C(i, j). Then you just fill the DP table, storing backtrack pointers.Abhishekhttps://www.blogger.com/profile/05112275378695185348noreply@blogger.com