Google CodeJam is a coding contest for programmers... The first round (Qualification round) was today, and I joined the fun [geeky fun - mind you]. The contest can be found here, and included three problems.
I published my solutions to all three problems at this location.
The first two problems were really easy. The third problem was a bit of a challenge because it required going back to geometry and trigonometry. The problem descriptions can be found at the contest location provided above.
Subscribe to:
Post Comments (Atom)
Posts
15 comments:
how can you say the problems were easy when you got the solution wrong ? I checked your solution for the train problems and its completely wrong
Then you must have done something wrong. I got perfect scores in this round.
Not sure what you did wrong, but its pretty straight forward.
1- You download the test file.
2- Run the program.
3- Press the button on the form.
4- Specify the input file (the file you just downloaded in step 1).
5- Specify an output file (saved to your hard disk).
6- Upload the file generated in step 5.
i"m tying to understand the solution of the third problem, but it's quite difficult... lol
Can you help with a quick explanation?
Ok, I made an explanation, and provided it as a PDF download.
Check here for the explanation.
Hi Great Mind,
I wish I could join Jam Code, I am busy these days :(.
If you are interested in challenging problems why don't you join Project Euler, my nickname in the Jordan Section is aboSamoor.
Best Wishes
Thank you AbuSamoor, ProjectEuler.net is a very interesting website, with various interesting problems.
Hopefully, I will start solving some of the problems there soon. One of my favorite problems are those that combine mathematics and programming, and thats exactly what Project Euler is about.
in your problem C solution, i think you got the formula for the area of a circular sector wrong.. isnt it 1/2r²Ө
Yes, you are right. In the code it is correct, but in the pdf explanation there is an errata. Fixed now. Thank you for pointing it out.
Nice to know U solution. I solved it too. and here are the solutions:
http://becomingguru.com/2008/07/google-code-jam.html
Do provide me ur feedback. Thanks
Hey Zaid, How did round one go?
Unfortunately, I did not participate in round 1 because I had things to do on that day. But I looked at the problems there, and one problem really blew my mind. I tried to see other people's solutions, but didn't understand them, nor do I have confidence that the problem is solvable to start with.
Thats to say, I suspect that even the "reference" answer might not be correct, because I don't think that the problem is easy.
The problem is to find exactly the three digits before the decimal point, for this expression:
(3+sqrt(5)) power N
where N is a large number (N can have upto 9 digits).
for example, say N=5, then
(3+sqrt(5)) power 5 = 3935.74
so the answer would be "935".
or say N=9, then
(3+sqrt(5)) power 9 = 2958335.91
so the answer would be "335".
And so on. Now how would you solve this to big values of N?! I don't think that this problem can be solved without using high precision arithmetics. Although the solutions that were accepted did not use high precision arithmetics. I am skeptic about the correctness of those solutions, and wish if someone can provide a mathematical justification for the solutions provided!
Hmm, after checking on the internet after I posted my comment (I checked before but didn't find anything), I found a reasonable explanation for the solution. And it now makes sense, although the solution uses a special case and may not be generalizable to all values of a and b in the form "a+sqrt(b) power N", it only works when a and sqrt(b) are less than 1 apart.
See here: Explanation
I might make a post to add some notes the the explanation provided in the link.
Hi
I have a question to your solution of fly swatter
How it's possible you calculate area of triangles in this way:
double AreaOfTriangles = 0.5 * (Y2 - RectY) * RectX + 0.5 * (X2 - RectX) * RectY;
How it works ? For me these are not the same triangles, as those going from the center of ring
I would calculate triangle height to ring radius for each triangle and then calculate area
Read my explanation here, and it should make things clear.
If you already read that, I can elaborate a little.
The code snipper is from the "Circle crosses lower corner", the first case that I considered in the above pdf file.
(RectX,RectY) represent the co-ordinates of point D (in the graph in the PDF).
(RectX,Y2) represent point A.
(X2,RectY) represent point B.
(zero,zero) is the point of origin, which is point C in the graph.
so:
0.5 * (Y2 - RectY) * RectX
is the area of rectangle CAD
AND
0.5 * (X2 - RectX) * RectY
is the area of rectangle CBD
Notice that for rectangle CAD,
Y2-RectY = length of AD (our base)
AND
RectX is the height of the rectangle. Remember that RectX is the X-coordinate of point D.
Same logic applies for rectangle CBD.
I hope all is clear now.
I get it now :) thanx
Post a Comment