tag:blogger.com,1999:blog-1953325079793449971.comments2019-01-14T22:21:08.526+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger689125tag:blogger.com,1999:blog-1953325079793449971.post-33754121110932720862019-01-14T22:21:08.526+03:002019-01-14T22:21:08.526+03:00I am generally looking for brand spanking new data...I am generally looking for brand spanking new data on this essential subject <br />matter, and am specifically ecstatic the moment I actually find blogs which have <br />been well-written and well-researched. I want to thank you for offering this kind of wonderful info, and I look onward to learning much more from your weblog in the future.Anonymousnoreply@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.comtag:blogger.com,1999:blog-1953325079793449971.post-41631784129694417802018-12-30T01:05:45.590+03:002018-12-30T01:05:45.590+03:00I submitted the 2200 on AGC with push-relabel and ...I submitted the 2200 on AGC with push-relabel and got TLE (in C++). Once I replaced with Hopcroft-Karp I got AC in 200ms...desert97http://yangpliu.github.ionoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-66972824333768715682018-12-27T19:33:51.954+03:002018-12-27T19:33:51.954+03:00No idea about published testcases, and to get an O...No idea about published testcases, and to get an Open Cup login you (roughly) need to organize regular participation in your university if there isn't one: https://codeforces.com/blog/entry/20887Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-36048087442191346232018-12-27T19:16:48.344+03:002018-12-27T19:16:48.344+03:00is there any published testcase? or can we registe...is there any published testcase? or can we register for an open cup login?Felix Jhttps://www.blogger.com/profile/02491866886784258210noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-31372310541190945342018-12-27T19:00:02.961+03:002018-12-27T19:00:02.961+03:00I'm not aware of any OJ except the Open Cup up...I'm not aware of any OJ except the Open Cup upsolving unfortunately, and that one requires an Open Cup login. Maybe other readers will have some pointers?..Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-17531214613955152582018-12-27T18:18:12.889+03:002018-12-27T18:18:12.889+03:00can I asked how to do the opencup problem? is ther...can I asked how to do the opencup problem? is there any OJ which the problem exists? kattis or codeforces or anything?<br /><br />Thanks!Felix Jhttps://www.blogger.com/profile/02491866886784258210noreply@blogger.com