Pre-qualifications have started!

[Fletch F Fletch]

Re: problems with the pre-qualification grader

- The grader did not give proper feedback. We improved this a little bit early on, but have learned our lesson and will be improving the feedback from the automated grader before DefCon. Specifically, we will be splitting test cases into their own files and reporting how many files succeeded and how many failed, so you at least know whether you're going in the right direction or not.

Also, kudos for that. It will make our lives (and yours) easier. An IQ test with just one (super-hard) problem doesn't give much information about peoples' intelligence. Finer-grained feedback might make some problems tractable.

By the way, how sure are you that the "official" answers to problems are right? As you may remember, team Frink Rules! found errors in two of the "sample input/output" examples from problems last year. I'm not trying to be a dick in bringing that up, but is it possible to determine if a team originally submitted the right answer if an error in the "official" answers is found later? Will a judge be looking over outputs and sanity-checking them? Do you keep all submissions? There was a hint here that our submissions could be overwritten by later submissions. At least logging our outputs using append (>> vs. > in Perl) might help resolve this potential issue on later review, if necessary.

Now I can just set the auto-learning Frinkbot free to do a binary search of the problem space...

[Gigs]

Re: Pre-qualifications have started!

This was surely compensated for in the hand-grading, but it was not anywhere in the spec that our program should be able to handle more than one "game" per execution.

Originally I wrote multiple test cases per input file while my partner was working on the parser. When his algorithm didn't work on my file I brought it up to him, and he pointed out that the spec just showed one game as the example input, and didn't say anywhere that there would be multiple games per file, so I let it slide.

Smitty, do you still need any logistical help running the event? No hard feelings about cutting me, I'd still like to be part of the event even if it means shlepping beers around and gophering extension cords.

[Krissy]

Re: Pre-qualifications have started!

Smitty, do you still need any logistical help running the event? No hard feelings about cutting me, I'd still like to be part of the event even if it means shlepping beers around and gophering extension cords.

Team Distraction! Team Distraction always needs help, and wants you.

[Gigs]

Re: Pre-qualifications have started!

Team Distraction! Team Distraction always needs help, and wants you.

You all wouldn't "distract" me any more after you saw my wedding ring!

[namniart]

Re: Pre-qualifications have started!

We're reasonably sure that our test cases are correct; we have two independently written reference implementations, one by the problem author (Gius) and one by myself.

We have always stuck to one game per file, but it's possible to test many, many edge cases in a single game. We're since split the testing out into multiple games.

While the grader only grades one submission every 5 minutes, it time-stamps and archives all of your submissions, so it it possible to re-run all of the previous submissions with new test data; this is precisely what we did as part of our final decision-making process.

For next time, I'm considering implementing a way to run the reference implementations through the web interface; would anyone be interested in this?

I've turned the grader back on so that the qual problem is now available by default, for anyone who wants to wrestle with it some more. Obviously this won't affect our team selections, but it will give you a chance to play with the grader and the problem some more. I'll be making some improvements to the grader feedback over the next few days as I have time.

[Gigs]

Re: Pre-qualifications have started!

For next time, I'm considering implementing a way to run the reference implementations through the web interface; would anyone be interested in this?

I was thinking it might be better to go more ACM style, and have 5 or more easier problems to choose from in the 3 hour period. Complete as many as you can in the time allotted, your choice.

More smaller problems where it's more clear if the answer is right or wrong, instead of one intricate problem with dozens of edge cases. We wouldn't really need access to a reference implementation with simpler problems. As well it helps mitigate the issue of cultural bias since if someone doesn't understand a problem they can still complete other problems.

[SmittyHalibut]

Re: Pre-qualifications have started!

Team Distraction! Team Distraction always needs help, and wants you.

Actually, she's not kidding. We've got at least one girl competing who needs a distraction. :-)

Otherwise, if you show up around 7pm, I'm sure we can put you to use hauling and setting up stuff. I would appreciate that, yeah. Thanks. :-)

[Gigs]

Re: Pre-qualifications have started!

Did anyone else figure out the elegant O(1) (well O(log10(n)) technically) solution to the Ones problem?

[pH_Boston]

Re: Pre-qualifications have started!

Did anyone else figure out the elegant O(1) (well O(log10(n)) technically) solution to the Ones problem?

Whoa there I just solved it the fastest way I could think of instead of going for the elegant solution I'd do at work. But now I know what I'll be working on tonight. I think you specifying log10 gave it away though....

[Fletch F Fletch]

Re: Pre-qualifications have started!

Did anyone else figure out the elegant O(1) (well O(log10(n)) technically) solution to the Ones problem?

Knowing what I know about radix conversion algorithms, I don't think it's possible to do it in O(log10(n)) time. Division itself is probably O(n^2) in the functions you used. (I doubt you're doing Karatsuba division or Barrett or Burnikel-Ziegler division, which are asymptotically faster than O(n^2), but not faster for small numbers like these.) I'd be interested to hear about this algorithm.

[Gigs]

Re: Pre-qualifications have started!

Knowing what I know about radix conversion algorithms, I don't think it's possible to do it in O(log10(n)) time (and I think you could even view it as O(1) in terms of a list of numbers, but that's stretching it) Division itself is probably O(n^2) in the functions you used. (I doubt you're doing Karatsuba division or Barrett or Burnikel-Ziegler division, which are asymptotically faster than O(n^2), but not faster for small numbers like these.) I'd be interested to hear about this algorithm.

data=sys.stdin.read()
for number in data.splitlines():
    total=0
    numdigits=len(number)
    reversed_number=number[::-1]
    for placeval, digit in enumerate(reversed_number):
        digit=int(digit)
        digitsbefore=number[0:numdigits-placeval-1]
        if (digitsbefore == ''):
            digitsbefore='0'

        digitsbefore=int(digitsbefore)
        digitsafter=number[numdigits-placeval:]
        if (digitsafter == ''):
            digitsafter='0'
        digitsafter=int(digitsafter)

        if (digit == 0):
            total+=pow(10,placeval)*digitsbefore
        elif (digit == 1):
            total+=pow(10,placeval)*digitsbefore
            total+=(digitsafter+1)
        else:
            total+=pow(10,placeval)*(digitsbefore+1)
    print total

Basically it considers the place value of each digit, and what that digit has "contributed" in terms of ones.

I guess it's O(n) over the number of digits in the number, but it's log n if you consider the "n" as the quantity of numbers counting up to the target number. In any case it's hugely faster than the naive algorithm of actually counting up to the target and scanning the number for ones.

There is probably a faster way to get the place values than splitting it up as a string.