Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

A problem on DoTA hero pool.

Revision en3, by Yuki726, 2019-05-15 13:42:18

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Yuki726 2019-05-15 13:42:18 1 Tiny change: 'a mid hero we can al' -> 'a mid hero, we can al'
en2 English Yuki726 2019-05-15 13:38:06 41 Tiny change: 't picks a hero we c' -> 't picks a mid hero we c' (published)
en1 English Yuki726 2019-05-15 13:33:15 503 Initial revision (saved to drafts)