yaksha's blog

Help with a new type of Dynamic Programming
By yaksha, history, 7 years ago, In English

Hi all, I have been doing some dynamic programming problems and I stumbled around a Never seen before type of problem

Ofcourse the problem is new to me maybe because I am not much experienced but I still feel like the problem uses a unconventional style of DP and I am NOT able to understand it,

If some people have not tried DP , or want to try new problem on DP, attempt the problem,its a good one ( when doing with DP) : Problem : 276D - Девочка и максимальный XOR || Author's DP solution

Please help me understand the DP state and the transition,I tried understanding with editorial but was not able to after my best efforts,

Thankyou,looking forward to your help.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it might help you to see l and r as binary numbers — the easiest solution I can see looks like a greedy one

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

    The DP solution also see's l and r as binary numbers,

    Also,yeah the greedy solution is pretty easy to grasp and all,If I wanted to just solve the problem,I could have done the greedy way,,

    But the DP way is a new thing to learn for me,if you don't know the technique,instead of passing it,maybe I should learn about it.That's why tried a lot to understand it but coudn't

    → Reply