Isn't this an exponential time complexity brute forcer?
I had to pull quite a number of tricks to get within the time limit, and I see most respected colleague-solvers getting times above 1 second. Even so, there are some people getting very fast times. Did I miss something?
11187 - Water Crisis
Moderator: Board moderators
I used the following DP-approach: The problem basically comes down to splitting a set of objects into three sets (the three trucks) in such a way that the maximum of the weights of the numbers a set is minimal.
This can be solved using a three dimensional dp, where dp[j][k] denotes if it is possible to split the first i numbers in such a way that the sum of weights in the first set is j and in the second set is k (and the third set is therefore fixed).
This gives an O(KT^2) algorithm, where K (<=200) is the total demand and T is the total time we hame (T<=60*20=1200). Because we have to ride back to the office, all numbers will be even, so we can reduce T by 2 => our algorithm takes maximal 200*600*600=72.000.000 operations, which unfortunately gives TLE.
We can optimize our algorithm a bit by only considering j<=k and only looping till the sum so far etc, but it still gives TLE. What we need is that if there are 4 (our more) objects in our set with the same weight, then at least one of the trucks has to do at least 2 of these objects, so we can combine 2 of these objects into an object with duplicate size. This reduction can be applied until all weights have maximum frequency three, after which we can run our algorithm with a lower K.
This last optimization was enough to give me AC in 7.658 seconds.
This can be solved using a three dimensional dp, where dp[j][k] denotes if it is possible to split the first i numbers in such a way that the sum of weights in the first set is j and in the second set is k (and the third set is therefore fixed).
This gives an O(KT^2) algorithm, where K (<=200) is the total demand and T is the total time we hame (T<=60*20=1200). Because we have to ride back to the office, all numbers will be even, so we can reduce T by 2 => our algorithm takes maximal 200*600*600=72.000.000 operations, which unfortunately gives TLE.
We can optimize our algorithm a bit by only considering j<=k and only looping till the sum so far etc, but it still gives TLE. What we need is that if there are 4 (our more) objects in our set with the same weight, then at least one of the trucks has to do at least 2 of these objects, so we can combine 2 of these objects into an object with duplicate size. This reduction can be applied until all weights have maximum frequency three, after which we can run our algorithm with a lower K.
This last optimization was enough to give me AC in 7.658 seconds.
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
That last trick is very clever (reminds me of another problem dealing with marbles, but i can't remember the problem title). I thought of the DP solution, but rejected it in an early stage, because of the too high memory consumption (which was premature, I see now).
My solution is an (intrinsically worse) O(3^K) backtracker, where at each level one of the K loads is assigned to one of the three trucks. Some of the tricks I used:
- You know the best possible time at forehand, so once you find a solution with this time, you can stop the search; if this time is too big, you don't have to search at all. It's not guaranteed that this works in all cases, but if it does, it's a time saver.
- Sort the loads by time required. Once a truck is not assigned a load of a specific duration, he will never be assigned a load of that same duration. There are only max. 19 different durations, so this is a major time saver.
- The first load is always assigned to the first truck. The second truck has to be assigned a load before the third truck gets an assignment. This reduces the search time by a factor 6.
My runtime is 0.1 seconds, but I fear my program would time out on horror-cases, although I haven't tried. Still there are times below 0.01 seconds, and I wonder how that is possible.
My solution is an (intrinsically worse) O(3^K) backtracker, where at each level one of the K loads is assigned to one of the three trucks. Some of the tricks I used:
- You know the best possible time at forehand, so once you find a solution with this time, you can stop the search; if this time is too big, you don't have to search at all. It's not guaranteed that this works in all cases, but if it does, it's a time saver.
- Sort the loads by time required. Once a truck is not assigned a load of a specific duration, he will never be assigned a load of that same duration. There are only max. 19 different durations, so this is a major time saver.
- The first load is always assigned to the first truck. The second truck has to be assigned a load before the third truck gets an assignment. This reduces the search time by a factor 6.
My runtime is 0.1 seconds, but I fear my program would time out on horror-cases, although I haven't tried. Still there are times below 0.01 seconds, and I wonder how that is possible.
I had another similar 3 dimentional dp.
dp[j][k] = denotes the minimum time to finish the last i jobs (as time elapsed after the first truck leaves), where the second truck not available for the first j mins, and that the third truck is not available for the first j+k mins. Here, we can assume that we can just treat the 3 trucks as identical, and we sort the truck according to the when they are first available.
We can use the same trick of dividing all the times by 2, since all times are even. Furthermore we can guarantee that 0<= j,k < 100, since we know that no jobs requires more than 100 mins. (Using the krijger's trick to reduce K mentioned above would violate this requirement, but the bound can be modified).
Overall, the runtime is O(200*100*100) = 2 mil, 5.727sec which is quite ok, considering the fact that I didn't do any other optimizations.
dp[j][k] = denotes the minimum time to finish the last i jobs (as time elapsed after the first truck leaves), where the second truck not available for the first j mins, and that the third truck is not available for the first j+k mins. Here, we can assume that we can just treat the 3 trucks as identical, and we sort the truck according to the when they are first available.
We can use the same trick of dividing all the times by 2, since all times are even. Furthermore we can guarantee that 0<= j,k < 100, since we know that no jobs requires more than 100 mins. (Using the krijger's trick to reduce K mentioned above would violate this requirement, but the bound can be modified).
Overall, the runtime is O(200*100*100) = 2 mil, 5.727sec which is quite ok, considering the fact that I didn't do any other optimizations.
Last edited by sclo on Wed Mar 07, 2007 8:06 am, edited 1 time in total.
Quite similar to a problem named Bookcase in this years NWERC, but a bit more time hungry. For this one as the matrix can be very empty, so you can save in a array the places in the matrix that are correct, and sorting the length of the costs of the water delivery to not apply the same cost over and over again to the same valid configuration (If you have to make 4 deliveries with cost 5, only apply the second iteration to the points generated by the first, and so on). A little annoying having to adjust the algorithm constant costs to fit in time but i like that kind of problems.
Fear is the mind killer.
Because we are all classmates made in Taiwan, and discussed this problem together.sclo wrote:What is interesting is that the fastest 4 times are all people from Taiwan. I would think that their solutions are either the same or similar. I wouldn't be happy if all they did was to print the solutions. Usually only something close to a constant time solution or linear time solution can give runtimes that fast.
Actually I just did a simple backtracking.
Binary search the limit, and using the same idea from USACO problem Fence Rails (but with just 3 trucks).
Our solutions are similar with little joey's,
but I used an additional trick(my English is too poor to
describe it precisely), and we binary-search the min. time:
but I used an additional trick(my English is too poor to
describe it precisely), and we binary-search the min. time:
Code: Select all
a = infinity
i = best possible time
j = worst possible time
while(i<=j)
{
k = (i+j) / 2
if(All loads can be assigned)
a=min(res,k)
j=k-1
else
i=k+1
}
print res
Yeah, my solution was almost the same as my solution for Bookcase, with the same optimisations: keep track of which entries of the matrix are filled, prune away entries which can never improve upon the best solution found so far, and remove symmetries between states, e.g. state [j][k] is equivalent to [k][j] (and similarly for the third truck though I only did it for the first two).Noldorin wrote:Quite similar to a problem named Bookcase in this years NWERC, but a bit more time hungry.
That gave around 7 secs, but using krijgers second optimisation would probably decrease it a lot more.
I think the problem you talk about is 711 "Dividing up".little joey wrote:That last trick is very clever (reminds me of another problem dealing with marbles, but i can't remember the problem title). I thought of the DP solution, but rejected it in an early stage, because of the too high memory consumption (which was premature, I see now).
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm