Please Help Me - I Need Algorithm

attachment.php?attach_id=e2c99dda7043b0db1531f0ecbf460681&mid=id.262193397163391&ext=1322243664&hash=AQBkULFH5irKqTYh

i have two days to solve it :S

please any ideas ?!

Comments

  • I wrote this program but i will not get a result in two days !
        class Program
        {
            static bool sumDigit(int number)
            {
                int sum=0;
                while ((number) != 0)
                {
                    sum += number % 10;
                    number /= 10;
                }
                return (sum == 23);
            }
            static void Main(string[] args)
            {
                int base_num = int.Parse(Console.ReadLine());
                int power = int.Parse(Console.ReadLine());
                double n = Math.Pow(base_num, power);
                int counter = 0;
                for (int i = 23; i < Math.Pow(10, n); i=i+23)
                {
                    if (sumDigit(i))
                    {
                        counter++;
                    }
                }
                Console.WriteLine(counter);
            }
        }
    
  • Please place your code inside of [noparse]
    
    
    [/noparse] tags. I have edited them in for you.

    The image you posted seems to be broken.
  • yassin1.jpg

    Uploaded with ImageShack.us

    here is the qustion.. :S
  • The first thing that should be obvious is that, not only is 10^(11^12) too large to brute force (as you pointed out), but it's also too large to even fit in memory. It's a 3138428376721 digit number! That means around 2 terrabytes to even represent that number in binary.

    This should hint to you that you're going to have to be a lot smarter about how you approach this problem. You're going to have to try to exploit patterns created by the conditions, and probably avoid recomputing quantities that can be used within other contexts.

    I haven't given it much thought, but one possible approach might be to divide-and-conquer on the decimal representation of n (but this could take days), or at the very least re-use quantities that you've computed for individual segments.

    Also note that there are only so many ways that digits can add up to exactly 23. The rest of the digits will all have to be zero. That's probably the most useful restriction.

    Start thinking about how these patterns look. Perhaps brush up on your combinatorics.
  • take it as a challenge :P

    I challenge you ! to solve it in 24 hours :$

    and I'll be thankfull..

    this is a qustion in Algorithms course..
  • Although I do appreciate interesting problems, I'm a homework helper, not a homework do-er. I'd be much happier to see you solve it.

    What chapter/section is this question under? I'm asking because that's already a huge hint as to how it might be solved.
  • this is under the Flow network

    and I will be happier if I solve it ,appreciating your help...
  • Dividing and conquering the decimal representation of 11^12 wouldn't take days... edit: you mean the decimal representation of 10^11^12, do you not?

    Here's another hint: Sane basically told you how to do the problem. And if m = 23 computing S(n) generally takes O(m*log n) time.
  • I did mean the decimal representation of 10^11^12, so 'n' digits. Thanks. My guess on how long that would take is hazy. Edit: The divide and conquer I was thinking of was O(nlogn), but I hadn't thought about it, and that might be silly. O(mlogn) would be extremely quick. I will give this more thought when I'm not at work.

    Why the hell is this in the network flow chapter?
  • Sane wrote:
    I did mean the decimal representation of 10^11^12, so 'n' digits. Thanks. My guess on how long that would take is hazy. Edit: The divide and conquer I was thinking of was O(nlogn), but I hadn't thought about it, and that might be silly. O(mlogn) would be extremely quick. I will give this more thought when I'm not at work.

    Yeah, the difference here is that the "divide and conquer" is more like the kind seen in exponentiation or binary search, not in sorting.
Sign In or Register to comment.