Problem Link : CodeChef: Practical coding for everyone
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
The Answer is NO
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 CodeChef: Practical coding for everyone
Outputs No for this testcase and AC
1 Like
No,simple topological sort should give wrong answer
Similar Problem: Kick Start - Google’s Coding Competitions
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> 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())
{
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);
}
}
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
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.