مشكلة البرمجة - لعبة الكتل

Question

ربما سيكون لديك فكرة عن كيفية حل ما يلي مشكلة.

قرر جون أن يشتري لابنه جوني بعض الألعاب الرياضية.واحدة من أكثر ألعابه المفضلة هي كتل من ألوان مختلفة.قرر جون شراء كتل من C بألوان مختلفة.لكل لون سيشتري كتل googol (10^100).جميع الكتل من نفس اللون لها نفس الطول.لكن الكتل ذات الألوان المختلفة قد تختلف في الطول.قرر جوني استخدام هذه الكتل لإنشاء كتلة كبيرة مقاس 1 × n.إنه يتساءل عن عدد الطرق التي يمكنه من خلالها القيام بذلك.تعتبر طريقتان مختلفتان إذا كان هناك موضع يختلف فيه اللون.يوضح المثال كتلة حمراء بحجم 5، وكتلة زرقاء بحجم 3 وكتلة خضراء بحجم 3.ويوضح أن هناك 12 طريقة لصنع كتلة كبيرة طولها 11.

تبدأ كل حالة اختبار بعدد صحيح 1 ≥ C ≥ 100.يتكون السطر التالي من الأعداد الصحيحة c.يشير العدد الصحيح 1 ≥ leni ≥ 750 إلى طول اللون i.السطر التالي هو عدد صحيح موجب N ≥ 10^15.

يجب حل هذه المشكلة خلال 20 ثانية لـ T <= 25 حالة اختبار.يجب أن تحسب الإجابة MOD 100000007 (رقم اولي).

يمكن استخلاصها من مشكلة الأس المصفوفة، والتي يمكن حلها بكفاءة نسبيًا في O(N^2.376*log(max(leni))) باستخدام كوبسميث فينوغراد الخوارزمية والأس السريع.ولكن يبدو أن هناك حاجة إلى خوارزمية أكثر كفاءة، حيث يشير كوبرسميث-فينوغراد إلى عامل ثابت كبير.هل لديك أي أفكار أخرى؟من الممكن أن تكون نظرية الأعداد أو مشكلة فرق تسد

Answer 1

يرجى الاطلاع TopCoder Thread لحل. لم يكن أحد قريبًا بما يكفي للعثور على الإجابة في هذا الموضوع.

Answer 2

لاحظ أولاً أن عدد كتل كل لون لديك هو رنجة حمراء كاملة ، لأن 10^100> N دائمًا. وبالتالي فإن عدد كتل كل لون لا حصر لها من الناحية العملية.

لاحظ الآن أنه في كل موقف ، p (إذا كان هناك تكوين صالح ، لا يترك أي مسافات ، وما إلى ذلك) يجب أن يكون هناك حظر من اللون ، c. هناك len[c] طرق لكذب هذه الكتلة ، بحيث لا تزال تكمن على هذا الموقف ، p.

فكرتي هي تجربة جميع الألوان والمواقف الممكنة في وضع ثابت (N/2 نظرًا لأنه يقوم بنقص النطاق) ، ثم لكل حالة ، هناك b الخلايا قبل هذه الكتلة الملونة الثابتة و a بعد كتلة الألوان الثابتة هذه. لذلك إذا حددنا وظيفة ways(i) هذا يعيد عدد الطرق إلى البلاط i الخلايا (مع ways(0)=1). ثم عدد الطرق للبلاط لعدد من الخلايا مع كتلة لون ثابت في الموضع ways(b)*ways(a). إن إضافة جميع التكوينات الممكنة تعطي الإجابة ways(i).

الآن اخترت الموقف الثابت ليكون N/2 نظرًا لأن هذا النصف يمكن أن يرفع النصف إلى النصف على الأكثر ceil(log(N)) مرات. الآن بما أنك تتحرك كتلة حول N/2 سيكون عليك حساب من N/2-750 ل N/2-750, ، أين 750 هل طول الحد الأقصى الذي يمكن أن يكون له كتلة. لذلك سيكون عليك حساب حول 750*ceil(log(N)) (أكثر قليلاً بسبب التباين) أطوال للحصول على الإجابة النهائية.

لذلك من أجل الحصول على أداء جيد يجب عليك من خلاله في المذكرات ، لأن هذه الخوارزمية العودية بطبيعتها.

لذا باستخدام Python (منذ أن كنت كسولًا ولم أرغب في كتابة فئة كبيرة من الأرقام):

T = int(raw_input())

for case in xrange(T):
    #read in the data
    C = int(raw_input())
    lengths = map(int, raw_input().split())
    minlength = min(lengths)
    n = int(raw_input())

    #setup memoisation, note all lengths less than the minimum length are
    #set to 0 as the algorithm needs this
    memoise = {}
    memoise[0] = 1
    for length in xrange(1, minlength):
       memoise[length] = 0

    def solve(n):
        global memoise
        if n in memoise:
            return memoise[n]

        ans = 0
        for i in xrange(C):
            if lengths[i] > n:
                continue
            if lengths[i] == n:
                ans += 1
                ans %= 100000007
                continue 
            for j in xrange(0, lengths[i]):
                b = n/2-lengths[i]+j
                a = n-(n/2+j)
                if b < 0 or a < 0:
                    continue
                ans += solve(b)*solve(a)
                ans %= 100000007
        memoise[n] = ans
        return memoise[n]
    solve(n)
    print "Case %d: %d" % (case+1, memoise[n])

