Cases are Missing in the POWK Project_Code_1.0

help
1

https://www.codechef.com/viewsolution/33594282
Input:
1
6
3
k1 k2
k3 k4
k5 k6

I tried above input in the above accepted solution and it gives the following
Output:
YES
k2
k1
k4
k3
k6
k5

But the input does not gives a unique answer.And the answer should be no.
@vedant_k07 @codechef plz help.

2

Test cases might be weak.
I don’t really understand the inputs in the problem.
Consider the input-

6
9
k2 k1
k3 k2
k4 k3
k4 k6
k5 k4
k1 k5
k2 k1
k6 k4
k4 k6

How can k6 win in one round against k4 and in another k4?
This test case doesn’t follows what the problem statement says.

3

That is clear case of no, as the behaviour of knights is not defined clearly . And in my input examples also the input is undefined and so answer should be NO. But the accepted solution says yes. Test Cases needs to be improved as many like me would be solving for the given test case and might not get the proper way for implementation. But the test cases were weak and no one can predict it without submitting .

4

Prove me wrong-
You quoted-
’’’ as the behaviour of knights is not defined clearly ‘’'
If this is the case, then answer for any input will be No as in some random fight between k1 and k2, k1 might win. In some other k2 might win.
Secondly, the problem statement itself says this-
The knight who wins has more power than the knight who loses. No two knights have equal power.

If the behaviour was ambiguous…you can’t conclude anything.

5

Hi,

As seen in the sample input, we print NO if the ranks are undetermined, i.e. they form a cyclic graph.
If the graph is not cyclic, you use topological sort on it.

The input you mentioned can have multiple solutions. As mentioned in the last of the problem statement " There will always be a unique answer for each test case."
So cases, which have multiple solutions are not given to you.

Although checking if you can get more than one answer when using topological sort will not affect your submission. There is no need to do that as you will always have a unique solution.

I hope this helps you and thank you for asking the question.
We hope to make the questions easier to understand next time.
Your input is valuable to us.

6

Bro the link to solution is not mine it is of someone else. I was trying to get the answer for this undefined behaviour and it was giving yes for the test case. I did not tell that you were wrong.I also told the same thing that you are trying to tell.

1 Like
7

I just figured that if the size of the queue is greater than 1 at any time (the queue has nodes with in-degree 0), the answer is “NO” because multiple topological sorts will exist.
All you need to do is add if (pq.size() > 1) break; in the while loop of Kahn’s algorithm where pq is the priority queue.
The code is simply

#include <bits/stdc++.h>

using namespace std;

const int size = 1e2+1;
vector <int> adj[size];
vector <int> res;
vector <int> in(size);

void kahn(int n)
{
    priority_queue <int, vector <int>, greater <int>> pq;
    for (int i = 1; i <= n; ++i) if (in[i] == 0) pq.push(i);
    while (!pq.empty())
    {
        if (pq.size() > 1) break;
        int curr = pq.top();
        res.push_back(curr);
        pq.pop();
        for (int child : adj[curr])
        {
            in[child]--;
            if (in[child] == 0)
            pq.push(child);
        }
    }
    if (res.size() != n) cout << "NO\n";
    else {
        cout << "YES\n";
        for (int i : res)
        {
            string ans = "k";
            ans.append(to_string(i));
            cout << ans << '\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        string u, v;
        cin >> n;
        cin >> m;
        for (int i = 0; i < m; ++i)
        {
            cin >> u >> v;
            adj[stoi(v.substr(1, v.size()-1))].push_back(stoi(u.substr(1, u.size()-1)));
            in[stoi(u.substr(1, u.size()-1))]++;
       }
       kahn(n);
       res.clear();
       for (int i = 0; i < size; ++i) adj[i].clear();
       in.clear();
       in.resize(size);
    }
}

Pretty simple and my first time using topological sort :slight_smile:

1 Like