NEW: For a prettier blog interface, see the Wordpress version!

Tasks

Priorities - A: high, B: medium, C: low; Status - _: unfinished, X: finished, C: cancelled, P: pending, o: in progress, >: delegated. Covey quadrants - Q1 & Q3: urgent, Q1 & Q2: important
A1XRead http://www.javaalmanac.com (2002.11.28)
A2XRetrieve my password (2002.11.28)
A3XSet up the ACM problem set archives (2002.11.28)
A4XInstall J2SDK 1.4.0 and get it working (2002.11.28)
BXE-mail [email protected] and check out http://www.cs.toronto.edu/~igor/acm/next.html (2005.09.16)
BC@1030-1600 Attend ACM programming tryouts at BA3175 (2005.09.17)
B1CContest Scoreboard {{Tasks:848}} (2004.04.26)
B2CJolly Jumpers {{Tasks:842}} {{Schedule:20:00-21:00}} (2004.04.26)
B3CHartals {{Tasks:844}} {{Schedule:21:00-21:30}} (2004.04.26)
B4CCrypt Kicker {{Tasks:845}} {{Schedule:21:30-22:00}} (2004.04.26)
B5CStack 'em Up {{Tasks:846}} {{Schedule:22:00-22:30}} (2004.04.26)
B6CErdos Numbers {{Tasks:847}} {{Schedule:22:30-23:00}} (2004.04.26)
B7CPoker Hands {{Tasks:843}} (2004.04.26)
B8CYahtzee {{Tasks:849}} (2004.04.26)

Priorities - A: high, B: medium, C: low; Status - _: unfinished, X: finished, C: cancelled, P: pending, o: in progress, >: delegated. Covey quadrants - Q1 & Q3: urgent, Q1 & Q2: important
A5XSolve 198: Peter's calculator {{Tasks:58}} (2003.11.15)
B16X1.6.8: 10142: Australian voting {{Tasks:841}} (2004.04.07)
B17XSolve chapter 1 ACM problems {{Tasks:831}} (2004.04.07)
B9X1.6.7: 10196: Check the check {{Tasks:840}} (2004.04.06)
B10X1.6.6: 10033: Interpreter {{Tasks:839}} (2004.04.06)
B11X1.6.5: 10267: Graphical editor {{Tasks:838}} (2004.04.06)
B12X1.6.4: 706: LCD Display {{Tasks:837}} (2004.04.06)
B13X1.6.3: 10137: The Trip {{Tasks:836}} (2004.04.06)
B14X1.6.2: 10189: Minesweeper {{Tasks:835}} (2004.04.06)
B15X1.6.1: 100: 3n + 1 {{Tasks:834}} (2004.04.06)
C1X109: Scud Busters (2002.11.28)
C2X108: Maximum Sum (2002.11.28)
C3X107: The Cat in the Hat (2002.11.28)
C4X106: Fermat vs. Pythagoras (2002.11.28)
C5X105: The Skyline Problem (2002.11.28)
C6X104: Arbitrage (2002.11.28)
C7X103: Stacking Boxes (2002.11.28)
C8X102: Ecological Bin Packing (2002.11.28)
C9X101: The Blocks Problem (2002.11.28)
C10X100: 3n + 1 (2002.11.28)

Notes

6. ACM training again (2005.09.13:2)

Categories: None -- Permalink

I saw a poster for the ACM programming tryouts. I'm really rusty, but it would be good for me to find other geeks and learn from them. =) Besides, I'm curious about their training. Will I qualify, though? I'm not sure if my one class in an MAEd counts. I need less than 5 years of post-secondary studies. Ack, ack, ack.

It'll be fun to go anyway. =)

5. Rank 6741 (2004.04.07:3)

Categories: None -- Permalink

All those compile errors for Java... <grumble> I'm sticking to that language out of principle and because our students will probably submit using it, so I need to demonstrate that almost all the problems are easily doable in Java.

I had to rewrite the Australian Voting solution several times to get it to pass the weird mix of Java 1.1 and 1.2 on http://acm.uva.es . I suspect my final implementation is actually better, but still...

AcmTraining

4. Now up to 7522 in the ACM ranking (2004.04.06:4)

Categories: None -- Permalink

Got the Interpreter (10033) problem on the first try! =)

3. Finally accepted. Up to #8038. (2004.04.06:3)

Categories: None -- Permalink

Grrrr, not reading specs well enough...

E-Mail from Valladolid Online Judge

2. Dropped to 8579 (2004.04.06:2)

Categories: None -- Permalink

I'm still getting wrong-answer on my solution for 10267. I hope this isn't another Java/C thing. I'll translate my program tomorrow, although it's not half as fun in C...

AcmTraining

1. ACM status (2004.04.06:1)

Categories: None -- Permalink

I am currently a very lowly #8559. Will do another four problems tomorrow.

Training

Scratch

199partial differential equationsdon't really feel like solving this right now
198peter's calculatorstore the declarations in a vector, then have a method evaluate variables or throw an exception
197cubebrute force, then check if rotated already?
196spreadsheeteasy
195anagramstraightforward lexicographic non-repeating permutation
194trianglerelatively straightforward mathematics
193graph coloringa bit more complicated. white nodes can be adjacent. brute force? start with a black node, then add nodes that are connected to the graph, flipping the colors if necessary. If this results in more black nodes than previous configuration, mark this node as black and keep configuration, else mark this node as white. Greedy.
192synchronous designlook for cycles, check for delays. can find cycles when calculating delays. Start with nodes directly connected to input, have time associated with each node.
191intersectionstraightforward geom problem. just check if any of the lines that form the rectangle intersect with the line segment, or the line segment is completely contained within the rectangle. even easier because rectangle is parallel to axes.
190circle through three pointsfind the point of intersection of two normals at the halfway point.
189pascal program lengthsjust tokenize properly. stream?
188perfect hashhaven't thought about this much

ACM ICPC Finals 2003

Problem A: building bridges

Ideas:

Label all the buildings. Create a graph of the possible bridges. Test for disconnections. If there are subgraphs that cannot be connected (it's like a rook problem), then consider them on their own. Then do an MST for each subgraph.

Problem B: light bulbs

Ideas:

We solved the 5x5 puzzle before by brute-forcing the whole thing, but with the inputs as 100-digit-long decimal strings, I'm not sure if that's feasible. You are, after all, talking about 10^100, which is a heck of a lot of bits long. So we may actually be forced to find an elegant solution.

If this is the same as the 5x5 puzzle, then we don't have to worry about the minimum number of lights that need to be flipped; there is only one solution, if there is a solution.

Subproblems:

Convert long integers to binary. Java!

Exploit parity. If I decide what to do with the first bit, then all the rest of the bits follow, because I just flip according to the thing I'm currently examining. So there are actually only two cases, and both are checked when I hit the end.

Lovely, that. We'll try it out.

Problem J: toll

This looks like a straightforward greedy graph problem at first glance, but since the number of items at the start is variable, it's actually a bit harder. Ideas? Let's see.

(Comment from J. Anonymous Blog-reader: just go backwards.)

Previous day | Next day

I'd love to hear about any questions, comments, suggestions or links that you might have. Your comments will not be posted on this website immediately, but will be e-mailed to me first. You can use this form to get in touch with me, or e-mail me at [email protected] .

Page: Acm Training
Updated: 2005-09-17
NOTE: ANTI-SPAM MEASURE NOW IN PLACE. Please answer the following question with the right number in order to send me your comment.
What is two minus one? (hint: one ;) )
Name:
E-mail:
URL:
Comments: