@atul as the problem said i have to find Nth PDS number so N could be 10^9 so 9 digits and pds number can be of 10digits so scanning from 1 to 10^10 in each case (because we can make such a large hash) will cross time limits as there would be 10000 test cases so it become 10^14 and which can't complete in 20s so need some dp algo..... http://www.codechef.com/wiki/april-2012-contest-problem-editorials here is link to solution but i cant understand it... if some one get that what approach they used please explain. Thanks
On Sat, Apr 21, 2012 at 8:29 PM, atul anand <[email protected]> wrote: > numbers from 1 to 9 and 10,20,30,40....90 are pds number . so you just > need on if() check to count it directly when this numbers occurs no need of > checking these numbers by applying reverse and checking .... for all other > numbers this can be done. > > On Sat, Apr 21, 2012 at 2:02 AM, Ramindar Singh <[email protected]>wrote: > >> Just to add to Vandana >> >> certain observations like >> >> 1) consider 1,2,3,4..... 9 as 01,02,03,04...... 09 so the reverse of >> the strings are also present in the answer ie 10,20,30,40.... 90 >> 2) when you traverse the numbers like 11,12,13,14.... 19 and you dont >> find any PDS number you are omitting the numbers 21,31,41,51.... 91 so you >> need not to verify on these numbers >> Also in the next traversal you are not checking it for 21 as explained >> and for 22,23,24.... 29 you would omit the numbers 32,42,52.... 92 >> In the next line for 33,34,35,36....39, we have a PDS number 36 and also >> we have its reverse 63 as a PDS. >> >> So by the time you reach the 9* line you just need to verify the 99 digit >> as you have verified the others earlier. >> Hope this helps :) >> >> >> Thanks >> Ramindar Singh >> >> On Friday, 20 April 2012 23:49:48 UTC+5:30, amrit harry wrote: >>> >>> http://www.codechef.com/**APRIL12/problems/PDSNUM<http://www.codechef.com/APRIL12/problems/PDSNUM> >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/m1GvKl8FWcMJ. >> >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- AMRIT -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
