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
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
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
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
The output should be
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
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
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
Shahriar Nirjon
New poster
Posts: 16 Joined: Tue Dec 03, 2002 9:44 pm
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
Post
by Xmansk » Mon Nov 10, 2008 2:37 pm
Why for input
the outupt is
shouldn't it be 24?
suneast
New poster
Posts: 49 Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:
Post
by suneast » Tue Jul 20, 2010 2:59 am
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
why the first test case's output is -4?
annhy
New poster
Posts: 40 Joined: Sun May 27, 2007 1:42 am
Location: Taiwan
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...
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
why the first test case's output is -4?
My AC program outputs:
suneast
New poster
Posts: 49 Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:
Post
by suneast » Wed Nov 03, 2010 3:22 pm
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
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
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
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
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?