USACO 2.3 Zerosum – CPP solution

A DFS solution would be fast enough to pass the tests. We have just N-1 places to put signs where N is the number of digits we can use. This yields that the time complexity of our algorithms is O(3^(N-1)) where N can be maximum 9. We will generate every possible expression and then evaluate it. If it sums to zero, then we just print it. In order to get in in ASCII order, we will first use the empty sign, then the + sign and then the – sign.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

ifstream in;
ofstream out;

int n;

vector<int> numbers;
char signs[10];

int calcSum() {
    int sum = numbers[0];
    for (int i = 1; i < numbers.size(); ++i) {
        if (signs[i-1]=='+') {
            sum+=numbers[i];
        } else {
            sum-=numbers[i];
        }
    }
    return sum;
}

void printSolution() {
    for (int i = 0; i < numbers.size(); ++i) {
        int tmp = numbers[i];
        string c;
        while (tmp!=0) {
            c.insert(0,1,(char)(tmp%10 + '0'));
            if (tmp>10) c.insert(0,1,' ');
            tmp/=10;
        }
        out << c;
        if (i+1!=numbers.size()) out << signs[i];
    }
    out << endl;
}

void dfs(int curNumber, int curSign) {
    if (curNumber == n+1) {
        int sum = calcSum();
        if (sum==0) {
            printSolution();
        }
        return;
    }
    numbers[numbers.size()-1] = numbers[numbers.size()-1]*10+curNumber;
    dfs(curNumber+1,curSign);
    numbers[numbers.size()-1] = (numbers[numbers.size()-1]-curNumber)/10;
    signs[curSign] = '+';
    numbers.push_back(curNumber);
    dfs(curNumber+1,curSign+1);
    signs[curSign] = '-';
    dfs(curNumber+1,curSign+1);
    numbers.pop_back();
}

int main() {
    in.open("zerosum.in");
    in >> n;
    in.close();
    out.open("zerosum.out");
    numbers.push_back(1);
    dfs(2,0);
    out.close();
}

Another idea (not implemented): It is fairly obvious that we cannot have more than 2 empty signs since the integer would get too big and we cannot get a zero sum. We could generate every possible number (1,2,3,4 … 12,23,34 … 89). Keep an array dp[2000]. If dp[x] is equal to one, then we can generate the value X. We will always add an offset to the sum. That’s why we have to create such a big array. We will also keep a vector array (vector from[2000]) to keep the solutions. After we have calculated all the possible sums using dynamic programming, we will just use the from array to print all the solutions. What’s the time complexity? We have N numbers and a sum from -1000 to +1000 (+offset). For every number we will have to either add it, subtract it or append it to the current number in the dp array. The time complexity is O(C*N) where C is the maximum size of the array. As you have probably noticed, this solution is very similar to the 1-0 knapsack problem.

USACO 2.2 Preface Numbering – CPP solution

We just have to make some observations how the Roman numbers are converted from Arabic numbers. Basic examples:
I:1 , II:2, III:3, IV:4, V:5, VI:6, VII: 7, VIII: 8, IX = 9, etc.
Basically there are just three possible combination: just one character (I,V,X,L,C,D,M), a combination with substraction (IV -> 4) or a combination with addition (CI -> 101).
Dissembling of Arabic numbers: 268 = 200 + 60 + 8. We could just generate the Roman numbers for 200, 60 and 8. However, since we are at the 268th number, we have already calculated the Roman numbers (or more precisely the count of every Roman character) for 200, 600 and 8. Basically, this is the idea of dynamic programming -> we use previously calculated tasks in the current task.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

int n;

int s[] = {'I','V','X','L','C','D','M'};
int sum[100] = {0};
int vals[] = {1,10,100};
int combined[] = {3000,2000,300,200,100,30,20,10,3,2,1};
int nS = 7;

int direct[3001] = {0};
int dp[3501][100] = {0};
int done[3501] = {0};

void precompute() {
    direct[1] = 'I';
    direct[5] = 'V';
    direct[10] = 'X';
    direct[50] = 'L';
    direct[100] = 'C';
    direct[500] = 'D';
    direct[1000] = 'M';
}

vector<int> desemble(int number) {
    vector<int> q;
    int times = 1;
    while (number!=0) {
        q.push_back(number%10*times);
        number/=10;
        times*=10;
    }
    reverse(q.begin(),q.end());
    return q;
}

