tag:blogger.com,1999:blog-1953325079793449971.comments2019-03-19T07:37:07.156+03:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttps://plus.google.com/108329321411299197209noreply@blogger.comBlogger702125tag:blogger.com,1999:blog-1953325079793449971.post-11515349933912281872019-03-19T07:37:07.156+03:002019-03-19T07:37:07.156+03:00A Computer Science portal for geeks. It contains w...A Computer Science portal for geeks. It contains well written, well thought and well<br />explained computer science and programming articles, quizzes and practice/competitive<br />programming/company interview Questions.<br />website: geeksforgeeks.orgbyodbuzz04https://www.blogger.com/profile/16207049481222356975noreply@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.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.com