tag:blogger.com,1999:blog-29632375.post1030053286898259902..comments2023-06-19T19:45:40.281-07:00Comments on vexorian's blog: SRM 516 - So, I forgot I have a blog...Unknownnoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-29632375.post-51032364488687941032011-09-02T20:26:53.683-07:002011-09-02T20:26:53.683-07:00I tried in part 2.
I then tried again in the edit...I tried in part 2.<br /><br />I then tried again in the editorial.<br /><br />But maybe misof's explanation is still the best: http://apps.topcoder.com/forums/?module=Thread&threadID=719177&start=0vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-32164179658859873652011-09-01T22:45:11.726-07:002011-09-01T22:45:11.726-07:00Could you explain what the div1-500 problem is?
I ...Could you explain what the div1-500 problem is?<br />I can't understand what the problem is over 1 hour. T.Tibrokerhttps://www.blogger.com/profile/01482357696299908700noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-12724721792748354792011-08-31T17:49:25.712-07:002011-08-31T17:49:25.712-07:00Ah sorry, I didn't notice it. 50^5 is not that...Ah sorry, I didn't notice it. 50^5 is not that big for TC servers assuming the constant factor is not very large. <br /><br />Usually, my heuristic to know if something will pass in TC is to find 50^5 = 312500000 If the number has 10 digits, then it will most likely fail. But if it has 9 digits it may actually pass assuming there is not much overhead.vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-86405369741583485402011-08-31T13:26:58.972-07:002011-08-31T13:26:58.972-07:00Actually I figured it out. Thanks :)Actually I figured it out. Thanks :)Shuaibnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-54249255971911735192011-08-31T02:26:05.899-07:002011-08-31T02:26:05.899-07:00Thanks for the explanations vexorian. If only I ha...Thanks for the explanations vexorian. If only I had noticed for div1-250/div2-500 that checking keys for a single ciphertext is enough, it would have stopped me from making the mistakes that I made trying to do optimizations. <br /><br />Anyway, I notice that even if you don't do that, and actually go through all the ciphertexts generating keys and then checking if they are valid, produces an algo that is at worst case O(50^5), but such an implementation passed in practice room. I wonder why... whether there wasn't a test case that forced the worst case, or whether 50^5 is ok. Any thoughts?Shuaibnoreply@blogger.com