## 302 - John's trip

Moderator: Board moderators

GuAlex
New poster
Posts: 1
Joined: Tue Jul 23, 2002 8:04 am
Location: Russia

### 302 - John's trip

Please, help me understand problem text.

Where John live?

In poblem text:
Johnny lives at the _junction_ ending the 1st street input with smaller number.

In clarification:
John lives in the 1st _street_ input.

What first junction/street in John's path?

What mean phrase
"...[path] when written down as a sequence of street numbers is lexicographically the smallest." ?

What right order for street 20 100 3?
100 20 3 or
3 20 100

If only one street in input what should output?
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
The first street you are reading is the street where john lives.
Example input:
3 1 6
1 2 1
2 3 2
2 4 3
4 5 4
5 2 5
5 3 9
5 6 7
6 3 8
0 0
1 1 1
0 0
0 0
john lives in street 3 1 at junction 1. Output should be:
1 2 8 7 4 3 5 9 6

1
dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC
How could I get a sequence of street numbers is lexicographically the smallest ?
dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC

### 302 john's trip

Adrian Kuegel wrote:The first street you are reading is the street where john lives.
Example input:
3 1 6
1 2 1
2 3 2
2 4 3
4 5 4
5 2 5
5 3 9
5 6 7
6 3 8
0 0
1 1 1
0 0
0 0
john lives in street 3 1 at junction 1. Output should be:
1 2 8 7 4 3 5 9 6

1
How could I get a sequence of street numbers is lexicographically the smallest since I could use brutal force?
I always got 1 3 4 5 2 8 7 9 6
epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### like this?

since you use a "brute force" (i'd rather call it depth first exploration) all you have to do is test all the possibilities in the correct order, the first solution you find is the good one.

if you can take sreets i or j, and i<j, try to take street i first, if it fails, fall back to street j, etc...

this problem seems interesting (although still another graph pb), i might give it a try, if i succeed i'll give ya insights
dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC
If I use brutal force , I'll get TLE.
If you succeed, please give me a hint.
thanks a lot.
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### 302 - John Trip

hi,
can anyone provide me sample input/output?
i thought this is euler cycle problem. since the output must be lexicography street name first, from start, i search for the biggest street name, and so on.. (just like finding euler cycle as usual). but got WA in 5 sec.
thanks before

regards,

titid gede
Kalo mau kaya, buat apa sekolah?
jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am

### 302 (John's trip) test cases

Hi, is something wrong with my program's output for this input?

input:

2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
1 2 16
2 1 21
1 4 12
4 1 15
1 3 10
1 3 11
3 1 17
3 1 19
3 2 2
2 3 4
2 7 1
2 7 3
3 7 23
5 7 22
5 3 20
3 4 5
3 4 7
4 6 8
6 4 14
1 1 24
4 4 25
4 4 26
5 6 6
6 5 9
7 6 13
7 6 18
9 1 27
9 9 30
9 8 32
8 8 28
8 8 29
8 8 34
8 10 31
10 4 35
10 10 33
1 8 36
4 8 37
0 0
0 0

my program's output:

1 3 4 7 15 8 5 14 6 9 10 11 17 12 13 2 16

1 2 6 7 8 3 4 5

Round trip does not exist.

1 3 2 4 16 10 5 7 11 12 8 6 9 13 18 14 15 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36 21
jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am
above output is incorrect, and this is correct:

correct output:

1 16 2 3 4 9 10 11 17 12 13 6 14 5 7 15 8

1 2 6 7 8 3 4 5

Round trip does not exist.

10 2 1 3 4 5 7 11 12 8 6 9 13 18 14 15 16 21 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36
Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
you can check John's home in your code. [ at first look, i can't get John's home correctly].

you wrote:
i thought this is euler cycle problem. since the output must be lexicography street name first, from start, i search for the
biggest street
name, and so on..

why biggest? shouldn't you search for smallest?
__nOi.m....
artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

### Problem 302

I got WA many times.
Is my output for this test case is correct?

Code: Select all

``````2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
1 2 16
2 1 21
1 4 12
4 1 15
1 3 10
1 3 11
3 1 17
3 1 19
3 2 2
2 3 4
2 7 1
2 7 3
3 7 23
5 7 22
5 3 20
3 4 5
3 4 7
4 6 8
6 4 14
1 1 24
4 4 25
4 4 26
5 6 6
6 5 9
7 6 13
7 6 18
9 1 27
9 9 30
9 8 32
8 8 28
8 8 29
8 8 34
8 10 31
10 4 35
10 10 33
1 8 36
4 8 37
0 0
0 0
``````

Code: Select all

``````1 16 2 13 10 11 12 17 9 3 4 6 14 5 7 15 8

1 2 6 7 8 3 4 5

Round trip does not exist.

10 11 12 14 13 1 16 15 25 26 35 33 31 28 29 32 30 27 17 19 21 2 20 22 18 6 9 8 5 23 3 4 7 37 34 36 24

``````
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Correct output:

Code: Select all

``````1 16 2 3 4 9 10 11 17 12 13 6 14 5 7 15 8

1 2 6 7 8 3 4 5

Round trip does not exist.

10 2 1 3 4 5 7 11 12 8 6 9 13 18 14 15 16 21 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36
``````
artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

But why?

1 16 2 13 10 11 12 17 9 3 4 6 14 5 7 15 8

lexicographically smaller than

1 16 2 3 4 9 10 11 17 12 13 6 14 5 7 15 8.

If this sentence "... which finds the desired shortest round trip" means, that the path must have the smallest number of junction?
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Ignore the word "shortest." You need just to find the lexicographically smallest sequence, which represents any valid round-trip.
In this problem, a sequence {x_i} is smaller than {y_i}, if there exist j, such that x_i=y_i for all i<j, and x_j<y_j.
artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm
Thank you very much mf.
I got AC.