Admiral_General_Aladeen_'s blog

Need help in Kickstart Round C 2nd question
By Admiral_General_Aladeen_, history, 4 years ago, In English

I have tried to solve this question using topological sort. I am getting correct output for 3 out of the 4 test cases given in the sample test cases on kickstart website. I will be very thankful if someone can help me find the mistake in my code. I have been trying to find any mistake but couldn't

Approach — To get the correct ordering of letters I have made a string out of all columns starting from last row to first row. I am adding a letter of its type only once in a string. Now using all these strings I am building a graph pointing from bottom row to top row. Now I am just applying topological sort to get the ordered string as the answer.

Here is the link to my solution — http://p.ip.fi/IVy2 Here is the link for ideone (you can see that I am getting correct output for 3/4 cases) : https://ideone.com/OXNJcW

Thank you

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The approach I used is

  1. Read in the grid into a vector.

  2. Construct graph with vertices numbered 0-25 where x -> y if and only if y — 'A is seen directly above x — 'A' at least once in the grid.

  3. Run topological sort on the graph.

  4. Print the result.

There must be an implementation mistake on your part, which will be hard for other people to spot.

My code:

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

using ll = long long;
using ld = long double;
#define MAX(type) numeric_limits<type>::max()
#define MIN(type) numeric_limits<type>::min()

void dfs(int s);

int r, c;
vector<string> g;
vector<bool> seen;
vector<vector<int>> adj;
vector<vector<bool>> adjM;
vector<int> state;
string ans;
bool isPossible;

void dfs(int s) {
    if (state[s] == 2) {
        return;
    } else if (state[s] == 1) {
        isPossible = false;
        return;
    }
    state[s] = 1;

    for (auto u : adj[s]) {
        dfs(u);
    }
    state[s] = 2;
    ans += 'A' + s;
}

void solve() {
    cin >> r >> c;
    g.resize(r);
    seen.resize(26, false);
    for (int i = 0; i < r; i++) {
        cin >> g[i];
        for (int j = 0; j < c; j++) {
            seen[g[i][j] - 'A'] = true;
        }
    }

    adj.resize(26);
    adjM.resize(26, vector<bool>(26, false));
    for (int i = 1; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (g[i - 1][j] != g[i][j] &&
                !adjM[g[i][j] - 'A'][g[i - 1][j] - 'A']) {
                adj[g[i][j] - 'A'].push_back(g[i - 1][j] - 'A');
                adjM[g[i][j] - 'A'][g[i - 1][j] - 'A'] = true;
            }
        }
    }

    state.resize(26, 0);
    ans = "";
    isPossible = true;
    for (int i = 0; i < 26; i++) {
        if (seen[i]) {
            dfs(i);
        }
    }

    if (isPossible) {
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    } else {
        cout << -1 << "\n";
    }

    // Need to reset for the next test case!
    g.clear();
    seen.clear();
    adj.clear();
    adjM.clear();
    state.clear();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
    return EXIT_SUCCESS;
}
→ Reply