# 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

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,c;
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;
r[i].insert(ip);
c[j].insert(ip);
a[i][j] = ip;
if(i == j)tr+=ip;
if(any_magic_square(i,j+1))return true;
if(i == j)tr-=ip;
r[i].erase(ip);
c[j].erase(ip);
}
return false;
}

void solve(int test){
tr = 0;
loop(i,0,100){
c[i].clear();
r[i].clear();
}
cin >> n >> k;
p = n*(n+1);
p>>=1;
a.resize(n,vector<int>(n,0));
if(any_magic_square(0,0)){
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("\n");
}
}else{
printf("Case #%d: IMPOSSIBLE\n",test);
}
}
int main()
{
int t;
int i = 1;
cin >> t;
for(int i = 1; i <= t; ++i){
solve(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 and C 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 