PROBLEM LINK:
Author: Vinod
Tester: Vinod
Editorialist: Manjunath
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary Search, DFS of graph
PROBLEM:
Graph edges are being deleted one per day.We have to find sum of cost of days when graph can be colored using 2 colors such that no two vertices adjacent to each other colored with same color.Cost of day is considered as edges removed till that day.
QUICK EXPLANATION:
once the graph can be colored with 2 colors,after removing some more edges
also,it can be colored with 2 colors.So,we need to find first day when it can be colored using two vertices.then all days after that can also be colored with 2 colors till last day.we can easily find sum of those costs.
EXPLANATION:
once the graph can be colored with 2 colors,after removing some more edges
also,it can be colored with 2 colors.So,we need to find first day when it can be colored using two vertices.then all days after that can also be colored with 2 colors till last day.we can easily find sum of those costs.
we can binary search for the first day.
int cnt=count of edges;
int lo=0,hi=cnt,ans=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(can_be_colored(mid)){ // remove edges upto mid [0..mid) days not considering mid
ans=mid;
hi=mid-1;
}
else
lo=mid+1;
}
//by removing at least ans edges ,graph can be colored with 2 colors.
final_answer=((cnt)* (cnt+1) )/2 - (ans * (ans+1))/2;
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.