I sat for the morning exam... I think the morning session was a tad easier than the afternoon session. Apparently I got 200, but they say the code will be provided with additional test data later, so I'm not really sure. Has anyone seen getting his scores decreased after the code was fed by the additional input? Anyways, here are my solutions, which hopefully work. 1: This is a nice DP exercise. I made an array ans[n+1], where ans[n]= 0 and ans[i] is the answer for the sequence {a[i], a[i+1], ..., a[n-1]}. Now, it's easy to see that ans[n-1]=1 and ans[i]= max(ans[j]: min(ans[j]: j varying over all integers >=i such that the sequence {a[i], a[i+1], ..., a[j]} is a palindrome)+1. We can thus compute a[i] for all i<=n-1 recursively. recursively, and our answer is ans[0]. Overall complexity: O(n^3). 2: This is just trivial binary search. First, sort the sequence. Then, for all 1<=i<=n-1, compute the smallest index j satisfying a[j]>=a[i]+k using binary search, and add n-j to the answer. Overall complexity: O(n log n). Also, the server slowing down was a real big problem. >_< Did anyone else experience it too?

I sat for the morning exam... I think the morning session was a tad easier than the afternoon session. Apparently I got 200, but they say the code will be provided with additional test data later, so I'm not really sure. Has anyone seen getting his scores decreased after the code was fed by the additional input? Anyways, here are my solutions, which hopefully work. 1: This is a nice DP exercise. I made an array ans[n+1], where ans[n]= 0 and ans[i] is the answer for the sequence {a[i], a[i+1], ..., a[n-1]}. Now, it's easy to see that ans[n-1]=1 and ans[i]= max(ans[j]: j varying over all integers >=i such that the sequence {a[i], a[i+1], ..., a[j]} is a palindrome)+1. We can thus compute a[i] for all i<=n-1 recursively. Overall complexity: O(n^3). 2: This is just trivial binary search. First, sort the sequence. Then, for all 1<=i<=n-1, compute the smallest index j satisfying a[j]>=a[i]+k using binary search, and add n-j to the answer. Overall complexity: O(n log n). Also, the server slowing down was a real big problem. >_< Did anyone else experience it too?