11184 - Joyful Ride

[fpavetic]

hello
can somebody please give a hint about this problem?

thank you

[Miguel Angel]

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?

[fpavetic]

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.

[Hadi]

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

[arsalan_mousavian]

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

[Hadi]

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

I know!

[arsalan_mousavian]

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

I know!

how? can u give me a hint please?

[Erik]

He gave already:

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

[Observer]

You can easily prove by odd-even parity that there are no solutions if N = 4*k+1 or 4*k+2.

[rushel]

Can anybody give hint on how to generate those integers?

[sclo]

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

[deadangelx]

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.