void solve(int number) {
    vector<int> q = desemble(number);
    for (int i = 0; i < q.size(); ++i) {
        if (done[q[i]]==1) {
            for (int k = 0; k < nS; ++k) {
                dp[number][s[k]] += dp[q[i]][s[k]];
            }
            continue;
        }
        if (q[i] <= 1000 && direct[q[i]]>0) {
            dp[number][direct[q[i]]] = 1;
            done[q[i]] = 1;
            continue;
        }
        if (q[i] <= 2000 && q[i]%2==0 && direct[q[i]/2]>1) {
            dp[number][direct[q[i]/2]] = 2;
            done[q[i]] = 1;
            continue;
        }
        if (q[i] <= 3000 && q[i]%3==0 && direct[q[i]/3]>1) {
            dp[number][direct[q[i]/3]] = 3;
            done[q[i]] = 1;
            continue;
        }

        bool found = false;
        for (int k = 0; k < 3 && q[i]!=0 && found==false; ++k) {
            if (q[i]+vals[k]<=1000 && direct[q[i]+vals[k]]>0) {
                dp[number][direct[vals[k]]] += 1;
                dp[number][direct[q[i]+vals[k]]] += 1;
                done[q[i]] = 1;
                found = true;
            }
        }

        for (int k = 0; k < 11 && q[i]!=0 && found==false; ++k) {
            if (q[i]-combined[k]>0 && direct[q[i]-combined[k]]>0) {
                int cnt = 1;
                int del = 1;
                if (combined[k] == 2 || combined[k] == 20 || combined[k] == 200 || combined[k] == 2000) {
                    cnt = 2;
                    del = 2;
                }
                if (combined[k] == 3 || combined[k] == 30 || combined[k] == 300 || combined[k] == 3000) {
                    cnt = 3;
                    del = 3;
                }
                dp[number][direct[combined[k]/del]] += cnt;
                dp[number][direct[q[i]-combined[k]]] += 1;
                found = true;
                done[q[i]] = 1;
            }
        }
    }
}

int main() {
    ifstream in("preface.in");
    in >> n;
    in.close();
    ofstream out("preface.out");
    precompute();
    for (int i = 1; i<= n; ++i) {
        solve(i);
        for (int k = 0; k < nS; ++k) {
            sum[s[k]] += dp[i][s[k]];
        }
    }
    for (int i = 0; i < nS; ++i) {
        if (sum[s[i]]) out << (char)s[i] << " " << sum[s[i]] << endl;
    }
    out.close();
}

USACO 2.2 Runaround Numbers – CPP solution

There are some solutions to this problem:
– Let’s say that N is the number of digits of our input number. We can just produce every possible variation with length N using the set {1,2,3,4,5,6,7,8,9}, check whether it’s bigger and a “runaround” number. This means we would have to do maximum N * N! steps. Is this a lot? It may pass the tests since N is maximum 9.
– Of course, there is a faster solution. We could just generate every possible runaround number (not definitely the next one) and check which is bigger and closer to the input number. Obviously, we will pick the second idea.

We can make something like a graph structure to show what’s the next index from our current state where the state is [length][index][number at this index].

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

char n[11];
int used[11] = {0};
int visited[11] = {0};
char cur[11];
char best[15] = "9999999999999";
int dp[11][11][11]={0};

void makeTable() {
    for (int i = 1; i< 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < 10; ++k) {
                dp[i][j][k] = (j+k)%i;
            }
        }
    }
}

bool ok(int l) {
    if (l>strlen(n)) return true;
    for (int i = 0; i < l; ++i) {
        if (n[i]!=cur[i]) return cur[i]>n[i];
    }
    return false;
}

void gen(int index, int cnt, int l) {
    if (cnt == l && index==0 && ok(l)) {
        if (strlen(best)>l || (strlen(best)==l && strcmp(best,cur)>0)) {
            for (int i = 0; i < l; ++i) {
                best[i] = cur[i];
            }
            best[l] = '\0';
        }
    }
    if (cnt > 0 && index==0) return;
    for (int i = 1; i<= 9; ++i) {
        if (used[i]!=1 && visited[dp[l][index][i]]!=1) {
            used[i] = 1;
            visited[dp[l][index][i]] = 1;
            cur[index] = (char)(i+'0');
            gen(dp[l][index][i],cnt+1,l);
            used[i] = 0;
            visited[dp[l][index][i]] = 0;
        }
    }
}

