tag:blogger.com,1999:blog-1953325079793449971.comments2019-05-20T18:15:35.918+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger707125tag:blogger.com,1999:blog-1953325079793449971.post-64939760220098556942019-05-20T18:15:35.918+03:002019-05-20T18:15:35.918+03:00Sorry, I did not see that it had already been answ...Sorry, I did not see that it had already been answered below. I will try to explain for case k = 2, to make it more clear.<br />--------------------------<br />Here, if gcd(2, n) = 2 (which means n is even). This means 1, 3, 5, 7, ..., n-1 are of one colour and 2, 4, 6, 8, ..., n are of another colour. So, total we get 2 ^ 2 = 4 stripes ( we have 2 colours, black and white).<br />We can see that if we take any stripe out of these 4, and rotate them by 2 we always obtain same stripe.<br />--------------------------<br />Now take gcd(2, n) = 1 (n is odd). Here, 1, 3, 5, ..., n, 2, 4, ..., n-1 will be of same colour. So all will be of same colour. So total there and 2 ^ gcd(2, n) = 2 stripes.<br />--------------------------<br />This way we can take any k (as done here) and show that no. of stripes which remain unchanged will be 2 ^ gcd(k, n). (read the blog for that part). I hope its clear.satyabrata1729https://www.blogger.com/profile/15533348898735919812noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-13622057738577652982019-05-20T18:05:40.960+03:002019-05-20T18:05:40.960+03:00Indeed, gcd(0, n) = n.
We are finding the number o...Indeed, gcd(0, n) = n.<br />We are finding the number of coloured circular stripes which when rotated 0 times, remain unchanged. When we take any coloured circular stripe, rotating 0 times it remains unchanged. So total is 2 ^ gcd(0, n) = 2 ^ n.satyabrata1729https://www.blogger.com/profile/15533348898735919812noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-30664075216640979402019-05-15T17:32:15.538+03:002019-05-15T17:32:15.538+03:00So what you say is 548354 smaller than 11111111111...So what you say is 548354 smaller than 111111111111 ?Unknownhttps://www.blogger.com/profile/01497797178619330077noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-86673740604070551902019-04-30T16:32:31.464+03:002019-04-30T16:32:31.464+03:00Hi I'm currently studying problem solving prin...Hi I'm currently studying problem solving principles such invariance, induction and so on. Do you have any suggestions on what are good books that can be read which are related to these concepts?BLAGGOThttps://www.blogger.com/profile/07084234288920897635noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-78516674144566448152019-04-15T15:13:41.522+03:002019-04-15T15:13:41.522+03:00hey Petr, I tried like 5 hours but couldn't fi...hey Petr, I tried like 5 hours but couldn't figured out, how you manage to get the test dialog in your intellij ide. I found it very useful, please help. ThanksUnknownhttps://www.blogger.com/profile/15831626239035385662noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-19438868291755274822019-04-04T19:06:02.835+03:002019-04-04T19:06:02.835+03:00you are the best coder , can you make video tutori...you are the best coder , can you make video tutorial pleaseAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-20349805397298086792019-03-12T07:13:02.759+03:002019-03-12T07:13:02.759+03:00An observation is that, if we generate another int...An observation is that, if we generate another integer x' by reshuffling decimal digits of a non-negative integer x, we have f(x) = f(x'). For example, f(123) = f(321). The order of digits doesn't matter when using a knapsack-like DP to calculate f(x), so if we only consider 0 <= m < 10^17, the number of distinct DP states should not exceed C(17+10-1, 10-1) = 3124550. With some observation mentioned in analysis, it is enough to only consider these m for building a considerable state space. However, it is still hard to explain why the number of states can be minimized into quite a smaller number than the number above.Jingzhe Tanghttps://www.blogger.com/profile/01861366645446189606noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-26960939026611654372019-03-12T00:54:05.209+03:002019-03-12T00:54:05.209+03:00Intermediate sums can be arbitrary, but it's n...Intermediate sums can be arbitrary, but it's not hard to prove that we can always obtain a number between 0 and 9 in the end.Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-66780953927446428332019-03-12T00:18:17.749+03:002019-03-12T00:18:17.749+03:00Is f(x) in every moment is less than or equal to 2...Is f(x) in every moment is less than or equal to 20 ?dalgeroknoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-89449482806901778292019-03-09T01:18:16.288+03:002019-03-09T01:18:16.288+03:00wow , what an amazing confidence you have . Just b...wow , what an amazing confidence you have . Just by seeing the submission you reached conclusion that if someone is able to solve that problem , then i could also . <br /><br />great . Unknownhttps://www.blogger.com/profile/18409198011346767092noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-82594075861128796112019-03-04T23:13:20.303+03:002019-03-04T23:13:20.303+03:00niceniceashutoshhttps://www.prohindiblogger.com/2019/03/how-to-fix-broken-link.htmlnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-69619063332451840722019-02-27T16:07:53.098+03:002019-02-27T16:07:53.098+03:00Yes, I was alone. I guess the problems suited me r...Yes, I was alone. I guess the problems suited me really well, last time I tried to do Open Cup alone I think I ended up outside the top 30.<br /><br />One advantage that I had compared to your team, for example, is that I had seen the scoreboard from the Beijing camp, so I knew which problems are easy.<br /><br />Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-37710746931903727022019-02-27T15:47:59.065+03:002019-02-27T15:47:59.065+03:00Is the gp of Bytedance your solo play? No offense,...Is the gp of Bytedance your solo play? No offense, I'm just really impressed by the performance.xudyhhttps://www.blogger.com/profile/07975820600036974310noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-13005016000014046392019-02-18T17:57:19.001+03:002019-02-18T17:57:19.001+03:00nice
nice<br />Unknownhttps://www.blogger.com/profile/12635708429243729033noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-13693905931506052902019-02-18T04:00:45.107+03:002019-02-18T04:00:45.107+03:00Nice post man. Nice post man. Krishhttps://www.blogger.com/profile/07248542701423975569noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-20692578993162785152019-02-11T05:04:33.246+03:002019-02-11T05:04:33.246+03:00No problem for this week :(No problem for this week :(gagannagpal68https://www.blogger.com/profile/05761487952049924233noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-3270566053398806842019-02-04T22:59:33.801+03:002019-02-04T22:59:33.801+03:00Looks good modulo small details!Looks good modulo small details!Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-34554426550493642092019-02-04T08:53:29.296+03:002019-02-04T08:53:29.296+03:00Hi, I have a solution. Please try to give it a loo...Hi, I have a solution. Please try to give it a look.<br /><br />Check if parity of count of '1' in target matrix is same as that of source matrix.<br />If it is not, answer is clearly not possible.<br />Now, let diff = courn1(source) - count1(target)<br />We need to destroy diff number of '1's from source, if diff is negative. ans is not possible.<br />Strategy to destroy 1's seems important. A greedy strategy(Destroying right bottom corer 1's could be wrong). <br />Let's think after some point. We can create a graph from source to target 1's. Edges from source 1's will be to all target 1's which are in bottom right. Just a max bi partite matching would tell us. Now, We will be destroying redundant edges. This can take 9*47/2 = 212 operations in worst case.<br />Now, In gauss elimination fashion we can move our 1's.<br />This can take 9*47 = 423 moves.<br /><br />Total moves = 635 moves.gagannagpal68https://www.blogger.com/profile/05761487952049924233noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-68489497109852874392019-02-03T11:26:56.294+03:002019-02-03T11:26:56.294+03:00hi i am new to this blog could you please tell me ...hi i am new to this blog could you please tell me how should i proceed to learn algorithm and data structure.Also i it would be better if you could tell me how can i perfect them?Unknownhttps://www.blogger.com/profile/12048406708116046023noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-12108991592431827882019-01-13T13:38:48.278+03:002019-01-13T13:38:48.278+03:00It's a bit surprising that 9 years have passed...It's a bit surprising that 9 years have passed since I set problems :)<br />Makoto Soejimahttps://www.blogger.com/profile/04015679813508313744noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-34958969164067298512019-01-13T10:06:02.204+03:002019-01-13T10:06:02.204+03:00I don't, so I've never tried to use any to...I don't, so I've never tried to use any tools for it. Consider searching or asking on Codeforces directly :)Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-57499389511063857552019-01-11T15:53:23.638+03:002019-01-11T15:53:23.638+03:00Petr, do you use Visual Studio for codefource comp...Petr, do you use Visual Studio for codefource competitions? Is it possible to create some tests in Visual studio for the program by setting inputs and outputs like it work in Idea?Олег Игнатовhttps://www.blogger.com/profile/01696849881143325134noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-46302063896248546282019-01-11T15:51:47.494+03:002019-01-11T15:51:47.494+03:00This comment has been removed by the author.Олег Игнатовhttps://www.blogger.com/profile/01696849881143325134noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-6743149909235348872019-01-08T12:24:36.995+03:002019-01-08T12:24:36.995+03:00Wow, nice spot! Here's a link for the TopCoder...Wow, nice spot! Here's a link for the TopCoder problem: https://community.topcoder.com/stat?c=problem_statement&pm=10758&rd=14154Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-69900244094693310252019-01-08T11:07:45.319+03:002019-01-08T11:07:45.319+03:009 years passed. The hard of SRM 472 became B of Co...9 years passed. The hard of SRM 472 became B of Codeforces. :(Unknownhttps://www.blogger.com/profile/07651003745735072591noreply@blogger.com