10747 - Maximum Subsequence

[Shahriar Nirjon]

<^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

[marian]

Your method is good, but there are couple of special cases to consider:

for example, in the input:
4 2
7 -9 -10 100

you have to switch 7 for -10, and not -9 for 100.

Also, in the input
4 3
0 0 -1 -1

It is better to take 0 0 -1, as opposed to 0 -1 -1.

[Shahriar Nirjon]

<^7,
Alhamdulillah ! it's AC. I dedicate my solution to Marian.

[Maniac]

Problem statement:

You have to pick such a subsequence, so that multiplication of all its integers is maximum.

So if the input is

Code: Select all

6 3
-5
-10
-2
-4
-8
-12

The output should be

Code: Select all

-11

right? (choosing -2, -4 and -5)

[Maniac]

My solution produces for the following input

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

this output:

Code: Select all

5
4
27
-97
10
4
8
-12
-19
-1
-9
-10
-3
3
-5

Is this output correct?

Thanks, Erik

[Shahriar Nirjon]

<^7,

Is this output correct?

Yes, your outputs are correct. (similar to my AC)

[windows2k]

<^7,

Is this output correct?

Yes, your outputs are correct. (similar to my AC)

Hello, I used the same method as you describe,and passed all the input/output above. But still get Wrong Answer.
Could someone offer me some critical input/output? thx

[Shahriar Nirjon]

<^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.

[Xmansk]

Why for input

Code: Select all

6 4
0
0
-12
12
-4
8

the outupt is

Code: Select all

4

shouldn't it be 24?

[suneast]

Hi,
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

output

Code: Select all

-4
-4
-3
-2
-5
-4
-4
-5

why the first test case's output is -4?

[annhy]

Hi,
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

output

Code: Select all

-4
-4
-3
-2
-5
-4
-4
-5

why the first test case's output is -4?

My AC program outputs:

Code: Select all

1
-4
-3
-2
-5
-4
-2
-5

[suneast]

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

[brianfry713]

Input:

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

AC output:

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

[AKJ88]

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:

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

AC Output:

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

[hpjhc]

Code: Select all

13 12
49
-23
2
15
2
18
0
30
14
11
-23
7
-48
0 0

What about this case, the output is 77 in uva toolkit, an AC program is 125, another AC program is 102, but this program's output is 0 for case 1 1 -41, my WA program is 102. I think my output is correct, two AC program is wrong. Do I misunderstand the problem's meaning?