tag:blogger.com,1999:blog-1953325079793449971.post6385634862936988642..comments2024-06-12T05:08:36.036+02:00Comments on Algorithms Weekly by Petr Mitrichev: A power of two weekPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-1953325079793449971.post-32575528155096474632023-08-14T07:22:09.111+02:002023-08-14T07:22:09.111+02:00Thanks for the reply!
I did come up with a way to...Thanks for the reply!<br /><br />I did come up with a way to achieve a cyclic shift with arbitrary gaps using similar reasoning ("can I do something reliably?"), but instead of asking myself "Can I change the target values so that their relative order will be a cyclic shift of my initial values?", I just discarded the approach becase "this spends 1 operation per number, and we have only 1 operation per number, so this is clearly a dead end" :) I guess one could just call this a case of bad luck (or bad intuition) and move on.Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-61816953304294048842023-08-14T01:07:06.773+02:002023-08-14T01:07:06.773+02:00> Do you routinely try to convert the sample an...> Do you routinely try to convert the sample answers from the "modulo prime" form to the fraction form?<br />Never. I can convert the answer printed by my solution to fraction for debugging purposes.<br />If I want to try to guess some formula (or at least some properties of denominators), I usually calculate small answers in fractions by hand, instead of looking at the samples.<br /><br />> Do you have some tricks on how to do this more reliably?<br />I'm not exactly sure how you define "reliably" in this situation. Since the denominators in your examples turned out to be close to sqrt(MOD), there is technically nothing you can do, since it is reasonable to expect some collisions at this point.<br />There are ways to do it faster though. There was a blog about exactly that on cf, but I can't find it now. Related problems: https://codeforces.com/gym/102354/problem/I , https://judge.yosupo.jp/problem/min_of_mod_of_linear<br /><br />> how did you arrive at the solution? Is there some intermediate reasoning step that makes the last leap of faith smaller, or is it just small enough for you as it is?<br />Well, if you jump right to the plan that just works, it is a leap of faith. But I find the sequence logical.<br />The operation is too powerful and changes everything unpredictably, so I want to make it weaker and simpler. I thought about interleaving, but that still changes a lot of things, I can't keep the results from previous steps because each time I will change half of elements. So the next step of simplifying the operation is to move just one element (and increase all by the same constant, but in terms of gaps it is just one element). Now the operation is very simple, but it is too restrained: I can only do cyclic shifts. On the other hand, I can get any cyclic shift with any gaps in linear number of operations. Now I ask myself "Can I change the target values so that their relative order will be a cyclic shift of my initial values?" The answer is yes, the inverse of the operation is even more powerful (and not unique), so getting the required relative order is very easy.Um_nikhttps://www.blogger.com/profile/17373530217609811086noreply@blogger.com