iPSC 2013
by math_explorer, Jun 9, 2013, 1:47 AM
I made two really stupid bugs. See if you can find them for yourself.
1: (D1, determine whether a string contains all permutations of an alphabet)
I kept getting "Bus error: 10". The 10 made me think it might be the Windows / Unix newlines at first. Darn. Oh well, that's the price you pay for needing a low-constant-factor program.
After final debugging, this ran for 80 minutes before producing the answer ---
with
, times 120 test cases. This is pretty much the solution they give in the booklet, and I tried really hard to use bit operations instead of anything more high-level. Is this really the algorithm they used to grade Problem R!?
2: (I1, unscramble grayscale images and find cats)
This bug cost us a lot longer, maybe 45 minutes, because it caused me to think that my strategy of greedily grabbing "nearby" columns failed to unscramble the images. It would have worked, but I gave up on it and ended up hacking together a responsive GUI in order to try swapping columns manually. ~80 more lines of code + screwing around with threads. Darn.
I feel like I might have gotten M1 in those 45 minutes, although given the 5 out of 38 correct submissions (even compared to insane C1) maybe I'm missing something. Or is it just the problem ordering plus leaderboard peer pressure?
Just in case my partner does not want to reveal who he is, I'm not going to say stuff about the results, although it's probably guessable.
1: (D1, determine whether a string contains all permutations of an alphabet)
for (int i = slen - 1; i >= 0; i++){ if (str[i] == c) { lastPassed = i + 1; } nextPos[a][i] = lastPassed; }
I kept getting "Bus error: 10". The 10 made me think it might be the Windows / Unix newlines at first. Darn. Oh well, that's the price you pay for needing a low-constant-factor program.
After final debugging, this ran for 80 minutes before producing the answer ---


2: (I1, unscramble grayscale images and find cats)
for (int c1 = 0; c1 < 32; c1++) { diffs[c1][c1] = 0; for (int c2 = c1 + 1; c2 < 32; c2++) { diffs[c1][c2] = diff(imgs, c1, c2); } } // later... (simplified) int fst = deque.getFirst(); for (int c = 0; c < 32; c++){ if (!taken[c]) { if (diffs[fst][c] < best) { best = diffs[fst][c]; bestc = c; } } }
This bug cost us a lot longer, maybe 45 minutes, because it caused me to think that my strategy of greedily grabbing "nearby" columns failed to unscramble the images. It would have worked, but I gave up on it and ended up hacking together a responsive GUI in order to try swapping columns manually. ~80 more lines of code + screwing around with threads. Darn.
I feel like I might have gotten M1 in those 45 minutes, although given the 5 out of 38 correct submissions (even compared to insane C1) maybe I'm missing something. Or is it just the problem ordering plus leaderboard peer pressure?
Just in case my partner does not want to reveal who he is, I'm not going to say stuff about the results, although it's probably guessable.