tag:blogger.com,1999:blog-1953325079793449971.comments2019-07-04T06:35:04.042+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger715125tag:blogger.com,1999:blog-1953325079793449971.post-47376635402081046412019-07-04T06:35:04.042+03:002019-07-04T06:35:04.042+03:00:(:(Miguel MinĂhttps://www.blogger.com/profile/09077738777924605133noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-41016257507275554842019-06-26T14:03:53.405+03:002019-06-26T14:03:53.405+03:00and conquer the world of programming.and conquer the world of programming.Vivek Patel (vivekout)https://www.blogger.com/profile/18148440622931969237noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-105243474798450622019-06-09T16:18:30.224+03:002019-06-09T16:18:30.224+03:00Given that we're already reaching the limits o...Given that we're already reaching the limits of floating-point types with values up to 100, at this point I doubt that solving it with values up to 1000000 is possible at all. Do you have grounds to believe that problem is solvable in those constraints? (for example, did a well-known problemsetter set it?..)Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-53311485504335542902019-06-09T07:54:30.801+03:002019-06-09T07:54:30.801+03:00https://uva.onlinejudge.org/external/131/13143.pdf...https://uva.onlinejudge.org/external/131/13143.pdf<br /><br />But can you solve this harder problem? Power Towers Longest Path in Graph problem?<br />Lucashttps://uva.onlinejudge.org/external/131/13143.pdfnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-48732240742411690672019-06-08T22:53:25.539+03:002019-06-08T22:53:25.539+03:00Neat! This is a blast from the past. I really li...Neat! This is a blast from the past. I really like your Expand idea to determine how many "interesting" tower powers there are.<br /><br />You're right that the leap of faith is what kept this in a Practice round instead of a Finals set. Realistically, solving this in a contest would require you to estimate roughly what level of precision (and what KIND of precision) is required, like you did with your logs of logs. But if you submitted and got WA, it'd be hard to know whether a) you've got a bug, or b) there's some mathematical construction (or coincidence) that produces tower powers that come closer than you'd expect.<br /><br />I'm something of a closet fan of Googology, the study of big numbers. In addition to this problem, I also wrote an MIT Mystery Hunt puzzle that required you to sort even crazier numbers: http://web.mit.edu/puzzle/www/2016/puzzle/identify_sort_index_solve/ (Whoops, looks like the Mathjax on that page broke. Oh well.)SnapDragonnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-38474550412043850932019-06-08T13:10:32.555+03:002019-06-08T13:10:32.555+03:00your maths is very very strong. your maths is very very strong. FanofPetrnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-45470440439654048502019-06-08T13:09:29.142+03:002019-06-08T13:09:29.142+03:00your maths is very very strong.your maths is very very strong.Unknownhttps://www.blogger.com/profile/18409198011346767092noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-71648088717304417832019-05-28T21:49:42.284+03:002019-05-28T21:49:42.284+03:00Thanks a lot for this information. I loves to read...Thanks a lot for this information. I loves to read this blog<a href="https://www.iitmind.com" rel="nofollow">.</a> <br />Sachin Singhhttps://www.iitmind.comnoreply@blogger.comtag: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.com