PEG Judge - NOI '13 - Inner Product

National Olympiad in Informatics, China, 2013

Day 1, Problem 1 - Inner Product

The inner product (a.k.a. dot product) of two d-dimensional vectors A = [a₁, a₂, …, a_d] and B = [b₁, b₂, …, b_d] is equal to the sum of products of their corresponding components. Specifically:

$\displaystyle (A,B)=\sum_{i=1}^{d}a_ib_i=a_1b_1+a_2b_2+\cdots +a_db_d$

Given n such d-dimensional vectors, x₁, …, x_n, Little Meow-Meow would like to know if there exists two vectors whose inner product is a multiple of k. Please help her solve this problem.

Input Format

The first line of input contains 3 positive integers n, d, and k, respectively representing the number of vectors, the number of dimensions, and the number of which a inner product could be a multiple.
The next n lines each contains d nonnegative integers. On the i-th of these lines, the j-th integer represents x_i,j, the j-th component of vector x_i.

Output Format

Output two integers, separated by a space.
If there exists two vectors x_p and x_q whose inner product is an integer multiple of k, then output their indices p and q (p < q). If there are multiple answers, output any one of them.
If an answer does not exist, then output two -1's separated by a space.

Sample Input

Sample Output

2 3

Explanation

(x₁, x₂) = 1
(x₁, x₃) = 1
(x₂, x₃) = 2

Constraints

Test Case	`n`	`d`	`k`	`x_i,j`
1	2	20	2	≤ 10
2	5	20	2	≤ 10
3	10	20	3	≤ 10
4	20	20	2	≤ 100
5	50	20	3	≤ 100
6	50	50	2	≤ 1000
7	50	50	3	≤ 3000000
8	80	80	2	≤ 2000000
9	100	100	3	≤ 3000000
10	500	100	3	≤ 3000000
11	1000	100	2	≤ 2000000
12	1000	100	3	≤ 3000000
13	10000	100	2	< 10
14	10000	100	3	< 10
15	15000	100	2	< 10
16	18000	100	2	< 10
17	20000	100	2	< 10
18	50000	30	3	< 10
19	80000	30	3	< 10
20	100000	30	3	< 10

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 5.00s
Memory Limit: 256M
Added: May 18, 2015

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

ainta on Dec 25, 2019 - 5:31:38 pm UTC Test cases are weak?

(0/0)

I think many solutions will fail on this test:

5 3 3
1 1 1
1 1 1
1 1 1
1 1 1
0 0 1

I think many solutions will fail on this test:

5 3 3
1 1 1
1 1 1
1 1 1
1 1 1
0 0 1

Alex on May 18, 2015 - 2:24:29 am UTC Caution

(1/0)

I'm pretty that the answers for the data are unique. However, if you seriously suspect that a custom grader is needed, let me know.

I'm pretty that the answers for the data are unique. However, if you seriously suspect that a custom grader is needed, let me know.

simp1eton on Sep 15, 2015 - 12:29:47 am UTC Re: Caution

(0/0)

Nick Wu wrote a program that received WA (i.e. his program claimed that a solution exists and this solution is different from the expected solution). This means that multiple solutions are possible?

Nick Wu wrote a program that received WA (i.e. his program claimed that a solution exists and this solution is different from the expected solution). This means that multiple solutions are possible?

yingted on Sep 15, 2015 - 12:32:10 am UTC Re: Caution

(0/0)

I think he guessed after running out of time.

I think he guessed after running out of time.

xiaowuc1 on Sep 15, 2015 - 1:38:30 am UTC Re: Caution

(0/0)

To close the loop, a custom grader is required for the given test data.

To close the loop, a custom grader is required for the given test data.

Alex on Sep 17, 2015 - 4:36:07 pm UTC Re: Caution

(0/0)

OK. The grader is added and I've rejudged all submissions.

OK. The grader is added and I've rejudged all submissions.