You are not logged in. Please login at www.codechef.com to post your questions!

×

PROC18C(Awkward Pairs)- Help

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

insanity_123's gravatar image

3★insanity_123
-73
accept rate: 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.

link

answered 28 Nov '18, 02:53

xariniov9's gravatar image

6★xariniov9
1.1k18
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) insanity_1233★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,172
×58

question asked: 22 Nov '18, 16:28

question was seen: 388 times

last updated: 28 Nov '18, 11:38