Help Alice in giving candies

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#

-
The task seems fine, but what's your justification for the language restriction? Such restrictions are generally frowned upon here, unless there is a particular reason why it has to be some particular language. And what's the winning criterion, anyway? Is this code golf? – leftaroundabout Aug 31 '12 at 20:52
What precisely does "Alice wants to give at least 1 candy for each child" mean? That the answer cannot be less than N, but that some children can receive 0? – Peter Taylor Aug 31 '12 at 21:14
@leftaroundabout This appears to have come from Interviewstreet, so I'd imagine the best algorithm would be the goal. How we'd measure that effectively though, I'm not sure. Comp-sci people, any suggestions? Also I'm not sure why the languages have been narrowed down, Interviewstreet appears to take entries in PHP, Python, Ruby, Perl, Haskell... – Gareth Aug 31 '12 at 21:46
@rmckenzie I thought that the example was wrong the same as you, but after rereading the question saw that the first number in the input is the number of children in the class. – Gareth Aug 31 '12 at 22:09
Ok, so two more questions. Firstly, am I correct to assume that higher number is higher rating, or is rmckenzie correct to assume that lower number is higher rating? Secondly, how is `1 2 1` a solution to children `1 2 2`? The 2s are equal, so unless they get the same number of candies one will be jealous of the other. – Peter Taylor Aug 31 '12 at 22:20

Java

``````import java.io.*;
class Alice {
public static void main(String[] args) throws IOException {
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.

-
Not that my solution is correct for this case, but it fails the input "5\n3\n2\n1\n\4\n4\n", being the ordering 3, 2, 1, 4, 4. In this case, 3 gets 1, 2 gets 2, 1 gets 3, and the fours get one each for a total of 8. Your program claims that three is sufficient in this case. – rmckenzie Sep 1 '12 at 1:38
@rmckenzie: first, I'm printing the max number any kid gets, not the total. I'll have to fix that. But also I'm treating higher rankings as better, you are doing the opposite. – Keith Randall Sep 1 '12 at 2:15
If you do that then the only provided test case is incorrect. The twos rank higher than the one, giving the candy count [1 2 2] for a total of five, not the four given in the spec. – rmckenzie Sep 1 '12 at 2:22
@rmckenzie: no, the kids can be satisfied with [1 2 1]. – Keith Randall Sep 1 '12 at 2:22
Oh yeah... OP never came back on that one. Yay bad spec! – rmckenzie Sep 1 '12 at 2:23

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
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.

-