/* Entry name: ShowMeTheMoney */ /* Name: Hal Burch & Danny Sleator */ /* E-mail: hburch+@cs.cmu.edu */ /* Instructions: use that funky gcc */ #include #include #include #include #include /* Okay...we're going to use _my_ random, so it produces the same sequence on every machine (technically, I snarfed the random code from libc) */ #define srand srand_loc #define rand rand_loc void srand_loc(unsigned int x); long int rand_loc(void); #define MAXN 256 #define MAXTICK 16384 /* the size of the three sets that we'll split the groups into */ /* given the number of tickets required for each set size, this calculation is a simple DP problem */ int split[201][3] = { {0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}, {4, 0, 0}, {5, 0, 0}, {6, 0, 0}, {7, 0, 0}, {7, 0, 1}, {7, 0, 2}, {7, 0, 3}, {7, 0, 4}, {7, 0, 5}, {7, 0, 6}, {7, 0, 7}, {7, 1, 7}, {7, 2, 7}, {7, 3, 7}, {7, 4, 7}, {7, 5, 7}, {7, 6, 7}, {7, 7, 7}, {9, 6, 7}, {9, 7, 7}, {10, 7, 7}, {9, 7, 9}, {10, 7, 9}, {9, 9, 9}, {10, 9, 9}, {11, 9, 9}, {11, 9, 10}, {15, 7, 9}, {15, 7, 10}, {15, 9, 9}, {15, 9, 10}, {15, 9, 11}, {15, 10, 11}, {15, 7, 15}, {15, 8, 15}, {15, 9, 15}, {15, 10, 15}, {15, 11, 15}, {15, 12, 15}, {15, 13, 15}, {15, 14, 15}, {15, 15, 15}, {16, 15, 15}, {17, 15, 15}, {18, 15, 15}, {19, 15, 15}, {18, 15, 17}, {18, 15, 18}, {19, 15, 18}, {19, 15, 19}, {18, 18, 18}, {19, 18, 18}, {19, 18, 19}, {19, 19, 19}, {20, 19, 19}, {21, 19, 19}, {22, 19, 19}, {22, 19, 20}, {22, 19, 21}, {22, 19, 22}, {22, 20, 22}, {22, 21, 22}, {22, 22, 22}, {23, 22, 22}, {24, 22, 22}, {25, 22, 22}, {25, 22, 23}, {25, 22, 24}, {25, 22, 25}, {25, 23, 25}, {25, 24, 25}, {25, 25, 25}, {26, 25, 25}, {27, 25, 25}, {27, 25, 26}, {27, 25, 27}, {27, 26, 27}, {27, 27, 27}, {28, 27, 27}, {29, 27, 27}, {30, 27, 27}, {29, 27, 29}, {30, 27, 29}, {29, 29, 29}, {30, 29, 29}, {30, 29, 30}, {30, 30, 30}, {31, 30, 30}, {32, 30, 30}, {32, 30, 31}, {32, 30, 32}, {32, 31, 32}, {32, 32, 32}, {33, 32, 32}, {34, 32, 32}, {35, 32, 32}, {34, 32, 34}, {35, 32, 34}, {34, 34, 34}, {35, 34, 34}, {35, 34, 35}, {35, 35, 35}, {36, 35, 35}, {37, 35, 35}, {37, 35, 36}, {37, 35, 37}, {37, 36, 37}, {37, 37, 37}, {38, 37, 37}, {39, 37, 37}, {39, 37, 38}, {39, 37, 39}, {39, 38, 39}, {39, 39, 39}, {40, 39, 39}, {41, 39, 39}, {41, 39, 40}, {41, 39, 41}, {41, 40, 41}, {41, 41, 41}, {42, 41, 41}, {42, 41, 42}, {42, 42, 42}, {43, 42, 42}, {43, 42, 43}, {43, 43, 43}, {44, 43, 43}, {44, 43, 44}, {44, 44, 44}, {45, 44, 44}, {46, 44, 44}, {46, 44, 45}, {46, 44, 46}, {46, 45, 46}, {46, 46, 46}, {47, 46, 46}, {48, 46, 46}, {48, 46, 47}, {48, 46, 48}, {48, 47, 48}, {48, 48, 48}, {49, 48, 48}, {50, 48, 48}, {50, 48, 49}, {50, 48, 50}, {50, 49, 50}, {50, 50, 50}, {51, 50, 50}, {51, 50, 51}, {51, 51, 51}, {52, 51, 51}, {52, 51, 52}, {52, 52, 52}, {53, 52, 52}, {53, 52, 53}, {53, 53, 53}, {54, 53, 53}, {54, 53, 54}, {54, 54, 54}, {55, 54, 54}, {55, 54, 55}, {55, 55, 55}, {56, 55, 55}, {56, 55, 56}, {56, 56, 56}, {57, 56, 56}, {57, 56, 57}, {57, 57, 57}, {58, 57, 57}, {58, 57, 58}, {58, 58, 58}, {59, 58, 58}, {59, 58, 59}, {59, 59, 59}, {60, 59, 59}, {60, 59, 60}, {60, 60, 60}, {61, 60, 60}, {61, 60, 61}, {61, 61, 61}, {62, 61, 61}, {62, 61, 62}, {62, 62, 62}, {64, 61, 62}, {64, 62, 62}, {64, 61, 64}, {64, 62, 64}, {64, 63, 64}, {64, 64, 64}, {65, 64, 64}, {66, 64, 64}, {66, 64, 65}, {66, 64, 66}, {66, 65, 66}, {66, 66, 66}, {67, 66, 66}, {68, 66, 66}, }; /* the magic seeds...determined by running the generation code with a * bunch of different seeds and picking the best one...note that * if you alter these seeds, you'll use more tickets, but it'll * still produce a completely valid solution */ int seeds[72] = { 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10600, 10000, 10016, 10352, 18394, 3324708, 48779, 893535, 588894, 430555, 20977, 15236, 10016, 10212, 79568, 52763, 12253, 10382, 53457, 16971, 12843, 37688, 10908, 11701, 11837, 10003, 14630, 36661, 14473, 14582, 11510, 30203, 14634, 10586, 11108, 43922, 11929, 21279, 10731, 10213, 21083, 11462, 10134, 27101, 10437, 10748, 30102, 10344, 10446, 32711, 28832, 11271, 10059, 11377, 10278, 16775, 10646, 17785, 11426, 11692, 11113, }; int numruns; /* archaic */ unsigned char matrix[80][80][80]; /* is there a ticket with x, y, & z on it? */ int count[MAXTICK]; /* how many non-zero entries are on this ticket */ int tickets[MAXTICK][8]; /* the tickets...zero entries specify "don't care" */ int n, ntick; int cnt; int covercnt; /* how many triplets x < y < z covered with the current set */ int f = 0; /* the magic flag...do we really care about the matrix data? */ /* when combining the three sets, we'll do some manipulations, but we don't what matrix touched, since the numbers are out of bounds...thus, this flag */ /* the 4 here is archaic, it should be 2 */ int sticks[4][MAXTICK][8]; /* the tickets for each subgroup (1-based) */ int numticks[4]; /* the number of tickets in each subgroup */ /* outdated, from when I did the DP here */ int twosum[7], twoloc[7]; int threesum[10], threeloc[10]; /* antiquated */ int usage[MAXN]; /* obsolete (good grief, I should've cleaned up this code) */ #define MAXKING 32 int klen; int king[MAXKING]; int kused[MAXKING]; int tusage[MAXN]; /* how many times is N used in the tickets...used to renumber to reduce total */ int distcomp(const void *p1, const void *p2) { /* which one is used more? */ int i1, i2; i1 = *(int *)p1; i2 = *(int *)p2; if (tusage[i1] > tusage[i2]) return -1; else if (tusage[i1] == tusage[i2]) return 0; /* For some reason, Sun's qsort library requires this */ else return 1; } int intcomp(const void *p1, const void *p2) { /* which integer is higher */ if (*(int *)p1 > *(int *)p2) return -1; else return 1; } int check_loc(int ltick, int pos) { /* Do I use the pos'th number in the ltick'th ticket? */ int lv, lv2; int *tick; int v1, v2, v3; tick = tickets[ltick]; v1 = tick[pos]; for (lv = 0; lv < 6; lv++) if ((v2 = tick[lv])) { for (lv2 = lv+1; lv2 < 7; lv2++) if ((v3 = tick[lv2])) { if (matrix[v1][v2][v3] == 1) return 0; } } return 1; } void sub_matrix(int ltick) { /* Remove this ticket from the matrix array */ int lv, lv2, lv3; int *tick; int v1, v2, v3; tick = tickets[ltick]; for (lv = 0; lv < 5; lv++) if ((v1 = tick[lv])) { for (lv2 = lv+1; lv2 < 6; lv2++) if ((v2 = tick[lv2])) { for (lv3 = lv2+1; lv3 < 7; lv3++) if ((v3 = tick[lv3])) { v3 = tick[lv3]; matrix[v2][v1][v3]--; matrix[v2][v3][v1]--; matrix[v3][v2][v1]--; matrix[v3][v1][v2]--; matrix[v1][v3][v2]--; matrix[v1][v2][v3]--; if (!matrix[v1][v2][v3]) covercnt--; /* update, update */ } } } } void fill_matrix(int ltick) { /* Add this ticket's coverage to the matrix array */ int lv, lv2, lv3; int *tick; int v1, v2, v3; tick = tickets[ltick]; for (lv = 0; lv < 5; lv++) if ((v1 = tick[lv])) { for (lv2 = lv+1; v1 && lv2 < 6; lv2++) if ((v2 = tick[lv2])) { for (lv3 = lv2+1; v2 && lv3 < 7; lv3++) if ((v3 = tick[lv3])) { if (!matrix[v1][v2][v3]) covercnt++; matrix[v1][v2][v3]++; matrix[v1][v3][v2]++; matrix[v2][v1][v3]++; matrix[v2][v3][v1]++; matrix[v3][v2][v1]++; matrix[v3][v1][v2]++; } } } } /* I don't do anything anymore if I run out of time, but this is legacy code */ int timeup; void setflag(int sig) { if (sig == SIGALRM) { #ifdef DEBUG fprintf (stderr, "TIME UP!\n"); #endif timeup = 1; } } void cover(int base, int n) { /* Construct a set of tickets that (completely) covers N (base is not used) */ int goal; int lv, lv2, lv3, lv4, lv5; int blv, blv2, blv3; int cnt; int bst, bloc; int v1; int choices[MAXN]; int numch; int *ticket; goal = n*(n-1)*(n-2)/6; /* we need this many coverages to occur */ covercnt = 0; for (blv = 1; blv <= n; blv++) for (blv2 = blv+1; blv2 <= n; blv2++) for (blv3 = blv2+1; blv3 <= n; blv3++) if (!matrix[blv][blv2][blv3]) { /* find a triplet uncovered */ ticket = tickets[ntick]; ticket[0] = blv; ticket[1] = blv2; ticket[2] = blv3; for (lv2 = 3; lv2 < 7; lv2++) { /* for each position left */ bst = 0; numch = 1; choices[0] = 0; for (lv3 = 1; lv3 <= n; lv3++) { /* for each choice */ cnt = 0; for (lv4 = 0; lv4 < lv2; lv4++) if (ticket[lv4] == lv3) break; if (lv4 < lv2) continue; /* not on the ticket left */ for (lv4 = 0; lv4 < lv2; lv4++) { /* calculate how many new coverages adding it would create */ int v2; unsigned char *m; v1 = ticket[lv4]; m = matrix[v1][lv3]; for (lv5 = lv4+1; lv5 < lv2; lv5++) { v2 = ticket[lv5]; if (m[v2] == 0) cnt++; } } if (cnt > bst) { /* if it's the best, keep it */ bst = cnt; numch = 1; choices[0] = lv3; } else if (cnt == bst) /* in fact, keep all the best */ choices[numch++] = lv3; } if (bst == 0) { /* this ticket isn't full, but adding anything to it doesn't help (cover more uncover triplets) */ while (lv2 < 7) ticket[lv2++] = 0; } else { /* pick a random 'best' */ bloc = choices[rand() % numch]; ticket[lv2] = bloc; } } qsort(ticket, 7, sizeof(int), intcomp); fill_matrix(ntick); /* update the matrix & covercnt */ count[ntick] = 0; for (lv2 = 0; lv2 < 7; lv2++) if (ticket[lv2]) count[ntick]++; ntick++; } } void reduce(void) { /* given tickets with "don't care"s in them, try to combine them to reduce the count */ int lv, lv2, lv3; int min; int p1, p2, c; int minloc; for (lv = 0; lv < ntick; lv++) { if (count[lv] < 7) { /* we deleted some from this one...let's see if we can combine it */ min = 8; for (lv2 = lv+1; lv2 < ntick; lv2++) { if (count[lv2] == 7) continue; p1 = p2 = 7; c = 0; while (p1 && p2) { while (p1 > 0 && tickets[lv][p1-1] == 0) p1--; if (p1 == 0) break; while (p2 > 0 && tickets[lv2][p2-1] == 0) p2--; if (p2 == 0) break; if (tickets[lv][p1-1] < tickets[lv2][p2-1]) { c++; p1--; } else if (tickets[lv][p1-1] == tickets[lv2][p2-1]) { c++; p1--; p2--; } else { c++; p2--; } } if (p1) while (p1 > 0) if (tickets[lv][--p1]) c++; if (p2) while (p2 > 0) if (tickets[lv2][--p2]) c++; if (c <= 7 && (c - count[lv2]) < min) /* PAR-TAY! We can reduce! */ { /* minimize number added */ min = c - count[lv2]; minloc = lv2; } } if (min < 8) { /* did we find a place to reduce? */ lv2 = minloc; { int newtick[7]; c = 6; p1 = p2 = 7; while (p1 || p2) { while (p1 && tickets[lv][p1-1] == 0) p1--; if (!p1) break; while (p2 && tickets[lv2][p2-1] == 0) p2--; if (!p2) break; if (tickets[lv][p1-1] < tickets[lv2][p2-1]) { newtick[c--] = tickets[lv][p1-1]; p1--; } else if (tickets[lv][p1-1] == tickets[lv2][p2-1]) { newtick[c--] = tickets[lv2][p2-1]; p1--; p2--; } else { newtick[c--] = tickets[lv2][p2-1]; p2--; } } while (p2) { if (tickets[lv2][--p2]) newtick[c--] = tickets[lv2][p2]; } while (p1) { if (tickets[lv][--p1]) newtick[c--] = tickets[lv][p1]; } for (lv3 = c; lv3 >= 0; lv3--) newtick[lv3] = 0; ntick--; if (!f) /* only play with matrix if we care about it */ { sub_matrix(lv); sub_matrix(lv2); } for (lv3 = 0; lv3 < 7; lv3++) { tickets[lv][lv3] = newtick[lv3]; tickets[lv2][lv3] = tickets[ntick][lv3]; } count[lv2] = count[ntick]; count[lv] = 7-c; if (!f) fill_matrix(lv); lv--; } } } } } void eliminate(void) { /* The goal is to reduce the number of tickets. This is done by repetitititively changing all the positions to "don't care"s that don't add to covercnt and then trying to combine the tickets to reduce the overall count */ int sv; int c, p1; int lv, lv2; do { sv = ntick; for (lv = 0; lv < ntick; lv++) { p1 = 0; c = tickets[lv][0]; for (lv2 = 0; lv2 < 7; lv2++) { if (tickets[lv][lv2] && check_loc(lv, lv2)) { /* can we mark this one out? */ sub_matrix(lv); c = tickets[lv][lv2]; p1 = lv2; tickets[lv][lv2] = 0; fill_matrix(lv); count[lv]--; } } if (count[lv] == 6) { /* if we can't eliminate at least 2, don't bother */ count[lv] = 7; sub_matrix(lv); tickets[lv][p1] = c; fill_matrix(lv); } } reduce(); /* now that we've marked 'em out, combine them */ } while (sv != ntick); /* continue until we make no progress */ } void main(int argc, char **argv) { int lv, lv2, lv3; int sv; int maxn; int goal; int splv, splv2; int cnt; int map[MAXN]; int invmap[MAXN]; if (argc != 2) { fprintf (stderr, "Usage: %s N\n", argv[0]); exit(1); } maxn = atoi(argv[1]); if (maxn < 3 || maxn > 200) { fprintf (stderr, "Illegal number in the hat: %s\n", argv[1]); exit(1); } cnt = n; #ifndef DEBUG alarm(600); signal(SIGALRM, setflag); #endif for (splv = 0; splv < 3; splv++) { /* for each of the subgroups */ numticks[splv] = 10000; n = split[maxn][splv]; srand(seeds[n]); numruns = 1; for (lv = 0; lv < numruns; lv++) { /* numruns == 1 */ ntick = 0; cover(1, n); /* calculate initial cover */ eliminate(); /* reduce it */ if (ntick < numticks[splv]) /* == 1 */ { /* save it */ memcpy(sticks[splv], tickets, sizeof(tickets[0])*ntick); numticks[splv] = ntick; } memset(matrix, 0, sizeof(matrix)); /* reset the matrix */ } } ntick = numticks[0]; memcpy(tickets, sticks[0], sizeof(tickets[0])*ntick); splv = split[maxn][0]; for (lv = 0; lv < numticks[1]; lv++) { for (lv2 = 0; lv2 < 7; lv2++) if (sticks[1][lv][lv2]) tickets[ntick+lv][lv2] = sticks[1][lv][lv2] + splv; else tickets[ntick+lv][lv2] = 0; } ntick += numticks[1]; splv += split[maxn][1]; for (lv = 0; lv < numticks[2]; lv++) { for (lv2 = 0; lv2 < 7; lv2++) if (sticks[2][lv][lv2]) tickets[ntick+lv][lv2] = sticks[2][lv][lv2] + splv; else tickets[ntick+lv][lv2] = 0; } ntick += numticks[2]; for (lv = 0; lv < ntick; lv++) { count[lv] = 0; for (lv2 = 0; lv2 < 7; lv2++) if (tickets[lv][lv2]) count[lv]++; } cnt = n = maxn; f = 1; reduce(); /* we might be able to combine tickets across set boundaries */ for (lv = 0; lv < ntick; lv++) { /* fill in all the non-zero entries */ sv = 1; for (lv2 = 0; lv2 < 7; lv2++) if (tickets[lv][lv2] == 0) { /* sv == guess on what to fill in */ for (lv3 = 0; lv3 < 7; lv3++) if (tickets[lv][lv3] == sv) { /* oops, sv is already there, gotta try the next one */ sv++; lv3 = 0; } tickets[lv][lv2] = sv; } } #ifdef DEBUG #ifndef NOOUT printf ("%i\n%i\n", n, ntick); #else printf ("%i: %i\n", n, ntick); #endif #endif /* calculate tusage */ memset(tusage, 0, sizeof(tusage)); for (lv = 0; lv < ntick; lv++) { for (lv2 = 0; lv2 < 7; lv2++) if (tickets[lv][lv2]) tusage[tickets[lv][lv2]]++; } /* renumber the ticket numbers to reduce the overall sum */ for (lv = 1; lv <= maxn; lv++) map[lv] = lv; qsort(map+1, maxn, sizeof(map[1]), distcomp); invmap[0] = 0; for (lv = 1; lv <= maxn; lv++) invmap[map[lv]] = lv; for (lv = 0; lv < ntick; lv++) { for (lv2 = 0; lv2 < 7; lv2++) tickets[lv][lv2] = invmap[tickets[lv][lv2]]; } #ifndef NOOUT for (lv = 0; lv < ntick; lv++) printf ("%i %i %i %i %i %i %i\n", tickets[lv][0], tickets[lv][1], tickets[lv][2], tickets[lv][3], tickets[lv][4], tickets[lv][5], tickets[lv][6]); #endif } /* --- cut from libc source --- */ /* the random/srand code used */ /* * Copyright (c) 1983 Regents of the University of California. * All rights reserved. * * Redistribution and use in source and binary forms are permitted * provided that the above copyright notice and this paragraph are * duplicated in all such forms and that any documentation, * advertising materials, and other materials related to such * distribution and use acknowledge that the software was developed * by the University of California, Berkeley. The name of the * University may not be used to endorse or promote products derived * from this software without specific prior written permission. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. */ /* * This is derived from the Berkeley source: * @(#)random.c 5.5 (Berkeley) 7/6/88 * It was reworked for the GNU C Library by Roland McGrath. */ #define TYPE_0 0 #define BREAK_0 8 #define DEG_0 0 #define SEP_0 0 #define TYPE_1 1 #define BREAK_1 32 #define DEG_1 7 #define SEP_1 3 #define TYPE_2 2 #define BREAK_2 64 #define DEG_2 15 #define SEP_2 1 #define TYPE_3 3 #define BREAK_3 128 #define DEG_3 31 #define SEP_3 3 #define TYPE_4 4 #define BREAK_4 256 #define DEG_4 63 #define SEP_4 1 #define MAX_TYPES 5 /* Max number of types above. */ static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; static int seps[MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; static long int randtbl[DEG_3 + 1] = { TYPE_3, -851904987, -43806228, -2029755270, 1390239686, -1912102820, -485608943, 1969813258, -1590463333, -1944053249, 455935928, 508023712, -1714531963, 1800685987, -2015299881, 654595283, -1149023258, -1470005550, -1143256056, -1325577603, -1568001885, 1275120390, -607508183, -205999574, -1696891592, 1492211999, -1528267240, -952028296, -189082757, 362343714, 1424981831, 2039449641, }; static long int *fptr = &randtbl[SEP_3 + 1]; static long int *rptr = &randtbl[1]; static long int *state = &randtbl[1]; static int rand_type = TYPE_3; static int rand_deg = DEG_3; static int rand_sep = SEP_3; static long int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])]; void srand_loc(unsigned int x) { state[0] = x; if (rand_type != TYPE_0) { register long int i; for (i = 1; i < rand_deg; ++i) state[i] = (1103515145 * state[i - 1]) + 12345; fptr = &state[rand_sep]; rptr = &state[0]; #if 0 /* this probably should be done, but my original runs to calculate * the magic seeds were done without this (under Linux, this links * O.K., so I didn't know I wasn't doing this), so to avoid recalculation, * I commented it out so it'll run on Sun -hjb */ for (i = 0; i < 10 * rand_deg; ++i) (void) __random(); #endif } } long int rand_loc(void) { if (rand_type == TYPE_0) { state[0] = ((state[0] * 1103515245) + 12345) & 0x7fffffff; return state[0]; } else { long int i; *fptr += *rptr; /* Chucking least random bit. */ i = (*fptr >> 1) & 0x7fffffff; ++fptr; if (fptr >= end_ptr) { fptr = state; ++rptr; } else { ++rptr; if (rptr >= end_ptr) rptr = state; } return i; } }