Project Code 1.0 : PCO12020-POWK doubt

editorials for all the sums will be out soon

Hi,

As mentioned in the last line of the problem statement. “There will always be a unique answer to each test case

So you won’t get such inputs while testing. The only cases the answer should be no are the ones where ranks cannot be determined i.e. the graph formed is cyclic.

1 Like

@vedant_k07 What is the approach for last problem

1 Like

hey!! can anyone check why my code gives WA

  1. I check first graph is cyclic or not if it is cyclic than answer is no
  2. topological sort using kahn algo printing yes
    CodeChef: Practical coding for everyone

Many users have mentioned using topological sorting to solve this problem, I used a slightly different approach.

firstly i tried to calculate all the possible deduction i can make based on the give fight results, for which i used a set and used the condition that if for two pairs {p1,p2} and {p2,p3}, then {p1,p3} is also a pair. I kept on adding pairs of these kinds untill i could, and then used simple logic that the most powerful knight shoul defeat all other n knight and thus should apperar n-1 time as the first element, similarly for all the other knights also.

link to my code

You just need to check if the number of nodes in the queue are greater than 1 at any time. If so, the answer is “NO” because multiple topological sorts will exist.
The code is:

#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);
    }
}

Topological sort suffices for this problem. Very simple! :slight_smile:

hello coders ,need your suggestion and review .
here goes my documented code in python3.

will be waiting for review.
in case any thing in ambiguous or unclear,plz let me know
happy coding.

Bro,I tried to do the same thing …can you please have a look at my code and tell where is it going wrong .
https://www.codechef.com/viewsolution/33616776

Hi,
We will share the editorial by the end of the day

2 Likes

Thanks!