# NPLFTC-Editorial

Author: Vinod
Tester: Vinod
Editorialist: Manjunath

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.