int main() {
    makeTable();
    ifstream in("runround.in");
    in >> n;
    in.close();
    ofstream out("runround.out");
    int q = strlen(n);
    while (strcmp("9999999999999",best)==0) {
        gen(0,0,q++);
    }
    out << best << endl;
    out.close();
    return 0;
}

USACO 2.2 Lamps – CPP solution

We could try to solve the problem like in the previous problems by generating every possible value. Is this quick enough? Apparently not since we have C operations (buttons) to be used where every operation can be a number from 1 to 4. Thus, we have 4^C steps where C has a maximum value of 10000. That’s really a lot. So, basically a simple solution would not work.
We will have to do some observations:
– Pushing a button even times will be the same as not pushing it at all. This drastically reduces the value for C.
– Some examples. If C = 2 we will have just a few unique solutions: {1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,1}. That’s all. If C = 3, we will be able to generate the same set if C=1 + {1,2,3},{2,3,4},{1,2,4}. And so on.
– With just 4 moves we can generate every possible state of the lamps. We don’t have to do more steps.
– Since C won’t be greater than 4, we could solve the problem recursively which means that our algorithms will do just 4^4 (256) steps. Fairly a small number.
– The number of solutions is a really small number. We wouldn’t have more than 8 solutions. We will keep our solutions in a set.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

int n,c;
string must;
string ex;

set<string> ans;

char toogle (int c) {
    if (c=='1') return '0';
    return '1';
}

bool check (string tmp) {
    for (int i = 0; i < n; ++i) {
        if (must.at(i)=='.') continue;
        if (must.at(i)!=tmp.at(i)) return false;
    }
    return true;
}

string doMove(string s, int move) {
    if (move == 1) {
        for (int i = 0; i< n; ++i) {
            char k = s.at(i);
            s.erase(i,1);
            s.insert(i,1,toogle(k));
        }
    } else if (move == 2) {
        for (int i = 0; i < n; i+=2) {
            char k = s.at(i);
            s.erase(i,1);
            s.insert(i,1,toogle(k));
        }
    } else if (move == 3) {
        for (int i = 1; i < n; i+=2) {
            char k = s.at(i);
            s.erase(i,1);
            s.insert(i,1,toogle(k));
        }
    } else if (move == 4) {
        for (int i = 0; 3*i < n; ++i) {
            char k = s.at(3*i);
            s.erase(3*i,1);
            s.insert(3*i,1,toogle(k));
        }
    }
    return s;
}

void solve(string tmp, int k) {
    if (k == c) {
        //cout << tmp << endl;
        if (check(tmp) && ans.find(tmp)==ans.end()) {
            ans.insert(tmp);
        }
        return;
    }
    for (int j = 1; j<= 4; ++j) {
        solve(doMove(tmp,j),k+1);
    }
}

int main() {
    ifstream in("lamps.in");
    in >> n >> c;
    int a;
    int cntOn=0,cntOff = 0;
    for (int i = 0; i< n; ++i) must.insert(i,1,'.');
    for (int i = 0; i < n; ++i) ex.insert(i,1,'1');
    while (1) {
        in >> a;
        if (a==-1) break;
        must.insert(a-1,1,'1');
        ++cntOn;
    }
    while (1) {
        in >> a;
        if (a==-1) break;
        must.insert(a-1,1,'0');
        ++cntOff;
    }

    in.close();
    if (c>4) c = 4;
    solve(ex,0);


    ofstream out("lamps.out");
    if (ans.empty()) {
        out << "IMPOSSIBLE" << endl;
    } else {
        set<string>::iterator it;
        for (it = ans.begin(); it !=ans.end(); ++it) {
            out << *it << endl;
        }
    }
    out.close();
    return 0;
}

USACO 2.2 Subset sums – CPP solution

We will make some observations:
– We know that the maximum value in the sequence is 39.
– The sum of all numbers from 1 to 39 is 780. However, we are interested in the subset of numbers which sums to maximum 390. Generally, if S is the sum of the numbers from 1 to n, we will just find the subset which sums to S/2.
– Obviously, the problem is NP-complete unless we use a technique such as dynamic programming. Using recursion to generate every possible subset will not pass the tests.
– If the sum is not divisible by 2, then we don’t have a solution. For example, for n=5 we don’t have a solution.

