CHFIMPRS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an N \times M matrix, find if its elements can be interchanged so that the sequence produced by writing the elements row by row, starting from the left for the first row, then right for the second row and alternating, is same as the sequence produced on writing the elements row by row, starting from the right for the first row, then left for the second row, and then alternating. Also produce the resultant matrix if a solution exists.

HINTS:

Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, try solving the problem on your own.

Hint 1:

A solution only exists if the elements of the matrix can be interchanged, such that every row is a palindrome. How to check if it is possible to rearrange the elements such that every row is a palindrome?


Hint 2:

Find the frequency of every element. If the number of columns is even, then there can be no integer in the matrix with an odd frequency. If M is odd, then there can be at most N elements with an odd frequency.


Hint 3:

How to arrange the elements if a solution exists?

If a middle column exists (it will exist if M is odd), leave it empty and fill all other columns first. Take the even frequency elements and place one of them on one side of a row, and the other on the opposite side of the same row, such that they are equidistant from the ends of that row. Do this for other even frequency elements as well, till all columns, except the middle one are filled. Now, fill the middle column with the remaining elements.


QUICK EXPLANATION:

show

A solution only exists if the elements of the matrix can be rearranged such that every row is a palindrome. If M is odd, this is only possible if the number of elements with odd frequency don’t exceed N, while for an even number of columns, this is only possible if there are no elements with an odd frequency. If a solution exists, fill all columns except the middle one (in case of odd number of columns) with equal elements placed on the same row, on the opposite sides, equidistant from the two ends of the row. After this is done, the remaining elements can be used to fill the middle column, if it exists.

EXPLANATION

show

Chef’s sequence will be produced by reading the elements from left to right for the first row, then right to left for the second row, then left to right for the third row, and so on, alternating this for every row.

On the other hand, Chefina’s sequence will be produced by reading the elements from right to left for the first row, left to right for the second row, right to left for the third row, and so on, alternating this for every row.

Thus, if a matrix is like:

a b c d e
f g h i j
k l m n o

Then the sequences are:

  • a b c d e j i h g f k l m n o
  • e d c b a f g h i j o n m l k

For the sequences to be equal, the element at a will have to be equal to the element at e, b with d, f with j, g with i, k with o and l with n. The elements at positions c, h and m can be anything, and they don’t affect the equality of the sequences.

Thus, for the sequences to be equal, there must exist a way to interchange the elements of the matrix such that every row is a palindrome.

The elements of the middle column can be anything, as they don’t affect the sequences, while all other elements should have an even number of occurrence in the matrix. This is necessary for them to be arranged in a way such that every row is a palindrome. If there is no middle coumn, i.e., if M is even, then every distinct integer in the matrix should have an even frequency in the matrix. Refer to the following for a better understanding:

  • When M is odd, the matrix should look like this after interchanging:

    a b c b a
    d e f e d
    g h i h g

c, f and i can be anything, they don’t affect the palindromicity of the rows, while all other elements should have an even frequency.

  • When M is even, the resultant matrix should be of the form:

    a b b a
    c d d c
    e f f e
    g h h g

i.e., every element should have an even frequency.

Thus, if M is even, a solution won’t exist if any element has an odd frequency in the matrix, while, if M is odd, a solution won’t exist if there are more than N elements with an odd frequency (as these are the elements which will be used to fill the middle column, and there are N rows in each coumn).

So, we need to find the frequency of every integer in the matrix. To do this, we can use an unordered/hash map as described here, or use sorting, as described here. Another way to do this, is to maintain a frequency array. This is possible to do since the sum of number of elements over all test cases does not exceed 5*10^5. So, we can maintain an array of 10^5 elements, calculate the frequencies, keep track of the elements that affected the frequency array, and then clear it while answering the next test case.

Once we know the frequency of every integer in the matrix, we can check whether or not a solution is possible. If M is even, there should be no integer in the matrix with an odd frequency, while if M is odd, there should be no more than N (distinct) integers in the matrix with an odd frequency.

Now, if we know that a solution exists, how to produce it? There different ways to do this, however, they all have similar ideas.

If M is even and a solution exists, then we know that every element in the matrix has an even frequency. Thus, equal elements can be placed on the opposite sides of the same row, equidistant from the ends of the row, so that every row is a palindrome. As an example, suppose an element is placed at the i th column of a row. As the frequency of every element is even, we shall also place it on the (M-i-1) th column of that row. If we do this for every element, every row in the resultant matrix will be a palindrome. Note the the indices here are 0 - indexed.

If M is odd, we can first fill all the columns except the middle one. We shall place the elements with even frequencies in the same way as described above, till all the columns, except the middle one are filled. Then, we fill the middle column with the remaining elements. We can do this because the elements in the middle column won’t affect the palidromicity of the rows.

