# Project Code 1.0 : PCO12020-POWK doubt

Guys,I have a slight doubt in this question,POWK.for the following tc :-
1
3
2
k1 k2
k1 k3
Shouldn’t the answer be “NO” since we can’t say k2 > k3 or k3>k2 by any means.
I got WA when i considered this and modified the topological sort.Though after contest i saw some AC sols which just do topological sort and print YES and a sequence without considering this .Please help.Thanks in advance.

2 Likes

@rakshi20_20 I think the answer must be NO because in qstn it was clearly stated there must be unique ans

Can someone tell me what is wrong in my code?https://www.codechef.com/viewsolution/33614358

This gives WA and on the other hand, the AC solutions are outputting “YES”

True, even I noticed this. Not so strong test cases it seems.

Nah bro…
See my solution https://www.codechef.com/viewsolution/33608855
Outputs No for this testcase and AC

1 Like

No,simple topological sort should give wrong answer

``````1
3
2
k1 k2
k1 k3
``````

these can be arranged in increasing order so the answer is YES since all values are distinct,
but there is no way to compare `k2` & `k3` so any valid Topological Order is `true`

this dosen’t make any sense. I think author made test cases that have only one valid Topological Order.

Well, damn. My AC code outputs

``````YES
k2
k3
k1
``````

I used topological sorting with Kahn’s algorithm.The indegree of nodes `k2` and `k3` and 0 initially. After removing them, the indegree of `1` becomes 0. So my code outputs “YES” along with that order.
My code:

``````#include <bits/stdc++.h>

using namespace std;

const int size = 1e2+1;
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())
{
int curr = pq.top();
res.push_back(curr);
pq.pop();
{
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;
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);
}
}
``````

Will adding Kosaraju’s or Tarjan’s algorithm for finding the number of strongly connected components work? Becasue from my observations of the sample testcases, the answer was “NO” only when the number of strongly connected components exceeded 1 (and you cannot perform topological sort). Someone please let me know about this.
And @rakshi20_20, thanks a lot for pointing this out. Gotta improve my solution now .

1 Like

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.

1 Like

I will tell what I did-
It is pretty straightforward.
Consider the test case-

``````4
7
k1 k2
k1 k2
k2 k3
k1 k3
k2 k3
k3 k4
k1 k4
``````

Consider the `first column` as `list-1` and `second` as `list-2`. I’m first assuming that a valid unique permutation exists such that all above requirements are satisfied.
Observe that `k4` is not present in `list-1`. This suggests that `k4` has least power as it didn’t win any competition(I have assumed that a unique valid permutation exists and till now no constraint has been broken). So, till now `arr = [k4]`.
I will remove the fights where `k4` is involved as now I know the exact place of `k4`.
Fights reduce to-

``````k1 k2
k1 k2
k2 k3
k1 k3
k2 k3
``````

Now, repeat the same thing and append `k3` to arr. So, `arr = [k4, k3]`

Repeating till we get a valid permutation - `arr= [k4, k3, k2, k1]`

What are the conditions when the ans will be **No**?

At any stage (before we get valid permutation, if possible),

• If there this no one (out of remaining people which are yet to be placed in `arr`) which is not present in list-1 (or simply everyone is present) that means the input is invalid. Ideally, this case should not occur according to problem statement but the problem has an input (input-2) where it occurs. I’d consider that input incorrect. Thus, if input is incorrect, no valid permutation would exist.
• If there are more than 1 persons which are not in list-1 means we can’t conclude and multiple valid permutations may satisfy the constraints. There is no unique answer. So, we’ll output No.
Code in Python3
``````t=int(input())
for _ in range(t):
n = int(input())
m = int(input())
arr=[]
for i in range(m):
a,b=input().split()
arr.append((int(a[1:]),int(b[1:])))
ans=[]
tot=[x for x in range(1,n+1)]
while True:
if len(ans)==n:
break
d={}
for i in arr:
if i[1] not in ans:
d[i[0]]=1
ele=list(set(tot)-set(d.keys()).union(set(ans)))
if len(ele)!=1:
ans = "NO"
break
ans.append(ele[0])
if ans=="NO":
print(ans)
else:
print("YES")
for i in ans:
print('k'+str(i))
``````
1 Like

yeah i think we have to just print topological order. According to the question k4 and k6 can not win to each other at the same time.
But if we consider the topological order then there will be a cycle
between k4 and k6 so i think test cases are made according to the topological order but not considering the question stated.
There is fault in the test cases

1 Like

Yes…It is indeed topological sorting.
TS doesn’t exist if it is not a DAG.
So, yeah, second input forms a cycle…so, no valid TS permutation as I explained above.
If for any input TS exists, it should be unique else answer will be No.

2 Likes

Thanks for the solution…maybe those which I saw somehow managed to pass testcases . Anyways thanks for providing

@anon53253486 yeah…I ,too, need to improve my WA solution

I did topological sorting using a queue but every time a node was pushed to queue,I was checking if only a single node had in-degree==0 which means it’s the highest (orderwise) among all left. But this gave me WA,any ideas why it fails ?

Can you attack the relevant code? I’ll reply in some time.

Yeah Sure…here’s the link to my solution
https://www.codechef.com/viewsolution/33616776