015. Subway System

Codeforces

IDCF10269015

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You're going to a large city with a complex subway system. You need to find out how many subway lines you will take from the airport to your hotel. Given a list of stations that each subway line stops at, print the minimum number of lines you need to take to get from the airport to your hotel. The first lines contains one integer _n_, representing the number of different lines in the subway. The next _n_ lines contain an arbitrary number of space-separated strings, each representing the various stations that the subway lines stop at. The airport's station will be _Airport_ in the station list, and the hotel's station will be _Hotel_. There will not be more than 1000 distinct station names. Output one positive integer _l_: the minimal number of different subway lines that you should take to reach the hotel station from the airport station. A note from the creator of the problem (Xavier): This problem is _really_ hard. I created the problem and it took me over an hour to come up with a valid solution. Please only attempt this problem if you know what you're doing. ## Input The first lines contains one integer _n_, representing the number of different lines in the subway. The next _n_ lines contain an arbitrary number of space-separated strings, each representing the various stations that the subway lines stop at. The airport's station will be _Airport_ in the station list, and the hotel's station will be _Hotel_. There will not be more than 1000 distinct station names. ## Output Output one positive integer _l_: the minimal number of different subway lines that you should take to reach the hotel station from the airport station. [samples] ## Note A note from the creator of the problem (Xavier): This problem is _really_ hard. I created the problem and it took me over an hour to come up with a valid solution. Please only attempt this problem if you know what you're doing.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of subway lines. Let $ L_1, L_2, \dots, L_n \subseteq S $ be the sets of stations for each line, where $ S $ is the finite set of all station names, and $ \text{Airport}, \text{Hotel} \in S $. **Constraints** - $ |S| \leq 1000 $ - $ \text{Airport} \in \bigcup_{i=1}^n L_i $, $ \text{Hotel} \in \bigcup_{i=1}^n L_i $ **Objective** Find the minimum number of lines $ l \in \mathbb{Z}^+ $ such that there exists a sequence of lines $ L_{i_1}, L_{i_2}, \dots, L_{i_l} $ satisfying: - $ \text{Airport} \in L_{i_1} $, - $ \text{Hotel} \in L_{i_l} $, - $ L_{i_j} \cap L_{i_{j+1}} \neq \emptyset $ for all $ j \in \{1, \dots, l-1\} $. Output $ l $.

API Response (JSON)

{
  "problem": {
    "name": "015. Subway System",
    "description": {
      "content": "You're going to a large city with a complex subway system. You need to find out how many subway lines you will take from the airport to your hotel. Given a list of stations that each subway line stops",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269015"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're going to a large city with a complex subway system. You need to find out how many subway lines you will take from the airport to your hotel. Given a list of stations that each subway line stops...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of subway lines.  \nLet $ L_1, L_2, \\dots, L_n \\subseteq S $ be the sets of stations for each line, where $ S $ is the finite set of all stati...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments