Implemented the nemesis-filter today. That gave a huge speed improvement.
My program now can read command line arguments, so it should be easy to execute for non-programmers.
Nice! Though, you're using the nemesis-filter in an unsafe way. The "nemeses < team_size" is really only safe when number_of_top_teams is 1. Try this for example, it only produces seven teams instead of the ten it should and surely exist:
python guildford_challenge.py USA events="333 222" team_size=2
(The seven teams include five different people, so it should still find 5C2=10 teams, so looks like something else is fishy as well.)
A safe filter would be "nemeses < team_size * number_of_top_teams". Maybe less would be safe as well (but I must run to class right now).
Thanks for checking my code. The bug of 7 people instead of 5C2 was, that I disallowed branches, if the times are already worse than the worst entry in my TopTeams-Struct, but forgot to check, if TopTeams is full or not.
And for nemesis filtering:
"nemesis < team_size + number_of_top_teams - 1" is safe.
The proof is quite simple:
Let t=team_size and n=number_of_top_teams and the person P has >= t+n-1 nemesis. If A is part of a t-person-team TA, which is in the top n. Then I can replace A with the t+n-1 nemesis. In the worst case t-1 teams are not valid, because the replaced nemesis was already in the team. This leaves us with >= n valid teams. One of these n valid teams is different from the n-1 already in the list.
Therefore If A is in a team TA in the top n, we can find a better one, and the team TA slides at least position down. We can repeat this procedure until the team TA is out of the list. Therefore the premise was wrong, and A isn't part of any team in the top n.
And for nemesis filtering:
"nemesis < team_size + number_of_top_teams - 1" is safe.
The proof is quite simple:
Let t=team_size and n=number_of_top_teams and the person P has >= t+n-1 nemesis. If A is part of a t-person-team TA, which is in the top n. Then I can replace A with the t+n-1 nemesis. In the worst case t-1 teams are not valid, because the replaced nemesis was already in the team. This leaves us with >= n valid teams. One of these n valid teams is different from the n-1 already in the list.
Therefore If A is in a team TA in the top n, we can find a better one, and the team TA slides at least position down. We can repeat this procedure until the team TA is out of the list. Therefore the premise was wrong, and A isn't part of any team in the top n.
Correcting "P" to "A" and "nemesis" to "nemeses" was easy, but I still don't understand the proof. What does "worst" case mean, and why is it t-1? And how do you have n valid teams when t-1 of them are invalid? And what n-1 are already in the list? What list?
Ok I got it now. The problem was that you used "teams" for two different things (the original top teams as well as the possible replacement teams) and that the proof was unnecessarily complicated. I'll rephrase/shorten:
Let's say I have n+(t-1) nemeses, and consider the best team including me. That team can be improved by replacing me with one of my nemeses not already in the team. Of my n+(t-1) nemeses, up to t-1 might be on the team already, but at least n are not. Replacing me with (one of) these n nemeses results in n better teams. Thus I'm not in the top n teams.
Btw, that's also the best we can do with looking just at t and n, because there's a scenario where someone with n+t-2 nemeses is in team n.
Let's say we have t events (i.e., same as team size) and:
- Number the events 1 to t.
- Number the persons 1, 2, 3, ... according to their rank in event t.
- Person 1 is also the only one who can do event 1.
- Person 2 is also the only one who can do event 2.
...
- Person t-1 is also the only one who can do event t-1.
Now:
Team 1 is persons 1 to t-1 (because they're the only ones who can do events 1 to t-1) and person t (=t-1+1).
Team 2 is persons 1 to t-1 (because they're the only ones who can do events 1 to t-1) and person t-1+2.
...
Team n is persons 1 to t-1 (because they're the only ones who can do events 1 to t-1) and person t-1+n.
Thus person t-1+n, who has t+n-2 nemeses, is on team n.
Hmm, interesting. Then it reaches a kind of critical mass, where being consistently great outweighs not doing much and being lucky. Yu Nakajima wins average, Antoine Cantin wins single and "both". Both have all 33 ranks.
Computing standard deviation of raw ranks just doesn't mean anything given the disparities in the numbers of competitors between events. What would be already more interesting to compute is the standard deviation of the percentages of competitors which are better ranked than you in every event.
I thought so at first as well, but once you're near the top in every event, like Antoine and Nakaji are, then the total number of competitors becomes rather irrelevant. And raw absolute ranks are more interesting (they're also the only ones shown on the WCA site).
Anyway, here are tables now, though I used 3 instead of 5 as minimum requirement, in order to show that "critical mass". You can see the top people have either a low or a high number of ranks, almost nobody with a "medium" number of ranks made it.
[NOPARSE]SELECT
personId Cuber,
round(std(worldRank), 1) 'Standard\nDeviation',
group_concat(worldRank order by worldRank) Ranks,
round(avg(worldRank), 1) 'Mean',
count(*) Number
FROM RanksAverage
GROUP BY personId
HAVING Number >= 3
ORDER BY 2, Number desc
LIMIT 10[/NOPARSE]
[NOPARSE]SELECT
personId Cuber,
round(std(worldRank), 1) 'Standard\nDeviation',
group_concat(worldRank order by worldRank) Ranks,
round(avg(worldRank), 1) 'Mean',
count(*) Number
FROM (select * from RanksSingle union all select * from RanksAverage) tmp
GROUP BY personId
HAVING Number >= 3
ORDER BY 2, Number desc
LIMIT 10[/NOPARSE]
[NOPARSE]SELECT
personId Cuber,
round(std(worldRank), 1) 'Standard\nDeviation',
group_concat(worldRank order by worldRank) Ranks,
round(avg(worldRank), 1) 'Mean',
count(*) Number
FROM RanksSingle
GROUP BY personId
HAVING Number >= 3
ORDER BY 2, Number desc
LIMIT 10[/NOPARSE]
Thanks for doing this! I wonder what it would look like if you calculated not having a rank as being last in that event (same way missing ranks are calculated in sum of ranks). I thought there would be mostly people who aim to have the lowest highest ranking, (practicing their worst event).
how about top 100 averae sum of ranks but instead of having a person who doesnt compete in a event the last place of the people who compete in the event you would have the last person out of all wca members.
example: 2x2 has 30 competitors worldwide and 300 competitors worldwide for any event, now if you dont compete in 2x2 you are not 30th but 300th.
Antonie: Why? I don't see a good reason for that. And it would be an ugly mix of standard and modified competition ranking (see here). Also, it would basically be the normal sum of ranks but only for people who completed all events.
Btw, you forgot to add 1. In your example, they'd share place 31, not 30.
Edit: Oh.... I see... you want Faz out of the top 10 sum of ranks, I guess? You're a bad fan.
