Search found 519 matches

Fri Mar 17, 2006 4:56 am
Forum: Volume 2 (200-299)
Topic: 204 - Robot Crash
Replies: 26
Views: 5777
That corresponds to minimizing the max time of the two robots at each intersection which is a collision. I got AC with it, so probably that's the correct interpretation.
Thu Mar 16, 2006 3:52 am
Forum: Volume 2 (200-299)
Topic: 203 - Running Lights Visibility Calculator
Replies: 22
Views: 5765
The judge is still pretty sensitive to floating point errors, I have to use long double to compute the bearing. But if I used long double for all calculations then I get WA. I only get AC if I only use long double to compute the bearing.
Wed Mar 15, 2006 2:56 am
Forum: Volume 6 (600-699)
Topic: 604 - The Boggle Game
Replies: 33
Views: 10124
you should generate the words in the first square and at the same time check to see if the square are adjacent. you can do that using dfs to do the backtracking. Then you generate words in the second square, and output only those that are found in first square. You can also use the number of vowels ...
Wed Mar 15, 2006 2:02 am
Forum: Volume 2 (200-299)
Topic: 245 - Uncompress
Replies: 40
Views: 9208
your code was way too long to read. It can definitely be done in less than 40 lines of code.
Wed Mar 15, 2006 1:28 am
Forum: Volume 2 (200-299)
Topic: 296 - Safebreaker
Replies: 13
Views: 3574
I don't know if it can be solved other than brute force.
Tue Mar 14, 2006 11:13 pm
Forum: Volume 110 (11000-11099)
Topic: 11000 - Bee
Replies: 25
Views: 12274
This problem is supposed to be trivial, we don't even need big int
Tue Mar 14, 2006 11:10 pm
Forum: Volume 2 (200-299)
Topic: 220 - Othello
Replies: 9
Views: 5627
My advice is to try to recode it until it is less than 80 lines. It too easy to make mistakes in long code.
Tue Mar 14, 2006 9:44 pm
Forum: Volume 101 (10100-10199)
Topic: 10132 - File Fragmentation
Replies: 24
Views: 11340
what should be done in case there is no possible solution or there is not an even number of lines in the input? such cases do not exist. Also the only allowed characters in the file are '0' and '1'. All the fragments are nonempty, and there are always at least one solutions. Therefore some kind of ...
Sun Mar 12, 2006 2:00 am
Forum: Volume 110 (11000-11099)
Topic: 11002 - Towards Zero
Replies: 39
Views: 17789
I think you can use a bound to figure out which values to dp on and which to simply return 0. That took off about 2 secs off my solution. These kind of optimization that is often used in backtracking problems might work here.
Fri Mar 10, 2006 2:49 am
Forum: Volume 110 (11000-11099)
Topic: 11010 - Tic-Tac-Tough
Replies: 20
Views: 7218
Johnny's ranking functions: (pick min score) 0,1 -> 0 -1,1 -> 1 0,-1 -> 2 1,1 -> 3 -1,-1 -> 4 0,0 -> 5 -1,0 -> 6 1,-1 -> 7 1,0 -> 8 ( a,b->c stands for if outcome a given mary starts, b given johnny starts, the ranking would be c; -1: tie, 1:johnny wins, 0:mary wins) i thoroughly misunderstood your...
Thu Mar 09, 2006 9:52 pm
Forum: Volume 110 (11000-11099)
Topic: 11010 - Tic-Tac-Tough
Replies: 20
Views: 7218
1. who starts the game will win the game : value = 1000 ; 2. the result of the game does not depend on who starts the game : value = 0 ; 3. if by starting the game player will get better score : value = 500 ; my ranking function for these are quite different from yours. I have 9 possible scores (si...
Thu Mar 09, 2006 8:27 pm
Forum: Volume 110 (11000-11099)
Topic: 11010 - Tic-Tac-Tough
Replies: 20
Views: 7218
dear sclo my algorithm is exactly as same as you explained first i calculate the final result of each board if john or mary start playing on that board ,then in the second stage for each player i choose the board that has the most advantage to him/herself and most disadvantage for his/her oponnent ...
Thu Mar 09, 2006 7:49 pm
Forum: Volume 110 (11000-11099)
Topic: 11007 - Mini Cube
Replies: 11
Views: 7394
Try searching from both initial and final state. The technique is called meet-in-the-middle. Let A[X] be distance from initial state to state X and B[X] be distance from final state to state X. If you can find some state X that is reachable from both initial and final state then you can get from in...
Thu Mar 09, 2006 7:23 pm
Forum: Volume 110 (11000-11099)
Topic: 11010 - Tic-Tac-Tough
Replies: 20
Views: 7218
It is possible to solve this using part greedy and part dp. For each board, use dp to determine the optimal outcome if mary starts, and if johnny starts. Think about why we can consider each board independently from the others, and why it doesn't really matter if a player temporarily has no board. A...
Thu Mar 09, 2006 7:18 pm
Forum: Volume 110 (11000-11099)
Topic: 11008 - Antimatter Ray Clearcutting
Replies: 81
Views: 39054
I believe that algorithm is O(n^2 * 2^n) but it can be improved to O(n * 2^n) with bitmasks. (actually it just replaced the constant with a smaller constant).