Thus, to solve the problem:

  1. Observe that for the sequences to be equal, there must exist a way to rearrange elements such that the elements of each row form a palindrome.
  2. If M, the number of columns, is even, then this is only possible if there are no elements in the matrix with an odd frequency. If M is odd, then the number of elements with an odd frequency can’t be greater than N.
  3. If M is even, place equal elements on the opposite sides of the same row, with an equal distance from the ends of the row. If M is odd, fill all the columns, except the middle one in the same way, and fill the middle column with the elements that remain.

In my implementation, I have sorted the elements to get the elements with odd and even frequencies. Then, I have checked whether or not a solution exists.

If a solution exists, and if M is odd, I have first filled the middle column with a single occurrence of the elements with odd frequency. Note that these elements will now have an even frequency remaining. After this, if the middle column is not yet filled, I have filled the remaining rows of the middle column with even frequency elements. Note that after the middle column is filled in this fashion, all the remaining elements will still have an even frequency.

If M is even, I have filled the matrix in the same way as I have described in the solution.

TIME COMPLEXITY:

show

As there are N*M elements, the time complexity is: O((N*M) log (N*M)) per test case, if we use sorting to calculate the frequency of the elements, and O(N*M) per test case, if instead we use an unordered map, or a frequency array.

Rearranging the elements takes O(N*M), and the space complexity will also be O(N*M), for storing the initial and solution matrices.


SOLUTIONS:

Setter
#include <bits/stdc++.h>
 
#define int long long
#define endl "\n"
 
using namespace std;
 
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int t;
	cin >> t;
 
	while(t--)
	{
		int n,m;
		cin >> n >> m;
 
		map <int,int> freq;
 
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				int x;
				cin >> x;
 
				freq[x]++;
			}
		}
 
		bool flag = true;
 
		if(m%2 == 0)
		{
			for(auto i:freq)
			{
				if(i.second%2)
				{
					flag = false;
					break;
				}
			}
		}
		else
		{
			int cnt = 0;
 
			for(auto i:freq)
				cnt += (i.second%2);
 
			if(cnt > n)
				flag = false;
		}
 
		if(!flag)
		{
			cout << -1 << endl;
			continue;
		}
 
		vector <int> cnt1;
		int a[n][m];
		int id = 0;
 
		for(auto i:freq)
		{
			int x = i.second;
 
			if(x%2)
				a[id++][m/2] = i.first;
 
			x /= 2;
 
			while(x--)
				cnt1.push_back(i.first);
		}
 
		for(int i=0;i<m/2;i++)
		{
			for(int j=0;j<n;j++)
			{
				a[j][i] = a[j][m-i-1] = cnt1.back();
				cnt1.pop_back();
			}
		}
 
		while(id < n && m%2)
		{
			a[id++][m/2] = cnt1.back();
			a[id++][m/2] = cnt1.back();
			cnt1.pop_back();
		}
 
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
				cout << a[i][j] << " ";
			cout << endl;
		}
	}
 
	return 0;
} 
Tester
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
vector<vi>a;
map<int,int>mapi;
map<int,int>::iterator it;
int inv[1000005],cnt[1000005];
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,m,i,j,c,row,l,r,odd=0;
		cin>>n>>m;
		a.clear();
		a.resize(n);
		rep(i,n){
			a[i].resize(m);
		}
		assert(n*m<=1e6);
		mapi.clear();
		rep(i,n){
			rep(j,m){
				cin>>a[i][j];
				mapi[a[i][j]]=1;
			}
		}
		if(m==1){
			rep(i,n){
				cout<<a[i][0]<<endl;
			}
			continue;
		}
		c=0;
		for(it=mapi.begin();it!=mapi.end();it++){
			cnt[c]=0;
			it->ss=c;
			inv[c]=it->ff;
			c++;
		}
		rep(i,n){
			rep(j,m){
				a[i][j]=mapi[a[i][j]];
				cnt[a[i][j]]++;
			}
		}
		odd=0;
		if(m%2){
			odd=n;
		}
		rep(i,c){
			if(cnt[i]%2){
				odd--;
			}
		}
		if(odd<0){
			cout<<-1<<endl;
		}
		else{
			row=0;
			l=0;
			r=m-1;
			rep(i,c){
				while(cnt[i]>=2){
					a[row][l]=inv[i];
					a[row][r]=inv[i];
					cnt[i]-=2;
					l++;
					r--;
					if(l==m/2){
						row++;
						l=0;
						r=m-1;
						if(row==n){
							break;
						}
					}
				}
				if(row==n){
					break;
				}
			}
			row=0;
			rep(i,c){
				while(cnt[i]--){
					assert(row<n);
					a[row][m/2]=inv[i];
					row++;
				}
			}
			rep(i,n){
				rep(j,m){
					cout<<a[i][j]<<" ";
				}
				cout<<endl;
			}
		}
	}
	return 0;
} 
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
	public static void main(String[] args) throws IOException
	{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	    int i,N,M;

	    int T = Integer.parseInt(br.readLine().trim());
	    StringBuilder sb = new StringBuilder();

	    while (T-->0)
	    {

	        String[] s = br.readLine().trim().split(" ");
	        N = Integer.parseInt(s[0]);
	        M = Integer.parseInt(s[1]);

	        int[] a = new int[N * M];
	        int k = 0;
	        for (i = 0; i < N; i++)
	        {
	            s = br.readLine().trim().split(" ");
	            for (int j = 0; j < M; j++) a[k++]  = Integer.parseInt(s[j]);
	        }

	        Arrays.sort(a);

	        //will store elements with odd and even frequencies respectively
	        ArrayList<Integer> odd = new ArrayList<>();
	        ArrayList<Integer> even = new ArrayList<>();

	        //calculating the frequencies of elements.
	        //If frequency is odd, put once instance of it into odd list
	        //and decrease the frequency. It will now have an even frequency.
	        //If frequency is even, put it into the even list.
	        int cur = 1;
	        for (i = 1; i < N * M; i++)
	        {
	            if (a[i] == a[i - 1]) cur++;
	            else
	            {
	                if (cur % 2 == 1)
	                {
	                    odd.add(a[i - 1]);
	                    cur--;
	                }
	                for (int j = 0; j < cur / 2; j++) even.add(a[i - 1]);

	                cur = 1;
	            }
	        }
	        if (cur % 2 == 1)
	        {
	            odd.add(a[i - 1]);
	            cur--;
	        }
	        for (int j = 0; j < cur / 2; j++) even.add(a[i - 1]);

	        //Does a solution exist?
	        if ((M % 2 == 0 && odd.size() > 0) || odd.size() > N)
	        {
	            sb.append(-1).append("\n");
	            continue;
	        }

	        k = i = 0;
	        int[][] ans = new int[N][M];

	        //Filling the middle column if M is odd with odd frequency elements
	        for (int j : odd) ans[k++][M / 2] = j;
	        if(M%2==1)
	        {
	            //filling the remaining rows of middle column with even frequency elements
	            for(;k<N;k+=2)
	                ans[k][M / 2] = ans[k+1][M / 2] = even.get(i++);
	        }

	        //filling the other columns, to make every row a palindrome
	        int r = 0, c = 0;
	        for (; i < even.size(); i++)
	        {
	            if (c == M / 2)
	            {
	                r++;
	                c = 0;
	                if (r == N) break;
	            }
	            ans[r][c] = ans[r][M - c - 1] = even.get(i);
	            c++;
	        }

	        for (i = 0; i < N; i++)
	        {
	            for (int j = 0; j < M; j++) sb.append(ans[i][j]).append(" ");
	            sb.append("\n");
	        }
	    }
	    System.out.println(sb);
	}
}

Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions :slight_smile:

