Code Chef RAINBOW Palindrome Problem


  Determine whether an array is "Rainbow", i.e. it has the following
  structure:
  
  
  First a1 elements equal 1.
  Next a2 elements equal 2.
  Next a3 elements equal 3.
  Next a4 elements equal 4.
  Next a5 elements equal 5.
  Next a6 elements equal 6.
  Next a7 elements equal 7.
  Next a6 elements equal 6.
  Next a5 elements equal 5.
  Next a4 elements equal 4.
  Next a3 elements equal 3.
  Next a2 elements equal 2.
  Next a1 elements equal 1.
  
  
  ai can be any positive integer. There are no other elements in array.


Solution

(defn palindrome? [items]
  "Efficient algorithm: loops through only (array-size/2)"
  (loop [i 0
         j (-&gt; items count dec)]
    (cond (&gt;= i j)
          true
          (not= (nth items i) 
                (nth items j))
          false
          :else
          (recur (inc i) (dec j)))))

(let [test-cases-count (Integer/parseInt (read-line))
      test-cases       (for [i (range test-cases-count)]
                         (let [nums-count (read-line)
                               nums-temp (-&gt; (read-line) (clojure.string/split #"\s+"))
                               nums (map #(Integer/parseInt %) nums-temp)]
                           nums))]
  (for [t test-cases]
    (if (palindrome? t)
      (println "Yes")
      (println "No"))))


Not able to figure out how to optimize this.
(defn palindrome? [items]
  "Efficient algorithm: loops through only (array-size/2)"
     ...
         (not= (nth items i) 
               (nth items j))


nth is efficient on vectors and other things that support random indexing. On sequences, which you're passing in right now, it's O(n) per lookup since it has to walk the list.

Changing your test cases to use vectors should help (use mapv instead of map):

(let [...
      nums (mapv #(Integer/parseInt %) nums-temp)]




(def example (concat (range 1000) (reverse (range 1000))))
(count example)   ; 2000
(def examplev (vec example))
(count examplev)  ; 2000

(dotimes [_ 3] (time (palindrome? example)))
; "Elapsed time: 45.167334 msecs"
; "Elapsed time: 44.568282 msecs"
; "Elapsed time: 45.304136 msecs"

(dotimes [_ 3] (time (palindrome? examplev)))
; "Elapsed time: 0.317649 msecs"
; "Elapsed time: 0.272229 msecs"
; "Elapsed time: 0.30044 msecs"