KETEKIR1 Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

DIFFICULTY:

MEDIUM

PREREQUISITES:

Bitmasking

PROBLEM:

Given an undirected acylic graph, find the minimum number of vertices to remove from the graph such that the maximum degree of the nodes of the graph decreases by at least 1.

QUICK EXPLANATION:

Run a bitmask, since the contraints are less than 20 its possible in the time limit, on the nodes selecting a set of them one at a time, using btimasking which can be done due to constraints. Find the maximum degree in each case and record the number of nodes to be removed in each case. Print the minimum number of nodes to be removed.

EXPLANATION:

Using bitmasking enumerate all the various ways in which the nodes can be selected. In each case, find the maximum degree of the nodes. If the maximum degree of the nodes is decreases at least by 1, record the value of the number of nodes that aren’t selected in that case. Print the maximum of them.

SOLUTIONS:

Setter's Solution 
using System;
using System.Collections.Generic;
class some
{
	public static int n;
	public static int[,]arr;
	public static void Main()
	{
		n=int.Parse(Console.ReadLine());
		arr=new int[n,n];
		int k=0;
		int t=0;
		for(int i=0;i<n;i++)
		{
			string[]vals=Console.ReadLine().Split();
			int count=0;
			for(int j=0;j<n;j++)
			{
				arr[i,j]=int.Parse(vals[j]);
				count+=arr[i,j];
			}
		
			k=Math.Max(k,count);
		}
		for(int i=0;i<n;i++)
		{
		
			int count=0;
			for(int j=0;j<n;j++)
			{
			
				count+=arr[i,j];
			}
			if(count==k)t++;
		}
		int mcount=n;
		double fval=(n+(k-1)*t)/2*k;
		for(int i=0;i<(1<<n);i++)
		{
			int[,]temp=new int[n,n];
			int count=0;
			for(int j=0;j<n;j++)for(int k1=0;k1<n;k1++)temp[j,k1]=arr[j,k1];
			for(int j=0;j<n;j++)
			{	
				if((i&1<<j)!=0)
				{
					for(int k1=0;k1<n;k1++){temp[j,k1]=0;temp[k1,j]=0;}count++;
				}
			}
			int kk=ct(temp);
			int tt=ck(temp,kk);
			if(count==n)continue;
			if(kk<k)
			{
				if(count<mcount)
				{
					mcount=count;
				}
			}
		}
		if(mcount<=fval)
		{
			Console.WriteLine("Yes, "+mcount);
		}
		else Console.WriteLine("No");
	}
	public static int ct(int[,]temp)
	{
		int ret=0;
		for(int i=0;i<n;i++)
		{
			int count=0;
			for(int j=0;j<n;j++)
			{
				count+=temp[i,j];
			}
			ret=Math.Max(ret,count);
		}
		return ret;		
	}
	public static int ck(int[,]temp,int kk)
	{
		int ret=0;
		for(int i=0;i<n;i++)
		{
			int count=0;
			for(int j=0;j<n;j++)
			{
				count+=temp[i,j];
			}
			if(count==kk)ret++;
		}
		return ret;		
	}
}