Search found 11 matches

by Krzysztof Sikora
Sat Sep 28, 2002 11:30 pm
Forum: Volume 100 (10000-10099)
Topic: 10037 - Bridge
Replies: 84
Views: 23411

I have algorithm like LittleJohn. My program pass all Waterloo tests. I know that one test has more then n people. I tried three ways: 1. read n for i = 1 to n read human read line until empty line 2. read integer (n, dummy line) n = 0 read human; n++; until empty line 3. specification All three met...
by Krzysztof Sikora
Thu Sep 26, 2002 11:40 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously? Because if #fs = 0 then for all vertex dist. from firestation to it was infinity and '1' was written and ...
by Krzysztof Sikora
Wed Sep 25, 2002 2:38 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

OK. Output belongs to Even is correct. At last I've got ACCEPTED. My algorithm is almost good. It produced bad solutions for m = 0. For this case you can find solution in time O(E) and overall O(ElogV). In spite of that, my program has O(VElogV) complexity because there was less modification to crea...
by Krzysztof Sikora
Wed Sep 25, 2002 11:39 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

My program write the same output. But I'm given WA.
by Krzysztof Sikora
Tue Sep 24, 2002 9:58 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

Output:

Code: Select all

1

1
Warning. My program is not ACCEPTED.
by Krzysztof Sikora
Sat Sep 21, 2002 3:33 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

Sorry, no lowest but highest. Find max in array of dist. Normally we use Dijksta with one vertex (source) and dist for this vertex is 0. In this case we use Dijkstra with a set (set of firestations) and for all vertex from this set dist is 0. Now you must launch Dijksta. After it max := -1; for all ...
by Krzysztof Sikora
Sat Sep 21, 2002 11:05 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

To Hongping.

You needn't iterate through all possible intersection.
Initially, you can put all firestations to heap and run Dijkstra.
Than find the intersection with the lowest distance.
Time Complexity O(E*logV).
by Krzysztof Sikora
Sat Sep 21, 2002 11:00 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

2 2
1
2
my output is 1.
by Krzysztof Sikora
Sat Sep 21, 2002 9:57 am
Forum: Volume 102 (10200-10299)
Topic: 10212 - The Last Non-zero Digit.
Replies: 63
Views: 30474

Let l = length of N = O(log(N))
The complexity of this your algorithm is O(N) = O(10^l). :-?
by Krzysztof Sikora
Mon Sep 02, 2002 11:45 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.
by Krzysztof Sikora
Mon Sep 02, 2002 4:48 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

10278 - Fire Station

I solved this problem but I got WA.
I used Dijkstra and set all cities with fire station on 0, others on infinity.
Could you help me? Maybe a trick?

Go to advanced search