Google Code Jam 2013 page 2

53 posts

Flag Post

Haha, I didn’t sleep at all the night before, don’t ask why. :P
It was actually probably somewhere around 15 hours. ;-;

 
Flag Post

I just looked through some random entries…. a guy named ‘Soultaker’ from NL (rank 62). the first tic tac toe source code is just a txt file saying he did it in hand. for the large tic tac toe there is a brainfuck code, and the rest is coded in python, c and c++ hereby changing language at every problem >_<…. That Brainfuck part…. lol.

 
Flag Post

pssh brainfuck is so easy… take a look at KirarinSnow’s Whirl solution

http://www.go-hero.net/jam/13/name/KirarinSnow

 
Flag Post

haha, thanks for sharing that site as well! Funny to see the list of my own country xD

also; I was 1/7 contestans using ActionScript xD… together with UG I see.

 
Flag Post

:D Haha, yep! How did you know I used AS?

I was on the fence between that and Java but I’d have to download JDK or JRE or whatever to get BlueJ to work so I chose AS.

And thanks for that awesome site Jonathan.

EDIT Oh, it lists usernames.
EDIT x2 Nice fair and square solution. Almost the exact same as mine in terms of logic. Your palindrome code was exactly like I did it too. value.split("").reverse().join("")

 
Flag Post

Yeah… It ended up working… But it wasn’t fast enough to calculate the large input file xD

 
Flag Post

Exactly! I clicked the large before testing a single large value with mine by accident. D: It timed out calculating the first one! If they allowed for retries I could have optimized it easily to do the first large data set.

 
Flag Post

For fair and square, I figured you should just iterate through the square numbers (which I did), and so getting through 107 numbers (note also storing these – pre-computation) is obviously a breeze, but I still don’t have a clue as to how to solve the extra large, having already very briefly glanced at a few solutions out there; somehow you’ve got to pick out a mathematical property of possibly palindromes with squares that greatly reduces the sample space

 
Flag Post

The official analysis is always posted quite soon after the round ends. You can find it by clicking “Contest Analysis” on the sidebar (https://code.google.com/codejam/contest/2270488/dashboard#s=a)

 
Flag Post
So for the fair and square one:
Naive Solution: go from a to b and check if palindrome then check if sqrt is palindrome
Slightly Better: go from ceil(sqrt(a)) to floor(sqrt(b)) and check if palindrome and then check if square is palindrome
Even Better: generate only palindromes between ceil(sqrt(a)) to floor(sqrt(b)) and then check if square is palindrome
Best(?): generate only palindromes between ceil(sqrt(a)) to floor(sqrt(b)) that could possible have a square palindrome and check if square is a palindrome

Some interesting data that makes it easier to see patterns - here's a list of fair and square pairs from 1 to 1030. It took < a second to generate on my computer using a method between the last two I listed (I'm fairly certain the data is correct - I generated it using my solution to the 1014 round, but there's a small chance that after 1014 something could have gone wrong)




1 1
2 4
3 9
11 121
22 484
101 10201
111 12321
121 14641
202 40804
212 44944
1001 1002001
1111 1234321
2002 4008004
10001 100020001
10101 102030201
10201 104060401
11011 121242121
11111 123454321
11211 125686521
20002 400080004
20102 404090404
100001 10000200001
101101 10221412201
110011 12102420121
111111 12345654321
200002 40000800004
1000001 1000002000001
1001001 1002003002001
1002001 1004006004001
1010101 1020304030201
1011101 1022325232201
1012101 1024348434201
1100011 1210024200121
1101011 1212225222121
1102011 1214428244121
1110111 1232346432321
1111111 1234567654321
2000002 4000008000004
2001002 4004009004004
10000001 100000020000001
10011001 100220141022001
10100101 102012040210201
10111101 102234363432201
11000011 121000242000121
11011011 121242363242121
11100111 123212464212321
11111111 123456787654321
20000002 400000080000004
100000001 10000000200000001
100010001 10002000300020001
100020001 10004000600040001
100101001 10020210401202001
100111001 10022212521222001
100121001 10024214841242001
101000101 10201020402010201
101010101 10203040504030201
101020101 10205060806050201
101101101 10221432623412201
101111101 10223454745432201
110000011 12100002420000121
110010011 12102202520220121
110020011 12104402820440121
110101011 12122232623222121
110111011 12124434743442121
111000111 12321024642012321
111010111 12323244744232321
111101111 12343456865434321
111111111 12345678987654321
200000002 40000000800000004
200010002 40004000900040004
1000000001 1000000002000000001
1000110001 1000220014100220001
1001001001 1002003004003002001
1001111001 1002223236323222001
1010000101 1020100204020010201
1010110101 1020322416142230201
1011001101 1022123226223212201
1011111101 1022345658565432201
1100000011 1210000024200000121
1100110011 1210242036302420121
1101001011 1212203226223022121
1101111011 1212445458545442121
1110000111 1232100246420012321
1110110111 1232344458544432321
1111001111 1234323468643234321
2000000002 4000000008000000004
10000000001 100000000020000000001
10000100001 100002000030000200001
10000200001 100004000060000400001
10001010001 100020201040102020001
10001110001 100022201252102220001
10001210001 100024201484102420001
10010001001 100200120040021002001
10010101001 100202122050221202001
10010201001 100204124080421402001
10011011001 100220341262143022001
10011111001 100222343474343222001
10100000101 102010002040200010201
10100100101 102012022050220210201
10100200101 102014042080240410201
10101010101 102030405060504030201
10101110101 102032425272524230201
10110001101 102212122262221212201
10110101101 102214144272441412201
10111011101 102232545484545232201
10111111101 102234567696765432201
11000000011 121000000242000000121
11000100011 121002200252002200121
11000200011 121004400282004400121
11001010011 121022221262122220121
11001110011 121024421474124420121
11010001011 121220122262221022121
11010101011 121222324272423222121
11011011011 121242363484363242121
11011111011 121244565696565442121
11100000111 123210002464200012321
11100100111 123212222474222212321
11101010111 123232425484524232321
11101110111 123234645696546432321
11110001111 123432124686421234321
11110101111 123434346696643434321
20000000002 400000000080000000004
20000100002 400004000090000400004
100000000001 10000000000200000000001
100001100001 10000220001410002200001
100010010001 10002002100400120020001
100011110001 10002222123632122220001
100100001001 10020010200400201002001
100101101001 10020230421612403202001
100110011001 10022014302620341022001
100111111001 10022234545854543222001
101000000101 10201000020402000010201
101001100101 10201222221612222210201
101010010101 10203022140604122030201
101011110101 10203244363836344230201
101100001101 10221210222622201212201
101101101101 10221432643834623412201
101110011101 10223234344844343232201
110000000011 12100000002420000000121
110001100011 12100242003630024200121
110010010011 12102202302620320220121
110011110011 12102444325852344420121
110100001011 12122010222622201022121
110101101011 12122252443834425222121
110110011011 12124214524842541242121
111000000111 12321000024642000012321
111001100111 12321244225852244212321
111010010111 12323222344844322232321
111100001111 12343210246864201234321
200000000002 40000000000800000000004
1000000000001 1000000000002000000000001
1000001000001 1000002000003000002000001
1000002000001 1000004000006000004000001
1000010100001 1000020200104010020200001
1000011100001 1000022200125210022200001
1000012100001 1000024200148410024200001
1000100010001 1000200030004000300020001
1000101010001 1000202030205020302020001
1000102010001 1000204030408040304020001
1000110110001 1000220232126212320220001
1000111110001 1000222232347432322220001
1001000001001 1002001002004002001002001
1001001001001 1002003004005004003002001
1001002001001 1002005006008006005002001
1001010101001 1002021222306032221202001
1001011101001 1002023224327234223202001
1001100011001 1002201232026202321022001
1001101011001 1002203234227224323022001
1001110111001 1002221454348434541222001
1001111111001 1002223456569656543222001
1010000000101 1020100000204020000010201
1010001000101 1020102020205020202010201
1010002000101 1020104040208020404010201
1010010100101 1020120402306032040210201
1010011100101 1020122422327232242210201
1010100010101 1020302030406040302030201
1010101010101 1020304050607060504030201
1010110110101 1020322434528254342230201
1010111110101 1020324454749474544230201
1011000001101 1022121002226222001212201
1011001001101 1022123024227224203212201
1011010101101 1022141424528254241412201
1011011101101 1022143446549456443412201
1011100011101 1022323232448442323232201
1011101011101 1022325254649464525232201
1100000000011 1210000000024200000000121
1100001000011 1210002200025200022000121
1100002000011 1210004400028200044000121
1100010100011 1210022220126210222200121
1100011100011 1210024420147410244200121
1100100010011 1210220032026202300220121
1100101010011 1210222232227222322220121
1100110110011 1210242254148414522420121
1100111110011 1210244454369634544420121
1101000001011 1212201002226222001022121
1101001001011 1212203204227224023022121
1101010101011 1212223242528252423222121
1101011101011 1212225444549454445222121
1101100011011 1212421234248424321242121
1101101011011 1212423436449446343242121
1110000000111 1232100000246420000012321
1110001000111 1232102220247420222012321
1110010100111 1232122422348432242212321
1110011100111 1232124642369632464212321
1110100010111 1232322032448442302232321
1110101010111 1232324252649462524232321
1111000001111 1234321002468642001234321
1111001001111 1234323224469644223234321
2000000000002 4000000000008000000000004
2000001000002 4000004000009000004000004
10000000000001 100000000000020000000000001
10000011000001 100000220000141000022000001
10000100100001 100002002010040010200200001
10000111100001 100002222012363210222200001
10001000010001 100020001200040002100020001
10001011010001 100020221222161222122020001
10001100110001 100022003410262014300220001
10001111110001 100022223434585434322220001
10010000001001 100200100020040020001002001
10010011001001 100200320240161042023002001
10010100101001 100202104032060230401202001
10010111101001 100202324254383452423202001
10011000011001 100220121220262022121022001
10011011011001 100220341462383264143022001
10011100111001 100222125432484234521222001
10100000000101 102010000002040200000010201
10100011000101 102010222202161202222010201
10100100100101 102012022032060230220210201
10100111100101 102012244234383432442210201
10101000010101 102030201204060402102030201
10101011010101 102030423426181624324030201
10101100110101 102032223434282434322230201
10110000001101 102212100022262220001212201
10110011001101 102212322442383244223212201
10110100101101 102214124054282450421412201
10111000011101 102232321224484422123232201
11000000000011 121000000000242000000000121
11000011000011 121000242000363000242000121
11000100100011 121002202210262012202200121
11000111100011 121002444212585212444200121
11001000010011 121022001220262022100220121
11001011010011 121022243242383242342220121
11001100110011 121024203630484036302420121
11010000001011 121220100022262220001022121
11010011001011 121220342242383242243022121
11010100101011 121222304234282432403222121
11011000011011 121242121242484242121242121
11100000000111 123210000002464200000012321
11100011000111 123210244202585202442012321
11100100100111 123212222232484232222212321
11101000010111 123232201224484422102232321
11110000001111 123432100024686420001234321
20000000000002 400000000000080000000000004
100000000000001 10000000000000200000000000001
100000010000001 10000002000000300000020000001
100000020000001 10000004000000600000040000001
100000101000001 10000020200010401000202000001
100000111000001 10000022200012521000222000001
100000121000001 10000024200014841000242000001
100001000100001 10000200021000400012000200001
100001010100001 10000202021020502012020200001
100001020100001 10000204021040804012040200001
100001101100001 10000220221212621212202200001
100001111100001 10000222221234743212222200001
100010000010001 10002000102000400020100020001
100010010010001 10002002102200500220120020001
100010020010001 10002004102400800420140020001
100010101010001 10002020304030603040302020001
100010111010001 10002022304232723240322020001
100011000110001 10002200143002620034100220001
100011010110001 10002202143222722234120220001
100011101110001 10002220345234843254302220001
100011111110001 10002222345456965454322220001
100100000001001 10020010000200400200001002001
100100010001001 10020012002200500220021002001
100100020001001 10020014004200800240041002001
100100101001001 10020030220410601402203002001
100100111001001 10020032222412721422223002001
100101000101001 10020210221220602212201202001
100101010101001 10020212223240704232221202001
100101101101001 10020230441632823614403202001
100101111101001 10020232443654945634423202001
100110000011001 10022012102202620220121022001
100110010011001 10022014104402720440141022001
100110101011001 10022032324432823442323022001
100110111011001 10022034326634943662343022001
100111000111001 10022212343224842234321222001
100111010111001 10022214345444944454341222001
101000000000101 10201000000020402000000010201
101000010000101 10201002020020502002020010201
101000020000101 10201004040020802004040010201
101000101000101 10201020402030603020402010201
101000111000101 10201022422032723022422010201
101001000100101 10201202021220602212020210201
101001010100101 10201204041240704214040210201
101001101100101 10201222423432823432422210201
101001111100101 10201224443454945434442210201
101010000010101 10203020102040604020102030201
101010010010101 10203022122240704222122030201
101010101010101 10203040506070807060504030201
101010111010101 10203042526272927262524030201
101011000110101 10203222143242824234122230201
101011010110101 10203224163462926436142230201
101100000001101 10221210000222622200001212201
101100010001101 10221212022222722222021212201
101100101001101 10221230422432823422403212201
101100111001101 10221232444434943444423212201
101101000101101 10221412221442824412221412201
101101010101101 10221414243462926434241412201
101110000011101 10223232102244844220123232201
101110010011101 10223234124444944442143232201
110000000000011 12100000000002420000000000121
110000010000011 12100002200002520000220000121
110000020000011 12100004400002820000440000121
110000101000011 12100022220012621002222000121
110000111000011 12100024420014741002442000121
110001000100011 12100220023002620032002200121
110001010100011 12100222223022722032222200121
110001101100011 12100242243214841234224200121
110001111100011 12100244443236963234444200121
110010000010011 12102200102202620220100220121
110010010010011 12102202302402720420320220121
110010101010011 12102222324232823242322220121
110010111010011 12102224524434943442542220121
110011000110011 12102420145204840254102420121
110011010110011 12102422345424942454322420121
110100000001011 12122010000222622200001022121
110100010001011 12122012202222722220221022121
110100101001011 12122032240432823404223022121
110100111001011 12122034442434943424443022121
110101000101011 12122230223242824232203222121
110101010101011 12122232425262926252423222121
110110000011011 12124212102424842420121242121
110110010011011 12124214304624942640341242121
111000000000111 12321000000024642000000012321
111000010000111 12321002220024742002220012321
111000101000111 12321022422034843022422012321
111000111000111 12321024642036963024642012321
111001000100111 12321222023224842232022212321
111001010100111 12321224243244944234242212321
111010000010111 12323220102244844220102232321
111010010010111 12323222322444944422322232321
111100000001111 12343210000246864200001234321
111100010001111 12343212222246964222221234321
200000000000002 40000000000000800000000000004
200000010000002 40000004000000900000040000004
1000000000000001 1000000000000002000000000000001
1000000110000001 1000000220000014100000220000001
1000001001000001 1000002002001004001002002000001
1000001111000001 1000002222001236321002222000001
1000010000100001 1000020000300004000030000200001
1000010110100001 1000020220302216122030220200001
1000011001100001 1000022002321026201232002200001
1000011111100001 1000022222323458543232222200001
1000100000010001 1000200010020004000200100020001
1000100110010001 1000200230042016102400320020001
1000101001010001 1000202012221206021222102020001
1000101111010001 1000202232243438343422322020001
1000110000110001 1000220012320026200232100220001
1000110110110001 1000220232344238324432320220001
1000111001110001 1000222014541248421454102220001
1001000000001001 1002001000002004002000001002001
1001000110001001 1002001220222016102220221002001
1001001001001001 1002003004005006005004003002001
1001001111001001 1002003224225238325224223002001
1001010000101001 1002021020302206022030201202001
1001010110101001 1002021240524418144250421202001
1001011001101001 1002023024325228225234203202001
1001100000011001 1002201210022026202200121022001
1001100110011001 1002201430264038304620341022001
1001101001011001 1002203214225228225224123022001
1001110000111001 1002221232322248422232321222001
1010000000000101 1020100000000204020000000010201
1010000110000101 1020100222200216120022220010201
1010001001000101 1020102022021206021202202010201
1010001111000101 1020102244221438341224422010201
1010010000100101 1020120200302206022030020210201
1010010110100101 1020120422504418144052240210201
1010011001100101 1020122222343228223432222210201
1010100000010101 1020302010020406040200102030201
1010100110010101 1020302232242418142422322030201
1010101001010101 1020304032241608061422304030201
1010110000110101 1020322212322428242232122230201
1011000000001101 1022121000002226222000001212201
1011000110001101 1022121222422238322242221212201
1011001001001101 1022123024025228225204203212201
1011010000101101 1022141220304428244030221412201
1011100000011101 1022323210022448442200123232201
1100000000000011 1210000000000024200000000000121
1100000110000011 1210000242000036300002420000121
1100001001000011 1210002202201026201022022000121
1100001111000011 1210002444201258521024442000121
1100010000100011 1210022000320026200230002200121
1100010110100011 1210022242322238322232422200121
1100011001100011 1210024202541048401452024200121
1100100000010011 1210220010022026202200100220121
1100100110010011 1210220252044038304402520220121
1100101001010011 1210222212423228223242122220121
1100110000110011 1210242012342048402432102420121
1101000000001011 1212201000002226222000001022121
1101000110001011 1212201242222238322222421022121
1101001001001011 1212203204205228225024023022121
1101010000101011 1212223020322428242230203222121
1101100000011011 1212421210024248424200121242121
1110000000000111 1232100000000246420000000012321
1110000110000111 1232100244200258520024420012321
1110001001000111 1232102222221248421222222012321
1110010000100111 1232122200322248422230022212321
1110100000010111 1232322010022448442200102232321
1111000000001111 1234321000002468642000001234321
2000000000000002 4000000000000008000000000000004
[Finished in 0.8s]
 
Flag Post

Thanks a lot for the link

 
Flag Post
Originally posted by jonathanasdf:

The official analysis is always posted quite soon after the round ends. You can find it by clicking “Contest Analysis” on the sidebar (https://code.google.com/codejam/contest/2270488/dashboard#s=a)

Ha ha, wouldn’t have had to post my thoughts if I knew this existed.

“An alternative is to simply generate all the fair and square numbers up to 1014 before processing the test cases.” I was wondering if this was legal, guess it was.

 
Flag Post

http://www.go-hero.net/jam/13/name/Jonathanasdf

ugh i can’t believe people other than me used cool, pike, and haxe.. guess i need to choose weirder languages next time.. (not that haxe is really weird or anything though)

 
Flag Post

I decided to join in and solved the first two problems in the only language I had at hand, C++ (which a don’t even now that well). I would have used C#, but I didn’t fancy downloading mono and a mono IDE just for that…

Mad props to you guys who actually solved each problem in a different language. It’s quite impressive. I considered trying #2 in befunge, but I never got around to it.

 
Flag Post

Even if I did it in different languages… I would just have ended up using all the ‘normal’ ones such as java, javascript, c, c++ and c#…. Heck, even Matlab >_> It’s not much interesting when ActionScript is the most exotic one I know of xD…

 
Flag Post

Round 1A 2013 starts tomorrow.

 
Flag Post
Originally posted by UnknownGuardian:

Round 1A 2013 starts tomorrow.

Shoot – anyone else think these things are purposelessly designed to be at hard-to do / annoying times? I mean, I love programming contests and all, but not exactly how I want to spend my Friday night :D

 
Flag Post

They have three sub-rounds to ensure that at least one is likely to be at a reasonable time

Argh! Unbelievable!

Got frustrated with the pretty trivial bullseye problem, because I couldn’t simplify a bog-standard algebraic sum on paper in an (‘easy’) attempt to go straight for an efficient solution… :(!
Ended up solving the manage your energy problem after 2:28:41 and a hell of a lot of ridiculous debugging… yeah… just over 1 minute spare, and thus came a few hundred ranks short

By far the most disappointing code jam session I’ve taken part in over the past four or so years.
Then again, I was just a few seconds away from walking out with 0 points haha

Well, good thing the next rounds don’t actually start at 2:00am, like this one did; better luck next time

EDIT: Congrats on the fastest first problem solution by the way, jonathan

 
Flag Post

thanks.

I usually never try for the efficient solution right away, but rather go for something that solves the small fast. Chances are, in the process of coding that, you will gain some insights into the problem.

I had to recode both A and B in order to solve the large.

 
Flag Post

For A I used AS and then I was going to do the large, so I downloaded Java and got to work with BigInteger. Which apparently still isn’t large enough. Lovely. Then I got interrupted to watch a movie, so I left it running and 2 hours later it had processed to #2500. Terrible stuff.

 
Flag Post

I tried using BigInteger/BigDecimal post-event, but I needed to square root, and that caused problems for me

My solution would have otherwise been a four or so lines worth of mathematical equations – no loops involved whatsoever

 
Flag Post
Originally posted by jonathanasdf:

thanks.

I usually never try for the efficient solution right away, but rather go for something that solves the small fast. Chances are, in the process of coding that, you will gain some insights into the problem.

I had to recode both A and B in order to solve the large.

I didn’t get to do this round, but I think this is good advice. Also, once in awhile, the easy solution is efficient enough to handle the large cases, although I bet that might only be the case in the qualifying round

 
Flag Post

The analysis for 1A has just gone up: https://code.google.com/codejam/contest/2418487/dashboard#s=a

 
Flag Post

For the bullseye problem, I was surprised to see the analysis settling on a binary search method when the solution can be derived directly by solving a quadratic equation as:

N = floor((sqrt((2r-1)^2+8t)-(2r-1))/4)

Assuming you use Numbers to store r and t you could solve this problem with AS3 without fear of overflowing.

 
Flag Post

Yeah, but for some reason I couldn’t deal with that equation in Java without error