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
 A1 X Read http://www.javaalmanac.com A2 X Retrieve my password A3 X Set up the ACM problem set archives A4 X Install J2SDK 1.4.0 and get it working B X E-mail [email protected] and check out http://www.cs.toronto.edu/~igor/acm/next.html B C @1030-1600 Attend ACM programming tryouts at BA3175 B1 C Contest Scoreboard {{Tasks:848}} B2 C Jolly Jumpers {{Tasks:842}} {{Schedule:20:00-21:00}} B3 C Hartals {{Tasks:844}} {{Schedule:21:00-21:30}} B4 C Crypt Kicker {{Tasks:845}} {{Schedule:21:30-22:00}} B5 C Stack 'em Up {{Tasks:846}} {{Schedule:22:00-22:30}} B6 C Erdos Numbers {{Tasks:847}} {{Schedule:22:30-23:00}} B7 C Poker Hands {{Tasks:843}} B8 C Yahtzee {{Tasks:849}}

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
 A5 X Solve 198: Peter's calculator {{Tasks:58}} B16 X 1.6.8: 10142: Australian voting {{Tasks:841}} B17 X Solve chapter 1 ACM problems {{Tasks:831}} B9 X 1.6.7: 10196: Check the check {{Tasks:840}} B10 X 1.6.6: 10033: Interpreter {{Tasks:839}} B11 X 1.6.5: 10267: Graphical editor {{Tasks:838}} B12 X 1.6.4: 706: LCD Display {{Tasks:837}} B13 X 1.6.3: 10137: The Trip {{Tasks:836}} B14 X 1.6.2: 10189: Minesweeper {{Tasks:835}} B15 X 1.6.1: 100: 3n + 1 {{Tasks:834}} C1 X 109: Scud Busters C2 X 108: Maximum Sum C3 X 107: The Cat in the Hat C4 X 106: Fermat vs. Pythagoras C5 X 105: The Skyline Problem C6 X 104: Arbitrage C7 X 103: Stacking Boxes C8 X 102: Ecological Bin Packing C9 X 101: The Blocks Problem C10 X 100: 3n + 1

## Notes

### 6. ACM training again (2005.09.13:2)

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)

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...

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

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

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

Grrrr, not reading specs well enough...

### 2. Dropped to 8579 (2004.04.06:2)

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...

### 1. ACM status (2004.04.06:1)

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

### Scratch

 199 partial differential equations don't really feel like solving this right now 198 peter's calculator store the declarations in a vector, then have a method evaluate variables or throw an exception 197 cube brute force, then check if rotated already? 196 spreadsheet easy 195 anagram straightforward lexicographic non-repeating permutation 194 triangle relatively straightforward mathematics 193 graph coloring a 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. 192 synchronous design look for cycles, check for delays. can find cycles when calculating delays. Start with nodes directly connected to input, have time associated with each node. 191 intersection straightforward 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. 190 circle through three points find the point of intersection of two normals at the halfway point. 189 pascal program lengths just tokenize properly. stream? 188 perfect hash haven'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.)

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: