I'm collecting cool graph algorithms problems

noris · Post by **noris** » Thu Apr 22, 2004 9:40 pm

Hi,

I'm preparing a short talk about graph algorithm's problems.

Did you have a problem in which you didn't expect a graph problem behind, or which has a nice or cool solution (possibly for
teaching purposes)?

Many Thanks in advance!

playerX · Post by **playerX** » Thu Apr 22, 2004 10:12 pm

of course, immeadiatly I remember about 429 - Word Transformation, there are several others, I don't remember which ones :\

sumankar · Post by **sumankar** » Fri Apr 23, 2004 6:29 am

Well there is one I remember:439 Knight Moves
Its about finding shortest route
for a chess knight to take between
any two point on a standard chessboard or
something very similar

Hth,

Suman

Duy Hung · Post by **Duy Hung** » Fri Apr 23, 2004 3:45 pm

yes, and I suggest that U post some problem that can use graph to solve.....

Alexander Denisjuk · Post by **Alexander Denisjuk** » Tue May 04, 2004 10:04 am

Consider please:
10239 The Book-shelver's Problem (the shortest path)
10266 Surveying (connected components)
10265 Toroidal Chess Queens' Problem (tree rounds ???)
709 Formatting Text (the shortest path)

jagadish · Post by **jagadish** » Wed May 05, 2004 8:26 pm

here are some more..

280(vertex)
459,10147 ,10397 - connectivity
10178(count the faces)

Alessandro · Post by **Alessandro** » Fri Jun 18, 2004 12:06 am

I don't know if this problem is in the problem set, I did it during the selection for the IOI...

There are some cities, and streets between them. A station must be put in every street to control it, at the entrance at one of the city linked by that street. Every street need no more than one station.

For every street linking, e.g., city A and B, find if the station must be put at the entrance of city A or city B. You must minimize the difference between the city with the most stations at its entrances and the one with the smallest one. E.G., if city A has 4 stations and city E has 3 ones, the difference is 1.

It's a rare graph problem...

Goodbye

FAQ · Post by **FAQ** » Mon Jun 21, 2004 5:14 pm

Alessandro, Do you have its test data ?

Alessandro · Post by **Alessandro** » Mon Jun 21, 2004 10:36 pm

No. I met this problem at the last contest for the selection of the IOI italian ieam, and I don't think my trainers will release the test cases. I'm sorry...

Ciao

Pavl0 · Post by **Pavl0** » Thu Jul 29, 2004 9:28 am

10054 - euler problem , but j get WA

mlvahe · Post by **mlvahe** » Mon Aug 02, 2004 6:26 pm

USACO 5.5 Telecowmunication(But I don't know how to solve i

)

Farmer John's cows like to keep in touch via email so they have created a network of cowputers so that they can intercowmunicate. These machines route email so that if there exists a sequence of c cowputers a1, a2, ..., a(c) such that a1 is connected to a2, a2 is connected to a3, and so on then a1 and a(c) can send email to one another.

Unfortunately, a cow will occasionally step on a cowputer or Farmer John will drive over it, and the machine will stop working. This means that the cowputer can no longer route email, so connections to and from that cowputer are no longer usable.

Two cows are pondering the minimum number of these accidents that can occur before they can no longer use their two favorite cowputers to send email to each other. Write a program to calculate this minimal value for them, and to calculate a set of machines that corresponds to this minimum.

For example the network:

1*
/
3 - 2*
shows 3 cowputers connected with 2 lines. We want to send messages between 1 with 2. Direct lines connect 1-3 and 2-3. If cowputer 3 is down, them there is no way to get a message from 1 to 2.

PROGRAM NAME: telecow
INPUT FORMAT
Line 1
Four space-separated integers: N, M, c1, and c2. N is the number of computers (1 <= N <= 100), which are numbered 1..N. M is the number of connections between pairs of cowputers (1 <= M <= 600). The last two numbers, c1 and c2, are the id numbers of the cowputers that the questioning cows are using. Each connection is unique and bidirectional (if c1 is connected to c2, then c2 is connected to c1). There can be at most one wire between any two given cowputers. Computer c1 and c2 will not have a direction connection.

Lines 2..M+1
The subsequent M lines contain pairs of cowputers id numbers that have connections between them.

SAMPLE INPUT (file telecow.in)
3 2 1 2
1 3
2 3
OUTPUT FORMAT
Generate two lines of output. The first line is the minimum number of connections that can be down before terminals c1 & c2 are no longer connected. The second line is a minimal-length sorted list of cowputers that will cause c1 & c2 to no longer be connected. Note that neither c1 nor c2 can go down. In case of ties, the program should output the set of computers that, if interpreted as a base N number, is the smallest one.

SAMPLE OUTPUT (file telecow.out)
1
3

Malcolm · Post by **Malcolm** » Mon Nov 01, 2004 6:32 pm

Alexander Denisjuk wrote:Consider please:
10239 The Book-shelver's Problem (the shortest path)
10266 Surveying (connected components)
709 Formatting Text (the shortest path)

Could you give me some hints about those problems?

I got AC on other problems in this thread, but I have exactly no idea about the three you listed.

bugzpodder · Post by **bugzpodder** » Tue Nov 02, 2004 11:10 pm

117
125
793
10608
20731

and those annoying questions with all possible 4 letter combinations of {a,b,c,d} appears once in a string
like
aaaabaaac etc

backslash null · Post by **backslash null** » Wed Nov 10, 2004 2:23 pm

here is a usefull like to both graph algos and examples of each algo:

http://www.comp.nus.edu.sg/~stevenha/pr ... raph1.html

good luck in ur talk:)

OJ Board

I'm collecting cool graph algorithms problems

I'm collecting cool graph algorithms problems

Hi:Graph Probleems

hi