Corey's Party (AIO 2014: Australia)

NaN.

From International Olympiad in Informatics Training: Path to Gold course

Please provide a hint regarding what algorithm to use for the following problem: Given an undirected graph of N nodes and M edges find the maximum size of a subgraph of the graph such that the degree of each node is greater than equal to A and degree of each node is less than equal to K - B. Here K refers to the size of the subgraph and A and B are supplied in the input.

This is an Australian Informatics Olympiad question (with other details involving the theme that I have removed). Subtasks 1 worth 50 marks is for b = 0 which can be done using greedy approach. Hints for the general please.

Australian Informatics Training Site

In the second sample case, Corey can invite friends 1, 2, 4, 5 and 6. This satisfies Corey's constraint that every guest must know at least 2 other guests and not know at least 1 other guest. Corey's Partypartyin.txtpartyout.txt1 secondYour friend Co

http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio14int&problemid=780

Category: International Olympiad in Informatics

Comment