kritak's blog

Can anyone tell me what I am missing in this solution for SPOJ-KFSTB problem.
By kritak, history, 4 years ago, In English

SPOJ-KFSTB

I am using dp with dfs to calculate the number of paths to each point. Can somebody tell me what am I missing?

const int mod = 1e9 + 7;

void solve () {

int C, B, S, T;
cin >> C >> B >> S >> T;

vector<ll> graph[C + 1];
vector<bool> vis(C + 1);

for (int i = 0; i < B; i++) {
    ll x, y;
    cin >> x >> y;
    graph[x].push_back(y);
}

vector<ll> dp(C + 1);
dp[S] = 1LL;
stack<ll> st;
st.push(S);

while (!st.empty()) {
    ll v = st.top();
    st.pop();
    vis[v] = true;

    for (ll u: graph[v]) {
        dp[u] = (dp[u] + dp[v]) % mod;
        if (!vis[u])
            st.push(u);
    }
}

cout << dp[T] % mod << "\n";

}

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin >> t;
while (t--) {
    solve();
}

}

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

"Have you tried the following:

  • Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)
  • Write a program to generate thousands of small (!) test cases
  • Using those two, find a test case where your program gives the wrong answer
  • Use print statements or a debugger to see where exactly your program does the wrong thing.

98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms."

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea of using DFS is wrong. Let say there is path from 'A' to 'B' and your dfs chooses this path, now the possibility is that there can be other paths merging in this path, but since you already visited the previous path you will not update the result. Use topological sort instead.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Consider these edges exist in input 

s->x
s->a 
a->b
b->x
b->t
x->t

so you will push x and a in queue and value of dp[x] will be 1 when you wil pop it out. Now you will add dp[x] to dp[t]. But you must have noticed that there are 2 ways of reaching x 

s->x 
and 
s->a->b->x

So you should have added 2 in dp[t].

If you want to use bfs you have to do it topologically i.e. only push x in queue when all of its parents have been pushed in and popped out of queue.

→ Reply