Can someone tell me if these lectures are useful for INOI ?
Need Help to find the mistake
I am getting WA.
I looked at your solution.
but can’t find the mistake.
import java.util.;
import java.lang.;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int test=sc.nextInt();
for(int t=1;t<=test;t++)
{
int n=sc.nextInt();
int m=sc.nextInt();
int visited[]=new int[n+1];
int color[]=new int[n+1];
Map<Integer,List<Integer>> al=new HashMap<>();
for(int i=1;i<=n;i++)
al.put(i,new ArrayList<Integer>());
for(int i=0;i<m;i++)
{
int u=sc.nextInt();
int v=sc.nextInt();
al.get(u).add(v);
al.get(v).add(u);
}
boolean ans=true;
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
boolean ca=check(i,0,al,visited,color);
if(ca==false)
ans=false;
}
}
System.out.println("Scenario #"+t+":");
if(ans==false)
{
System.out.println("Suspicious bugs found!");
}
else
{
System.out.println("No suspicious bugs found!");
}
}
}
public static boolean check(int v,int c,Map<Integer,List<Integer>> al,int visited[],int color[])
{
visited[v]=1;
color[v]=c;
//System.out.println("trace "+v+" "+color[v]);
for(int node:al.get(v))
{
if(visited[node]==0)
{
c=c^1;
boolean ans=check(node,c,al,visited,color);
if(ans==false)
return false;
}
else
{
// System.out.println("tr "+v+" "+color[v]+" "+node+" "+color[node]);
if(color[v]==color[node])
return false;
}
}
return true;
}
}
In the counting rooms problem on CSES, I have used the same algorithm used in video but I am still getting TLE on test cases 9 and 10. What is happening? I’m using python 3. Did anyone’s python solution get accepted?
Code is here.
which problem are you solving?
in dfs function you are passing visited array and I am not sure if in python function calls are by reference or by value.
if python follows call by value then you need to stop passing visited array and define it globally
1 Like
i am trying to solve this problem.
here is my solution: Solutions/Bug_Life.java at master · jarvis-007/Solutions · GitHub
By the way i completed the graph theory playlist today. It was really awesome.
Thank you very much. Eagerly waiting for more videos.
your code is perfectly fine except at one point where you are messing with color.
in dfs function when you are making recursive calls to child of certain node ,
if parent has color c then all it’s children must get color c^1.
what you are doing is changing the value of color by setting c = c^1.
this should not happen.
suppose current node say node 1 has 3 children(2 , 3 and 4) nodes and c for node 1 is 0.
so all child of node 1 should get color 1.
suppose you are making call to node 2 then node 3 then node 4.
when you are making call to node 2 you are updating c to 1 from 0 and making call to 2.
so this is good
but now when you have to make call to 3 you are again updating c , this time it will become 0 so 3 will get color 0 which is not good.
so do not update c again and again , just pass the value c^1 in dfs function.
in simple words , instead of this
if(visited[node]==0)
{
c=c^1;
boolean ans=check(node,c,al,visited,color);
if(ans==false)
return false;
}
do this
if(visited[node]==0)
{
boolean ans=check(node,c^1,al,visited,color);
if(ans==false)
return false;
}
.
1 Like
it was a silly mistake.
Thank you for pointing that out.
i am waiting for further videos on graph theory. 
I did it globally and now it’s TLE in one more test case (no. 8) too. It’s not reference by value by the way. Is there any other method that’s faster than this?
give me the link of updated submission , I am not very good with python but I will try to figure out the problem
1 Like
you’re welcome man
1 Like
Hey! Can you please solve this problem from codeforces?It is a dp problem and I can’t solve it for the larger constraints
Thanks!
This is where I declared the matrices globally :-
Click Here
And this is where I tried a lot of modifications and declared the matrices locally :-
Click Here
I don’t know if you’ll be able to access the links but in case you can’t then here are the two codes as well :-
Globally
Locally
If you can’t figure out the problem, then it’s fine anyway because a real test most likely won’t have time limit this tight.
I think if you use fast IO , it can pass time limit.
I submitted your solution with global array and it is getting TLE in 3 test cases , in all those 3 test cases N and M are 1000 and 1000.
it’s not like your solution is asymptotically slower , if it was the case then your code would not be able to solve Test Case 7 which also has N and M as 1000 * 1000.
read this for fast IO or google : performance - Fastest stdin/out IO in python 3? - Stack Overflow
as I said again I am not very good with python so it will take a lot of time for me to implement and debug.
try for once
after a small change that I made , now the solution is getting TLE on only 2 test cases (3 previously) : https://ideone.com/HIlpK8
I am sure if you use fast I/O it will pass the time limit
I will try to use even faster I/O. Thanks.
gonna do this after exams, thanks a ton man
you’re welcome
Bro In Your Bridge Finding Algorithm , I think You might be missed some edge cases for disconnected graph ???
For example suppose this is the Question
Now suppose Tc is
1
5 3
0 1 1 2 3 4
3 4
Basically Graph is in the form
0-1-2
3-4
and asked that is 3-4 is bridge then Cp algo code giving WA.
{Our code give 0 but actually ans is 1(yes) }
My Solution {After Learning From Your Video}
PS:-
I have already spend 3+ hours to Get AC in this Question, Please let me know how to correct this code.
Finally,
YOU ARE OUR INSPIRATION, THANK-YOU FOR EVERYTHING WHICH YOU HAVE DONE FOR US!!!.
Thank you for this @waqar_ahmad224, a dumb suggestion/question, are you planning to make these videos available as a playlist on Youtube on the channel? so that one(like me) can watch all of them in one sitting? 
Please suggest.