PROC18C(Awkward Pairs)- Help

general
,
1

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 :slight_smile:
@joffan i read your discussion but couldnt understand , please if you could elaborate :smiley: thank you.
PROC18C

2

Hi,

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.

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.

Coming back to finding the count of each sum, it is a very simple DP. I would suggest you to go through recursion from here and solve some simple DP problems first.

3

Thanks so much :smiley: @xariniov9 i figured sum of all digits wont exceed 200 if you could write the recurrence relation though it would be nice :stuck_out_tongue: thanks anyways for the the link too.