What’s the DP idea? We will try to generate every possible sum (less than the [sum of 1 to n]/2) of the possible subsets. In order to prevent repetition, we will find every possible subset using every number till i (i.e. every subset till 1, till 2, till 3… till n).

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

int n;

int sum = 0;
long long dp[40][391] = {0};

void calcSum()
{
    for (int i = 1; i <= n; ++i)
    {
        sum+=i;
    }
}

int main()
{
    ifstream in("subset.in");
    in >> n;
    in.close();
    ofstream out("subset.out");
    calcSum();

    if (sum%2 != 0)
    {
        out << 0 << endl;
    }
    else
    {
        sum>>=1;
        for (int i = 1; i<=n; ++i)
        {
            for (int j = 1; j <= sum; ++j)
            {
                dp[i][j] = dp[i-1][j];
            }
            ++dp[i][i];

            for (int j = 1; j<=sum; ++j)
            {
                if (dp[i-1][j]>0 && j+i<=sum) {
                    dp[i][j+i] += dp[i-1][j];
                }
            }
        }
        out << (dp[n][sum]>>1) << endl;
    }

    out.close();
    return 0;
}


We could save some space though by just using an 1-dimensional array for the possible sums. However, we will have to edit the inner cycle to start from sum and go down to 0.

USACO 2.1 Hamming – CPP solution

Obviously the set of numbers we can use is [0;2^b]. We will just have to generate all of the possible solutions. One of the ideas is to keep an array and generate every possible permutation of this array and check for the differences. However, this is really slow and it may not pass the tests. As you have probably read in the bit tutorial, we can use the & sign to check whether a bit is on or off.
For example, if A&i != B&i where A and B are numbers from the set and i corresponds to the bit we are considering, then we have a difference at the i’th bit.
So, we will generate every possible solution and select the best one. To check which one is the smallest, we will select the solution with the smallest length. This does not always yields the best solution, but if we generate the solutions in ascending order by the value of each element, then it will.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

int n,b,d;

int m;

bool dif(int f, int s) {
    int cnt = 0;
    for (int i = 1; i <= m;) {
        if ((f&i)!=(s&i)) ++cnt;
        i<<=1;
    }
    return cnt>=d;
}

string toString(int number) {
    string s;
    while (number!=0) {
        char c = (char)(number%10+'0');
        number /= 10;
        s.insert(0,1,c);
    }
    return s;
}

void print(vector<int> q) {
    for (int i = 0; i < q.size(); ++i) {
        cout << q[i] << " ";
    }
    cout << endl;
}

int main() {
    ifstream in("hamming.in");
    in >> n >> b >> d;
    m = pow(2,b);
    in.close();
    vector<int> ans;
    string ansS;
    ofstream out("hamming.out");
    for (int i = 0; i <= m; ++i) {
        int cnt = 0;
        string tmp;
        vector<int> seq;
        for (int j = i; j <= m && cnt < n; ++j) {
            bool isOk = true;
            for (int k = 0; k < seq.size() && isOk; ++k) {
                if(!dif(seq[k],j)) isOk=false;
            }
            if (isOk) {
                seq.push_back(j);
                tmp.append(toString(j));
                ++cnt;
            }
        }
        if (cnt==n && (ansS.length()==0 || ansS.length()>tmp.length())) {
            ans = seq;
            ansS = tmp;
        }
    }
    for (int i = 0; i < ans.size(); i+=10) {
        for (int j = 0; j < 10 && i+j < ans.size(); ++j) {
            out << ans[i+j];
            if (i+j!=ans.size()-1 && j!=9) {
                out << " ";
            }
        }
        out << endl;
    }
    out.close();
    return 0;
}

USACO 2.1 Sorting a Three-Valued Sequence – CPP solution

We could easily implement an algorithm to set every number to its correct place (zone). However, this would be slow though it may run fast enough to pass the tests at USACO. The latter algorithm would have running time of O(n^2) or O(3n) considering my ideas. However, we could solve the problem in O(n) time with some considerations:

– We don’t care about the sequence of moves. Just for its number of swaps.

