Created
March 22, 2024 17:11
-
-
Save ColmBhandal/a33b15410a5c12f633b36eb81c67da26 to your computer and use it in GitHub Desktop.
More efficient variant of joriki/Question4882568.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.ArrayList; | |
| import java.util.BitSet; | |
| import java.util.List; | |
| public class MatchScheduler { | |
| static boolean [] [] played; | |
| static int count; | |
| static int n; | |
| static List<Integer> factorials = new ArrayList<Integer>(); | |
| public static void main (String [] args) { | |
| factorials.add(1); | |
| for (n = 2;;n += 2) { | |
| updateFactorials(n); | |
| count = 0; | |
| generatePlayed(); | |
| recurse (null,n,0); | |
| System.out.println(n + " : " + count*factorials.get(n-1)); | |
| } | |
| } | |
| private static void updateFactorials(int n){ | |
| int prev = factorials.get(n-2); | |
| int next = prev*(n-1); | |
| int next2 = next*n; | |
| factorials.add(n-1, next); | |
| factorials.add(n, next2); | |
| } | |
| private static void generatePlayed() { | |
| played = new boolean [n] [n]; | |
| } | |
| static void recurse (BitSet matched,int daysLeft,int unmatched) { | |
| if (daysLeft == 0){ | |
| count++; | |
| } | |
| else if (unmatched == 0){ | |
| int newDaysLeft = daysLeft - 1; | |
| recurse (generateBitset(newDaysLeft),newDaysLeft,n-2); | |
| } | |
| else { | |
| int toMatch = matched.nextClearBit (0); | |
| matched.set (toMatch); | |
| int team = toMatch; | |
| for (;;) { | |
| team = matched.nextClearBit (team + 1); | |
| if (team == n || toMatch == n) | |
| break; | |
| if (!played [toMatch] [team]) { | |
| set (toMatch,team,true); | |
| matched.set (team); | |
| recurse (matched,daysLeft,unmatched - 2); | |
| matched.clear (team); | |
| set (toMatch,team,false); | |
| } | |
| } | |
| matched.clear (toMatch); | |
| } | |
| } | |
| private static BitSet generateBitset(int daysLeft) { | |
| if (daysLeft == 0) return null; | |
| BitSet bitSet = new BitSet (n); | |
| int opponent = n - daysLeft; | |
| bitSet.set(0); | |
| bitSet.set(opponent); | |
| set(0, opponent, true); | |
| return bitSet; | |
| } | |
| static void set (int i,int j,boolean value) { | |
| played [i] [j] = played [j] [i] = value; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment