codejam - Developer IT

Google Code Jam 2010 Large DataSets Take Too Long to Submit

- by Travis

Hey Guys, I'm participating in the 2010 code jam and I solved two of the problems for the small data sets, but I'm not even close to solving the large data sets in the 8 minute time frame. I'm wondering if anyone out there has solved the large data set: What hardware were you running on? What language were you running on? What performance tuning techniques did you do on your code to run as fast as possible? I'm writing the solutions in Ruby, which is not my day to day language, and executing them on my Macbook Pro. My solutions for problem A and problem C are on github at http://github.com/tjboudreaux/codejam2010. I'd appreciate any suggestions that you may have. FWIW, I have alot of experience in C++ from college, my primary language is PHP, and my "sandbox" language is Ruby. Was I just a bit ambitious by taking a shot at this in Ruby, not knowing where the language struggles for performance, or does anyone see anything that's a redflag as to why I can't complete the large dataset in time to submit.

Read the article

Faster or more memory-efficient solution in Python for this Codejam problem.

- by jeroen.vangoey

I tried my hand at this Google Codejam Africa problem (the contest is already finished, I just did it to improve my programming skills). The Problem: You are hosting a party with G guests and notice that there is an odd number of guests! When planning the party you deliberately invited only couples and gave each couple a unique number C on their invitation. You would like to single out whoever came alone by asking all of the guests for their invitation numbers. The Input: The first line of input gives the number of cases, N. N test cases follow. For each test case there will be: One line containing the value G the number of guests. One line containing a space-separated list of G integers. Each integer C indicates the invitation code of a guest. Output For each test case, output one line containing "Case #x: " followed by the number C of the guest who is alone. The Limits: 1 = N = 50 0 < C = 2147483647 Small dataset 3 = G < 100 Large dataset 3 = G < 1000 Sample Input: 3 3 1 2147483647 2147483647 5 3 4 7 4 3 5 2 10 2 10 5 Sample Output: Case #1: 1 Case #2: 7 Case #3: 5 This is the solution that I came up with: with open('A-large-practice.in') as f: lines = f.readlines() with open('A-large-practice.out', 'w') as output: N = int(lines[0]) for testcase, i in enumerate(range(1,2*N,2)): G = int(lines[i]) for guest in range(G): codes = map(int, lines[i+1].split(' ')) alone = (c for c in codes if codes.count(c)==1) output.write("Case #%d: %d\n" % (testcase+1, alone.next())) It runs in 12 seconds on my machine with the large input. Now, my question is, can this solution be improved in Python to run in a shorter time or use less memory? The analysis of the problem gives some pointers on how to do this in Java and C++ but I can't translate those solutions back to Python.

Read the article

Google CodeJam shows "No output file" when trying to send

- by Tom Brito

I've looked in the page for instrutions on this, tried .out or .output extensions and filenames, but nothing works.. How I am supporte to upload the ouput?

Read the article

what does this C++ line of code mean "sol<?=f((1<<n)-1,i,0)+abs(P[i])*price;"

- by KItis

Could anyone help me to understand following line of code. sol I am studying an algorithm written using c++ and it has following operator " following is the error message returned. Hello.cpp: In function ‘int main()’: Hello.cpp:115: error: ‘memset’ was not declared in this scope Hello.cpp:142: error: expected primary-expression before ‘?’ token Hello.cpp:142: error: expected primary-expression before ‘=’ token Hello.cpp:142: error: expected ‘:’ before ‘;’ token Hello.cpp:142: error: expected primary-expression before ‘;’ token may be " Thanks in advance for the time you spent reading this post.

Read the article

Cannot write the output to a text file in cpp program

- by swapedoc

I have this input file "https://code.google.com/codejam/contest/351101/dashboard/do/A-large-practice.in?cmd=GetInputFile&problem=374101&input_id=1&filename=A-large-practice.in&redownload_last=1&agent=website&csrfmiddlewaretoken=OWMxNTVmMTUyODBiYjhhN2Q2OTM3ZGJiMTNhNDkwMDF8fDEzNzIxNzI1NTE3ODAzMjA%3D" I tried to read this file :-using freopen("filename.txt",r,stdin); and then I wanted the output written to be written to another text file which I can upload in this codejam practice question for the judge. #include<iostream> #include<cstdio> using namespace std; int main() { int t,k=0,a[2000]; freopen("ab.txt","r",stdin); scanf("%d",&t); while(t--) { freopen("cb.txt","w",stdout); int c; scanf("%d",&c); int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); printf("Case #%d: ",++k); for(int i=0;i<n-1;i++) {for(int j=i+1;j<n;j++) if((a[i]+a[j])==c) {printf("%d %d\n",i+1,j+1); i=n;} } } return 0; } This is my code. Now the problem is the output file cb.txt contains only the last line of the input. I want the the whole of the output to be written to cb.txt,so what should I do.

Read the article

Google Jam 2009. C. Welcome to Code Jam. Can't understand Dynamic programming

- by vibneiro

The original link of the problem is here: https://code.google.com/codejam/contest/90101/dashboard#s=p2&a=2 In simple words we need to find how many times the string S="welcome to code jam" appears as a sub-sequence of given string S, e.g. S="welcome to code jam" T="wweellccoommee to code qps jam" I know the theory but not good at DP in practice. Would you please explain step-by-step process to solve this DP problem on example and why it works?

Read the article

Extracting rightmost N bits of an integer

- by srandpersonia

In the yester Code Jam Qualification round http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0 , there was a problem called Snapper Chain. From the contest analysis I came to know the problem requires bit twiddling stuff like extracting the rightmost N bits of an integer and checking if they all are 1. I saw a contestant's(Eireksten) code which performed the said operation like below: (((K&(1<<N)-1))==(1<<N)-1) I couldn't understand how this works. What is the use of -1 there in the comparison?. If somebody can explain this, it would be very much useful for us rookies. Also, Any tips on identifying this sort of problems would be much appreciated. I used a naive algorithm to solve this problem and ended up solving only the smaller data set.(It took heck of a time to compile the larger data set which is required to be submitted within 8 minutes.). Thanks in advance.

Developer IT