A Math Contest P1 - Arrays - DMOJ: Modern 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 \leq N \leq 2 \times 10^{5}$

$-10^9 \le a_i \le 10^9$ $- 10^{9} \leq a_{i} \leq 10^{9}$

At least one $a_i \ne 0$ $a_{i} \neq 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

Copy

3
2 -1 3

Sample Output

Copy

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 92 days ago ← 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?