## 11187 - Water Crisis

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 11187 - Water Crisis

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?

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm
can you share those tricks?

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
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.

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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.
Last edited by sclo on Wed Mar 07, 2007 8:06 am, edited 1 time in total.

Noldorin
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm
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.

erictwpt
New poster
Posts: 6
Joined: Mon Oct 10, 2005 5:13 am
Location: Taiwan
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.
Because we are all classmates made in Taiwan, and discussed this problem together.
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).

s000015
New poster
Posts: 5
Joined: Sat Oct 08, 2005 1:56 pm
Location: Taiwan
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:

Code: Select all

a = infinity
i = best possible time
j = worst possible time
while(i<=j)
{
k = (i+j) / 2
a=min(res,k)
j=k-1
else
i=k+1
}
print res

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Noldorin wrote:Quite similar to a problem named Bookcase in this years NWERC, but a bit more time hungry.
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).

That gave around 7 secs, but using krijgers second optimisation would probably decrease it a lot more.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Per wrote:That gave around 7 secs, but using krijgers second optimisation would probably decrease it a lot more.
Yes, it did. Doing the full symmetry optimisations as well, it ended up on roughly 1 second.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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).
I think the problem you talk about is 711 "Dividing up".
My signature:
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
.. wrote: I think the problem you talk about is 711 "Dividing up".
Yes it is
Everything well with you, Lawrence? I noticed you're working man now.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Hello.
I tried to solve the problem with the thought mentioned above.
But get wa all the time.
Could someone give some input/output for me?
Thanks