UCF HSPT 2016 - Chomp Chomp

Question

我在尋找UCF HSPT編程競賽中問題＃9的有效解決方案時遇到了很多麻煩。整個pdf可以查看here，問題叫做「Chomp Chomp！」。

本質上來說，問題涉及從數組中取出2個「chomps」，其中每個chomp是數組中連續的元素鏈，並且2個chomps必須至少有它們之間不是「chomped」的元素。一旦確定了兩個「chomps」，兩個「chomps」中所有元素的總和必須是輸入中給定數字的倍數。我的解決方案基本上是一種蠻力，它貫穿每一個可能的「chomp」，我試圖通過存儲以前計算的chomps總和來提高速度。

我的代碼：

import java.util.Arrays; 
import java.util.HashMap; 
import java.util.Scanner; 

public class chomp { 
    static long[] arr; 

    public static long sum(int start, int end) { 
     long ret = 0; 
     for(int i = start; i < end; i++) { 
      ret+=arr[i]; 
     } 
     return ret; 
    } 

    public static int sumArray(int[] arr) { 
     int sum = 0; 
     for(int i = 0; i < arr.length; i++) { 
      sum+=arr[i]; 
     } 
     return sum; 
    } 

    public static long numChomps(long[] arr, long divide) { 
     HashMap<String, Long> map = new HashMap<>(); 
     int k = 1; 
     long numchomps = 0; 
     while(true) { 
      if (k > arr.length-2) break; 
      for (int i = 0; i < arr.length -2; i++) { 
       if ((i+k)>arr.length-2) break; 
       String one = i + ""; 
       String two = (i+k) + ""; 
       String key1 = one + " " + two; 
       long first = 0; 
       if(map.containsKey(key1)) { 
        //System.out.println("Key 1 found!"); 
        first = map.get(key1).longValue(); 
       } else { 
        first = sum(i, i+k); 
        map.put(key1, new Long(first)); 
       } 
       int kk = 1; 
       while(true){ 
        if (kk > arr.length-2) break; 
        for (int j = i+k+1; j < arr.length; j++) { 
         if((j+kk) > arr.length) break; 
         String o = j + ""; 
         String t = (j+kk) + ""; 
         String key2 = o + " " + t; 
         long last = 0; 
         if(map.containsKey(key2)) { 
          //System.out.println("Key 2 found!"); 
          last = map.get(key2).longValue(); 
         } else { 
          last = sum(j, j+kk); 
          map.put(key2, new Long(last)); 
         } 
         if (((first+last) % divide) == 0) { 
          numchomps++; 
         } 
        } 
        kk++; 
       } 
      } 
      k++; 
     } 
     return numchomps; 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     Scanner in = new Scanner(System.in); 
     int n = Integer.parseInt(in.nextLine()); 
     for(int i = 1; i <= n; i++) { 
      int length = in.nextInt(); 
      long divide = in.nextLong(); 
      in.nextLine(); 
      arr = new long[length]; 
      for(int j = 0; j < length; j++) { 
       arr[j] = (in.nextLong()); 
      } 
      //System.out.println(arr); 
      in.nextLine(); 
      long blah = numChomps(arr, divide); 
      System.out.println("Plate #"+i + ": " + blah); 
     } 

    } 

} 

我的代碼得到正確的答案，但似乎太長了，特別是對於大的投入，當數組的大小爲1000或更大。我試圖提高我的算法的速度，我存儲了以前計算在HashMap中的總和，但這並沒有顯着提高我的程序速度。我能做些什麼來提高速度，以便在10秒內運行？

Answer 1

無效率的第一個來源是不斷重新計算總和。您應該製作部分款項的輔助陣列long [n] partial;，然後您可以簡單地執行partial[i + k] - partial[i]而不是致電sum(i, i + k)。

現在的問題簡化爲查找索引i<j<k<m這樣

(partial[j] - partial[i] + partial[m] - partial[k]) % divide == 0 

，或者重新安排方面，

(partial[j] + partial[m]) % divide == (partial[i] + partial[k]) % divide 

要找到他們，你可以考慮三元(s, i, j)數組，其中s = (partial[j] - partial[i]) % divide，穩定的排序它通過s，並檢查不重疊的「chomps」的相等範圍。

該方法提高了從O（n ）到O（n log n）的性能。現在你可以將它改進爲O（n log n）。