Server Help :: View topic - NyahahahahaahahahahahahaAaaa!

Server Help

Trash Talk - NyahahahahaahahahahahahaAaaa!

SamHughes - Wed Oct 17, 2007 1:45 pm
Post subject: NyahahahahaahahahahahahaAaaa!

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 - Wed Oct 17, 2007 3:37 pm
Post subject:

awesome, what are you going to buy man?

Bak - Wed Oct 17, 2007 5:28 pm
Post subject:

wat! I won a programming contest at RPI and all I got was a mouse for my laptop!

Cyan~Fire - Wed Oct 17, 2007 6:54 pm
Post subject:

Yeah, that's a lot of money! Nice.

tcsoccerman - Wed Oct 17, 2007 8:42 pm
Post subject:

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

Quote:

Subject: ACM/UPE Programming Contest Results

that's not a language..right? what language was it in?

Dr Brain - Wed Oct 17, 2007 9:26 pm
Post subject:

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.

CypherJF - Wed Oct 17, 2007 9:34 pm
Post subject:

Sweet deal; ACM challenges are some of the more difficult to answer.

Bak - Thu Oct 18, 2007 1:29 am
Post subject:

what were the 7 problems?

SamHughes - Thu Oct 18, 2007 2:01 am
Post subject:

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 - Thu Oct 18, 2007 2:46 pm
Post subject:

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 - Thu Oct 18, 2007 9:09 pm
Post subject:

Bak wrote:

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.

Which professor? Edit: Oh, and that's the hilariousest thing I've heard all week.

Bak wrote:

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.

Oh I guess that means you could do:

Code: Show/Hide

void merge(char a, char b, std::vector<int>& groups) {
if (groups[a - 'A'] != groups[b - 'A']) {
int aval = groups[a - 'A'];
int bval = groups[b - 'A'];
std::replace(groups.begin(), groups.end(), bval, aval);
}
}

Bak - Fri Oct 19, 2007 2:22 am
Post subject:

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 - Sun Oct 21, 2007 10:29 pm
Post subject:

Bak wrote:

wat! I won a programming contest at RPI and all I got was a mouse for my laptop!

RPI? In Troy? I go to SUNY Albany.