– There are at most 3 distinct values.

– There are just two types of swaps – two-way swaps and three-way swaps. The first one has a cost of 1 and the second one has a cost of 2 swaps. Basically, we can do two-way swaps between 1 and 2 as long as there are 1’s in the second zone and 2’s in the first zone, etc. When we have for example 3’s in the first zone, 1’s in the second zone and 2’s in the third zone then we would have to do 3-way swaps.

We will just have to count the 1’s, 2’s and 3’s for each zone and calculate the number of possible 2-way and 3-way moves (times 2) adding them to the answer variable.

With some other considerations we could downgrade the running time to O(1).

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n;

int cnt[4] = {0};
int q[1001];
int table [4][4]={0};
int endIndex[4];
int startIndex[4];
int ans=0;

int getZone(int i) {
int number = q[i];
for (int k = 1; k< =3; ++k) { if (i>=startIndex[k] && i< =endIndex[k]) return k; } } void solve() { startIndex[1] = 0; endIndex[1] = cnt[1]-1; startIndex[2] = endIndex[1]+1; endIndex[2] = startIndex[2]+cnt[2]-1; startIndex[3] = endIndex[2]+1; endIndex[3] = startIndex[3]+cnt[3]-1; for (int i = 0; i < n; ++i) { ++table[getZone(i)][q[i]]; } int min1swap2 = min(table[1][2],table[2][1]); table[1][2]-=min1swap2; table[2][1]-=min1swap2; int min1swap3 = min(table[1][3],table[3][1]); table[1][3]-=min1swap3; table[3][1]-=min1swap3; int min2swap3 = min(table[2][3],table[3][2]); table[2][3]-=min2swap3; table[3][2]-=min2swap3; ans = min1swap2+min1swap3+min2swap3; int tripleswap = 0; for (int i = 1; i <=3; ++i) { for (int j = 1; j <= 3; ++j) { if (i==j) continue; tripleswap = max(tripleswap,table[i][j]); } } tripleswap<<=1; ans+=tripleswap; } int main() { ifstream in("sort3.in"); in >> n;
for (int i = 0; i < n; ++i) { in >> q[i];
++cnt[q[i]];
}
in.close();
solve();
ofstream out(“sort3.out”);
out < < ans << endl; out.close(); return 0; } [/code]

USACO 2.1 Castle – CPP solution

The idea:

We will make an adjacency list of the possible neighbors and an adjacency list of the walls while we are reading the data. The we examine every node in the graph and start a depth-first search from the current node if it has not been visited before. In this way we will find all the components. For every node we will also see its surrounding walls and connect the components (sum the sizes) to see whether the current concatenation is the biggest. Then we should only check which one is the wall and the direction of the removal. The running time of the algorithm would be O(4nm). As you will see in the code, we make a time-memory trade-off by pre-computing the possible situations of walls, the neighbors list and the non-neighbors list instead of computing them for each node.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define pii pair<int,int>

FILE * in,*out;

int n,m;

int walls[16][4] = {
    {1,2,4,8},
    {2,4,8,0},
    {1,4,8,0},
    {4,8,0,0},
    {1,2,8,0},
    {2,8,0,0},
    {1,8,0,0},
    {8,0,0,0},
    {1,2,4,0},
    {2,4,0,0},
    {1,4,0,0},
    {4,0,0,0},
    {1,2,0,0},
    {2,0,0,0},
    {1,0,0,0},
    {0,0,0,0}
};

