CCO '15 P1 - Hungry Fox

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 1G
Author:
SourSpinach
Problem type
Canadian Computing Olympiad: 2015 Day 1, Problem 1

It's dinner time for your pet fox! His meal consists of N crackers, with the i^\text{th} cracker having a temperature of T_i degrees Celsius. He also has a large dish of water, which has a temperature of W degrees Celsius.

After taking an initial sip of water, your fox begins his meal. Every time he eats a cracker, its tastiness is equal to the absolute difference between its temperature, and the temperature of the last thing he ate or drank (be it the previous cracker he ate, or a sip of water, whichever he consumed most recently). He can drink some water whenever he wants. Depending on the order in which your fox eats and drinks, the total tastiness of the crackers consumed may vary. What are the minimum and maximum values it can have?

Input Specification

The first line contains two integers, N (1 \le N \le 100\,000) and W (0 \le W \le 10^9), representing the number of crackers and the water's temperature. On the next N lines, there is one integer, T_i (0 \le T_i \le 10^9 for 1 \le i \le N), representing the temperature of the i^\text{th} cracker.

For at least 30% of the marks for this problem, W = 0.

Output Specification

The output is one line containing two integers: the minimum and maximum total tastiness your fox can experience during his meal, respectively.

Sample Input

3 20
18
25
18

Output for Sample Input

7 16

Explanation of Output for Sample Input

To minimize the total tastiness, the fox might drink water, eat the first cracker, eat the third cracker, drink more water, and finally eat the second cracker. He will then experience temperatures of 20, 18, 18, 20, and 25 degrees Celsius, and the crackers will have tastiness values of 2+0+5 = 7.

To maximize the total tastiness, the fox might drink water, and then eat the crackers in order. He will then experience temperatures of 20, 18, 25, and 18 degrees Celsius, and the crackers will have tastiness values of 2+7+7 = 16.

Comments


  • 0
    aaronhe07  commented on Oct. 4, 2022, 7:12 p.m.

    This is probably the toughest greedy algorithm problem I managed to solve without any help. Also, I'm 8th on the submission leaderboard somehow?


  • 29
    moladan123  commented on Dec. 15, 2015, 3:29 a.m. ← edited

    You know, it is pretty typical for the ccc to have pretty absurd numbers, but having a 10^9 °C cracker is pretty insane. To compare, the core of our sun is measly 2.7 * 10^7 °C. I must say that these are very hot crackers. Very, very hot crackers. I wonder what kind of fox this is.


  • 2
    kobortor  commented on Aug. 19, 2015, 10:16 p.m. 
    5 0
23 30 48 42 49

    • 0
      awaykened  commented on Aug. 19, 2015, 10:49 p.m. ← edited 
      49 195

      • 1
        kobortor  commented on Aug. 19, 2015, 10:53 p.m.

        How did you get the 195?


        • 8
          awaykened  commented on Aug. 19, 2015, 10:56 p.m.

          I plugged it into Andy's solution on my laptop


          • 3
            kobortor  commented on Aug. 19, 2015, 10:58 p.m. ← edited

            Idk, I'm taking a drink of water after eating each cracker, so I reset the temperature back to 0.

            This way I'm getting 23 + 30 + 48 + 42 + 49 = 192

            Edit: Nevermind, it seems the solution is to take

            49, 23, water, 30, water, 48, water 42 which gives 195.


            • 2
              awaykened  commented on Aug. 19, 2015, 11:00 p.m. ← edited

              that isn't optimal

              edit: proof: andy's solution gives a different answer