constructing dodge ball team

Vote count:

0

A coach is trying to construct a dodge ball team. Each player is assigned a student ID, and if one player's ID divides by other player's ID, they fight. So the couch wants to make a team so that no one fights in the team. Given the number N (ID is assigned 1 to N), find out the minimum number K where the couch is unable to make a team in which no one fights.

input (N): 3 output (K): 2

For example, N = 3,

K = 3, {1,2,3} --> Player 1 and 2 has a fight.

K = 2, {2,3} --> No one fights.

input (N): 3 output (K): 2

N = 4,

K = 4, {1,2,3,4} -> more than a pair of players (1,2), (1,3), etc, fights.

K = 3, {1,2,4}, {2,3,4}, {1,3,4} --> players fights in all teams.

K = 2, {2,3} --> No one fights.

So basically, given N, find out the minimum K that a couch can't make any combination of K players so that no one fights. (This is also the maximum number K'+1 where a couch can find at least one team of K' where no one fights.)

A greedy solution I and my friend came up with is try finding the maximum set from the given N. The optimal set must contain the big numbers because since if we start putting small numbers, 2, 3, ..., all the multipliers of these numbers can't be included. So we can start putting N to N/2 in a set as long as the new number is not a divisor of some number already included in the set. We are not entirely sure if this solution would be correct, so we would love to discuss the correctness of our solution and hear other people's ideas.

I was asked to solve this coding problem during an online coding test but couldn't figure it out how to solve.

asked 37 secs ago

pandagrammer

142

constructing dodge ball team