Official

C - Calendar Validator Editorial by en_translator


One can observe by explicitly writing down the matrix that the elements of \(A\) are pairwise distinct, that is, if \((i,j) \neq (k,l)\) then \(A_{i,j} \neq A_{k,l}\) is satisfied.

Therefore, given an element of \(A\), one can uniquely determine which column and row the element belongs. Specifically, denoting the value by \(x\), it belongs in the \(\left(\frac{x-1}{7}\right)\)-th row, rounded up, and in the (remainder of \((x-1)\) by \(7\), plus \(1\))-th column.

Therefore, it is sufficient to determine for each element of \(B\) which row and column it belongs, and check if they form a rectangular region.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N,M; cin >> N >> M;
    vector<vector<int>> B(N,vector<int>(M));
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++) cin >> B[i][j];
    }
    vector<vector<int>> x(N,vector<int>(M)),y(N,vector<int>(M));
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            x[i][j] = (B[i][j]+6)/7;
            y[i][j] = (B[i][j]-1)%7+1;
        }
    }
    string ans = "Yes";
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(0 < i && x[i][j] != x[i-1][j]+1) ans = "No";
            if(0 < j && y[i][j] != y[i][j-1]+1) ans = "No";
            if(0 < j && x[i][j] != x[i][j-1]) ans = "No";
            if(0 < i && y[i][j] != y[i-1][j]) ans = "No";
        }
    }
    cout << ans << endl;
}

posted:
last update: