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 02:53:06 +0530Answer 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