tag:blogger.com,1999:blog-1953325079793449971.comments2019-02-18T17:57:19.001+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger694125tag: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.comtag:blogger.com,1999:blog-1953325079793449971.post-53044329345264730922019-01-07T12:48:33.396+03:002019-01-07T12:48:33.396+03:00My numbers are from your first definition of unifo...My numbers are from your first definition of uniform random -- it can also be stated as choosing uniformly from the volume of the n-1 dimensional space of possible distributions. The second definition is a little different since the total denominator is not independent w.r.t. individual weights, which favors "middling" distributions more since a higher numerator also corresponds to a higher denominator.<br /><br />Your approach makes sense and is good in practice when N is high enough. It will systematically underestimate the lower-mass values (and overestimate higher-mass values), in short because for p1 < p2 < 0.5 it's less likely for a population of p1 to produce a sample of p2 than for a population of p2 to produce a sample of p1. This is essentially the same relation as t-stat vs. z-score in single variable distributions.<br /><br />My slightly modified version of your code is here: https://pastebin.com/Q8PmbHWcScottnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-88655556097831223902019-01-07T11:15:51.237+03:002019-01-07T11:15:51.237+03:00Thanks! The reason I did not choose that path is t...Thanks! The reason I did not choose that path is that I could not explain to myself what is a uniformly random population distribution. Is it the one where we pick n-1 weights such that their sum is less than 1 and probability density is constant everywhere, and pick the n-th weight as one minus the sum? Or is it the one where we pick n uniformly random weights between 0 and 1 and divide by their sum?<br /><br />Could you share the code you used to obtain your numbers?<br /><br />I thought my approach would be a good practical way to sample from the unknown distribution space. I.e., I'm essentially assuming that for discrete distributions with the same denominator the probability to sample A from B is similar to the probability to sample B from A [times the prior for A], at least when the two distributions are close. Does it make sense?Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-20543712495224253472019-01-07T01:55:22.354+03:002019-01-07T01:55:22.354+03:0060% is a great ballpark! The Colab essentially cal...60% is a great ballpark! The Colab essentially calculates "Assuming this result as the true population distribution, what is the probability that a choice will win on 91 randomly selected votes?"<br /><br />The number you actually want is roughly the converse: "If a randomly-selected population distribution produced this result in 91 votes, what is the probability of a choice being the true population max?" If you choose a uniformly random population distribution, the results are quite similar although the smaller choices are given significantly more mass -- 58% chance for problem 4 compared to 60% in your model, but 0.61% chance for problem 5 compared to your 0.34%.Scottnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-48919021075426181432019-01-06T17:42:22.192+03:002019-01-06T17:42:22.192+03:00This is Laax.This is Laax.Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-46565721196559332772019-01-06T17:05:56.316+03:002019-01-06T17:05:56.316+03:00which place is this?? @petrwhich place is this?? @petrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-26585671423086581862019-01-06T16:37:11.856+03:002019-01-06T16:37:11.856+03:00wowowowowowowwowowowowowowAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-89574640565478329512019-01-06T14:21:15.180+03:002019-01-06T14:21:15.180+03:00Cool, thanks a lot! :)Cool, thanks a lot! :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-11077830700996605902019-01-06T13:24:00.951+03:002019-01-06T13:24:00.951+03:00https://en.wikipedia.org/wiki/Sch%C3%B6llenen_Gorg...https://en.wikipedia.org/wiki/Sch%C3%B6llenen_GorgePetr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-10924465948351037592019-01-06T13:13:36.624+03:002019-01-06T13:13:36.624+03:00Where did you take this photo?Where did you take this photo?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-50672665640863260112019-01-02T15:11:39.060+03:002019-01-02T15:11:39.060+03:00It is now available here, thanks to ko_osaga: http...It is now available here, thanks to ko_osaga: https://codeforces.com/gym/102059/problem/BPetr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-73161461498937234052018-12-30T16:47:03.396+03:002018-12-30T16:47:03.396+03:00Alright, good to know that you read this. Give it ...Alright, good to know that you read this. Give it thought if sometime you feel like it.<br />Thanks for the response.Arun Kumarhttps://www.blogger.com/profile/07879522210390584739noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-73035146174234762082018-12-30T13:48:11.606+03:002018-12-30T13:48:11.606+03:00I do read this, but frankly, I have no idea what t...I do read this, but frankly, I have no idea what to answer, sorry :(Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-71640763691919033892018-12-30T13:19:05.123+03:002018-12-30T13:19:05.123+03:00I know that you will probably never read this, but...I know that you will probably never read this, but worth a shot:<br /><br />Can you make a post about, what path should a new competitive programmer should take or more like what path would you have taken if you are given a chance to go back in life and relive your years to be where you are right now, like what resources and what kinda competition would you have opted for.Arun Kumarhttps://www.blogger.com/profile/07879522210390584739noreply@blogger.com