Server Help

[SamHughes]

So there was held a programming contest at my college this Saturday, with 7 questions to be answered in the time period from 3:30-6:30.

I got this email in my inbox the other day:

Code: Show/Hide Subject: [..] Programming Contest Results Dear [..] Programming Contest participants, I am pleased to announce the results of the contest held yesterday, October 13. The winners are as follows: First Place ($1,000 Amazon.com gift card): Sam Hu[..]ghes Number of successful submissions: 7 Time of last successful submission: 5:33 PM Second Place ($500 Amazon.com gift card): [...] Number of successful submissions: 7 Time of last successful submission: 6:25 PM Third Place ($250 Amazon.com gift card): [...] Number of successful submissions: 6 Time of last successful submission: 6:03 PM The winners will be contacted regarding their prizes via email. Thank you to all who participated, and we'll see you again next year. -- [...]

Muhahahahahhahaaahahahaahahahahahahhhaaaa!

Edit: I guess I'm a bit of a jerk for posting it like this.

[The Apache]

awesome, what are you going to buy man?

[Bak]

wat! I won a programming contest at RPI and all I got was a mouse for my laptop!
_________________
SubSpace Discretion: A Third Generation SubSpace Client

[Cyan~Fire]

Yeah, that's a lot of money! Nice.
_________________
This help is informational only. No representation is made or warranty given as to its content. User assumes all risk of use. Cyan~Fire assumes no responsibility for any loss or delay resulting from such use.
Wise men STILL seek Him.

[tcsoccerman]

Nice. Too bad it's just for amazon, but still.

[Dr Brain]

Was it hard to win? How many people were you up against?

That seems like a lot of money to shell out for a contest like that. Your CS department must be better funded than the one at my university.
_________________
Hyperspace Owner

Smong> so long as 99% deaths feel lame it will always be hyperspace to me

[CypherJF]

Sweet deal; ACM challenges are some of the more difficult to answer.
_________________
Performance is often the art of cheating carefully. - James Gosling

[Bak]

what were the 7 problems?

[SamHughes]

It was funded by Morgan Stanley and they had a resume upload field on the registration page, so I guess it was a cheap way to recruit. It was run by RPI's ACM and UPC chapters, I think. You could use C, C++, or Java; I used C++, since I used to write homework in it 2.5 years ago and the STL is useful.

They weren't ACM competition level questions -- some of them were trivially easy. No, all of them were, of course, but some moreso than others. Here's my review of them, because I feel like ranting.

1. "mapquest". You're given a list of edges in the form "AB\nCD\nAD\n...", specifying an undirected graph, followed by 00\n, followed by a list of pairs of nodes in the form "AC\nZX\n...". for each pair of nodes, tell if the two nodes on the graph have a path between them.


This kind of question separates people, because you have to figure out the best way to represent the graph and how to see if two nodes have a path between them. If you try an adjacency list, you're going to have to deal with some ugly DFS algorithm that marks nodes it has visited, with which you have to be careful and it will take time to code. The better way is to make a boolean adjacency matrix, 26x26, and square it (with | as addition and & as multiplication) until it stops changing (or just square it 5 times; that's sufficient since 32 > 25). Squaring is just a triple for loop, and you don't have to be all careful and recursive.

Come to think of it, my solution was wrong; I forgot to prefill the matrix with adjacencies connecting nodes to themselves. But it passed the judging tests.


2. "union". You're given the upper left and lower right corners of two rectangles. Find the areas of their union and intersection.


This is easy, the first I did; make a function for rectangle area, implement intersection with max/min operations, and compute the union's area by adding the areas and subtracting the intersection area. You'll get slowed down if you use special cases instead of max/min.


3. "areafill". Fill a region like the MS Paint paintbucket. Only it's with ASCII art.


Just use a queue of edges to be filled; make sure your coordinates aren't upside down. Represented the ascii drawing as a vector of strings; if you're retarded you'll use a vector of vectors.


4. "jumble". You're given a list of words to go into the dictionary, followed by a blank line, followed by a list of jumbled words. Unjumble the words and output the unjumbled version with the capitalization given in the dictionary.


Sucks to use C; map, sort, and next_permutation are your friends. Your program will run too slow on the judge's input because you have a 15 second limit, without maps (mapping lowercased to input-cased strings for the dictionary) or hash tables. People who don't know about next_permutation and possibly those using Java will be slowed down significantly on this one.

Edit: Sigh, I'm dumb. Just store a map of _sorted_ strings (sorted by character) to their original input format! That's much better.


5. "dates". Find the difference between two dates. All the dates are between "01012000" and the contest date.


Just compare to a reference date and subtract. Hurts people who paid enough attention in data structures & algorithms to do well on the other problems but suffer a mental block on this kind of problem, trying to do direct subtraction, which is ugly. That killed about 3-5 minutes for me.


6. "base convert". Read a number in decimal and a number from 2-36 and convert it to that number system.


Come on, that's easy! Maybe the judge's input had negative numbers to trip people who assumed from the examples that they would all be positive. I wish, because I coded that check just in case. You coded this on a TI-83 in 9th grade, right?


7. "raid". Your raid array has been corrupted! Given five bytes, one of them corrupted (given as a string of ten hexadecimals with one pair replaced by XX), replace the XX with the appropriate byte!


Just xor them together people. This description was very long and looked intimidating, but what it amounted to was replacing the XX in abXXcdef23 with the value (0xab ^ 0xcd ^ 0xef ^ 0x23). You have to know some basic bitwise operations and how to convert two digit hex into an unsigned char I guess. This problem measures your ability to read, more than anything.





The competition (meaning the other people in the room), I'd say, was largely lame. If it wasn't, I'd have lost, or wouldn't have won by 52 minutes. For example, the guy next to me was using Visual Studio, and I get the feeling he couldn't program his way outside a plastic bag. (Or at least he spent an inordinate amount of time staring vacantly at his screen.) There was one potential competitor that I recognized, but he got in an ideological dispute because they wouldn't let him use Jython to generate Java code or something, so he left. (He was a moron for wanting to use Python anyway; static typing and compiler checks are very handy when writing code as fast as you can.) I think he's more ego than ability, but I don't actually know. I'm not going to say his name, but let's just say you could install a birds' nest in his beard. He makes me think of Richard Stallman. Bak probably knows who I'm talking about.

The people in 2nd and 3rd place were freshman, one compsci and one undeclared engineering. After googling them, they look like the kind of people who programmed their calculators in assembly language. In elementary school. I'm not sure if these two were just generally slower than me or if they just got slowed down by some particular problem.

In general, if it's possible to get through RPI as a CS major while holding a strong conviction that vectors are implemented as linked lists, that rules out 2/3 of the CS majors here.

[Bak]

Oh beardy's still around? I had programming languages with him and he argued with the professor and stormed out during lecture about 50% of the time.

For the first one, doesn't it amount to checking if the two nodes are in the same connected component? I'd probably make a vector of sets and add elements / merge sets as necessary and then see if the two elements are in the same set to see if there's a path between them.

[SamHughes]

[Bak]

It was with professor moorthy. He wasn't the best teacher but any reasonable person could see the points he was trying to make; I actually think I remember people telling the kid to shut up as he argued with the prof... it's like he has his laptop open all class not paying attention, then when he finds one detail he disagrees with he can argue for 30 minutes about it...

anyways I think your function would work if you initialize the vector such that every value is unique.

[Purge]