Answers to: PROC18C(Awkward Pairs)- Helphttps://discuss.codechef.com/questions/140957/proc18cawkward-pairs-help<p>This was one of the problems i was trying to solve and i looked for some submissions they were DP, I was unable to understand I am newbie in DP if anyone could help highly appreciated :)
<a href="/users/325448/joffan">@joffan</a> i read your discussion but couldnt understand , please if you could elaborate :D thank you.
<a href="https://www.codechef.com/PROC2018/problems/PROC18C">PROC18C</a> </p>enWed, 28 Nov 2018 11:38:04 +0530Comment by insanity_123 on xariniov9's answerhttps://discuss.codechef.com/questions/140957/proc18cawkward-pairs-help#141242<p>Thanks so much :D <a href="/users/107941/xariniov9">@xariniov9</a> i figured sum of all digits wont exceed 200 if you could write the recurrence relation though it would be nice :P thanks anyways for the the link too.</p>insanity_123Wed, 28 Nov 2018 11:38:04 +0530https://discuss.codechef.com/questions/140957/proc18cawkward-pairs-help#141242Answer by xariniov9https://discuss.codechef.com/questions/140957/proc18cawkward-pairs-help/141223<p>Hi,</p>
<p>The problem is not very difficult if you observe that sum of digits cannot be very large. That is the largest sum can be from the number with all 9's, which is around 150.</p>
<p>Now, if you calculate the count of each possible sum, finding total number of awkward pairs is straight forward. You just need check all the pairs with gcd = 1 and adding their product to the answer.</p>
<p>Coming back to finding the count of each sum, it is a very simple DP. I would suggest you to go through recursion from <a href="https://xariniov9.wordpress.com/" title="here">here</a> and solve some simple DP problems first.</p>xariniov9Wed, 28 Nov 2018 02:53:06 +0530https://discuss.codechef.com/questions/140957/proc18cawkward-pairs-help/141223