Code Jam 2020 - Problem 5

How to generate the main diagonal sequence? Or share your approach. Thanks.

PS: my approach is to generate the sequence and then fill the rest grid using DFS backtracking

Problem link

I could just solve it for partial case.

Approach: I just ran it for a brute search

My code
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)

using namespace std;

int n,k;
vector<vector<int>> a;
unordered_set<int> r[100],c[100];
int tr;
int p;

bool any_magic_square(int i, int j){
    if(i == n-1 && j == n)return tr==k;
    if(i < n-1 && j == n)j=0,i++;
    for(int ip = 1; ip <= n; ++ip){
        if(r[i].find(ip) != r[i].end())continue;
        if(c[j].find(ip) != c[j].end())continue;
        a[i][j] = ip;
        if(i == j)tr+=ip;
        if(any_magic_square(i,j+1))return true;
        if(i == j)tr-=ip;
    return false;

void solve(int test){
    tr = 0;
    cin >> n >> k;
    p = n*(n+1);
        printf("Case #%d: POSSIBLE\n",test);
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j)printf("%d ",a[i][j]);
        printf("Case #%d: IMPOSSIBLE\n",test);
int main()
    int t;
    int i = 1;
    cin >> t;
    for(int i = 1; i <= t; ++i){

    return 0;

Thanks for the reply. I’m really sorry about the fact that I don’t know c++. Could you please explain the approach?

I just ran brute force, or say checked all the possible combinations.

Since simple brute force would be 25^5 for TC1, therefore I maintained data structure R[100] and C[100] which tells if an element is present in C[i] or R[i] in amortized O(1) .

So since I am putting not same elements in a row or column again it, reduces possible generated combinations.

1 Like

Bro… thanks a lot bro :heart: