10747 - Maximum Subsequence
Moderator: Board moderators
-
- New poster
- Posts: 16
- Joined: Tue Dec 03, 2002 9:44 pm
10747 - Maximum Subsequence
<^7,
I tried to solve the problem 10747 Maximum Subsequence by sorting the numbers by their abs value ( and then replace one of the top K numbers when odd number of negative numbers is in first K) but WA. I also took special care for N=K, all positive, all negative cases.
I need some special input/output. Or any alternate way to solve
I tried to solve the problem 10747 Maximum Subsequence by sorting the numbers by their abs value ( and then replace one of the top K numbers when odd number of negative numbers is in first K) but WA. I also took special care for N=K, all positive, all negative cases.
I need some special input/output. Or any alternate way to solve
-
- New poster
- Posts: 16
- Joined: Tue Dec 03, 2002 9:44 pm
Uff
<^7,
Alhamdulillah ! it's AC. I dedicate my solution to Marian.
Alhamdulillah ! it's AC. I dedicate my solution to Marian.
Problem statement:
The output should be
right? (choosing -2, -4 and -5)
So if the input isYou have to pick such a subsequence, so that multiplication of all its integers is maximum.
Code: Select all
6 3
-5
-10
-2
-4
-8
-12
Code: Select all
-11
My solution produces for the following input
this output:
Is this output correct?
Thanks, Erik
Code: Select all
6 6
-1
-2
-5
2
4
7
6 4
0
0
-12
12
-4
8
5 4
10
-20
12
0
5
4 3
9
10
-7
-100
4 4
1
2
3
4
4 1
1
2
3
4
4 2
4
4
-4
-4
4 2
-1
-3
-5
-7
4 2
-3
-7
0
-12
5 3
6
7
0
-3
-5
3 3
-2
-3
-4
4 4
-1
-2
-3
-4
5 3
-1
-2
-3
-4
0
1 1
3
2 1
-5
-7
0 0
Code: Select all
5
4
27
-97
10
4
8
-12
-19
-1
-9
-10
-3
3
-5
Thanks, Erik
-
- New poster
- Posts: 16
- Joined: Tue Dec 03, 2002 9:44 pm
yes
<^7,
Yes, your outputs are correct. (similar to my AC)Is this output correct?
Re: yes
Hello, I used the same method as you describe,and passed all the input/output above. But still get Wrong Answer.Shahriar Nirjon wrote:<^7,
Yes, your outputs are correct. (similar to my AC)Is this output correct?
Could someone offer me some critical input/output? thx
-
- New poster
- Posts: 16
- Joined: Tue Dec 03, 2002 9:44 pm
Changed solution
<^7,
Hi,
I changed my algorithm since I could not make out how to handle special cases with that algo. The previous one (sort by abs value) was replaced by another one (trying to take big positive numbers, then even number of negetive numbers, finally special checks etc)
for special test case, u may try to generate tests where you must take at least one zero.
hope it helps.
Hi,
I changed my algorithm since I could not make out how to handle special cases with that algo. The previous one (sort by abs value) was replaced by another one (trying to take big positive numbers, then even number of negetive numbers, finally special checks etc)
for special test case, u may try to generate tests where you must take at least one zero.
hope it helps.
Re: 10747 - Maximum Subsequence
Why for input
the outupt is
shouldn't it be 24?
Code: Select all
6 4
0
0
-12
12
-4
8
Code: Select all
4
Re: 10747 - Maximum Subsequence
Hi,
I don't know why the following input have such a strange answer...
can anyone please help me?
input
output
why the first test case's output is -4?
I don't know why the following input have such a strange answer...
can anyone please help me?
input
Code: Select all
8 1
1 -1 -1 0 1 -3 -1 -1
8 2
1 -1 -1 0 1 -3 -1 -1
8 3
1 -1 -1 0 1 -3 -1 -1
8 4
1 -1 -1 0 1 -3 -1 -1
8 5
1 -1 -1 0 1 -3 -1 -1
8 6
1 -1 -1 0 1 -3 -1 -1
8 7
1 -1 -1 0 1 -3 -1 -1
8 8
1 -1 -1 0 1 -3 -1 -1
0 0
Code: Select all
-4
-4
-3
-2
-5
-4
-4
-5
Re: 10747 - Maximum Subsequence
My AC program outputs:suneast wrote:Hi,
I don't know why the following input have such a strange answer...
can anyone please help me?
inputoutputCode: Select all
8 1 1 -1 -1 0 1 -3 -1 -1 8 2 1 -1 -1 0 1 -3 -1 -1 8 3 1 -1 -1 0 1 -3 -1 -1 8 4 1 -1 -1 0 1 -3 -1 -1 8 5 1 -1 -1 0 1 -3 -1 -1 8 6 1 -1 -1 0 1 -3 -1 -1 8 7 1 -1 -1 0 1 -3 -1 -1 8 8 1 -1 -1 0 1 -3 -1 -1 0 0
why the first test case's output is -4?Code: Select all
-4 -4 -3 -2 -5 -4 -4 -5
Code: Select all
1
-4
-3
-2
-5
-4
-2
-5
Re: 10747 - Maximum Subsequence
Thx annhy
I have solved it a few months ago...
my output above is generated by UVaToolKit, I think there maybe something wrong with Toolkit's solution
Keep posting!
Happy AC
I have solved it a few months ago...
my output above is generated by UVaToolKit, I think there maybe something wrong with Toolkit's solution
Keep posting!
Happy AC
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10747 - Maximum Subsequence
Input:AC output:
Code: Select all
16 4
10
-81
-99
-99
-2
80
-18
79
11
-45
44
11
70
94
-90
-87
18 3
-21
-25
18
48
-25
91
60
23
84
65
61
32
36
-80
1
-13
-79
100
7 3
78
28
8
21
-61
-73
-36
14 6
46
-60
20
-80
8
-33
-55
-1
77
68
-18
-9
-22
64
3 1
-35
14
-30
18 6
24
92
-42
82
-38
-53
-91
26
-54
-50
-79
-64
20
92
45
37
-63
94
6 6
-75
54
-67
90
80
-18
7 3
52
-82
24
-75
-91
33
-93
12 11
-84
47
77
-84
69
63
36
60
-43
-78
47
-50
2 2
-24
-12
20 11
-83
17
-81
-89
-82
-63
-15
-56
97
68
-49
-83
-2
-83
64
-26
-67
32
87
19
3 3
41
89
-6
6 5
20
-37
-25
-15
-70
92
17 16
-90
-9
-23
-46
-63
-56
-45
-46
42
-28
-82
66
-45
0
3
24
42
13 9
31
91
-61
21
-39
-48
97
46
-18
88
-100
-26
48
2 1
52
-21
12 10
33
-63
-72
1
53
-17
-99
-45
-94
43
-99
-80
10 6
-91
-5
-97
-39
-9
-1
44
-72
-1
68
10 4
-32
28
70
-88
-15
-48
100
13
54
53
6 4
-93
53
-53
60
24
-79
19 19
16
-45
95
57
4
-12
85
-97
-45
11
-56
23
90
-87
-15
-26
-35
-15
87
7 7
33
-27
95
-64
-29
4
60
11 1
-8
8
61
-64
-36
-35
-26
99
-82
29
10
14 11
-1
-25
-13
73
-10
72
9
-91
59
93
-18
53
-72
3
9 1
45
63
80
-48
24
-84
-34
89
-10
7 3
70
75
-32
71
-77
-7
-43
8 2
-72
-46
42
37
97
75
-10
75
8 2
12
73
-91
-58
75
33
-42
-59
18 18
-44
-23
-83
-70
-5
89
-47
38
96
99
-29
75
-98
63
11
50
-13
51
18 17
-53
87
-63
-93
-72
-89
40
-64
-98
-89
-16
-92
-62
2
89
-16
-60
-59
15 3
90
-58
-91
43
-95
21
-8
-58
-29
66
57
-31
52
44
-24
1 1
66
1 1
27
19 6
16
52
5
100
92
-3
-80
-74
-64
-37
-64
29
-82
7
-80
-40
28
87
68
15 4
11
-78
-32
-84
39
-17
-25
-35
33
92
81
-16
-54
30
-25
11 7
-48
30
64
-62
-42
32
45
-71
42
-28
-85
2 2
3
71
4 2
87
30
-96
-39
15 4
-98
26
22
-51
-94
97
42
7
-52
-79
-30
-64
-20
52
81
15 1
-97
-26
-98
-78
77
23
-87
-2
-41
-6
-48
21
-61
39
-27
16 1
-28
21
-93
-86
-73
-95
-65
-53
-58
-35
99
73
74
-8
76
98
6 5
25
67
12
-78
76
-95
13 13
95
13
20
9
24
92
-70
-19
56
-43
-64
42
5
14 7
-47
-99
31
45
27
28
39
-25
-48
-45
37
-76
-69
-8
6 3
-14
62
97
95
-65
89
4 2
44
-68
52
-15
16 13
-58
40
82
73
-65
-42
-50
74
33
-47
-71
-81
-23
-90
11
-24
16 14
88
-66
92
-78
-78
-85
38
16
-53
-61
52
34
-81
44
-76
51
13 12
-91
16
-68
-8
69
-89
12
-54
-79
-78
-28
-41
-81
17 11
61
-19
-35
76
-82
31
74
-93
-68
-43
-73
76
-19
28
-59
-10
-13
12 7
80
-24
-16
-59
-28
-44
-87
44
-35
83
-98
58
4 3
73
-31
-49
3
5 1
36
-51
-64
11
-19
11 9
71
-99
-90
-57
31
-14
28
72
59
34
35
20 19
18
-45
6
-40
38
-22
-21
40
81
-29
49
16
21
85
78
52
-2
-70
22
-1
10 7
-71
26
94
51
-66
27
-14
-13
-25
-97
13 1
-87
-71
-42
-7
19
-62
14
-33
5
85
-49
-68
36
4 1
-92
99
2
24
20 7
-33
29
63
94
-86
100
-82
68
41
99
32
20
-94
75
-61
-56
-12
-44
-1
-27
2 2
-92
-93
Code: Select all
-375
275
-56
115
14
190
64
-132
103
-36
-379
124
-55
-266
122
52
-473
-187
34
-59
35
72
99
121
89
216
172
148
160
-710
-96
66
27
-124
11
-115
74
-135
-14
77
99
-5
160
-339
281
96
-202
-213
-532
-100
-67
-7
36
141
270
-87
85
99
256
-185
Check input and AC output for thousands of problems on uDebug!
Re: 10747 - Maximum Subsequence
I got a lot of WAs on this problem because my program would fail on cases that product of all selected numbers became zero and I hadn't noticed that by excluding negative numbers we would reach a better sum.
This testcase my help other people making the same mistake:
Input:
AC Output:
This testcase my help other people making the same mistake:
Input:
Code: Select all
6 4 5 -2 -1 0 0 0
4 4 1 2 3 4
4 1 1 2 3 4
4 2 4 4 -4 -4
5 1 -2 -1 0 1 2
3 1 -2 -1 0
3 1 0 1 2
3 1 -3 -2 -1
5 2 -2 3 0 0 0
5 3 -2 3 0 0 0
3 2 -2 -2 0
5 3 -5 -5 0 0 0
5 3 5 5 0 0 0
5 3 -5 5 0 0 0
5 4 -1 -1 5 5 0
5 4 -1 -1 -1 5 0
6 4 -1 -1 -1 5 0 0
5 3 -5 -1 -2 -4 -3
4 3 0 0 -1 -1
6 3 -5 -10 -2 -4 -8 -12
4 2 100 -10 -9 7
4 3 -100 -100 -99 1
4 2 200 -100 -3 -4
4 2 200 -100 3 4
6 4 -12 12 8 -4 0 0
0 0
Code: Select all
5
10
4
8
2
0
2
-1
3
3
-4
0
10
5
8
3
4
-6
-1
-11
107
-199
-104
204
4
Re: 10747 - Maximum Subsequence
Code: Select all
13 12
49
-23
2
15
2
18
0
30
14
11
-23
7
-48
0 0