Page 1 of 2
302 - John's trip
Posted: Mon Aug 26, 2002 12:33 pm
by 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?
Posted: Sun Sep 15, 2002 1:39 am
by 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
Posted: Fri Nov 01, 2002 7:31 pm
by dabendan
How could I get a sequence of street numbers is lexicographically the smallest ?
302 john's trip
Posted: Thu Nov 21, 2002 2:15 am
by dabendan
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
like this?
Posted: Fri Nov 22, 2002 10:31 am
by 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
Posted: Wed Nov 27, 2002 10:23 am
by dabendan
If I use brutal force , I'll get TLE.
If you succeed, please give me a hint.
thanks a lot.
302 - John Trip
Posted: Wed Oct 22, 2003 10:58 am
by 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
302 (John's trip) test cases
Posted: Wed Dec 03, 2003 11:41 am
by 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
Posted: Mon Dec 08, 2003 7:29 pm
by 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
Posted: Sun Jan 18, 2004 9:12 pm
by 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?
Problem 302
Posted: Tue Aug 30, 2005 4:37 pm
by 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
Posted: Tue Aug 30, 2005 5:38 pm
by 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
Posted: Tue Aug 30, 2005 7:59 pm
by 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?
Posted: Tue Aug 30, 2005 9:47 pm
by 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.
Posted: Tue Aug 30, 2005 10:36 pm
by 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