## Search found 63 matches

Sat Oct 26, 2002 5:57 pm
Forum: Volume 103 (10300-10399)
Topic: 10391 - Compound Words
Replies: 40
Views: 16946
I think the main problem is the time limit. If you get WA, it's probably better to briefly describe your algorithm here. We might then be able to discuss and post some counterexamples.
Mon Sep 30, 2002 11:07 am
Forum: Volume 1 (100-199)
Topic: 193 - Graph Coloring
Replies: 93
Views: 20543

### 193 - Graph Coloring

Hello, I tried to solve 193 (and got AC in 0.01s), but I'm using some kind of probabilistic approach: I randomly select a node, remove it and its neighbours until there are no nodes left. I repeat this several times (100 is enough) to get the maximum node count. I know that this problem (Maximum Ind...
Tue Jul 30, 2002 12:23 pm
Forum: Volume 103 (10300-10399)
Topic: 10339 - Watching Watches
Replies: 10
Views: 2992
Thank you, got AC.

The wrong formula was a typing mistake in my post.

The main problem really was the rounding error! Stupid mistake.
Tue Jul 30, 2002 9:40 am
Forum: Volume 103 (10300-10399)
Topic: 10339 - Watching Watches
Replies: 10
Views: 2992

### 10339 - Watching Watches

Hello! Problem 10339 seems tricky to me. My idea to solve it was: When a (real) day has passed, the k-watch has counted (86400-k) seconds. The same holds for the m-watch and (86400-m) seconds. I calculate the number of (real) days, when the time difference between the two watches becomes 12 hours (4...
Tue Jul 30, 2002 8:41 am
Forum: Volume 103 (10300-10399)
Topic: 10338 - Mischievous Children
Replies: 56
Views: 19819
Just precalculate and store the factorials in an array. I'm using the same algorithm and get AC in 0.210 seconds.
Mon Jul 15, 2002 12:52 am
Forum: Volume 6 (600-699)
Topic: 615 - Is It A Tree?
Replies: 71
Views: 22873

1 2 2 3 3 1 4 5 0 0

it should be "not a tree". Such cases were a topic in the old message board long ago.

I don't know if there is any limit for the node numbers (except the limits of "integer"), so I stored the numbers in another array and did two lookups on every edge.
Sun Jul 14, 2002 2:52 pm
Forum: Volume 103 (10300-10399)
Topic: 10325 - The Lottery
Replies: 14
Views: 5816
Hi, I did it the following way: - set the initial "result" value to n. - compute the lcm of every subset of divisors (except the empty one) - if the size of a subset it odd, subtract n/lcm from "result" - if it is even, add n/lcm to "result" Those operations can be done in an iteration loop, doing s...
Fri Jul 05, 2002 11:15 am
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19059
Thank you!
Tue Jul 02, 2002 12:54 pm
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19059
Your algorithm seems quite correct to me, but I think there are some critical points:

In how many ways can 0\$ be made up by 0 coins? 0 or 1?
In how many ways can more than 0\$ be made up by 0 coins? 0 or 1?
Tue Jun 18, 2002 3:21 pm
Forum: Volume 8 (800-899)
Topic: 851 - Maze
Replies: 35
Views: 16368
The locations which are considered as "escaped" are those you marked with "A":

Code: Select all

``````  OOAO
A..O
OO.A
OAAO

``````
Tue Jun 18, 2002 12:00 pm
Forum: Volume 8 (800-899)
Topic: 851 - Maze
Replies: 35
Views: 16368
You may always change direction after moving one field.
Thu Jun 13, 2002 1:40 am
Forum: Volume 2 (200-299)
Topic: 208 - Firetruck
Replies: 48
Views: 14677
http://www.acm.inf.ethz.ch/ProblemSetAr ... 1/acm91a.c

This is the "official" backtracking solution, which should make the output format clearer, but don't try it on Valladolid, it gets TLE.
Thu Jun 13, 2002 12:39 am
Forum: Volume 103 (10300-10399)
Topic: 10303 - How Many Trees?
Replies: 19
Views: 3055

### 10303 - How Many Trees?

After the input limit was set to 1000, I got some time problems, and - with BigNum and DP - I currently reach about 21 seconds. I'm using a sum of products to find the number. My question:

Is there an explicit formula to calculate those numbers?
Sat Apr 27, 2002 10:30 pm
Forum: Volume 2 (200-299)
Topic: 288 - Arithmetic Operations With Large Integers
Replies: 14
Views: 5996
I finally got AC - forgot to reset the sign flag in multiplication...

Thanks for the inspiration...
Sat Apr 27, 2002 8:43 pm
Forum: Volume 2 (200-299)
Topic: 288 - Arithmetic Operations With Large Integers
Replies: 14
Views: 5996

### 288 - Arithmetic Operations With Large Integers

Hello World, I tried to get AC for that one several times, but no way... I'm currently using term splitting, scanning for "+" and "-" from the right (they associate left), afterwards for "*" from the right (dito) and for "**" (which I replaced before) from the left (right associative). I'm then call...