Page 2 of 5 FirstFirst 1234 ... LastLast
Results 11 to 20 of 43

Thread: Window Washer Problem

  1. #11
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    this is really easy once you can understand the problem, and then visualize it. the zig zag fashion has nothing to do with the solution. only that a particular number of columns are done by each worker.

    if the job is done in the minimum amount of time, then all workers (who worked) finished their work in just about the same amount of time.
    assume ri is the speed the ith worker washes at.
    assume wi is the number of windows the ith worker washes.
    we want the minimum for cost = Sum(i=0 to n, ri*wi ), or something like that.

    cost = aA + bB+ cC + dD + ...
    a is number of window, A is rate...

    total windows = width * height = a + b + c + d + ...

    if every body does almost the same amount of work,
    AvgTime = aA = bB = cC = dD = .....

    if x persons do work... then
    cost = x * AvgTime

    that should help, my code goes a bit further though, hope you people understand it.
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

  2. #12
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    minimum for cost = Sum(i=0 to n, ri*wi ), or something like that
    Yes the solution is simple
    Do a brut search of all possible options, and select the one with lowest cost.

    //vary the amount of workers
    for( 1 worker used to all workers )

    //when the amount of workers is fixed, vary the names selected
    for( all combinations of the workers used )

    //when you have a particular team, vary the amount of windows they each must wash to complete.
    //eg if 50 windows must be washed by 5 people, then 1 can wash 46 and the others can wash one each

    for( all starting positions of the workers )

    //Calculate sum
    for( all used workers )
    ....sum += worker time * his windows;
    ....if sum > min_sum goto next possibibilty


    This is one implementation and no means the only one.


    This could be done in about 50 lines, but I would take probably 200. I realized I use unecessary logic in my algorithm implemetations.
    Last edited by crosswire; Aug 20, 2005 at 04:00 AM.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  3. #13
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    Here's a more interesting problem
    ParkingLot
    I am not attempting this one, because I fraid it send me to the madhouse.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  4. #14
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

    Crosswire 'Parking Lot' is not very hard either. You just have to do take a things into consideration. Infact one thing how quick from the store to the spot you park, multiply it by two and you have time to walk to store.

    Well let us hope i read the problem correctly. If i did that is the complexity of that problem.
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

  5. #15
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    I agree that it is not that hard still, but IMO, it is harder than the previous.

    I think something is missing about it but I have to read it again.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  6. #16
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    Quote Originally Posted by crosswire
    Yes the solution is simple
    Do a brut search of all possible options, and select the one with lowest cost.
    No!! never, i say never use a brute force algorithm unless you know absolutely nothing about the problem(which is impossible).

    always use all that you know. like for example we can order the set of work rates.
    then we know the persons who work slow might end up doing less columns than faster workers.
    so when we find the average work time, we divide by the work rate and find the number of columns he completed.
    we then remove that number of columns from the work schedule and remove the worker... Chip and Conquer.

    Quote Originally Posted by crosswire
    //Calculate sum
    for( all used workers )
    ....sum += worker time * his windows;
    ....if sum > min_sum goto next possibibilty
    we dont sum the work times of each worker, no. we find the work times independently, and find who took the longest, thats what we do.
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

  7. #17
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

    Well icymint3 calm down, hold off on the caffine. LOL.

    But i agree with you brute force is so, what is that word i am looking for............. Ahh yes the word is "ineffiecient". Very few problems require brute force. We need to gently caress the problem until it open up and divulge it's secrets to us. Now the better you caress the problem the more effiecient the solution you will get.
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

  8. #18
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    Yes it is IN-efficient

    About the ParkingLot problem, I just read it. Before,I read something wrong. 1) I thought that two cars were not supposed to pass through the same square at the same time, but they can. 2) I thought that a person can walk to diagonal squares but he can only move up/down/left/right. Thus I said the problem was difficult. A car blocking another car for a certain time would have been interesting.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  9. #19
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    Back about the WindowWasher problem,
    like for example we can order the set of work rates.
    I like that idea. I will use it in optimizing other programs.

    we know the persons who work slow might end up doing less columns than faster workers.
    so when we find the average work time, we divide by the work rate and find the number of columns he completed.
    we then remove that number of columns from the work schedule and remove the worker
    Well I did not see that mathematical solution... I was not looking. Anyway that sounds logically smart. Use the fastest worker to do his share. That I realized after attempts to scrutinize your solution, we all cool. Only one minor problem, how would you handle the decimal fractions, if any?

    Let me change a bit, I am all two thumbs up with efficiency, but the accuracy of the algorithm is important (especially in TopCoder competition). There is also a time limit on how long you have to come up with a working solution. I am not sure that an efficient algorithm will give you more points unless stated in the problem. It however is good practice.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  10. #20
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    sorry bout the tone, it was this book i was reading (Catcher in the Rye - J.D. Salinger) and the narrator is very sarcastic. it kinda over-powered me a bit.

    use integer division it forces ( to round ) down those (slow) guys you make do their bit of work first.
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •