CCC '23 S2 - Symmetric Mountains - Olympiads Online Judge

CCC '23 S2 - Symmetric Mountains

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 1G

Author:

Problem type

Canadian Computing Competition: 2023 Stage 1, Senior #2

Rebecca is a tour guide and is trying to market the Rocky Mountains for her magazine. She recently took a beautiful picture consisting of $N$ ~N~ mountains where the $i$ ~i~-th mountain from the left has a height $h_i$ ~h_i~. She will crop this picture for her magazine, by possibly removing some mountains from the left side of the picture and possibly removing some mountains from the right side of the picture. That is, a crop consists of consecutive mountains starting from the $l$ ~l~-th to the $r$ ~r~-th mountain where $l \le r$ ~l \le r~. To please her magazine readers, Rebecca will try to find the most symmetric crop.

We will measure the asymmetric value of a crop as the sum of the absolute difference for every pair of mountains equidistant from the midpoint of the crop. To help understand that definition, note that the absolute value of a number $v$ ~v~, written as $|v|$ ~|v|~, is the non-negative value of $v$ ~v~: for example $|-6| = 6$ ~|-6| = 6~ and $|14| = 14$ ~|14| = 14~. The asymmetric value of a crop is the sum of all $|h_{l+i} - h_{r-i}|$ ~|h_{l+i} - h_{r-i}|~ for $0 \le i \le \frac{r-l}{2}$ ~0 \le i \le \frac{r-l}{2}~. To put that formula in a different way, we pair up the mountains working from the outside in toward the centre, calculate the absolute difference in height of each of these pairs, and sum them up.

Because Rebecca does not know how wide the picture needs to be, for all possible crop lengths, find the asymmetric value of the most symmetric crop (the crop with the minimum asymmetric value).

Input Specification

The first line consists of an integer $N$ ~N~, representing the number of mountains in the picture. The second line consists of $N$ ~N~ space-separated integers, where the $i$ ~i~-th integer from the left represents $h_i$ ~h_i~.

The following table shows how the available 15 marks are distributed:

Marks Awarded	Bounds on $N$ ~N~	Bounds on $h_i$ ~h_i~	Additional Constraints
5	$1 \le N \le 300$ ~1 \le N \le 300~	$0 \le h_i \le 10^5$ ~0 \le h_i \le 10^5~	None
5	$1 \le N \le 5\,000$ ~1 \le N \le 5\,000~	$0 \le h_i \le 10^5$ ~0 \le h_i \le 10^5~	Height of mountains are in non-decreasing order from left to right.
5	$1 \le N \le 5\,000$ ~1 \le N \le 5\,000~	$0 \le h_i \le 10^5$ ~0 \le h_i \le 10^5~	None

Output Specification

Output on one line $N$ ~N~ space-separated integers, where the $i$ ~i~-th integer from the left is the asymmetric value of the most symmetric picture of crops of length $i$ ~i~.

Sample Input 1

7
3 1 4 1 5 9 2

Output for Sample Input 1

0 2 0 5 2 10 10

Explanation of Output for Sample Input 1

We will show why the fifth value from the left is $2$ ~2~. Let us try to compute all the asymmetric values of crops with length $5$ ~5~.

The height of the mountains in the first crop is $[3, 1, 4, 1, 5]$ ~[3, 1, 4, 1, 5]~. The asymmetric value of this crop is $|3 - 5| + |1 - 1| + |4 - 4| = 2$ ~|3 - 5| + |1 - 1| + |4 - 4| = 2~.

The height of the mountains in the second crop is $[1, 4, 1, 5, 9]$ ~[1, 4, 1, 5, 9]~. The asymmetric value of this crop is $|1 - 9| + |4 - 5| + |1 - 1| = 9$ ~|1 - 9| + |4 - 5| + |1 - 1| = 9~.

The height of the mountains in the last crop is $[4, 1, 5, 9, 2]$ ~[4, 1, 5, 9, 2]~. The asymmetric value of this crop is $|4 - 2| + |1 - 9| + |5 - 5| = 10$ ~|4 - 2| + |1 - 9| + |5 - 5| = 10~.

Hence, the most symmetric crop of length $5$ ~5~ is $2$ ~2~.

Sample Input 2

4
1 3 5 6

Output for Sample Input 2

0 1 3 7

Explanation of Output for Sample Input 2

This sample satisfies the second subtask. Note that the only crop of length $4$ ~4~ is $[1, 3, 5, 6]$ ~[1, 3, 5, 6]~ which has an asymmetric value of $|1 - 6| + |3 - 5| = 7$ ~|1 - 6| + |3 - 5| = 7~.

Comments

-1

lis13 commented on Feb. 22, 2024, 3:04 a.m.

Spoiler alert: center

1

zhengbrayden commented on Sept. 28, 2023, 2:00 a.m. ← edited →

is this doable with python?

0

Joel_M commented on Jan. 21, 2024, 1:48 a.m.

Value's get too large for the programs to compute,I was able to write some python, it got AE, but it got a TLE. I asked ChatGPT to convert it to varius languages, it TLE'd except C# where it Gave points but still gave a TLE. So your program has to be very efficient, and use a language that is fast.

5

andy_zhu23 commented on Sept. 28, 2023, 6:22 a.m.

seems like no one ACed with Python 3, maybe you should try submitting with pypy 3

https://dmoj.ca/problem/ccc23s2/submissions/?status=AC&language=PYPY3

0

michaelskyba commented on Feb. 21, 2024, 2:33 p.m. ← edited →

Nvm s

0

onarvaez commented on Feb. 21, 2024, 2:29 p.m.

legend

3

can definitely solve contest problems in 4 seconds commented on Sept. 29, 2023, 12:54 a.m.

i literally spent 1 hour to figure out ways to make it as fast as possible and work in python but looks like its impossible

1

zhengbrayden commented on Sept. 28, 2023, 7:12 p.m.

wow thanks dude

9

yuqiao commented on Feb. 18, 2023, 3:38 a.m.

RIP CCC score; still have no idea how to solve subtask 3

3

bloomfield commented on March 14, 2023, 10:32 p.m.

interval dp

37

AQT commented on Feb. 18, 2023, 9:05 p.m. ← edited →

Hint

2

aldenstripes commented on Feb. 23, 2023, 1:28 a.m.

thanks

27

macOSbyApple commented on Feb. 21, 2023, 7:50 p.m.

Thank you for your hint, your hint is so inspiring that I solved the problem immediately and spontaneously developed an understanding of the c++ language. Thank you.

1

yuqiao commented on Feb. 18, 2023, 9:11 p.m.

??? Is that actually a hint?

3

AQT commented on Feb. 18, 2023, 9:19 p.m.

yeah :D

6

yuqiao commented on Feb. 18, 2023, 10:36 p.m. ← edited →

Did you solve all problems on CCC?

Edit: I just realized you r the author