Schneller Algorithmus als verschachtelte Schleifen?

Question

Für die google codeJam Qualifizierungsrunde war eines der Probleme herauszufinden, wie viele "recycelte Paare" es zwischen zwei gegebenen Ganzzahlen gibt.

Dies war meine Lösung, aber es war nicht schnell genug für den großen Dateneingangssatz. Bei etwas wie @a = 10, @b = 200000 wird es langsam.

Ich denke, meine Lösung wäre O (2^n) (ich habe noch keinen festen Griff auf große O-Analyse) was schrecklich ist. Ich habe mich gefragt, ob es eine Standardmethode gibt, zwei Schleifen mit einem schnelleren Algorithmus zu durchlaufen.

def getPairs 
    (@a..@b).each do |n| 
     (n..@b).each do |m| 
     if (containsSame(n,m)) && (isMatch(@a, n, m, @b)) 
      @recycledPairs += 1 
     end 
     end 
    end 
    end 

edit: Von Google CodeJam site:

Lasst uns ein paar verschiedene positive ganze Zahlen sagen (n, m) zurückgeführt wird, wenn Sie m, indem einige Ziffern von der Rückseite des n die erhalten Front, ohne ihre Reihenfolge zu ändern. Zum Beispiel ist (12345, 34512) ein recyceltes Paar, da Sie 34512 erhalten können, indem Sie 345 vom Ende von 12345 nach vorne verschieben. Beachten Sie, dass n und m die gleiche Anzahl von Ziffern haben müssen, um ein recyceltes Paar zu sein. Weder n noch m können führende Nullen haben.

Answer 1

Sie können the official analysis of this problem für die richtige Lösung lesen.

Grundsätzlich besteht die Lösung darin, alle eindeutigen Rotationen größer als n zu berechnen, jedoch nicht größer als B für jeden n.

Answer 2

Die Beschreibung sagt "Beachten Sie, dass n und m die gleiche Anzahl von Ziffern haben müssen, um ein recyceltes Paar zu sein."

Ihre innere Schleife berücksichtigt das nicht. Wenn @a = 2 und @b = 20.000, können Sie ganze Stücke der inneren Schleife ausschneiden. Wenn n zweistellig ist, müssen Sie nur zwei Ziffern von m testen. Schaue genau auf die obere Grenze deiner inneren Schleife.

Answer 3

Aus der Aussage: max b ist höchstens 2 * 10^6. Wie bei allen Codejam-Problemen gibt es auch Multi-Tests.

Schritt 1: Vorcal. Für jede Zahl n = [1..maxb], alle von ihm Zahlen zyklisiert speichern, die dann weniger streng sind (nicht mehr als 7 für jeden) z.B

10 - 1 
321 - 132, 213 

Schritt 2: für jeden Test. Gehen Sie durch jede Nummer von A nach B und zählen Sie die Anzahl der Zyklen zwischen A und B.

Zeit Komplexität: Schritt 1 arbeitet in (Anzahl der Ziffern) für jede Zahl, dh O (ln n) . Du musst es b mal machen. Alles in allem O (b * ln b). Gleiches gilt für Schritt 2. Dies funktioniert weniger als eine Sekunde bei großen Testfällen.