302 - John's trip

[GuAlex]

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?

[Adrian Kuegel]

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]

How could I get a sequence of street numbers is lexicographically the smallest ?

[dabendan]

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]

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]

If I use brutal force , I'll get TLE.
If you succeed, please give me a hint.
thanks a lot.

[titid_gede]

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

[jamu]

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]

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]

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?

[artem]

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]

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]

Thank you mf for answer.

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]

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]

Thank you very much mf.
I got AC.
If you have questions about this problems http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:50323 I help you