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)
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 --- $O(s2^s)$ with $s = 26$, 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)
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.

Comment

3 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Derp. People knowing your blog knows your real name, which can be used to search the registered teams to find your team. Of course, the AoPS username(s) of the remaining team member(s, if any) is probably the hard part. :P

I'm sure they graded my first submission (which misses the reverse permutation) in about 10 minutes, so yeah. But for D1-2 you can actually execute different testcases at different computers.

by chaotic_iak, Jun 9, 2013, 2:13 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Is "derp" experiencing a general resurgence in popularity now?

by math_explorer, Jun 9, 2013, 10:23 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
For me, yeah. Dunno 'bout the others.

by chaotic_iak, Jun 12, 2013, 4:33 PM

♪ i just hope you understand / sometimes the clothes do not make the man ♫ // https://beta.vero.site/

avatar

math_explorer
Archives
+ September 2019
+ February 2018
+ December 2017
+ September 2017
+ July 2017
+ March 2017
+ January 2017
+ November 2016
+ October 2016
+ August 2016
+ February 2016
+ January 2016
+ September 2015
+ July 2015
+ June 2015
+ January 2015
+ July 2014
+ June 2014
inv
+ April 2014
+ December 2013
+ November 2013
+ September 2013
+ February 2013
+ April 2012
Shouts
Submit
  • how do you have so many posts

    by krithikrokcs, Jul 14, 2023, 6:20 PM

  • lol⠀⠀⠀⠀⠀

    by math_explorer, Jan 20, 2021, 8:43 AM

  • woah ancient blog

    by suvamkonar, Jan 20, 2021, 4:14 AM

  • https://artofproblemsolving.com/community/c47h361466

    by math_explorer, Jun 10, 2020, 1:20 AM

  • when did the first greed control game start?

    by piphi, May 30, 2020, 1:08 AM

  • ok..........

    by asdf334, Sep 10, 2019, 3:48 PM

  • There is one existing way to obtain contributorship documented on this blog. See if you can find it.

    by math_explorer, Sep 10, 2019, 2:03 PM

  • SO MANY VIEWS!!!
    PLEASE CONTRIB
    :)

    by asdf334, Sep 10, 2019, 1:58 PM

  • Hullo bye

    by AnArtist, Jan 15, 2019, 8:59 AM

  • Hullo bye

    by tastymath75025, Nov 22, 2018, 9:08 PM

  • Hullo bye

    by Kayak, Jul 22, 2018, 1:29 PM

  • It's sad; the blog is still active but not really ;-;

    by GeneralCobra19, Sep 21, 2017, 1:09 AM

  • dope css

    by zxcv1337, Mar 27, 2017, 4:44 AM

  • nice blog ^_^

    by chezbgone, Mar 28, 2016, 5:18 AM

  • shouts make blogs happier

    by briantix, Mar 18, 2016, 9:58 PM

91 shouts
Contributors
Tags
About Owner
  • Posts: 583
  • Joined: Dec 16, 2006
Blog Stats
  • Blog created: May 17, 2010
  • Total entries: 327
  • Total visits: 354197
  • Total comments: 368
Search Blog
a