Help Alice in giving candies

Question

Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.

Input

The first line of the input is an integer N, the number of children in Alice's class.
Each of the following N lines contains an integer indicates the rating of each child.

Ouput

Output a single line containing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Ouput

4

Explanation

The number of candies Alice must give are 1, 2 and 1.

Constraints:

N and the rating  of each child are no larger than 10^5.

Language Restrictions:

C++/Java/C#

Answer 1

Java

import java.io.*;
class Alice {
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(r.readLine());
    int[] ratings = new int[n];
    for (int i = 0; i < n; i++) ratings[i] = Integer.parseInt(r.readLine());
    System.out.println(minCandies(ratings));
  }
  private static int minCandies(int[] ratings) {
    int n = ratings.length;
    int[] reverseRatings = new int[n];
    for (int i = 0; i < n; i++) reverseRatings[n-1-i] = ratings[i];
    int[] forwardRun = findRunLengths(ratings);
    int[] reverseRun = findRunLengths(reverseRatings);
    int sum = 0;
    for (int i = 0; i < n; i++) sum += Math.max(forwardRun[i], reverseRun[n-1-i]);
    return sum;
  }
  private static int[] findRunLengths(int[] ratings) {
    int lastInRun = -1;
    int runLength = 0;
    int[] runs = new int[ratings.length];
    for (int i = 0; i < ratings.length; i++) {
      int r = ratings[i];
      if (r > lastInRun) {
        lastInRun = r;
        runLength++;
      } else {
        runLength = 1;
        lastInRun = r;
      }   
      runs[i] = runLength;
    }
    return runs;
  }
}

Uses the fact that a kid will need C candies iff there is a strictly increasing run of C ratings in either direction that ends at that kid. Just walks the array in each direction looking for runs and keeps the length of the run found ending at each kid. O(n) time.

Answer 2

Clojure - 2495

(ns alice)

(defn invert-derivative [d]
  (cond (= d <=) >=
        :else <= ))

(defn chunk-by-derivative [ivec]
  (loop [prev-seqs []
         prev-els  [(first ivec)]
         cur-derivative (if (<= (first ivec) (second ivec)) <= >=)
         remainder (rest ivec)]
    (let [cursor (first remainder)
          holds-trend (cur-derivative (last prev-els) (if (nil? cursor) 0 cursor))]
      (cond (empty? remainder) 
                (conj prev-seqs prev-els)

            holds-trend
                (recur prev-seqs 
                       (conj prev-els cursor) 
                       cur-derivative 
                       (rest remainder))
            :else
                (recur (conj prev-seqs prev-els)
                       [cursor]
                       (invert-derivative cur-derivative)
                       (rest remainder))))))

(defn candy-delta [ivec]
    (reduce (fn [pr c]
              (let [{:keys [value candies] :as previous 
                     :or {:value 0 :candies 1}} (last pr)]
                (conj pr
                      (cond (empty? pr) {:candies 1 :value c}
                            (= value c)    previous
                            (> value c)    {:value c :candies (inc candies)}
                            (< value c)    {:value c :candies (dec candies)}))))
            [] ivec))

