i worked on bookshelves for 2 hrs and wrote the solution but i couldn’t imagine for which data it would get wrong output. Scoring a big 0…
sort both arrays
lots of cases (compare a1[n-1] with a2[n-1], a1[n-1] with a2[0], a1[n-2] with a2[0] and accordingly determine swap (not going to sit writing result for each case, hope you understand.
calculate minimum value of skew at each step.
break if any one array has all bigger values of skew, i.e. new skew after this swap will not result less than equal to current skew.
something like this…
as for the second problem,
Didn’t attempt bamboo one.
Giving Zco 2016 in Delhi was a very bad experience. Some of the computers even had windows 98 ( not all). Many candidates only got 90-100 minutes. There were a few guys who almost called the ico coordinator. The technical staff didn’t even knew the difference between compile and run atleast this never happened in IITD. Though I am Zio candidate but I feel bad for the potential candidates of ioitc who suffered because of this.
And I think Zio should be removed as it does not test a person’s coding ability, instead seats through zco should increase.
:’( Bad for me…It was really unexpected…only successfully submitted Subtask 1 of each problem. Means, total of 70 which confirms that I will not be selected. Actually not sure about it. If my codes fail in system test case, it will give me a ‘0’ marks. :3 …Well, may be the cut-off will be 100. I really don’t know why my codes gave wrong answer in subtask 2.
I scored 0.
My algorithms were
For Bookshelves
sort two arrays
swap(A1[n-1],A2[0])
store skew
in other copy of arrays
swap(A2[n-1],A1[0])
This didn’t worked so i tested for all swaps even that didn’t work and gave WA:-(
For Bamboo Sticks
I used dp a 2d array
B[i][j]=A[j]-A[i]
then store it in 1d array
then look for repeated digits whatever times repetition occurs thats answer
but my code didn’t work.
Experience:
Page developed by tcs was extremly bad, User foe page. I was not even told how to switch between c and c++.
No Demo Page provided!!
Continues crashing of dev c++
changed my pc 4 times!!
Above all resources for preparation are not provided.
@aalok_sathe and @alphastar: Say a= {1, 2, 3, 7, 8}, b= {1, 5, 6, 7, 8} and k=2. Swapping a[n-1] and b[0] gives the same skewness as swapping b[n-1] and a[0]. Which one do you choose? If you swap a[n-1] with b[0] you can get an arrangement with skewness 12 after the next swap. If you swap b[n-1] with a[0] the minimum skewness you can get after another swap is 14. How do you break the ties efficiently?
Here’s what I did for Bookshelves (got AC in contest; expecting 200 overall): Note that the largest book must contribute to the skewness. Our objective is to minimize the other book which contributes. To do this, we must bring the larger books to one of the arrays so that the maximum book of the other array is as small as possible. Let’s try the first case: we try to bring the large books to array a. Suppose there are p instances of the largest book in the second array. We need to bring these p instances to the first array. If we have enough amount of swaps and space available, we do this and do the same thing with the second largest book and so on. (Note that you must also take care that the total number of elements in the first array cannot exceed n.) Then do the same thing for the second array and print whichever solution is optimal. This can be implemented nicely with maps in O(n log n).
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.
@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?
how did you guys got to know your marks??
also i want to know that i compiled and run my program for many test cases and it worked alright but during submission of code system took more time to check the code and finally it showed that it doesn’t pass all the test cases. does it mean that i m not going to get any marks for that program???
Did you use the same logic I did for problem 2?