لاحظ أنني لم أختبر هذا بشكل شامل ، لكنني متأكد تمامًا من أنه سيفي بالحد من 20 ثانية ، إذا قمت بترجمة هذه الخوارزمية إلى C ++ أو Somesuch.

تحرير: إجراء اختبار مع N = 10^15 وكتلة بطول 750 أحصل على ذلك memoise يحتوي على 60000 العناصر التي تعني القليل من النظرة solve(n) يتم استدعاؤه حول نفس عدد الوقت.

Answer 3

كلمة تحذير: في الحالة C = 2 ، LEN1 = 1 ، LEN2 = 2 ، ستكون الإجابة هي رقم N'th Fibonacci ، وتنمو أرقام فيبوناتشي (تقريبًا) مع عامل نمو للنسبة الذهبية ، PHI ~ 1.61803399. بالنسبة للقيمة الضخمة n = 10^15 ، ستكون الإجابة حول phi^(10^15) ، وهو رقم هائل. سيكون للإجابة متطلبات تخزين بترتيب (ln (phi^(10^15)) / ln (2)) / (8 * 2^40) ~ 79 terabytes. بما أنك لا تستطيع حتى التمكن من 79 terabytes في 20 ثانية ، من غير المحتمل أن تتمكن من تلبية متطلبات السرعة في هذه الحالة الخاصة.

يحدث أفضل أمل لك عندما لا يكون C كبيرًا جدًا ، ويني كبير لكل ما أنا. في مثل هذه الحالات ، ستظل الإجابة تنمو بشكل كبير مع N ، لكن عامل النمو قد يكون أصغر بكثير.

أوصي بأن تقوم أولاً ببناء مصفوفة عدد صحيح M والتي ستحسب مصطلحات (i+1 ، ... ، i+k) في تسلسلك استنادًا إلى شروط (i ، ... ، i+k-1). (فقط الصف K+1 من هذه المصفوفة مثيرة للاهتمام). حساب إدخالات K الأولى "باليد" ، ثم احسب M^(10^15) بناءً على الخدعة المتكررة المتكررة ، وتطبيقها على الشروط (0 ... K-1).

ستنمو إدخالات (عدد صحيح) من المصفوفة بشكل كبير ، وربما بسرعة كبيرة في التعامل معها. إذا كان هذا هو الحال ، فقم بنفس الحساب ، ولكن Modulo P ، لعدة أعداد رئيسية معتدلة الحجم p. سيتيح لك ذلك الحصول على إجابتك Modulo P ، لمختلف P ، دون استخدام مصفوفة من BigInts. بعد استخدام ما يكفي من الأعداد الأولية حتى تعرف أن منتجها أكبر من إجابتك ، يمكنك استخدام ما يسمى "نظرية الباقي الصينية" لاستعادة إجابتك من إجابات MOD-P الخاصة بك.

Answer 4

أرغب في البناء على حل @JPvdMerwe السابق مع بعض التحسينات.في إجابته، @JPvdMerwe يستخدم أسلوب البرمجة الديناميكية/الحفظ، والذي أوافق على أنه هو الطريق الصحيح لحل هذه المشكلة.يعد تقسيم المشكلة بشكل متكرر إلى مشكلتين أصغر وتذكر النتائج المحسوبة مسبقًا أمرًا فعالاً للغاية.

أود أن أقترح العديد من التحسينات التي من شأنها تسريع الأمور بشكل أكبر:

1. بدلًا من مراجعة جميع الطرق التي يمكن من خلالها وضع الكتلة في المنتصف، ما عليك سوى مراجعة النصف الأول وضرب الحل في 2.وذلك لأن النصف الثاني من الحالات متماثل.بالنسبة للكتل ذات الطول الفردي، ستظل بحاجة إلى اتخاذ الموضع المركزي كحالة منفصلة.

2. بشكل عام، يمكن أن تكون التطبيقات التكرارية أسرع بعدة مقادير من التطبيقات العودية.وذلك لأن التنفيذ العودي يفرض حملاً إضافيًا على مسك الدفاتر لكل استدعاء دالة.قد يكون من الصعب تحويل الحل إلى ابن عمه التكراري، ولكن هذا ممكن عادةً.يمكن جعل حل @JPvdMerwe متكررًا باستخدام مكدس لتخزين القيم المتوسطة.

3. عمليات Modulo باهظة الثمن، وكذلك الضرب بدرجة أقل.يمكن تقليل عدد الضربات والمعاملات بمقدار عامل C = 100 تقريبًا عن طريق تبديل حلقة اللون مع حلقة الموضع.يتيح لك هذا إضافة قيم الإرجاع لعدة استدعاءات لـsolve() قبل إجراء الضرب والمعامل.

هناك طريقة جيدة لاختبار أداء الحل وهي الحالة المرضية.قد يكون ما يلي أمرًا شاقًا بشكل خاص:الطول 10^15، C=100، أحجام الكتل الأولية.

أتمنى أن يساعدك هذا.

Answer 5

في الجواب أعلاه

    ans += 1
    ans %= 100000007

يمكن أن يكون أسرع بكثير بدون عام Modulo:

    ans += 1
    if ans == 100000007 then ans = 0