want a hint

[nitin1]

here is a DP problem which i am solving from 2 days now. and i am finding a damn difficult. can you please tell what is overlaaping subproblem and what is optimal substructure in this problem. then i will try it again. any help will be appreciated. thanks

http://www.spoj.pl/problems/GNYR09F/

thanks

[rubberman]

So, how long ago did you get this assignment? Here it is, less than 2 days until it is due, and it doesn't appear to be a trivial problem. Sorry, but we don't help you cheat. You have to do this on your own. We'll help once you have made some REASONABLE attempt to solve it yourself, in that we will critique your code, or point you in the (hopefully) right direction. So far, you just want someone to solve your conundrum for you... :-(

[L7Sqr]

@rubberman: I think the comment was to mean that he had been working on it already for two days without luck. The link is to an online progreamming competition so I doubt this is an assignment, per se.

[nitin1]

ohh! on what basis thing have you thought that it is a homwork ? have you ever seen any teacher giving homwork from a online judge ?

[deceptikon]

"Homework" in this sense is any small exercise that is intended for learning, practice, or personal gain.

• Learning exercises don't teach you much if you're told how to do it or given the solution.
• Practice exercises don't let you practice when someone else does it.
• Since the point of a competition is for you to solve the problem, being told the solution is tantamount to cheating.

If you've been working on this for two days then you should have no problem describing the many ways you've tried to solve it and how those solutions weren't sufficient. If you can't do that then your claim of working on it for two days rings untrue.

[Gonbe]

There's multiple ways to do this. This could be solved with (discrete) math alone although I think you're aiming for a more brute-force approach right?

In that case a logical start would be to implement the AdjBC() function. You don't have to start at the most significant bit for obvious reasons so it's not that hard. You could start with something like this:

    // Just random to illustrate.
    int number = 100;

    // Going through the bits starting at the least significant bit.
    while (number != 0)
    {
        // Access your current bit with "(number & 0x1)".
        printf("%d", (number & 0x1));

        // Advance to the next bit by bitshifting.
        number >>= 1;
    }

You have a basic structure now to access every bit of a number so the remaining task, determining the result of AdjBC(), should be something you could manage now.

From then on determining x using n and k would be easy to brute-force. (but inefficient) Seems like a pretty fun problem to solve, might try it once I am home..

[Gonbe]

Giving it some thought you should ignore the previous post as I think it's a poor way of solving it. it will work and it pretty easy but after thinking about it dynamic programming would make this pretty easy to solve as well without going into mathematics that much while yielding better performance.

The result of n,k could be formed depending on the last bit and then entering recursion to check subproblems. (if the bit is 1 (n-1, k-1) otherwise (n-1, k)) you can use dynamic programming to speed this up. It's also incomplete the way I describe it now but the essence of it should work.

if it ends with a 0 you could see it as a direct subproblem but if it ends in a 1 you have to take into account that 1 and it's not a direct subproblem. (but very closely related)

-edit-
actually, if it ends in one it would default to the subproblem of ending_with_zero(n-1, k) + ending_with_one(n-1, k-1). The first would result in the ending of 10 so k remains the same while the other would result in the ending of 11 so k is lessened and the recursion should mind that ending in a 1 again would lessen k by 1 again.

[nitin1]

exactly, my thought was just like this, but my prob was that should i use a 3D Dp here ? because for n,k and one for 1 or 0 ?

[WaltP]

Giving it some thought you should ignore the previous post

The more you backtrack like this (you've done it twice that I know of today) maybe you should give it some thought before posting... Maybe??? ;-)

[Gonbe]

The more you backtrack like this (you've done it twice that I know of today) maybe you should give it some thought before posting... Maybe??? ;-)

Oh look, one of the clowns from the other thread. Nice contribution to this thread as well bud. I assume you're still upset about the discussion in the other thread? Maybe you should reply to the questions asked in threads instead of contributing absolutely nothing and merely attempt to de-rail the thread by attempting to flame someone who is actually trying to help the OP... Maybe??? ;-).

Besides, I can't care less about your opinion so you're just wasting your time. I'm honored you're tracking my posts though. I feel bad for having upset you so easily. Oh wait, I don't.

exactly, my thought was just like this, but my prob was that should i use a 3D Dp here ? because for n,k and one for 1 or 0 ?

Yeah that's what I would do. The 3rd dimension having a fixed size of 2. (so in that sense you could also view it as 2 2-dimensional arrays)

-edit-

To elaborate on the "should" part of your question: you'll want to track 2 different types of subsets. There's not 1 generic sub-problem once going into the recursion but 2. (the n,k combination could be identical but the context can be different; The 'outer problem' ended in either a 1 or 0. So this context provides a slightly different problem hence storing their results seperately (in a 3rd dimension))