A Math Contest P1 - Arrays - Olympiads Online Judge

A Math Contest P1 - Arrays

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 256M

Author:

Tommy_Shan

Problem type

You are given an array of $N$ ~N~ integers $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~. Suppose $b_1, b_2, \dots, b_N$ ~b_1, b_2, \dots, b_N~ is any array of $N$ ~N~ integers. Find the minimum possible positive value of $X = \sum_{i=1}^N a_i \times b_i$ ~X = \sum_{i=1}^N a_i \times b_i~.

Constraints

$1 \le N \le 2 \times 10^5$ ~1 \le N \le 2 \times 10^5~

$-10^9 \le a_i \le 10^9$ ~-10^9 \le a_i \le 10^9~

At least one $a_i \ne 0$ ~a_i \ne 0~.

Input Specification

The first line contains an integer, $N$ ~N~.

The next line contains $N$ ~N~ space-separated integers, $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~.

Output Specification

Output the minimum positive value of $X$ ~X~.

Sample Input

3
2 -1 3

Sample Output

Explanation for Sample

One possible value for array $b$ ~b~ is $[-2, 4, 3]$ ~[-2, 4, 3]~. Then, $X = (2)(-2) + (-1)(4) + (3)(3) = 1$ ~X = (2)(-2) + (-1)(4) + (3)(3) = 1~. This is the minimum positive value of $X$ ~X~ amongst all values of $b$ ~b~.

Comments

0

JajaaGamer commented on Dec. 24, 2024, 3:33 a.m. ← edited →

Can someone help me understand why this isn't a valid solution? My process is to initially add all of the values together (analogous to having array b filled with ones) then subtracting values from the array until the sum is minimized (until any further subtraction of values would cause a negative sum, this is essentially decrementing the multiple of the values of a found in the b array). Why does this not work? It passes the given test case but not the grader's cases. Is there some hidden rule that the elements must be distinct?