## Search found 18 matches

Mon Sep 26, 2005 7:29 pm
Forum: Volume 109 (10900-10999)
Topic: 10902 - Pick-up Sticks
Replies: 24
Views: 14008
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...
Mon Sep 26, 2005 6:28 pm
Forum: Volume 109 (10900-10999)
Topic: 10902 - Pick-up Sticks
Replies: 24
Views: 14008
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 ...
Sun Sep 25, 2005 4:25 pm
Forum: Volume 109 (10900-10999)
Replies: 54
Views: 24407

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...
Sat Sep 24, 2005 10:36 pm
Forum: Volume 109 (10900-10999)
Replies: 54
Views: 24407
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...
Sat Sep 24, 2005 4:53 am
Forum: Volume 109 (10900-10999)
Replies: 54
Views: 24407
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...
Fri Sep 23, 2005 11:47 pm
Forum: Volume 109 (10900-10999)
Replies: 54
Views: 24407

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...
Mon Aug 08, 2005 11:58 pm
Forum: Volume 108 (10800-10899)
Topic: 10891 - Game of Sum
Replies: 33
Views: 13668
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.
Mon Mar 07, 2005 11:48 am
Forum: Volume 108 (10800-10899)
Topic: 10802 - Lex Smallest Drive
Replies: 36
Views: 15394
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 v...
Mon Mar 07, 2005 8:44 am
Forum: Volume 108 (10800-10899)
Topic: 10802 - Lex Smallest Drive
Replies: 36
Views: 15394
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...
Thu Oct 21, 2004 8:40 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 18007
i can assure you that the solution only considering proper supersets gets accepted; my running time is appr. 100x slower than yours, though .
Wed Oct 20, 2004 5:47 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 18007

### 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 ...
Thu Oct 07, 2004 6:51 pm
Forum: Volume 101 (10100-10199)
Topic: 10142 - Australian Voting
Replies: 82
Views: 32897
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...
Sat Sep 04, 2004 2:44 pm
Forum: Volume 106 (10600-10699)
Topic: 10608 - Friends
Replies: 75
Views: 28668
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--...
Wed Jul 23, 2003 9:25 am
Forum: Volume 103 (10300-10399)
Topic: 10397 - Connect the Campus
Replies: 75
Views: 27643
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,...
Tue Jul 22, 2003 6:06 pm
Forum: Volume 103 (10300-10399)
Topic: 10334 - Ray Through Glasses
Replies: 19
Views: 9130
Accepted