dextrous's blog

Need Few minutes of your time to Solve this problem !
By dextrous, 9 years ago, In English

Can someone explain the approach to the solution of the problem http://codeforces.net/contest/295/problem/C. I've gone through the editorial but it isn't very explanatory.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool, thanks for the down-votes !

Someone asks for a help on the forum(which is solely made for that purpose) and instead of helping(only if u are capable of helping), what people do is just downvote it(do u guys extract fun in down-voting, or what ? Sick !).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Come on it's not that bad. I know sometimes the community at Codeforces seems to downvote posts unreasonably, but the majority of the people here are really helpful and you can learn a lot from them (though i can understand why you are angry).

    As for the problem you're giving, I think that the key idea is to understand that while we're making trips back and forth between the river's 2 banks we can fully describe the situation we are in using just 3 variables (this is called state of the problem): the number of 50kg people and 100kg people at one specific shore and the shore we are in. For example,let 0 denote the shore we are initially and 1 the other shore. If we had A 50kg people and B 100kg people initially then our state would be a triplet of the form (A,B,0), with A+B = N

    Now, all you have to do is figure out the transitions between states,i.e how to go from one state to another. Obviously, to go from a state of the form (a,b,x) to another state we have to change shores (0->1 and 1->0). This is easily achieved with binary operations: x^=1(xor). Now remember that you have a 50kg people and b 100kg people on shore 0, so calculate a = A-a and b = B-b if you are on shore 1. Then take all possible trips you can make to the other shore and move accordingly.

    Imagine that the transitions between states forms a graph. You begin at node (A,B,0) and want to reach node (0,0,1). Every edge has a weight of 1(1 trip). So, since you want the minimum number of trips, just do BFS on the graph and you will find your answer.

    Last thing is about the number of trips. This one i haven't yet understood fully but I think that each time you choose some people to get in the boat while leaving some other people you could've chosen out, you actually create more ways to make a best trip. Therefore you need to count all ways the choice can be made. This is achievable using simple multiplication and combinatorics but I am not very certain.

    Anyways, this is all I can do now as I have to be leaving. Good luck in the contest later too.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation. It will surely help me in getting the solution.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Is your profile pic from The Slight Edge? Great, inspirational and instructional book.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, I just saw it somewhere and liked it to be my profile pic. Haven't read the book u mentioned, but will whenever I'll get some spare time (and i feel like reading :p )

      → Reply