In 2138C1 - Мейпл и красота дерева (простая версия) and 2138C2 - Мейпл и красота дерева (сложная версия), 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.
