There are approximately 35 mid heroes in dota 2. You are given a matrix winprob[35][35], where winprob[i][j] denotes the probability of ith hero winning against jth hero in midlane (matrix is derived from previously played games).
Problem : What's the minimum cardinal subset of heroes (to learn) such that when the opponent picks a mid hero, we can always pick a hero from our subset and get the probability of winning atleast (60%).
I can only think of bruteforce. Is there any better algorithm?
I believe it can be solved greedily. I would first determine for each hero the set of heroes he beats with pr >= 60% (this is O(N^2)). Then create DSU to keep all enemies we can beat. On each step pick a hero with the largest set of enemies he can beat but consider only those enemies that are not in DSU yet (such hero on each step could be found in O(N) since DSU search is Linear and overall is N^2 in the worst case). I believe the resulting set will be minimal.
I think, your approach is wrong. Consider following case:
Hero 1 can beat heroes 18-35 (18 enemies)
Hero 35 can beat heroes 1-17 (17 enemies)
Hero 10 can beat heroes 2-34 (33 enemies)
Other heroes can beat no one.
Your solution will first pick the 10th hero and then the 1st and 35th, because they are the only who can beat each other. But the optimal answer is 2 heroes — 1st and 35th, since they can cover the whole set.
Yes, you are right, thanks for pointing
This problem is equivalent to minimum hitting set and therefore NP-hard, so you cannot hope for better than exponential time.
There is no O(2^cn) algorithm with c < 1 for minimum hitting set unless the exponential time hypothesis fails, and a O(n 2^n) algorithm is easy, so there's not much you can do except heuristics.
It's NP-hard even if we force
winprob[a][b] + winprob[b][a] = 100%. For a reduction, if we have $$$n$$$ elements and $$$m$$$ sets, make $$$n+m+3$$$ heroes, the first $$$n$$$ corresponding to the elements, the $$$m$$$ corresponding to sets, and then $$$3$$$ more that we have to pick in any solution.Set
winprob[a][b] = 100%if hero a corresponds to an element that appears in the set that hero b corresponds to. Also setwinprob[a][b] = 100%when hero a is one of the 3 additional heroes, and hero b corresponds to any of the elements. Let the additional heroes be a1, a2, a3. Setwinprob[a1][a2] = 100%,winprob[a2][a3] = 100%,winprob[a3][a1] = 100%. Set the reverse win probabilities to zero, and set all other win probabilities towinprob[a][b] = 50%.We need to pick the three additional heroes, since no hero other than those can beat them. Then we automatically beat all of the heroes corresponding to elements. Then we have to choose a minimum hitting set of the heroes corresponding to elements to beat the heroes corresponding to sets.
To solve the hero problem with minimum hitting set, Have the heroes as elements, and make a set for every hero, consisting of every hero that can beat that hero with probability at least 60%.
That problem is the same as https://en.wikipedia.org/wiki/Set_cover_problem (NP-complete). I can give you a O(3^n) solution but that's hardly better than backtracking + heuristics (and actually worse than bruteforcing for this instance). Can anyone solve this with a clean meet in the middle solution?
Can we not iterate over all subsets (2^n of them) and check whether they can beat any enemy picked hero in o(n)? which leads to o(n*2^n). Even though it doesn't satisfy the constraints, its better than 3^n right?
Yes I was thinking about the original problem. Since n == m you can do that. Also to make it clear it would be something like max(3^n, 2^(m/2))