Author: Robert Hyatt
Date: 09:09:16 02/10/06
Go up one level in this thread
On February 10, 2006 at 11:00:50, Derek Mauro wrote: >On February 10, 2006 at 09:56:04, Robert Hyatt wrote: > >>On February 10, 2006 at 04:30:21, Ricardo Gibert wrote: >> >>>On February 09, 2006 at 23:53:33, Derek Mauro wrote: >>> >>>>So, today I found out that there was going to be an ACM programming contest at >>>>my school. Someone who knew I liked to program told me I should participate for >>>>fun. It was an algorithm contest. We were given 4 problems to solve in two >>>>hours. >>>> >>>>I read the first question. Basically, you were given a 4x4 magic square (see >>>>http://en.wikipedia.org/wiki/Magic_square if you don't know what that is) with 2 >>>>spots missing. Fill in the 2 missing spots and print the magic square. This is >>>>a pretty easy problem, and I figured it shouldn't take more than 10 minutes, if >>>>even that long. >>>> >>>>I looked at the second question, and my eyes lit up. The title of the problem >>>>was “Endgame”. You were given a chessboard as 8 lines of text to stdin (for >>>>example, rnbqkbnr for the first line). The positions were guaranteed to be a >>>>mate-in-1. You can ignore castling, en passant, and moving a pawn forward 2 >>>>squares. Print the position after the mating move. Now, I think it would be a >>>>pretty safe bet that I knew more about chess programming than the other 30 or so >>>>contestants in the room combined. I should have a huge advantage here. >>> >>>Ego. This is maybe one of your mistakes. >>> >>>> >>>>Silly me, instead of doing the easy question first, I immediately started coding >>>>the chess question. 15 minutes later I realized that the contest is first based >>>>on the number of questions you solve, and if there's a tie, the time you took, >>>>so I better just do the easy one first. >>>> >>>>I race through the magic square problem, print a sample problem, it doesn't >>>>work. I quickly saw the error in my mental math and fixed it, which (somehow) >>>>made me only the 4th person to submit a correct answer up to that point. >>>> >>>>I spent the rest of the time working on the chess problem. I had an almost >>>>working program with 50 minutes left of the original 2 hours, but I spent >>>>another 10 minutes figuring out why the IO didn't work. >>> >>>I strongly suspect there is a trick to solving this question and that the trick >>>consists of being smart enough to not attempt to solve the "endgame" problem at >>>all given the time constraints. >>> >>>The logical thing to do with such a test is to read all of it first, sort the >>>problems by order of how much estimated time they will take, then solve them in >>>order of this estimated time. The shortest estimated times being done first. >>>Hopefully, ego does not cloud your judgement here. >> >>That is actually probably a design goal of the contest. If you can't get the >>three "easy ones" done first, not much point in tackling the hardest one at all. >> Takes some mental discipline to do this... >> > >The questions were supposedly given in order of difficulty. I'll tell you the >other 2 questions and you can judge for yourself. > >Question 3 (about 2 pages long, here's a summary): There's an office building >that has been invaded by zombies. A security guard is in his office and on the >security cameras can see the which rooms contain zombies. An employee has >baracaded himself in his office, and won't move unless the security guard passes >though his room. The security guard has k shotgun shells, each capable of >clearing a room full of zombies. Zombies can multiply and spread to other >rooms. You are given number of shotgun shells, the room the security guard >starts in, the room the employee starts in, the rooms initially infested with >zombies, the list of rooms with doors to the outside, and a list of the internal >doors with a description of the door. A description of an internal door might >be "roomA roomB 1 3", meaning roomA is connected to roomB by a door a human can >pass through in 1 unit of time and a zombie can pass through in 3 units of time. > Output should be the maxiumum number of suriviors (0, 1, or 2). > >I probably should have tried that one first, but I wouldn't call it easy because >there are like 7 parameters. It also would have been nice if the room names >were integers and instead of strings. > >Question 4: An inverted cone is filled with water. You are given 2 floating >point numbers: the radius and height of the cone. Find the radius of the sphere >which if dropped into the cone would have caused the maxiumum amount of water to >spill over the top. The answer has to be accurate to 3 significant digits. >Maybe I could have figured out how to do this, in a week's time. That one sounds easiest. Restated: Find the sphere that will fit into the cone, where the surface of the sphere just contacts the top "surface" of the cone. That's the largest sphere you can put in there, which will displace the most water. You can reduce this to two dimensions, a triangle with base B and height H. Fit a circle into that triangle such that the base is a tangent to the circle, and the radius of the circle doesn't pass through the cone. I'd probably go about that like this: Center of the circle has to lie along the center of the cone that stretches from the vertex to the middle of the base. so my goal is to find a circle whose center is along that line, with radius R, such that R touches the base, and touches the side, both at 90 degrees. The algorithmic solution would probably be to slide the center upward from the base, testing the radius for reaching the side of the cone as the radius increases to push the center of the circle away from the base. > > >> >> >> >>> >>>> >>>>When you submit you answer, the system automatically tries several test cases. >>>>It indicated that my program crashed. Strange. Non of the test cases I tried >>>>caused a crash. I tried using the Visual C++ debugger. Unfortunately, the >>>>computers we were using were configured so that you can't debug a program unless >>>>you are an administrator. Idiots. The tournament director had no idea about >>>>this. >>>> >>>>I never figured out why the program was crashing. But I finished in 4th, >>>>winning me a Visual Studio t-shirt, with a Napoleon Dynamite (stupidest movie >>>>ever) joke on the back. I actually didn't read the other problems during the >>>>contest, because I was so determined to finish the chess question, but looking >>>>at them now, I think would have been able to do both (no one actually solved >>>>them). As far as I can tell, the solutions to the other 2 questions are much >>>>much shorter, and not nearly as tedious. The other problems are pretty cool, >>>>maybe I'll post the problems in CTF, if anyone is interested. >>>> >>>>So as I sit here dejected that I couldn't solve a problem I've spent years on, >>>>I'd like ask everyone this question: How confident are you that you can 100% >>>>accurately write the solution to the chess question in less than 2 hours, under >>>>the pressure of competition, without the use of a debugger? >>>> >>>>Or am I just an idiot? :)
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.