Hello, Codeforces!
Yesterday slappy advised me to stop writing problems. I will not listen to his advice and will not stop coming up with new problems. Moreover, the idea of problem 1118C - Palindromic Matrix is mine, and I do not consider it bad or unsuccessful.
IMHO, this is a good example of a problem, where an sloppy (almost slappy) implementation leads to a casework, duplication of code and a lot of formulas. On the other hand, a well-turned implementation is devoid of all these drawbacks and easy to write. It seems to me that such feedback about the problem is something of a Dunning-Kruger effect.
In general, this is an important skill of the developer to write such code, which solves the problem reliably, concisely and is not dirty. And if your code smells bad, then instead of the shaming the authors, I urge you to think "can I write a solution to this problem better?". Good way is to read solutions of other participants. You can choose short implementations from experienced participants. If you focus on learning, rather than just participating for fun, this should be the rule: read solutions of other participants (better experienced, choosing short codes or extremely efficient) and learn. The fact that you got “Accepted” does not mean that you have nothing to learn with this problem.
Here is the explanation of my solution which was written in ~10 minutes. Please, read the problem 1118C - Palindromic Matrix if you don’t know the statement. This problem is just a generalization of string palindrome constructing problem on 2D.
In general case there are 3 types of elements of a matrix (I didn’t spend to much time on drawing, the image is not perfect):
Each element in the blue area has 4 equal copies (itself and 3 additional symmetric cells). Each element in the yellow area has 2 equal copies (itself and 1 additional symmetric cell). And the single central cell (the green area) has only the single copy (itself). The yellow and green areas are absent in case of even n.
It means that you can fill the matrix with a greedy approach. At first process the blue area: for each cell take any value with number of occurrences at least 4 and fill the cell and its copies. After it process the yellow area (if any): for each cell take any value with number of occurrences at least 2 and fill the cell and its copy. Finally, process the green area (if any): take any value with number of occurrences at least 1 and fill the cell and its copy.
Easy to see that each time you can take a value with the greatest number of occurrences, so I used priority_queue<pair<int,int>> to maintain values ordered by number of occurrences. The first item in a pair is a number of occurrences, the second item in a pair is value itself. To construct such priority_queue q just use simple code like this:
map<int,int> cnts;
forn(i, n * n) {
int val;
cin >> val;
cnts[val]++;
}
for (auto [key, value]: cnts)
q.push({value, key});
To implement the rest of code, use simple function to reflect a position to the symmetric (in 1D):
int rev(int i) {
return n - i - 1;
}
Now the main part of the code is: iterate over blue, yellow, green areas and put values in the matrix (consider all symmetric copies in together):
int m = n / 2;
forn(i, m) // blue area
forn(j, m)
put({{i, j}, {i, rev(j)}, {rev(i), j}, {rev(i), rev(j)}});
if (n % 2 != 0) {
forn(i, m) { // yellow area
put({{i, m}, {rev(i), m}});
put({{m, i}, {m, rev(i)}});
}
put({{m, m}}); // green area
}
The function put takes a sequence of symmetric positions and put same values on them:
void put(vector<pair<int,int>> pos) {
auto t(q.top());
q.pop();
if (t.first < pos.size()) // can’t do it?
no();
for (auto [i, j]: pos)
a[i][j] = t.second;
t.first -= pos.size();
q.push(t);
}
So the complete code is very simple and contains only two if statements (almost no casework!).
Change Handle Feature
