Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove matches that will not affect the top rankings #3

Open
brennonbrimhall opened this issue Jul 31, 2018 · 0 comments
Open

Remove matches that will not affect the top rankings #3

brennonbrimhall opened this issue Jul 31, 2018 · 0 comments

Comments

@brennonbrimhall
Copy link
Owner

Since the algorithm is O(2^n), where n is the number of matches, a little bit of preprocessing can result in orders of magnitude of savings. See, for example, qualification match 66 and 71 at the 2018 IRI. Throwing both of these matches out would have resulted in the computation being sped up by a factor of 4.

Presumably, the algorithm would calculate the best-case scenario for each team. If the best-case was worse than the threshold provided as input, ignore matches. Some pseudocode follows:

create an empty set u
for each team t:
    for each match m:
        if that m contains t:
            have t's alliance win
    compute the rankings for this hypothetical scenario
    if the ranking of t is greater than the user-defined threshold, insert t into u
create an empty list m'
for each match m:
    if the teams in m are all in u, do nothing
    else put m into m'
use m' to calculate rankings
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant