I've read this problem in the USACO Training Pages. Here's the problem description...
"You have just won a contest where the prize is a free vacation in Canada. You must travel via air, and the cities are ordered from east to west. In addition, according to the rules, you must start at the further city west, travel only east until you reach the furthest city east, and then fly only west until you reach your starting location. In addition, you may visit no city more than once (except the starting city, of course). Given the order of the cities, with the flights that can be done (you can only fly between certain cities, and just because you can fly from city A to city B does not mean you can fly the other direction), calculate the maximum number of cities you can visit."
USACO, itself suggests this solution to solve it:
"However, if, instead of trying to find the path as described, it is found a different manner, then the number of states greatly decreases. Imagine having two travelers who start in the western most city. The travelers take turns traveling east, where the next traveler to move is always the western-most, but the travelers may never be at the same city, unless it is either the first or the last city. However, one of the traveler is only allowed to make "reverse flights," where he can travel from city A to city B if and only if there is a flight from city B to city A. It's not too difficult to see that the paths of the two travelers can be combined to create a round-trip, by taking the normal traveler's path to the eastern-most city, and then taking the reverse of the other traveler's path back to the western-most city. Also, when traveler x is moved, you know that the traveler y has not yet visited any city east of traveler x except the city traveler y is current at, as otherwise traveler y must have moved once while x was west of y. Thus, the two traveler's paths are disjoint. Why this algorithm might yield the maximum number of cities is left as an exercise."
But I didn't get it!
Please describe this solution, or suggest another solution to solve.
I'm waiting for your answer. Thanks for your help!
USACO - Dynamic Programming
Let's talk about algorithms!
Moderator: Board moderators
-
- New poster
- Posts: 12
- Joined: Fri May 25, 2012 5:36 pm
Jump to
- Real Time Contests and Last Minute Information
- ↳ General
- ↳ Real Time Clarification
- ↳ Fixing Mistakes
- ↳ HOWTOs
- ↳ Bugs and suggestions
- New system
- ↳ FAQ
- ↳ Bugs and suggestions
- Let's make some programs!
- ↳ Other words
- ↳ Algorithms
- ↳ New features
- Help on the Problemset
- ↳ Volume 1 (100-199)
- ↳ Volume 2 (200-299)
- ↳ Volume 3 (300-399)
- ↳ Volume 4 (400-499)
- ↳ Volume 5 (500-599)
- ↳ Volume 6 (600-699)
- ↳ Volume 7 (700-799)
- ↳ Volume 8 (800-899)
- ↳ Volume 9 (900-999)
- ↳ Volume 10 (1000-1099)
- ↳ Volume 11 (1100-1199)
- ↳ Volume 12 (1200-1299)
- ↳ Volume 13 (1300-1399)
- ↳ Volume 14 (1400-1499)
- ↳ Volume 15 (1500-1599)
- ↳ Volume 16 (1600-1699)
- ↳ Volume 17 (1700-1799)
- ↳ Volume 100 (10000-10099)
- ↳ Volume 101 (10100-10199)
- ↳ Volume 102 (10200-10299)
- ↳ Volume 103 (10300-10399)
- ↳ Volume 104 (10400-10499)
- ↳ Volume 105 (10500-10599)
- ↳ Volume 106 (10600-10699)
- ↳ Volume 107 (10700-10799)
- ↳ Volume 108 (10800-10899)
- ↳ Volume 109 (10900-10999)
- ↳ Volume 110 (11000-11099)
- ↳ Volume 111 (11100-11199)
- ↳ Volume 112 (11200-11299)
- ↳ Volume 113 (11300-11399)
- ↳ Volume 114 (11400-11499)
- ↳ Volume 115 (11500-11599)
- ↳ Volume 116 (11600-11699)
- ↳ Volume 117 (11700-11799)
- ↳ Volume 118 (11800-11899)
- ↳ Volume 119 (11900-11999)
- ↳ Volume 120 (12000-12099)
- ↳ Volume 121 (12100-12199)
- ↳ Volume 122 (12200-12299)
- ↳ Volume 123 (12300-12399)
- ↳ Volume 124 (12400-12499)
- ↳ Volume 125 (12500-12599)
- ↳ Volume 126 (12600-12699)
- ↳ Volume 127 (12700-12799)
- ↳ Volume 128 (12800-12899)
- ↳ Volume 129 (12900-12999)
- ↳ Volume 130 (13000-13099)
- ↳ Volume 131 (13100-13199)
- Help on languages
- ↳ C
- ↳ C++
- ↳ Pascal
- ↳ Java
- Off Topic
- ↳ Off topic (General chit-chat)
- Category
- ↳ ACM ICPC Archive Board