10747 - Maximum Subsequence

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

Moderator: Board moderators

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

10747 - Maximum Subsequence

Post by Shahriar Nirjon » Sun Oct 17, 2004 7:07 pm

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

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Sun Oct 17, 2004 9:42 pm

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
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

Uff

Post by Shahriar Nirjon » Mon Oct 18, 2004 12:10 pm

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

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Mon Oct 18, 2004 2:09 pm

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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Mon Oct 18, 2004 3:00 pm

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
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

yes

Post by Shahriar Nirjon » Mon Oct 18, 2004 9:25 pm

<^7,
Is this output correct?
Yes, your outputs are correct. (similar to my AC)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: yes

Post by windows2k » Sun Nov 07, 2004 3:53 am

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

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

Changed solution

Post by Shahriar Nirjon » Tue Nov 09, 2004 11:38 am

<^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
New poster
Posts: 2
Joined: Mon Nov 10, 2008 2:29 pm

Re: 10747 - Maximum Subsequence

Post by Xmansk » Mon Nov 10, 2008 2:37 pm

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
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 10747 - Maximum Subsequence

Post by suneast » Tue Jul 20, 2010 2:59 am

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

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: 10747 - Maximum Subsequence

Post by annhy » Wed Nov 03, 2010 3:15 pm

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

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 10747 - Maximum Subsequence

Post by suneast » Wed Nov 03, 2010 3:22 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10747 - Maximum Subsequence

Post by brianfry713 » Fri Aug 02, 2013 11:21 pm

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
Check input and AC output for thousands of problems on uDebug!

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 10747 - Maximum Subsequence

Post by AKJ88 » Sat Aug 03, 2013 12:27 pm

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
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

Re: 10747 - Maximum Subsequence

Post by hpjhc » Thu Feb 27, 2014 11:17 am

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?

Post Reply

Return to “Volume 107 (10700-10799)”