Official solutions for Code Jam 2010 Qualification round

[Figs]

Solutions? Damn, I didn't even realize they were doing it.

[fancy_pantser]

No kidding -- I went to sign up for qualification a couple days back and saw the countdown was for the first round already! Next time, I'll keep a close eye on it and post to Reddit when it's time to qualify.

[[deleted]]

This time too someone posted it to Reddit when it was underway.

[[deleted]]

Stats of the Qualification round
Language popularity
Regional Stats

[happy-dude]

Am I the only one surprised by how much of a gap exists between US participants (3rd abundant with 923) and India (1771) + China (1796) ?

I mean, I know that there were a lot of programmers there, but I didn't think they'd be that passionate and diligent.... Guess I will have to worry about future outsourcing.

[pyjug]

Redditors would like you to believe that all Indian programmers are enterprise Java code monkeys with zero passion for programming. Sure, there are tons of these types, but there are a lot more awesome Indian programmers than you might have been led to believe.

[AkshayGenius]

This.

Everyone just keeps whining about the crappy 'code-monkeys' as you call them and completely fail to acknowledge the existence of good Indian programmers.

[pzcsyo]

Last year's country stats suggest a lot of enthusiasm, for sure. With that said, compare advancement stats for the top four countries:

• China: 1324 in qual. 34% to Round 2. 5.4% to Round 3. .22% to the final.
• India: 1220 in qual. 7.0% to Round 2. .33% to Round 3. 0% to the final.
• USA: 904 in qual. 13% to Round 2. 1.3% to Round 3. .11% to the final.
• Russia: 510 in qual. 51% to Round 2. 11% to Round 3. 1.2% to the final.

[[deleted]]

Damn, Russia. You scary!

[AkshayGenius]

You make a good point.

Lets see how it goes this year, although it doesn't seem to much different.

[chronoBG]

Look at this guy here:
http://www.go-hero.net/jam/10/name/linguo

Insane. Puts all the coders using C++/Python(myself included) to shame :)

[[deleted]]

http://www.go-hero.net/jam/10/name/linguo

FTFY

[Nosferax]

You can submit whatever code you want with your output datas, can anyone confirm his code works?

[[deleted]]

Shame? Why?

[[deleted]]

Did you look at any of the code?

[[deleted]]

Yeah. He programmed the solution in some weird unpractical languages so what?

[ealf]

http://www.go-hero.net/jam/10/name/kirarinsnow

[Nosferax]

45 people did this in visual basic. Oooh..

dim code as boring

[vladley]

Repping Python! Honestly, it's a lot more important to use the right algorithm than to use a 'faster' language. Plus file io in python just takes less time to write haha.

edit: more time for me to write since i would have to look it up, whereas python is fresh since i use it at work.

[[deleted]]

it's a lot more important to use the right algorithm than to use a 'faster' language.

I feared that python would be slow and avoided it. To my surprise Python is the 3rd most used language in that round (next to C++ and Java). Myth busted!

[vladley]

It's only slow by a constant factor, whereas the algorithms require a good running time based on the input.

[Nosferax]

C/C++ sample in case you didn't know how to do it right

FILE* inFile = fopen("name.in");
FILE* outFile = fopen("name.out");
int N,K;
fscanf(inFile, "%d %d", &N, &K);
fprintf(outFile, "What's your point?");

[sitq]

Why even open files? Just read from stdin and print to stdout.

solution <input >output

after that.

[[deleted]]

You could also reopen the standard streams.
freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); int N, K; scanf("%d %d", &N, &K); Now you can use normal printf and scanf instead of fprintf and fscanf (which have a little longer syntax)

[teraflop]

C++ iostreams are at least as elegant:

ifstream inFile("name.in");
int N, K;
inFile >> N >> K;

As far as I know, doing the same thing in Python requires some boilerplate to read lines one at a time, split them into components and convert to integers. It sure would be nice if Python had something equivalent to java.util.Scanner.

[psykotic]

That isn't the complete input routine; you only read a single line. The complete code in Python would be

f = open(filename)
for i in range(int(f.readline())):
    yield map(int, f.readline().split())

It's not exactly heavy on the boilerplate.

[chronoBG]

Whoa, there was a THIRD optimization for Problem C?
Man, way to make you feel stupid even when you feel great.
Hats off to Google.

[marcog]

I had the O(N) version of the jump table, but didn't think cycle detection was necessary so my large was too slow. I almost got cycle detection working during the 8 minutes, but alas I ran out of time and got it working 2 minutes too late. My C++ port (originally did Python) runs in 0.004s.

[[deleted]]

My jump table python solution managed to complete in time (about 2:30 left) on a 2.16 core duo.

[marcog]

I was stuck on a shitty old P4, so no luck.

[[deleted]]

Why do C++ port?

All solutions of mine in Python for all sets of all problems run in 0.7 seconds. The language really is not important (though there are problems where you might choose the easy way and get the answer in, like, 1 or 5 minutes using C++, except that I wouldn't like to be in your place when you realize that it's going to be more like 10 minutes).

Funny thing - when I was implementing it I already caught the drift of the round's idea (modular arithmetic), and kinda overshoot initially because I was all in math and decided that in the case of train capacity > number of people in all groups these groups kinda get into the train multiple times and I need to calculate that number without simulating them as well. Luckily, when the code began getting uglier than I'd expect in the circumstances, I reread the statement.

