In 2138C1 - Maple and Tree Beauty (Easy Version) and 2138C2 - Maple and Tree Beauty (Hard Version), the testcases are weak.

DP is the only approach to be used in both, but unfortunately a greedy solution got Accepted:

Easy Version: 337674745

It even passed hard version: 337674792

Failed testcase:

Input:

1
19 8
1 1 1 1 2 3 4 5 6 6 7 8 9 10 11 12 13 14

Expected Output: 5

Greedy Approach Output: 4

maomao90, StarSilk, installb, tarjen, wjy666, 2014CAIS01

The problem wasn’t tested properly. Even though there are more than 60 test cases, it didn’t include this one. I hope the authors add this test case and rejudge all the accepted submissions on both problems.

Special thanks to nithish654 for coming up with this greedy approach which made me to hack. Thank god, the contest got unrated for some other reason anyway.

UPD: This case has been added as test 68.