(defn simple-min-candy [ivec]
  (let [m (apply min (map #(:candies %1) ivec))]
    (if (> 1 m) 
      (map #(assoc %1 :candies (+ (:candies %1) (- 1 m))) ivec) 
      ivec)))

(defn subseq-concat [s1 s2]
  (let [s1-l-candies (:candies (last s1))
        s1-l-value   (:value   (last s1))

        s2-f-candies (:candies (first s2))
        s2-f-value   (:value   (first s2))]
    (cond (and (> s1-l-value   s2-f-value)
               (< s1-l-candies s2-f-candies))
              (recur (let [delta (- s2-f-candies s1-l-candies)]
                       (map #(assoc %1 :candies (+ delta (:candies %1))) s1))
                     s2)
          :else (concat s1 s2))))

(defn join-subseqs [subseqs]
  (if (<= 2 (count subseqs))
    (reduce subseq-concat
            (first subseqs)
            (rest subseqs))
    (first subseqs)))

(defn pipeline [v]
  (->> v
      (chunk-by-derivative)
      (map candy-delta)
      (map simple-min-candy)
      (join-subseqs)
      (map #(:candies %1))
      (apply +)
      (println)))

(defn -main [& args]
  (let
    [line-count (read)
     v (map (fn [x] (read)) (range line-count))]
    (pipeline v)))

(-main)

Assumptions

• That the children numbered "2" rank below the child ranked "1"
• That two adjacent children of equal number should receive the same number of candies. Easy to change but until the OP clarifies the spec I'm keeping it that way.

General Algorithm

This solution is based on problem decomposition and composition of functions via the ->> operator.

The approach is to "chunk" the ordering of students into sub-orders which are increasing or decreasing. Using the simple approach outlined below which is correct in these cases, a partial candy count can be generated for each of these subsequences which is absolutely minimum for that sequence as argued below. Subsequences can then be joined by comparing the last value of the sequence to concatenate to and the first value of the sequence to be added, and if necessary adding a constant C to all elements of the sequence to be added to in order to ensure that the rank-based order property between children is maintained.

This approach is correct for the multi-delta case as it will consider the ordering [3 2 1 4 4] to be the two sequences [3 2 1] which is strictly increasing and receive respectively [1 2 3] pieces of candy and the sequence [4 4] which will receive the candy [1 1]. The concatenation of [1 2 3] and [1 1] respects the order property that child 1 receive more candy than any child 4 so the order is correct.

Algorithm for individual derivative constant sequences

This algorithm first generates a series of pairs [d, v] starting with [1, (first input value)] where the first element is the candy count of that child, being +1, +0, -1 from the last child. Note that these are ordered by the input (or seating) order, and thus correctly represent the minimum correct candy change between any pair of consecutive children [c, c'].

As the goal is to produce the number of total candies required, the first element of each pair is then taken to create a new sequence of numbers representing the candy count taken in comparison to the candy count of the child who happened to be seated first.

The last step then is to compute the final number of candies with regard to the child seated first. There are three cases here, all of which can be identified by the minimum number of candies given out to any one child.

1. The minimum is less than one. As all children must receive one or more candies all the children must gain K candies where K is 1 - (min chindren), thus guaranteeing that the bottom child receives exactly one candy.
2. The minimum is greater than one. An unreachable case, as the worst possible cases in terms of candy consumed are the increasing and decreasing sorts by rank. The decreasing sort would be handled by case 1, and the increasing sort would have a minimum value of 1 and require no further analysis.
3. The case where the minimum is one, so no further processing is required.

Correctness for all strictly increasing cases

For any strictly increasing ordering of children (c0 c1 c2 ... cn) the ith [counting from 0th] child will receive i + 1 pieces of candy. Consequently increasing the count of candy by one in the case of an increase in rank from [c -> c'] is necessarily correct.

Correctness for all strictly decreasing cases

By a similar argument, for any case where [c -> c'] is always decrease the subtraction of one candy from each child to the next is the minimum possible delta. The first biasing case then kicks in to ensure that the result guarantees one candy per child.

Correctness for all mixed cases

Any mixed sequence can be expressed as the composite of at least two sequences with different trends (being decreasing or increasing). By breaking such composite sequences into the trend-based subsequences, application of the known correct increasing/decreasing algorithm is trivially correct for all subsequences and a join of all subsequences which guarantees that the rank order property is preserved ensures that all resulting sequences are also minimal.

Test Cases

3
1
2
2

=> 4 being [2 1 1]

7
1
2
3
4
3
4
5

=> 20 being [5 4 3 2 3 2 1]

8
1
2
1
2
1
2
1
2

=> 12 being [2 1 2 1 2 1 2 1]

Bugs

If there are any please smack me upside the head for being a cocky jerk. This composition of functions should be generally correct but I do not doubt my capacity for overlooking my own errors.