NEW: For a prettier blog interface, see the Wordpress version!
Tasks
| A1 | X | Read http://www.javaalmanac.com (2002.11.28) |
| A2 | X | Retrieve my password (2002.11.28) |
| A3 | X | Set up the ACM problem set archives (2002.11.28) |
| A4 | X | Install J2SDK 1.4.0 and get it working (2002.11.28) |
| B | X | E-mail igor@cs.utoronto.ca and check out http://www.cs.toronto.edu/~igor/acm/next.html (2005.09.16) |
| B | C | @1030-1600 Attend ACM programming tryouts at BA3175 (2005.09.17) |
| B1 | C | Contest Scoreboard {{Tasks:848}} (2004.04.26) |
| B2 | C | Jolly Jumpers {{Tasks:842}} {{Schedule:20:00-21:00}} (2004.04.26) |
| B3 | C | Hartals {{Tasks:844}} {{Schedule:21:00-21:30}} (2004.04.26) |
| B4 | C | Crypt Kicker {{Tasks:845}} {{Schedule:21:30-22:00}} (2004.04.26) |
| B5 | C | Stack 'em Up {{Tasks:846}} {{Schedule:22:00-22:30}} (2004.04.26) |
| B6 | C | Erdos Numbers {{Tasks:847}} {{Schedule:22:30-23:00}} (2004.04.26) |
| B7 | C | Poker Hands {{Tasks:843}} (2004.04.26) |
| B8 | C | Yahtzee {{Tasks:849}} (2004.04.26) |
| A5 | X | Solve 198: Peter's calculator {{Tasks:58}} (2003.11.15) |
| B16 | X | 1.6.8: 10142: Australian voting {{Tasks:841}} (2004.04.07) |
| B17 | X | Solve chapter 1 ACM problems {{Tasks:831}} (2004.04.07) |
| B9 | X | 1.6.7: 10196: Check the check {{Tasks:840}} (2004.04.06) |
| B10 | X | 1.6.6: 10033: Interpreter {{Tasks:839}} (2004.04.06) |
| B11 | X | 1.6.5: 10267: Graphical editor {{Tasks:838}} (2004.04.06) |
| B12 | X | 1.6.4: 706: LCD Display {{Tasks:837}} (2004.04.06) |
| B13 | X | 1.6.3: 10137: The Trip {{Tasks:836}} (2004.04.06) |
| B14 | X | 1.6.2: 10189: Minesweeper {{Tasks:835}} (2004.04.06) |
| B15 | X | 1.6.1: 100: 3n + 1 {{Tasks:834}} (2004.04.06) |
| C1 | X | 109: Scud Busters (2002.11.28) |
| C2 | X | 108: Maximum Sum (2002.11.28) |
| C3 | X | 107: The Cat in the Hat (2002.11.28) |
| C4 | X | 106: Fermat vs. Pythagoras (2002.11.28) |
| C5 | X | 105: The Skyline Problem (2002.11.28) |
| C6 | X | 104: Arbitrage (2002.11.28) |
| C7 | X | 103: Stacking Boxes (2002.11.28) |
| C8 | X | 102: Ecological Bin Packing (2002.11.28) |
| C9 | X | 101: The Blocks Problem (2002.11.28) |
| C10 | X | 100: 3n + 1 (2002.11.28) |
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...
E-Mail from Valladolid Online Judge
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.
Training
- http://curry.ateneo.net/acm-icpc/
- http://curry.ateneo.net/acm-icpc/prob71a.html
- http://curry.ateneo.net/acm-icpc/prob71b.html
- http://curry.ateneo.net/acm-icpc/prob71c.html
- http://curry.ateneo.net/acm-icpc/prob71d.html
- http://curry.ateneo.net/acm-icpc/prob71e.html
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 sacha@sachachua.com .
