tag:blogger.com,1999:blog-29632375.post3139010651949868872..comments2023-06-19T19:45:40.281-07:00Comments on vexorian's blog: SRM 601: Another slow dayUnknownnoreply@blogger.comBlogger11125tag:blogger.com,1999:blog-29632375.post-11218505454589246682013-12-28T10:50:23.603-08:002013-12-28T10:50:23.603-08:00Why do you fucking care about who am I ?Why do you fucking care about who am I ?Anonnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-61574751315551900162013-12-24T11:47:48.539-08:002013-12-24T11:47:48.539-08:00Why Anon?Why Anon?ZeForcenoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-33142680807583131572013-12-24T11:12:37.918-08:002013-12-24T11:12:37.918-08:00Hi Nishant, How smart of you to apply summation fo...Hi Nishant, How smart of you to apply summation formula and reduce the complexity ! , I am sure nobody would have been able to think of that , except a ACM world finalist like you ;) ....Anonnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-33187766872087097662013-12-23T13:33:28.726-08:002013-12-23T13:33:28.726-08:000.3 seconds in c++0.3 seconds in c++vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-1579445484269511302013-12-23T13:24:26.235-08:002013-12-23T13:24:26.235-08:00Oh, i forgot :)Oh, i forgot :)Stanisławnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-46651837156100439762013-12-23T12:37:19.768-08:002013-12-23T12:37:19.768-08:00The choices are independent, so if you pick a numb...The choices are independent, so if you pick a number for X it cant be used in Y (or I don't get you)<br /><br />The solution I found is like this:<br /><br />The two numbers X and Y are such X < Y. <br /><br />Let's pick i for the most significant bit at which the two integers differ:<br /><br />So the two numbers will be of the kind:<br /><br />Y = abcde1?????<br />X = abcde0?????<br /><br /><br />Bits larger than i must be equal, bit i must be 1 in Y and 0 in X. The remaining bits can have anything.<br /><br />This actually means that the XOR of the most relevant bits (including i) must be 00..0001 . So you can make a dp: f(t, r, b)<br />- t: Is the number of numbers remaining: So you can still decide numbers 1 <= n <= t.<br />- r: Is the current xor value between X and Y. Adding a number q to X makes r = r ^ q, adding a number q to Y makes r = r ^ q too.<br />- b: Is the state of the i-th bit in X.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-32769788383478698292013-12-23T11:14:44.501-08:002013-12-23T11:14:44.501-08:00500 : Can't we just count the number of ways o...500 : Can't we just count the number of ways of choosing a subset from X, that have xor 1...(2^ceil(log2(N))) and the same for Y.<br />The rest is trivial.Stanisławnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-21992405609003674152013-12-23T07:48:53.108-08:002013-12-23T07:48:53.108-08:00Hi vexorian! Alternate solution with a better comp...Hi vexorian! Alternate solution with a better complexity -> http://ideone.com/yKmHhDZeForcenoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-58809464311262624682013-12-23T03:06:32.719-08:002013-12-23T03:06:32.719-08:00Hi vexorian! I thought that in the 250 pt, the sol...Hi vexorian! I thought that in the 250 pt, the solution which most of the people submitted would time out. So, I came up with a O(n) solution where n is the size of the apple vector.<br />Have a look.<br /><br />class WinterAndPresents {<br /> public:<br /> long long getNumber( vector apple, vector orange ) {<br /> long long res = 0; <br /> long long lim = apple[0] + orange[0], n = apple.size();<br /> for (long long i = 0; i < n; ++i)<br /> lim = min(lim, 1LL * apple[i] + orange[i]);<br /><br /> res = (lim * (2LL * (n + 1) + (lim - 1LL) * n)) / 2LL;<br /> for (long long i = 0; i < n; ++i) {<br /> if (lim > orange[i])<br /> res -= ((lim - orange[i]) * (lim - orange[i] + 1)) / 2LL; <br /> if (lim > apple[i])<br /> res -= ((lim - apple[i]) * (lim - apple[i] + 1)) / 2LL; <br /> }<br /> return res;<br /> }<br />};ZeForcenoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-71947682599424614232013-12-22T18:01:46.285-08:002013-12-22T18:01:46.285-08:00That's right.That's right.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-77256642851368493912013-12-22T15:06:16.414-08:002013-12-22T15:06:16.414-08:00I think we don't need the if condition in d1 e...I think we don't need the if condition in d1 easyvijaynoreply@blogger.com