11184 - Joyful Ride

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

Moderator: Board moderators

Post Reply
fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

11184 - Joyful Ride

Post by fpavetic » Mon Feb 26, 2007 3:27 pm

hello
can somebody please give a hint about this problem?

thank you

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Post by Miguel Angel » Mon Feb 26, 2007 3:59 pm

Well..I tried that problem during the contest..I guessed there was a solution when (n-4)%3 == 0, you can make the sample for 4, 7, 11 and you will find that the solution follows a pattern. Though I didn't get AC :p, so, perhaps I was missing something else?
:D Miguel & Marina :D

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Mon Feb 26, 2007 4:06 pm

Miguel Angel wrote:Well..I tried that problem during the contest..I guessed there was a solution when (n-4)%3 == 0, you can make the sample for 4, 7, 11 and you will find that the solution follows a pattern. Though I didn't get AC :p, so, perhaps I was missing something else?
well, i don't think that is quite correct as there are solutions for 8, 11 and there can be many more when your condition does not hold, just that i can't find them with my bruteforce program in realistic ammount of time.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Mon Feb 26, 2007 4:18 pm

You might like to try to find a pattern for 4*k and 4*k+3 :wink:

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Feb 26, 2007 4:28 pm

i think i solved the problem in O(N^2) but i've got TLE, does anybody know any faster algorithm?
In being unlucky I have the record.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Mon Feb 26, 2007 4:50 pm

arsalan_mousavian wrote:i think i solved the problem in O(N^2) but i've got TLE, does anybody know any faster algorithm?
I know! :roll:

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Feb 26, 2007 4:52 pm

Hadi wrote:
arsalan_mousavian wrote:i think i solved the problem in O(N^2) but i've got TLE, does anybody know any faster algorithm?
I know! :roll:
how? can u give me a hint please?
In being unlucky I have the record.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Mon Feb 26, 2007 4:56 pm

He gave already:
Hadi wrote:You might like to try to find a pattern for 4*k and 4*k+3 :wink:

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Feb 26, 2007 5:46 pm

You can easily prove by odd-even parity that there are no solutions if N = 4*k+1 or 4*k+2.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Thu Mar 01, 2007 10:54 am

Can anybody give hint on how to generate those integers?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Mar 01, 2007 12:54 pm

I generated the solutions for small n by bruteforce, then the pattern should be rather clear.

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 11184 - Joyful Ride

Post by deadangelx » Mon Mar 02, 2009 5:00 am

test cases

Code: Select all

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
0
answer

Code: Select all

Case 1: -1
Case 2: 1 2 4
Case 3: 1 3 2 5
Case 4: -1
Case 5: -1
Case 6: 1 4 5 3 7 2 8
Case 7: 1 5 4 6 3 8 2 9
Case 8: -1
Case 9: -1
Case 10: 1 6 7 5 8 4 10 3 11 2 12
Case 11: 1 7 6 8 5 9 4 11 3 12 2 13
Case 12: -1
Case 13: -1
Case 14: 1 8 9 7 10 6 11 5 13 4 14 3 15 2 16
Case 15: 1 9 8 10 7 11 6 12 5 14 4 15 3 16 2 17
Case 16: -1
Case 17: -1
Case 18: 1 10 11 9 12 8 13 7 14 6 16 5 17 4 18 3 19 2 20
Case 19: 1 11 10 12 9 13 8 14 7 15 6 17 5 18 4 19 3 20 2 21
Case 20: -1
Case 21: -1
Case 22: 1 12 13 11 14 10 15 9 16 8 17 7 19 6 20 5 21 4 22 3 23 2 24
Case 23: 1 13 12 14 11 15 10 16 9 17 8 18 7 20 6 21 5 22 4 23 3 24 2 25
Case 24: -1
Case 25: -1
Case 26: 1 14 15 13 16 12 17 11 18 10 19 9 20 8 22 7 23 6 24 5 25 4 26 3 27 2 28
Case 27: 1 15 14 16 13 17 12 18 11 19 10 20 9 21 8 23 7 24 6 25 5 26 4 27 3 28 2 29
Case 28: -1
Case 29: -1
Case 30: 1 16 17 15 18 14 19 13 20 12 21 11 22 10 23 9 25 8 26 7 27 6 28 5 29 4 30 3 31 2 32
Case 31: 1 17 16 18 15 19 14 20 13 21 12 22 11 23 10 24 9 26 8 27 7 28 6 29 5 30 4 31 3 32 2 33
Case 32: -1
Case 33: -1
Case 34: 1 18 19 17 20 16 21 15 22 14 23 13 24 12 25 11 26 10 28 9 29 8 30 7 31 6 32 5 33 4 34 3 35 2 36
Case 35: 1 19 18 20 17 21 16 22 15 23 14 24 13 25 12 26 11 27 10 29 9 30 8 31 7 32 6 33 5 34 4 35 3 36 2 37
Case 36: -1
Case 37: -1
Case 38: 1 20 21 19 22 18 23 17 24 16 25 15 26 14 27 13 28 12 29 11 31 10 32 9 33 8 34 7 35 6 36 5 37 4 38 3 39 2 40
Case 39: 1 21 20 22 19 23 18 24 17 25 16 26 15 27 14 28 13 29 12 30 11 32 10 33 9 34 8 35 7 36 6 37 5 38 4 39 3 40 2 41
Case 40: -1
Case 41: -1
Case 42: 1 22 23 21 24 20 25 19 26 18 27 17 28 16 29 15 30 14 31 13 32 12 34 11 35 10 36 9 37 8 38 7 39 6 40 5 41 4 42 3 43 2 44
Case 43: 1 23 22 24 21 25 20 26 19 27 18 28 17 29 16 30 15 31 14 32 13 33 12 35 11 36 10 37 9 38 8 39 7 40 6 41 5 42 4 43 3 44 2 45
Case 44: -1
Case 45: -1
Case 46: 1 24 25 23 26 22 27 21 28 20 29 19 30 18 31 17 32 16 33 15 34 14 35 13 37 12 38 11 39 10 40 9 41 8 42 7 43 6 44 5 45 4 46 3 47 2 48
Case 47: 1 25 24 26 23 27 22 28 21 29 20 30 19 31 18 32 17 33 16 34 15 35 14 36 13 38 12 39 11 40 10 41 9 42 8 43 7 44 6 45 5 46 4 47 3 48 2 49
Case 48: -1
Case 49: -1
Hope it helps.

Post Reply

Return to “Volume 111 (11100-11199)”