can anyone please provide me with a test case that on which my my solution fails as per first sub-task.
probelm link :
My Submission:
https://www.codechef.com/viewsolution/30435850
1
4 2
2 3 1 4
3 2 4 1
try this
your program outputs
3
0 4 4 0
but ans will be
2
0 4 1 0 ( 0 1 4 0 also possible)
Looks like i haven’t understood the problem properly. thanks 
Hey, I tried your test case and got the output:
2
0 1 4 0
still i am getting WA in subtask 1 and TLE in 1 task of subtask 2. It will be really helpful if you provide a strong test case or please look at my solution and point me out.
https://www.codechef.com/viewsolution/30332167
This code is quite unclear, could you just explain your logic?
while(k--) {
for(int i=0; i<n; ++i) {
cin >> a[i], --a[i];
//remove edges
for(int j=0; j<i; ++j)
adj[a[j]][a[i]]=0;
}
}
consider
4 1
1 2 3 4
here why are we removing edges (1 3), (2 3), (1 4) ,(2 4) ,(3 4) what actually we are trying to do by removing this edge ?? please help!!!
for each permutation i stored from j>i and j<N elements in a set and stored them as pair in vector. Eg 1324 {1,(3,2,4)}, {3,(2,4)}, {2,(4)} and if in other permutations there is an element such that it violates topological sort, i have removed those. Eg: if in new permutation {2,{1,3}} , so now i will have {1,(3,4)}, {3,(4)} from 1st permutation and second will have {2,()}. I have kept a frequency array to store how many time a number is occuring over all sets and then finally to choose which node will point its outer edge to which i thought of if a node has multiple elements choose which is least in frequency array and has’nt been used before. If all the elements have been used then the 1st element of the set is assigned to the node.
I hope i have explained my logic, Please help in any way possible
But i don’t think so this solution is optimal for large number of nodes. how can you proof your code optimality?
I was getting TLE because of the set, after changing it to unordered_set , TLE got removed but still getting WA.
Using hash set has reduced the time constraints , its just adding then removing nodes which violates and is deciding just by observing which nodes to be used as the number of nodes with indegree has to be minimum.
I would love to but my solution is getting WA, waiting for pro coders to judge if my approach is correct or not. If they point me the mistake i will improve and explain you in detail.
Problem link : CodeChef: Practical coding for everyone
My Solution : https://www.codechef.com/viewsolution/30307347
Correct solution (of @vd_patel ) : CodeChef: Practical coding for everyone
I have checked my code and vd_patel’s code on like 15-16 different input and everytime both output are same but still i am getting WA in all subtask.
so, can you please tell me where am I going wrong or any testcase where my output is wrong.
can i know what approach did you followed?
@tri123
First of all i created a list where list[i] contained all the nodes except i which means that if n=5 then list[1] will contain 2,3,4,5 and list[2] will contain 1,3,4,5 and so on.Now for each of the next k lines which is a permutation of 1 to N , I took the input in array a and removed a[j] from the list of a[i] for all j<i and I did this for all i<=n.Let’s take an example;
Suppose the permutation is : 3 2 4 1 5
Then i removed 3 from list[2]
removed 3 and 2 from list[4]
removed 3,2 and 4 from list[1]
and removed 3,2,4 and 1 from list[5]
After doing this for each one of the k lines , i iterated over all the list and counted the occurence of each element in the list.
For eg:if list[1]=5
list[2]=4,5
list[3]=2,4,1,5
list[4]=1,5
list[5]=empty
then c[1]=2(in list[3] and list[4])
c[2]=1
c[3]=0
c[4]=2
c[5]=4
then created an array flag initialised to 0
Now for each i , the answer would be the node present in list[i] with minimum count && flag[node]==0 and if the list is empty or flag of all the elements is 1 then answer will be 0 and will set the flag[ans]=1
I used the same logic.
Can you please help me?@anon38711361
Problem link : CodeChef: Practical coding for everyone
My Solution : https://www.codechef.com/viewsolution/30307347
Correct solution (of @vd_patel ) : https://www.codechef.com/viewsolution/30378162
I have checked my code and vd_patel’s code on like 15-16 different input and everytime both output are same but still i am getting WA in all subtask.
so, can you please tell me where am I going wrong or any testcase where my output is wrong.
5 3
1 4 5 2 3
1 3 4 5 2
4 1 5 2 3
Can the output of the code be
2
5 0 0 5 2
Please help me to clear my confusion?
Okay I see the problem with this. I was trying a similar approach in the beginning. Think of a case like this:
list[1] = {3, 4}
list[2] = {3}
list[3] = {}
list[4] = {3}
In this case, I think you will output
3
3 0 0 0
Whereas the right answer is
2
4 3 0 0
I don’t know if this is the optimal solution but your edges are valid. However, should it not be
3
5 0 0 5 2
?