Search found 18 matches

by dispanser
Mon Sep 26, 2005 7:29 pm
Forum: Volume 109 (10900-10999)
Topic: 10902 - Pick-up Sticks
Replies: 24
Views: 13308

My idea of removing segments is of course only correct if I process them in the input order, which may not work for the n log n + k algorithm (I don't know how it works). hm... it's a sweepline algorithm where your event points are in increasing order along some line (like x-axis)... I can't possib...
by dispanser
Mon Sep 26, 2005 6:28 pm
Forum: Volume 109 (10900-10999)
Topic: 10902 - Pick-up Sticks
Replies: 24
Views: 13308

Read it more carefully, the worst case is actually (n+k)log n (page 8 ) - there is also a reference to an algorithm that is k + n log n. These are both *worse* in the worst case than n^2 (k is already in n^2), furthermore for this problem it seems that the algorithm needs to be chosen according to ...
by dispanser
Sun Sep 25, 2005 4:25 pm
Forum: Volume 109 (10900-10999)
Topic: 10901 - Ferry Loading III
Replies: 54
Views: 23208

Re: 10901(Ferry Loading III) I am getting Wrong Answer

Please give me some Sample Input And Output For this Problem. did you read the other thread? try this input; cars can leave earlier even though they arrived later than other cars... input: 1 3 5 7 0 left 1 left 2 left 3 left 5 left 5 right 11 right output: 5 15 15 15 25 10 20 as a side note, the ot...
by dispanser
Sat Sep 24, 2005 10:36 pm
Forum: Volume 109 (10900-10999)
Topic: 10901 - Ferry Loading III
Replies: 54
Views: 23208

Why do you believe that is not the case? i inserted all arrival times into a set. i checked wether the size of the set is equal to m (number of cars). that test failed. so the input contained different cars with equal arrival time. which, from my understanding, contradicts the problem statement. Yo...
by dispanser
Sat Sep 24, 2005 4:53 am
Forum: Volume 109 (10900-10999)
Topic: 10901 - Ferry Loading III
Replies: 54
Views: 23208

Why do you believe that is not the case? i inserted all arrival times into a set. i checked wether the size of the set is equal to m (number of cars). that test failed. so the input contained different cars with equal arrival time. which, from my understanding, contradicts the problem statement. By...
by dispanser
Fri Sep 23, 2005 11:47 pm
Forum: Volume 109 (10900-10999)
Topic: 10901 - Ferry Loading III
Replies: 54
Views: 23208

10901 - Ferry Loading III

According to the problem statement for Ferry Loading III: The arrival times for each test case are strictly increasing. for me "strictly increasing" means that each car arrives at a unique time. Obviously, that is not the case... Am i just reading this wrong or should the problem statement get chang...
by dispanser
Mon Aug 08, 2005 11:58 pm
Forum: Volume 108 (10800-10899)
Topic: 10891 - Game of Sum
Replies: 33
Views: 12618

cool. I couldn't figure that test case out until reading this thread. However, my program got AC during the contest. That's the magic about dynamic programming. You don't know what it does, but it eventually solves all your problems.
by dispanser
Mon Mar 07, 2005 11:48 am
Forum: Volume 108 (10800-10899)
Topic: 10802 - Lex Smallest Drive
Replies: 36
Views: 14701

Because "0 3 4 5 3 0 6 7 8 6" can loop. 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 9 is smaller than 0 4 3 5 3 0 6 7 8 6 9. And 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 9 is smaller. And ....... Can't define Smallest drive. ah now i see it... being at vertex 3, it's lex smaller to go to vertex 0, b...
by dispanser
Mon Mar 07, 2005 8:44 am
Forum: Volume 108 (10800-10899)
Topic: 10802 - Lex Smallest Drive
Replies: 36
Views: 14701

1 10 11 0 0 1 1 2 0 3 3 4 4 5 5 3 0 6 6 7 7 8 8 6 0 9 and, my output. Case #1: 0 0 1 0 1 2 0 3 0 3 4 0 3 4 5 0 3 4 5 3 0 6 0 3 4 5 3 0 6 7 0 3 4 5 3 0 6 7 8 No drive. is this correct? according to the problem setter, this is a correct solution. Even after reading the complete thread i still fail to...
by dispanser
Thu Oct 21, 2004 8:40 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17175

i can assure you that the solution only considering proper supersets gets accepted; my running time is appr. 100x slower than yours, though :evil: .
by dispanser
Wed Oct 20, 2004 5:47 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17175

Re: Bah

P.S. for those that still do not understand the problem statement, here is a simplified version: Given strings A and B. B dominates A if BOTH conditions below are satisfied: - Every distinct character in A also appears in B - Any character that appears multiple times in A must appear at least that ...
by dispanser
Thu Oct 07, 2004 6:51 pm
Forum: Volume 101 (10100-10199)
Topic: 10142 - Australian Voting
Replies: 82
Views: 30403

i believe the input is flawed, the description says something like: Up to 1000 lines follow; each contains the contents of a ballot. That is, each contains the numbers from 1 to n in some order. The first number indicates the candidate of first choice; the second number indicates candidate of second...
by dispanser
Sat Sep 04, 2004 2:44 pm
Forum: Volume 106 (10600-10699)
Topic: 10608 - Friends
Replies: 75
Views: 26784

the following code ends with a sigsegv. it's just reading the input. TC refers to the number of testcases, nC is the number of citizen, nP is the number of Pairs of input. i can't see a flaw in it. i know a adjacency matrix is not clever and will give TLE, but at least it should not fail! while(TC--...
by dispanser
Wed Jul 23, 2003 9:25 am
Forum: Volume 103 (10300-10399)
Topic: 10397 - Connect the Campus
Replies: 75
Views: 25756

well i am also a sufferer, does the picture f the problem indicate anything important, If it does they please post the picture here. Because it is not available in the site..; Please post the pictures. :oops: :oops: the picture is absolutely not important. you can see a few buildings from far away,...
by dispanser
Tue Jul 22, 2003 6:06 pm
Forum: Volume 103 (10300-10399)
Topic: 10334 - Ray Through Glasses
Replies: 19
Views: 8591

Accepted

:lol:

Go to advanced search