tag:blogger.com,1999:blog-1953325079793449971.post1489839113059618762..comments2024-09-20T21:17:15.980+02:00Comments on Algorithms Weekly by Petr Mitrichev: An apiad weekPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger4125tag: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.com