tag:blogger.com,1999:blog-1953325079793449971.comments2024-02-15T20:32:59.333+01:00Algorithms Weekly by Petr MitrichevPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger848125tag:blogger.com,1999:blog-1953325079793449971.post-71190253258214233002024-02-15T20:32:59.333+01:002024-02-15T20:32:59.333+01:00orzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzor...orzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-42328909577604583192024-02-15T20:31:08.753+01:002024-02-15T20:31:08.753+01:00Petr Orz!Petr Orz!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-22217714509232813512024-01-24T15:58:13.990+01:002024-01-24T15:58:13.990+01:00Source - It is well know in china.
https://codefor...Source - It is well know in china.<br />https://codeforces.com/blog/entry/124418?#comment-1104357Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-34178613915308999352024-01-22T16:07:36.286+01:002024-01-22T16:07:36.286+01:00Actually the LGM is ElegiaActually the LGM is ElegiaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-8516411094973063872023-12-31T17:14:19.957+01:002023-12-31T17:14:19.957+01:00I took a lot of time for problem F since there'...I took a lot of time for problem F since there's just so many different possible approaches: (approximate) diameter, cycles, components, ... . Eventually my solution was to add 5 edges between 4 largest-degree vertices. On the second run, I can check for (4th vertex's degree > 5th) and there are at least 5 out of possible 6 edges between the 4 top vertices. Now that I had more time to think, maybe dealing with cliques is possible, but I couldn't work out the probability.??https://google.comnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-85281327063197161372023-12-24T15:49:20.847+01:002023-12-24T15:49:20.847+01:00Thanks! Fixed.Thanks! Fixed.Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-7345249008846936832023-12-24T15:03:27.237+01:002023-12-24T15:03:27.237+01:00In problem H, n = 3e5 (not 1e5).In problem H, n = 3e5 (not 1e5).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-47214863536814321172023-12-13T20:47:28.945+01:002023-12-13T20:47:28.945+01:00A sequential week indeedA sequential week indeedAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-86351328791769391572023-10-18T14:26:22.686+02:002023-10-18T14:26:22.686+02:00I remember trying to solve this at SMU years back ...I remember trying to solve this at SMU years back using that logic. Never did manage to figure it out hahaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-67869386737316921512023-09-09T17:35:41.335+02:002023-09-09T17:35:41.335+02:00Thank you for coming to the Finals.
I'm so gla...Thank you for coming to the Finals.<br />I'm so glad that you enjoyed the event.<br />As the author of the contests, I'm looking forward to your comments on the problems!Riku Kawasakihttps://codeforces.com/profile/maroonrknoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-35888169211781767672023-09-09T17:12:43.642+02:002023-09-09T17:12:43.642+02:00Thanks for the info! The typhoon ended up not reac...Thanks for the info! The typhoon ended up not reaching Tokyo at all, as I understand, even though some flights were indeed canceled.Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-43472545971027409222023-09-06T20:48:31.265+02:002023-09-06T20:48:31.265+02:00I reside in Taiwan, not Tokyo, and Taiwan also enc...I reside in Taiwan, not Tokyo, and Taiwan also encounters frequent Taifun/Typhoons. The typhoon you're currently experiencing is not classified as severe. Thus, from my past experiences, the winds shouldn't be a major worry, although they may be stronger than usual. They might, however, affect air travel. If there are any concerns, they should primarily revolve around the rainfall. For instance, the 15th typhoon in 2022 caused a minor landslide and power outages in Shizuoka, Japan due to heavy rain. <br /><br />That said, Tokyo is a large and modern city, and since this typhoon isn't severe, it should generally be okay. Nevertheless, please keep in mind that I don't live in Tokyo, so I can't be 100% certain about the situation there. Just want to share some of my personal experience.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-22232493762674950452023-09-04T14:45:21.033+02:002023-09-04T14:45:21.033+02:00Hey, this is dev and as a reader I really apprecia...Hey, this is dev and as a reader I really appreciate your efforts. Its depicted in the article a great research you have done for this. Hope I will get more article like this. <a href="https://savivision.com/2023/08/28/godfrey-phillips-townhall/" rel="nofollow">The audio video conferencing system setup in Godfrey Phillips at Delhi</a> has a beautiful user experience which I also want to share with you.Dev Karanhttps://www.blogger.com/profile/09626023424322338936noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-35049057082423416982023-09-04T09:02:37.790+02:002023-09-04T09:02:37.790+02:00Thanks! I hope it won't have any material effe...Thanks! I hope it won't have any material effect on the onsite, too :)Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-11435204245524218232023-09-04T08:08:58.897+02:002023-09-04T08:08:58.897+02:00Oh I somehow missed this blog till now. I'm ve...Oh I somehow missed this blog till now. I'm very excited to meet you this weekend!<br /><br />BTW, our rule about online participation wasn't clear and I made some updates on the relevant post.<br />https://atcoder.jp/posts/982<br /><br />I hope it would work as a rule that accept wider participants, not the one that stops onsite things.<br />Riku Kawasakihttps://codeforces.com/profile/maroonrknoreply@blogger.comtag: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.comtag:blogger.com,1999:blog-1953325079793449971.post-79242746200390047362023-08-13T22:07:43.708+02:002023-08-13T22:07:43.708+02:00In my approach, since the equation system is full ...In my approach, since the equation system is full rank. So if you fixed the cross sum of each cell, it has a unique solution. You can write down these equations and do some arithmetic manipulations, you can reduce the problem to the following problem.<br /><br />Assign a[i] + b[j] (1 ≤ i, j ≤ n) into a n x n square such that for each row, and each column, the sum mod (n - 1) = sum(a[i] + b[i]). (The main reason is we need to divide n - 1 in the formula, we need these conditions to ensure an integer solution. )<br /><br />So the direct approach is to construct an Euler square I mentioned. But I can't find an easy approach for 4k+2, and it's impossible to construct for n = 6. The key point I noticed is there must be two elements a[i], a[j] that are equal mod (n - 1). But I didn't come up with a clever construction.<br /><br />But in my approach, I construct a square f[i][j] = a[i] + b[(i + j) mod n]. So for each column, it's just two permutations of a and b. It meets the condition. But for each row, it's incorrect. So we can randomly swap two elements in one column to make more and more rows satisfy the condition.xudyhhttps://www.blogger.com/profile/07975820600036974310noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-27403208094339025122023-08-13T21:53:05.133+02:002023-08-13T21:53:05.133+02:00Looking at your code (https://atcoder.jp/contests/...Looking at your code (https://atcoder.jp/contests/agc064/submissions/44567159), it seems that divisibility by n-1 is involved in some way, which is also what the editorial does for even n, so it seems I still needed to figure that out in addition to coming up with the random swaps :) Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-39559973283222334112023-08-13T21:45:11.488+02:002023-08-13T21:45:11.488+02:00Well, I try to not repeat the titles, so I had a d...Well, I try to not repeat the titles, so I had a dilemma: is "A too difficult week" (https://petr-mitrichev.blogspot.com/2018/11/a-too-difficult-week.html) a repeat? Once again congrats! :)<br /><br />Could you elaborate a bit on your approach? What does correct col sum mean in the context of this problem - do you still reduce the problem to making all row and column sums equal to zero?Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-13780482806200988362023-08-13T21:18:07.848+02:002023-08-13T21:18:07.848+02:00Haha I was a little surprised to see the title.
...Haha I was a little surprised to see the title. <br /><br />For problem E, it is called Euler square, or orthogonal Latin square, and I have some knowledge about them. But it didn't help me too much, since for n=6, it is impossible to construct.<br /><br />I've noticed some key points in the editorial, but I implemented a heuristic algo during the contest. I construct a Latin square with the correct row sum and randomly swap two elements in the same row to make more correct col sum. And it worked very well. I think it will not be too hard for experienced solvers like you to come up with that if more time is given haha.xudyhhttps://www.blogger.com/profile/07975820600036974310noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-49319752350595731012023-07-25T07:00:42.858+02:002023-07-25T07:00:42.858+02:00Welcome back 🤗🤗🤗🤗🤗🤗🤗Welcome back 🤗🤗🤗🤗🤗🤗🤗Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-14768809137071821302023-07-24T16:15:09.375+02:002023-07-24T16:15:09.375+02:00hi
hi<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-36782469907168569972022-12-03T10:09:48.233+01:002022-12-03T10:09:48.233+01:00nice bednice bedAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-77200214537199823062022-02-14T12:34:29.978+01:002022-02-14T12:34:29.978+01:00Great! Summarizes the CF Global 19 well. CP-Hall O...Great! Summarizes the CF Global 19 well. CP-Hall Of Fame (cphof.org) has been a new one for me, hoping to get a listing there someday :)Anonymousnoreply@blogger.com