Search found 44 matches

by kwedeer
Tue Aug 12, 2008 9:33 pm
Forum: Algorithms
Topic: Minimum set of nodes through which the eah path goes
Replies: 9
Views: 2649

Re: Minimum set of nodes through which the eah path goes

Hi, guys!. I guess I have found the right notions - the set under investigation is minimum vertex cut, see teh definition: http://www.nist.gov/dads/HTML/minvertexcut.html. Now I start to believe that success is really some 10% of talent and 90% of work and the latest portion includes some knowledge ...
by kwedeer
Tue Aug 12, 2008 4:17 pm
Forum: Algorithms
Topic: Minimum set of nodes through which the eah path goes
Replies: 9
Views: 2649

Re: Minimum set of nodes through which the eah path goes

OK - I am back to this very problem and I now I am considering the hypothesis, that this minimal set should be a graph cut - i.e. set of nodes, such, that if they are removed (each node of this set is split into two nodes and each part is given to subgraph with source and subgraph with target), then...
by kwedeer
Wed Jun 18, 2008 8:11 pm
Forum: Algorithms
Topic: Minimum set of nodes through which the eah path goes
Replies: 9
Views: 2649

Re: Minimum set of nodes through which the eah path goes

You are right about condition, that graph should be undirected. Well - I agree about bridges, but I would like to add, that finding the bridges is not enoug, the complete set should be union((send of endpoitns of bridges) and (articulation points)). E.g. the following graph shows why articulations p...
by kwedeer
Wed Jun 18, 2008 12:26 am
Forum: Algorithms
Topic: Minimum set of nodes through which the eah path goes
Replies: 9
Views: 2649

Re: Minimum set of nodes through which the eah path goes

OK - I started to implement the solution and my plan was - to find the strongly connected components SSC for the first instances. There is nice algorithm in Kormen for this: 1) one should make DFS for initial graph G and determin how the vortices are ordered according to time - say in some array f; ...
by kwedeer
Tue Jun 03, 2008 9:27 am
Forum: Algorithms
Topic: Minimum set of nodes through which the eah path goes
Replies: 9
Views: 2649

Minimum set of nodes through which the eah path goes

I am seeking for the following algorithm: The undirected graph G is given by list of edges, e.g. like 1-2, 2-3, 1-4,... and G has the S and T (source and target vortices, but as G is undirected graph, the they have only the follwing meaning - we sholud simply consider each path that can be from S to...
by kwedeer
Mon Sep 25, 2006 12:19 am
Forum: Off topic (General chit-chat)
Topic: Super Fast Programmer
Replies: 18
Views: 35107

to Vexorian 5 problems a day?!!! Seems almost impossible!!! :( I have fought with some dozen of problems almost half a year! And anyway - only half of them got accepted (the only satisfaction is that in all cases all of my solutions have agreement with test data, as they are usually provided in prob...
by kwedeer
Mon Sep 25, 2006 12:05 am
Forum: Volume 3 (300-399)
Topic: 380 - Call Forwarding
Replies: 3
Views: 3679

so - I have made my own code in Pascal - and got WA, although I have perfect agreement with the test case provided in the task. Can someone me provide the test case against which my code gives WA as it is executed by judge? So - as judge doesn't support TStringList and any serious map-type collectio...
by kwedeer
Sat Sep 23, 2006 7:29 pm
Forum: Volume 2 (200-299)
Topic: 245 - Uncompress
Replies: 40
Views: 9426

so - this is not direct reply for problem in the first post of thread - but - my usual request for help!!! So - here is my code - array pieces[...] contain the words to be exchanged by numbers in encryption/decription. No special collection (e.g. very nice Classes.TStringList) is used as Judge gives...
by kwedeer
Thu Sep 21, 2006 8:12 pm
Forum: Volume 5 (500-599)
Topic: 588 - Video Surveillance
Replies: 5
Views: 3227

Here is mine code in Pascal. My strategy was the following - I am assuming that the region where the camare can be located is perfect rectangle (can be described by 4 numbers - minx, maxx, miny, maxy) - initially - the full plane and then this rectangle is reduced with the each new wall and at the e...
by kwedeer
Sun Sep 17, 2006 4:57 pm
Forum: Other words
Topic: What 'memory limit exceed' means?
Replies: 2
Views: 3130

I have just discovered strange behavior (regarding the judge's decision of task mentioned in the first post): - so - judge shows memory 38000 and gives MLE but when running on oridnary platfrom then there is out of bound exception (for static array, Pascal) and small memory usage (this should be giv...
by kwedeer
Sun Sep 17, 2006 12:37 am
Forum: Other words
Topic: What 'memory limit exceed' means?
Replies: 2
Views: 3130

What 'memory limit exceed' means?

OK - I have this experience: my code is rejected with MLE by judge with the follwing results (taken from several runs): memory: 32900 - 37000, CPU: 0,6 - 0,676 (results are different for the code when it is executed more times) (as one can see from the list of accepted codes for the same task - then...
by kwedeer
Sun Sep 03, 2006 10:30 pm
Forum: Algorithms
Topic: algorithm to determine that polygon is star-shaped
Replies: 7
Views: 2820

I meant the following by 'outside of border': vertex of initial polygon that is no included on to the border of the constructed polygon. Namely, this vertex will be inside the border.
by kwedeer
Sun Sep 03, 2006 7:59 pm
Forum: Algorithms
Topic: algorithm to determine that polygon is star-shaped
Replies: 7
Views: 2820

now I have idea - simply collect all the vertices of polygon in on set and then try to construct the converx polygon from these vertices (using Graham scan or Jarvis march - both from Cormen algorithm book) and at the end check - if any vertex has been left outside the border of constructed convex p...
by kwedeer
Sat Sep 02, 2006 4:05 pm
Forum: Volume 103 (10300-10399)
Topic: 10330 - Power Transmission
Replies: 43
Views: 16338

OK - I have now got agreement with the test case provided in tasks and also - with the largest tests case provided in this thread - but - my program is still not accepted by judge - it give WA - so - I am posting my code and may some can execute it against some other judge test cases and provide the...
by kwedeer
Sat Sep 02, 2006 2:52 pm
Forum: Volume 6 (600-699)
Topic: 670 - The dog task
Replies: 16
Views: 8685

simply - the only thing that You need is the result of comparison - so - try to compare the squares instead of square-roots. btw - I have solution for the dog tasks which runs OK against tests cases given in task, but judge is giving WA, so - big please - can someone put some additional test cases f...

Go to advanced search