2 Likes

Can you please tell me how can I improve my program? I am getting TLE with 1.01 seconds
https://www.codechef.com/viewsolution/33538572 @akashbhalotia

My solution :- https://www.codechef.com/viewsolution/33580437
I have applied the same logic as discussed in the editorial but still i am getting WA.I have checked my code on several custom test cases but i couldn’t find any test case where my answer is wrong.Can you please give me a testcase where my code is giving wrong answer or find any mistake in my code? @akashbhalotia @rishup_nitdgp @raja1999

for(auto i:freq)
		{
			int x = i.second;
 
			if(x%2)
				a[id++][m/2] = i.first;
 
			x /= 2;
 
			while(x--)
				cnt1.push_back(i.first);
		}
 
		for(int i=0;i<m/2;i++)
		{
			for(int j=0;j<n;j++)
			{
				a[j][i] = a[j][m-i-1] = cnt1.back();
				cnt1.pop_back();
			}
		}
 
		while(id < n && m%2)
		{
			a[id++][m/2] = cnt1.back();
			a[id++][m/2] = cnt1.back();
			cnt1.pop_back();
		}
 
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
				cout << a[i][j] << " ";
			cout << endl;
		}
	}
 
	return 0;
} 
```plz explain all these loops

just explain what this loop does?

	for(auto i:freq)
		{
			int x = i.second;
 
			if(x%2)
				a[id++][m/2] = i.first;
 
			x /= 2;
 
			while(x--)
				cnt1.push_back(i.first);
		}
```bro can u explain what does this loop does
	for(auto i:freq)
		{
			int x = i.second;
 
			if(x%2)
				a[id++][m/2] = i.first;
 
			x /= 2;
 
			while(x--)
				cnt1.push_back(i.first);
		}
```can u explain me what does this whole block of loop does?
1 Like