Google Code Jam 2017

[Bobblehead]

[img]https://code.google.com/codejam/assets/codejam-logo-300x76.png[/img]

[url]https://code.google.com/codejam/[/url]

Google Code Jam starts in 5 hours. You should join! :)

This will be my first year competing. Is anyone else planning to participate?

[TrinityX]

Man, wish i saw this earlier...
I would have liked to try participating, but i'm not that good at algorithm programming, so i'd probably fail the qualifications.

I attempted to write a solution for question A of this year's qualification round just now, managed to solve all cases where the result is 0 or 1, but pretty much gave up on the other cases since i don't understand how you would figure out whether to flip "-++" or "++-" in the sample they provide [URL="https://code.google.com/codejam/contest/3264486/dashboard"]here[/URL].

Here's the code i wrote for anyone interested (C++): [url]https://fiz.pw/u/bJSy2N1.txt[/url]

[Bobblehead]

[QUOTE=TrinityX;52079846]
I attempted to write a solution for question A of this year's qualification round just now, managed to solve all cases where the result is 0 or 1, but pretty much gave up on the other cases since i don't understand how you would figure out whether to flip "-++" or "++-" in the sample they provide [URL="https://code.google.com/codejam/contest/3264486/dashboard"]here[/URL].[/QUOTE]

That one seemed really hard because the way it was worded made it seem like there was some super optimal way to do it, but in reality if you just went left to right, flipping everything to the right of each - you found, it would be optimal.

The case was impossible if the sum of +'s and the sum of -'s were [I]both[/I] not divisible by the spatula width.

[zerf]

bobblehead, did you qualify?

I made it through the qualifier round, but skipped round 1A. I will be participating in 1B and if necessary 1C.

I was able to [URL="https://gist.githubusercontent.com/bmwalters/a4d34a994bf4c9ad1a57718a4a1d7e4d/raw/309cfbe28ac4b1d7d3ff9146031ac3a6568a913d/tidy.cpp"]solve tidy[/URL] in a performant way. I also solved the smallest bathroom stalls problem, but could not come up with a decent solution. I couldn't figure out an algorithm for pancakes (as you've been discussing), and I hardly looked at fashion.

[editline]15th April 2017[/editline]

The funny thing about my tidy solution is that I originally wrote it in a way that would only handle changing one digit (such as 130 -> 129), but it would fail on cases like 110 (expected 99, mine would output 109).
I then just made it recursively run the code until no digits were changed, then I'd return it, and it worked :v:

[Bobblehead]

I qualified with 35 points, but I expected to get 50; I got one of the large datasets wrong.

In round 1A I couldn't get the first question correct in a timely manner so I quit after about an hour. Round 1A-C really weed out the competition so I'm not too worried if I can't make it. I typically perform better with these kinds of things when I'm not strapped for time.

My Tidy solution was based on the observation that any combo of 1's (such as 11, 111, 1111) could find a number that was tidy. I rounded the input down to the nearest multiple of one of these numbers and counted up from there. I guess it didn't work for the large dataset though...

I really wish it told you [I]where[/I] you went wrong, instead of just saying INCORRECT. Would make debugging much more realistic and actually possible.

Here's my solutions if anyone wants them:
[url]https://www.dropbox.com/sh/bmxcq24hjg4qrg9/AABNCdjv_6OdN4IZe5Z-gL6da?dl=1[/url]

EDIT:
[quote]

uint64_t get_largest_divisor(uint64_t num) {
	     if (num >= 1000000000000000000) { return 1000000000000000000; }
	else if (num >= 100000000000000000) { return 100000000000000000; }
	else if (num >= 10000000000000000) { return 10000000000000000; }
	else if (num >= 1000000000000000) { return 1000000000000000; }
	else if (num >= 100000000000000) { return 100000000000000; }
	else if (num >= 10000000000000) { return 10000000000000; }
	else if (num >= 1000000000000) { return 1000000000000; }
	else if (num >= 100000000000) { return 100000000000; }
	else if (num >= 10000000000) { return 10000000000; }
	else if (num >= 1000000000) { return 1000000000; }
	else if (num >= 100000000) { return 100000000; }
	else if (num >= 10000000) { return 10000000; }
	else if (num >= 1000000) { return 1000000; }
	else if (num >= 100000) { return 100000; }
	else if (num >= 10000) { return 10000; }
	else if (num >= 1000) { return 1000; }
	else if (num >= 100) { return 100; }
	else if (num >= 10) { return 10; }
	else { return 1; }
}

[/quote]
Something really funny about this function haha. You could have used pow(10, floor( log10(num) ) ).

EDIT 2:
I solved the bathroom one pretty well, I'd say. Lua tables worked nicely to store the available gaps for a person to go into, but the medium dataset took about 30 seconds and the large dataset took longer than the 8 minutes allotted.