Search found 63 matches

by Christian Schuster
Sat Oct 26, 2002 5:57 pm
Forum: Volume 103 (10300-10399)
Topic: 10391 - Compound Words
Replies: 40
Views: 17383

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.
by Christian Schuster
Mon Sep 30, 2002 11:07 am
Forum: Volume 1 (100-199)
Topic: 193 - Graph Coloring
Replies: 93
Views: 21246

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...
by Christian Schuster
Tue Jul 30, 2002 12:23 pm
Forum: Volume 103 (10300-10399)
Topic: 10339 - Watching Watches
Replies: 10
Views: 3095

Thank you, got AC.

The wrong formula was a typing mistake in my post. :oops:

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

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...
by Christian Schuster
Tue Jul 30, 2002 8:41 am
Forum: Volume 103 (10300-10399)
Topic: 10338 - Mischievous Children
Replies: 56
Views: 20292

Just precalculate and store the factorials in an array. I'm using the same algorithm and get AC in 0.210 seconds.
by Christian Schuster
Mon Jul 15, 2002 12:52 am
Forum: Volume 6 (600-699)
Topic: 615 - Is It A Tree?
Replies: 71
Views: 23458

What is your output for

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.
by Christian Schuster
Sun Jul 14, 2002 2:52 pm
Forum: Volume 103 (10300-10399)
Topic: 10325 - The Lottery
Replies: 14
Views: 5998

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...
by Christian Schuster
Fri Jul 05, 2002 11:15 am
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19409

Thank you! :)
by Christian Schuster
Tue Jul 02, 2002 12:54 pm
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19409

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?
by Christian Schuster
Tue Jun 18, 2002 3:21 pm
Forum: Volume 8 (800-899)
Topic: 851 - Maze
Replies: 35
Views: 16525

The locations which are considered as "escaped" are those you marked with "A":

Code: Select all

  OOAO
  A..O
  OO.A
  OAAO

by Christian Schuster
Tue Jun 18, 2002 12:00 pm
Forum: Volume 8 (800-899)
Topic: 851 - Maze
Replies: 35
Views: 16525

You may always change direction after moving one field.
by Christian Schuster
Thu Jun 13, 2002 1:40 am
Forum: Volume 2 (200-299)
Topic: 208 - Firetruck
Replies: 48
Views: 15165

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. :-?
by Christian Schuster
Thu Jun 13, 2002 12:39 am
Forum: Volume 103 (10300-10399)
Topic: 10303 - How Many Trees?
Replies: 19
Views: 3163

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?
by Christian Schuster
Sat Apr 27, 2002 10:30 pm
Forum: Volume 2 (200-299)
Topic: 288 - Arithmetic Operations With Large Integers
Replies: 14
Views: 6094

I finally got AC - forgot to reset the sign flag in multiplication... :-?

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

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

Go to advanced search