I got Bookshelves subtask 1 with brute force. Didn’t get subtask 2 of Bookshelves. For Bamboo Art, I sorted the input in increasing order, and then something like this:
max = 1;
for (i = 0; i < n-max; i++)
{
for (j = i+1; j < n; j++)
{
diff = l[j] - l[i];
for (k = l[j]+diff; binarysearch(l, n, k) != -1; k += diff)
temp++;
if (temp > max)max= temp;
}
}
l is the array containing the heights, n is the total no of sticks.
I got accepted on both of Bamboo Art. But I think it may fail when more input is provided.
I gave the ZCO in Delhi, and can confirm the experience was poor. Interestingly, I got 100 on Bamboo art even on a O(N^3) solution. The test cases were really weak today, I don’t expect to get 100 on actual testing.
I have the same solution and this should work as the overall complexity turns out to be N^2 log N which works well under the time limit for max test.
Edit: The binary search might cause problems as that adds a extra log N factor. I just used a array to check whether an element existed or not, making it constant time lookup.
I hope it doesn’t cause any problems! But, it will take 8-9 iterations for the worst case, so shouldn’t be such a big addition to the complexity, right?
@nishanthta: I used the same dp as animesh_f’s post above. My code is O(n^2 log n) because of the map, not really sure if it’s going to pass the second subtask (people are saying the pretests are weak…).
@AnonymousBunny I dont think that would be a factor, if it is so, I think you can contact the coordinator emplaining him that the logic was correct. IMO, data structure wont matter, not sure though.
Btw, why did you use map ?
Btw, it was given that the best solution will be submitted and used. For Bamboo Art, first I used int for everything, and got accepted. But later, I converted everything to long long int, and again submitted and got accepted. So which one will be used? What if the int one fails because of the input (the height was from 1 to 10^5)?
@aneesh2312 int to long long in this problem does not really matter. I had used a integer dp array of dimensions 2500’10^5. It passed the pretests and I got AC, does anyone know if this will be a problem in the system testing?
The experience at Delhi was indeed terrible. I have emailed the coordinator about the issues faced and hopefully they can do something about it.
I think I ended up scoring 130 because although my code passed the pre test-cases, they were supposedly very weak, and my solution would probably time out on decent test cases. By the way, somebody told me that problem 1 could be solved using a priority queue. Can anyone who solved it that way describe the solution, please?
I got an O(N^2 log N) solution for problem 2 (using DP and binary searching). It was taking a maximum of 0.95 seconds on the computer provided at the center but at my home it is running in 0.18 seconds. Does anyone how fast the official grading server(s) is?
i did the same. but foolishly set all the elements of dp array to 1, which could have been done efficiently as well. so time was n*max(a[i]). though it gave 100, will it succeed?