int l[16] = {4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
int lCheck[16] = {0,1,1,2,1,2,2,1,1,2,2,3,2,3,3,4};

int check[16][4] = {
    {0,0,0,0},
    {1,0,0,0},
    {2,0,0,0},
    {1,2,0,0},
    {4,0,0,0},
    {1,4,0,0},
    {2,4,0,0},
    {1,2,4,0},
    {8,0,0,0},
    {1,8,0,0},
    {2,8,0,0},
    {1,2,8,0},
    {4,8,0,0},
    {1,4,8,0},
    {2,4,8,0},
    {1,2,4,8}
};



pii preIndex[16];

int used[51][51];
vector<pii> nb[51][51];
vector<pii> notNb[51][51];
vector<pii> components[2501];
int largest = 0;
int componentsSize = 0;
int combined = 0;
pii wall = pii(51,51);
char direction;


bool operator ==(pii a, pii b) {
    if (a.first == b.first && a.second == b.second) return true;
    return false;
}

vector<pii> getNb(int index, int x, int y)
{
    vector<pii> temp;
    preIndex[1] = pii(x,y-1);
    preIndex[2] = pii(x-1,y);
    preIndex[4] = pii(x,y+1);
    preIndex[8] = pii(x+1,y);
    for (int i = 0; i < l[index]; ++i)
    {
        temp.push_back(preIndex[walls[index][i]]);
    }
    return temp;
}

bool ok(pii coord)
{
    if (coord.first < 0 || coord.first >= n || coord.second < 0 || coord.second >= m) return false;
    return true;
}

vector<pii> getNotNb(int index, int x, int y)
{
    vector<pii> temp;
    preIndex[1] = pii(x,y-1);
    preIndex[2] = pii(x-1,y);
    preIndex[4] = pii(x,y+1);
    preIndex[8] = pii(x+1,y);
    for (int i = 0; i < lCheck[index]; ++i)
    {
        if (ok(preIndex[check[index][i]])) temp.push_back(preIndex[check[index][i]]);

    }
    return temp;
}

pii smallest(pii a, pii b)
{
    if (a.second < b.second) return a;
    if (a.second > b.second) return b;
    if (a.first > b.first) return a;
    return b;
}

void dfs(int i, int j, int cmp)
{
    if (used[i][j]!=-1) return;

    used[i][j] = cmp;

    pii tmpPair = pii(i,j);
    components[cmp].push_back(tmpPair);
    int sz = nb[i][j].size();
    for (int k = 0; k < sz; ++k)
    {
        dfs(nb[i][j][k].first, nb[i][j][k].second,cmp);
    }
}

int main()
{
    in = fopen("castle.in","r");
    fscanf(in,"%d%d",&m,&n);
    int c;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            fscanf(in,"%d",&c);
            nb[i][j] = getNb(c,i,j);
            notNb[i][j] = getNotNb(c,i,j);
            used[i][j] = -1;
            //cout << i << " " << j << " " << c << ":" << endl;
            //print(i,j);
            //cout << endl;
        }
    }
    fclose(in);
    out = fopen("castle.out","w");
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (used[i][j]==-1)
            {
                dfs(i,j,componentsSize);
                largest = max(largest,(int)components[componentsSize].size());
                componentsSize+=1;
            }
            int sz = notNb[i][j].size();
            pii tmpPair = pii(i,j);
            for (int k = 0; k < sz; ++k)
            {
                pii tmp = notNb[i][j][k];
                if (used[tmp.first][tmp.second]!=-1 && used[tmp.first][tmp.second]!=used[i][j])
                {
                    int current = (int)(components[used[i][j]].size() + components[used[tmp.first][tmp.second]].size());
                    //cout << i+1 << " " << j+1 << " " << tmp.first+1 << " " << tmp.second+1 << " " << current  << " " << combined<< endl;

                    if (combined < current)
                    {
                        combined = current;
                        //cout << tmp.first+1 << " " << tmp.second+1 << " " << i+1 << " " << j+1 << " " << combined << endl;
                        wall = smallest(tmp,tmpPair);
                        if (tmp.second < j || tmp.second > j) {
                            direction = 'E';
                        } else {
                            direction = 'N';
                        }
                    }
                    else if (combined == current)
                    {
                        //cout << tmp.first+1 << " " << tmp.second+1 << " " << wall.first+1 << " " << wall.second+1 << " " << combined << endl;
                        pii tmpWall = wall;
                        wall = smallest(tmp,smallest(tmpPair,wall));
                        if (wall != tmpWall) {
                            if (j < tmp.second || j > tmp.second) {
                                direction = 'E';
                            } else {
                                direction = 'N';
                            }
                        }

                    }
                }
            }
        }
    }

    /*
    for (int i = 0; i < componentsSize; ++i)
    {
        cout << i << " " << components[i].size() << endl;
    }
    */
    //pii s = smallest(pii(3,1),pii(4,1));
    //cout << s.first << " " << s.second;
    fprintf(out,"%dn%dn%dn%d %d %cn",componentsSize,largest,combined,wall.first+1,wall.second+1,direction);
    fclose(out);
    return 0;
}