Page 1 of 2

10747 - Maximum Subsequence

Posted: Sun Oct 17, 2004 7:07 pm
by 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 :oops:

Posted: Sun Oct 17, 2004 9:42 pm
by 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.

Uff

Posted: Mon Oct 18, 2004 12:10 pm
by Shahriar Nirjon
<^7,
Alhamdulillah ! it's AC. I dedicate my solution to Marian.

Posted: Mon Oct 18, 2004 2:09 pm
by 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)

Posted: Mon Oct 18, 2004 3:00 pm
by 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

yes

Posted: Mon Oct 18, 2004 9:25 pm
by Shahriar Nirjon
<^7,
Is this output correct?
Yes, your outputs are correct. (similar to my AC)

Re: yes

Posted: Sun Nov 07, 2004 3:53 am
by windows2k
Shahriar Nirjon wrote:<^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 :D

Changed solution

Posted: Tue Nov 09, 2004 11:38 am
by 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.

Re: 10747 - Maximum Subsequence

Posted: Mon Nov 10, 2008 2:37 pm
by 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?

Re: 10747 - Maximum Subsequence

Posted: Tue Jul 20, 2010 2:59 am
by suneast
Hi,
I don't know why the following input have such a strange answer... :o
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? :-?

Re: 10747 - Maximum Subsequence

Posted: Wed Nov 03, 2010 3:15 pm
by annhy
suneast wrote:Hi,
I don't know why the following input have such a strange answer... :o
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

Re: 10747 - Maximum Subsequence

Posted: Wed Nov 03, 2010 3:22 pm
by suneast
Thx annhy :D

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 :wink:

Keep posting!
Happy AC :P

Re: 10747 - Maximum Subsequence

Posted: Fri Aug 02, 2013 11:21 pm
by 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

Re: 10747 - Maximum Subsequence

Posted: Sat Aug 03, 2013 12:27 pm
by 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

Re: 10747 - Maximum Subsequence

Posted: Thu Feb 27, 2014 11:17 am
by 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?