Description

Recently, Money became interested in artificial intelligence and started learning about neural networks.

A neural network receives some input values, performs several calculations, and finally produces a score for each possible class. The class with the highest score is chosen as the prediction.

In this problem, Money uses a small neural network with the following structure:

input x
   |
   v
linear(x, W1, b1)
   |
   v
ReLU
   |
   v
hidden result h
   |
   v
linear(h, W2, b2)
   |
   v
output scores y
   |
   v
argmax(y)
   |
   v
predicted class

The first linear layer combines the input values using weights and biases. Then, the ReLU function replaces negative values with zero. The second linear layer produces one score for each class. Finally, argmax finds the class with the largest score.

Money has already written the main neural-network structure for you, but four important functions are still missing. Your task is to complete:

dot(a, b)
linear(x, W, b)
relu(x)
argmax(x)

All values in this problem are integers. You do not need to use NumPy, PyTorch, TensorFlow, softmax, or floating-point calculations.

Variables

• D: the number of values in each input vector.
• H: the number of neurons in the hidden layer.
• C: the number of output classes.
• x: one input vector given to the neural network.
• W1: the weights of the first layer. It transforms x into the hidden layer.
• b1: the biases of the first layer. One bias is added to each hidden neuron.
• h: the hidden-layer result after the first linear layer and ReLU.
• W2: the weights of the second layer. It transforms h into the output scores.
• b2: the biases of the second layer. One bias is added to each output class.
• y: the final output scores for all classes.
• Q: the number of input vectors to process.

Functions to Implement

1. dot(a, b)

Given two lists a and b of the same length, return their dot product.

a = [1, 2, 3]
b = [4, 5, 6]

The result is:

1*4 + 2*5 + 3*6 = 32

Therefore, dot(a, b) should return 32.

2. linear(x, W, b)

For every row W[i], calculate:

dot(W[i], x) + b[i]

Return all results as a list.

x = [2, 3]

W = [
    [1, 4],
    [2, -1]
]

b = [5, 2]

The result is:

[19, 3]

because:

1*2 + 4*3 + 5 = 19
2*2 + (-1)*3 + 2 = 3

3. relu(x)

For every value in x:

• If the value is negative, replace it with 0.
• Otherwise, keep it unchanged.

relu([-3, 5, 0, -7, 2])

returns:

[0, 5, 0, 0, 2]

4. argmax(x)

Return the index of the largest value in x. The first element has index 0.

argmax([7, 20, -3, 15])

returns:

1

If the largest value appears more than once, return the smallest index.

argmax([10, 20, 20, 5])

returns:

1

Neural Network Function

The following function has already been written for you:

def neural_network(x, W1, b1, W2, b2):
    h = linear(x, W1, b1)
    h = relu(h)

    y = linear(h, W2, b2)

    return argmax(y)

You do not need to modify this function.

Constraints

• 1 <= D, H, C <= 50
• 1 <= Q <= 1000
• Every weight, bias, and input value is between -100 and 100.
• All values are integers.

Starter Code

def dot(a, b):
    # TODO
    pass


def linear(x, W, b):
    # TODO
    pass


def relu(x):
    # TODO
    pass


def argmax(x):
    # TODO
    pass


def neural_network(x, W1, b1, W2, b2):
    h = linear(x, W1, b1)
    h = relu(h)

    y = linear(h, W2, b2)

    return argmax(y)


D, H, C = map(int, input().split())

W1 = []
for _ in range(H):
    W1.append(list(map(int, input().split())))

b1 = list(map(int, input().split()))

W2 = []
for _ in range(C):
    W2.append(list(map(int, input().split())))

b2 = list(map(int, input().split()))

Q = int(input())

for _ in range(Q):
    x = list(map(int, input().split()))
    print(neural_network(x, W1, b1, W2, b2))

Input

The first line contains three integers:

D H C

• D: the number of values in each input vector.
• H: the number of neurons in the hidden layer.
• C: the number of output classes.

The next H lines describe W1. Each line contains D integers. Therefore, W1 has H rows and D columns.

The next line contains H integers representing b1.

The next C lines describe W2. Each line contains H integers. Therefore, W2 has C rows and H columns.

The next line contains C integers representing b2.

The next line contains one integer:

Q

where Q is the number of input vectors to process.

The following Q lines each contain D integers, representing one input vector x.

In short, the input is given in the following order:

D H C
H lines of W1
1 line of b1
C lines of W2
1 line of b2
Q
Q input vectors

Output

For each input vector x, print the predicted class returned by:

neural_network(x, W1, b1, W2, b2)

Print one answer per line.

Each answer is an integer from 0 to C - 1, representing the index of the class with the largest output score.

If more than one class has the same maximum score, the class with the smallest index is chosen.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Money is a teacher at NTHU. During class, he likes to choose a student and ask the students sitting around that student to come to the front and answer some questions.

However, there are simply too many students in the classroom, and Money cannot remember who is sitting next to whom.

Please help him!

The classroom consists of N rows and M columns of seats. Each seat is occupied by exactly one student. The student sitting in row i, column j has student ID A[i][j]. All student IDs are distinct.

There are Q queries. In each query, Money chooses a student with ID x. For that student, find the students sitting directly above, below, to the left, and to the right.

The classroom has a circular seating arrangement:

• If you move upward from the first row, you reach the last row.
• If you move downward from the last row, you reach the first row.
• If you move left from the first column, you reach the last column.
• If you move right from the last column, you reach the first column.

When N = 2 or M = 2, the same student may appear in more than one direction. Each student must be printed only once.

For each query, print all distinct neighboring student IDs in increasing order.

Constraints

• 2 <= N, M
• N * M <= 20000
• 1 <= Q <= 100000
• 1 <= A[i][j] <= 1000000000
• All student IDs are distinct.
• Every queried student ID appears in the classroom.

Example

Consider the following seating arrangement:

10 25  7 18
 3 12 30  6
21  9 15 27

If Money chooses student 10:

• Moving up wraps around to student 21.
• Moving down reaches student 3.
• Moving left wraps around to student 18.
• Moving right reaches student 25.

After sorting, the answer is:

3 18 21 25

Input

The first line contains two integers:

N M

• N: the number of rows in the classroom.
• M: the number of columns in the classroom.

The next N lines each contain M integers. The value A[i][j] represents the student ID of the student sitting in row i, column j.

The next line contains one integer:

Q

where Q is the number of queries.

Each of the following Q lines contains one integer:

x

representing the student ID chosen by Money.

In short, the input is given in the following order:

N M
N rows of student IDs
Q
Q queried student IDs

Sample Input

3 4
10 25 7 18
3 12 30 6
21 9 15 27
4
10
12
27
30

Output

For each query, output all distinct student IDs sitting directly above, below, to the left, or to the right of student x.

Print the student IDs in increasing order. Separate adjacent IDs with one space.

If the same student appears in more than one direction, print that student only once.

Sample Output

3 18 21 25
3 6 9 25
6 15 18 21
6 7 12 15

Sample Input  Download

Sample Output  Download

Tags

Discuss