302 - John's trip

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

302 - John's trip

Post by GuAlex » Mon Aug 26, 2002 12:33 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Sep 15, 2002 1:39 am

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

Post by dabendan » Fri Nov 01, 2002 7:31 pm

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

Post by dabendan » Thu Nov 21, 2002 2:15 am

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?

Post by epsilon0 » Fri Nov 22, 2002 10:31 am

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

Post by dabendan » Wed Nov 27, 2002 10:23 am

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

302 - John Trip

Post by titid_gede » Wed Oct 22, 2003 10:58 am

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

Post by jamu » Wed Dec 03, 2003 11:41 am

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

Post by jamu » Mon Dec 08, 2003 7:29 pm

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
Location: Bangladesh

Post by Noim » Sun Jan 18, 2004 9:12 pm

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

Post by artem » Tue Aug 30, 2005 4:37 pm

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:

Post by mf » Tue Aug 30, 2005 5:38 pm

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

Post by artem » Tue Aug 30, 2005 7:59 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Aug 30, 2005 9:47 pm

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

Post by artem » Tue Aug 30, 2005 10:36 pm

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

Post Reply

Return to “Volume 3 (300-399)”