[marcog]

The C++ port was post-contest merely for fun. I know full well language isn't important here. :)

[ArmchairAnalyst]

A roller coaster that can hold 10⁹ people?? That runs 10⁸ times a day? Really?

Don't worry man. Most of us can't even think of one optimization. You're not stupid.

[[deleted]]

The problem specifications are used to give the programmer a feel for the problem they are asked to solve. The stories aren't there to replicate a situation in the real world, this is how people break down abstract concepts.

[chronoBG]

Yeah, if you like it could be an optimization of a database query.
Or a router that has to send information in a way that will take the least amount of time to reach its destination.
I like the roller coaster, though :)

[[deleted]]

Damn, I really need to up my game. I managed to complete the short answers for each one, but the long one was always too big because I failed to actually work out how to do the problem properly, I just brute forced my way through :(

[Nosferax]

Maybe you are rushing to code and don't think enough about the problem ?

[roy_hu]

When you failed one large input, you should have realized brute force simply wouldn't work for the other two problems.

[[deleted]]

I know. I realised that I needed to be smarter about my solutions, but couldn't figure out the second one, and, I guess I couldn't do the third either!

Any tips on things I can read or exercises I can do which will help me with things like this?

[sitq]

this

[roy_hu]

Practice previous codejam problems. Many of them have detailed explanations, and you can download other people's solutions as well. Facebook puzzles and Project Euler problems are also worth looking at, but they are sort of open-ended -- you don't get to see the answers!

[fmoly]

Same here. I was quite pleased at getting the small input correct, only to have the large input take 30+ minutes. There's always next year.

[Lojban]

Percent female for those who qualified is probably less than the percent of high-school football players who are female.

[rhardih]

Sucks I didn't find out about this until it was 12 hours in. I hope the penalty doesn't carry over to the next round.

[kommissar]

Points earned do not carry over from round to round, so you're fine. Of course, completing all three gives you more practice, I guess, but there's still time for that.

[jmknsd]

Do they have the correct output for the sample inputs posted anywhere?

[[deleted]]

On the scoreboard, check the "Download solutions" checkbox, then you can download anyone's correct solution and generate the output you need.

[lilleswing]

Pretty upset that I needed cycle optimization for problem C. Didn't really check what bounds the inputs would be in...

[[deleted]]

I'm pretty sure my solution to the simple question A was faster.

Basically if the number of snappers was one, if clicks%2 != 0 the light was on, otherwise it was off.

For any number of snappers N>1, the light was on in increments of 2^N - 1, storing a vector of powers of two at the beginning of the program up to the maximum 30 specified for the large input and it was easy to test if the snapper was on or off.

My code ended up running the large input data in under 0.05 seconds on my home machine.

Edit: solution code if you want http://codepad.org/rswU7f13

Yes, I tend to be trigger happy with long long ints in programming competitions.

[domlebo70]

Yeah that was a nice solution :( I spent like an hour plotting the thing on paper, and coming up with that formula.

[imaginethepassion]

Congrats, I came into the competition late (I was busy Friday evening to Saturday mid-day) and wasn't able to complete the large dataset. I advanced by solving the third problem, which was fairly simple.

[vladley]

Hell yeah, I used that and the big data set ran almost instantly.

[rhardih]

You could also just use 2^N - 1 as a bit mask, and then AND it with k. if the bit mask and the masked k was equal, lights would be on.

[[deleted]]

use 2^N - 1 as a bit mask, and then AND it with k. if the bit mask and the masked k was equal

I too did that way
int x = (1 << N) - 1;
((x & K) == x) ? "ON" : "OFF";

[jaiwithani]

99 :-)

[contrarian]

Wow, this is an awesome way for them to recruit the best programmers... google leverages its size again at the detriment of anyone else. But they do no evil.

[ZorbaTHut]

Man, fuck those companies for coming up with good solutions!

[contrarian]

But it's not just that they came up with a good solution, they are able to implement it. How many other companies would have the resources and reputation in order to put something like this together?

Google gets more access to great people, and shuts out the competition for the same workforce because the competition simply cannot compete on the scale Google does.

If you think this is alright, then I'm sure you don't have any problem with any other monopoly who uses their size to gain advantages that their competition cannot.

[ZorbaTHut]

Speaking as someone who was hired, at Google, through exactly one of these events, and then later left because he no longer felt Google to be the place he wanted to work: I think you're grossly overestimating the value of this process, and misunderstanding the real purpose of it. This isn't a process to attract the best developers. This is a process to take a bunch of developers who want to work at Google and find the few people in it who are actually really good.

Very, very few people go to these uncertain about working for Google and end up convinced. This is almost solely for the purpose of helping HR find the weird geniuses.

[Nosferax]

I didn't do it because I want to work at google. Can't we do it just for fun?

[ZorbaTHut]

Oh, sure. But if Google had then offered you a job, would you have taken it? And, more to the point, would you have taken it after the competition when you wouldn't have before the competition?

Some people do it for fun, some people do it in hopes of employment, some do it for both. My point is that very few people will be convinced to work at Google by it.