kleemans.ch

Die etwas anspruchsvollere Aufgabe des SRM 505, PerfectSequences (siehe Problem Statement), verlangte, dass eine bestimmte Zahlensequenzen darauf überprüft wird, ob Sie "perfekt" ist oder man diese mit 1 Änderung “perfekt” gemacht werden könnte.

Perfekt heisst hier: Alle Zahlen sind nicht negativ (>=0) und zudem Summe = Produkt.

Perfekte Sequenzen sind z.B. {2,2} (Summe, Produkt = 4), {1,2,3}, und {1,1,2,4}

Mir war recht schnell klar, dass es nur mit kleinen Zahlen funktioniert, da sonst das Produkt schnell zu gross wird. Die Möglichkeit, Summen auszugleichen, besteht mit einfach Einsen hinzuzufüllen, welche das Produkt nicht beeinflussen. Die Eingabe ist auf 50 Zahlen beschränkt, also geht es maximal bis Zahlen mit 50.

Das eigentliche Problem ist nun aber nicht nur zu überprüfen, ob eine Eingabe eine perfekte Sequenz ist, sondern zu überprüfen, ob mit genau einer Änderung eine solche generiert werden könnte.

Die Lösungsidee ist, zuerst sehr hohe Eingaben auszusortieren (z.B. {10000,10000,100000,10000}), da Brute Force bei diesen zu lange dauern würde (Zeitlimit für Algorithmen in SRM: 2 Sekunden). Danach kann mit Brute Force jeder der maximal 50 Einträge ersetzt werden mit Zahlen kleiner gleich 50, und ist bei einer Kombination Summe = Produkt, kann “Yes” zurückgegeben werden (andernfalls “No).

Beispiele:

• {2,6} -> Ja, möglich: {2,2} (4)
• {1,1,1,1,5} -> Ja, möglich: {1,1,1,2,5} (10)
• {1,1,1,5} -> Nicht möglich.

Für mich gab’s leider auch hier keine Punkte, da ich nur bis 49 gesucht hatte, und ein Test war die Sequenz {1,1,1,1,…,2,50}, welche sowohl als Summe wie auch als Produkt die Zahl 100 hat und somit gültig ist. :(

Die Funktion perfectSeq(int[] seq) berechnet dabei die Summe und das Produkt einer gegebenen Zahlensequenz.

Korrigierte Version des Quellcodes:

public class PerfectSequences {
  public String fixIt(int[] seq) {
    String answer = "No";

    //one single number
    if (seq.length == 1)
      return "Yes";

    //if 2 numbers are over average and sum > 100, it cant be a perfect sequence
    int sum =0;
    for (int i=0;i
      sum += seq[i];
    }
    int count=0;
    for (int i=0;isum/seq.length+1)
        count++;
    }

    if (sum/seq.length>3 && count>1)
      return "No";

    //brute force change with 1, 2, 3, 4, 5... until prod is greater than sum
    int save = 0;
    int[] check = new int[2];
    for (int i=0;i
      for (int z=1;z<=50;z++) {
        if (z==seq[i]) continue;
        save = seq[i];
        seq[i] = z;
        check = perfectSeq(seq);
        //if yes return
        if (check[0]==check[1])
          return "Yes";
        //if no
        else
          seq[i] = save;
        //if prod greater than sum go to next number
        if (check[0]
          break;
      }
    }

    return answer;
  }

  private int[] perfectSeq(int[] seq) {
    int[] result = new int[2];
    int sum = 0;
    int prod = seq[0];
    for (int i=0;i0)
        prod *= seq[i];
    }
    result[0] = sum;
    result[1] = prod;
    return result;
  }

}