×

# PROC18C(Awkward Pairs)- Help

 0 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 :) @joffan i read your discussion but couldnt understand , please if you could elaborate :D thank you. PROC18C asked 22 Nov '18, 16:28 -7●3 accept rate: 0%

 0 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. answered 28 Nov '18, 02:53 1.1k●1●8 accept rate: 10% Thanks so much :D @xariniov9 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. (28 Nov '18, 11:38)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,085
×54

question asked: 22 Nov '18, 16:28

question was seen: 373 times

last updated: 28 Nov '18, 11:38