Description

You do not need to understand the following statement to solve the problem, you may skip directly to the Task section.

After repeatedly running out of paper, Cabi finally decided that relying on physical paper was fundamentally unsafe.

A sheet of paper may be lost, torn apart, given to suffering students during a lab, or destroyed by an unexpected earthquake.

Sometimes, Cabi falls down and causes a huge earthquake, which may destroy his remaining paper. Therefore, Cabi began designing an earthquake-resistant storage facility exclusively for his remaining paper.

Unfortunately, Cabi had no idea how to determine whether the structure would survive an earthquake.

To analyze the building, engineers model the displacement of a solid object using the equations of elastodynamics: , where

• is the material density,
• is the displacement field,
• is the stress tensor,
• represents external forces.

After studying for the equation for several minutes, Cabi successfully understood none of it ._. .

Fortunately, a mysterious engineer had already transformed the entire problem into a system of linear equations: .

The matrix is large, sparse, symmetric, and positive-definite.

Cabi first tried to solve the system using the Conjugate Gradient algorithm that you provided for him. However, the convergence was not fast enough to guarantee the safety of his paper before the next time he fell down.

He therefore decided to use a more powerful method: the Preconditioned Conjugate Gradient algorithm, also known as PCG.

Unfortunately, implementing it required paper to calculate the preconditioner.

Cabi had no paper.

Therefore, this problem now belongs to you.

---

TASK

Now, your task is to help Cabi solve the problem. Write a program to solve the linear system using the Preconditioned Conjugate Gradient (PCG) algorithm.

Unlike Gaussian Elimination, CG is an iterative method perfect for large, sparse, and symmetric positive-definite matrices. However, there is an even stronger version of CG called Preconditioned Conjugate Gradient (PCG), which uses a preconditioner to improve the convergence of the algorithm.

Here is how it works:

0. Prepare a starting vector called , the matrix and the vector .

1. Initiate variables: let

   • is the diagonal of matrix , , and for all
   • , where

2. Iterate the below for

As a kind TA, Cabi has already written a basic structure for you, but some of the functions are still missing. Your task is to complete those functions.

Variables

• N:The dimension of the linear system. This is also the size of the vectors and the matrix
• step: the number of iterations you need to perform for the PCG algorithm.
• d: a list of length . d[i] represents the diagonal element of matrix at row (i.e.,).
• pos: a list of lists. pos[i] contains the column indices of the non-zero off-diagonal(非對角線) elements in row of the matrix .
• val: a list of lists. val[i] contains the values of the non-zero off-diagonal elements in row , corresponding to pos[i] of the matrix .
• b: the right-hand side of the equation of length .
• x0: the initial guess vector of length .

Example for the sparse matrix format:

Suppose we have a matrix :

The inputs for this matrix will look like this:

4 4 5 (this is d)
1 1 -1           (Row 0: 1 off-diagonal element at column 1, value is -1)
2 0 2  -1 -2      (Row 1: 2 off-diagonal elements at column 0 and 2, values are -1 and -2)
1 1 -1           (Row 2: 1 off-diagonal element at column 1, value is -1)

And for such it is

Function to Implement

To help you build the PCG algorithm, you need to implement the following helper functions:

• dot(v1, v2): Returns the dot product of two vectors v1 and v2(i.e.,,)
• vec_add(v1, v2): Returns a new vector which is the element-wise addition of v1 and v2.
• vec_sub(v1, v2): Returns a new vector which is the element-wise subtraction of v1 and v2.
• vec_const_mul(c, v): Returns a new vector where each element of v is multiplied by a constant c.
• spmul(d, pos, val, v): Performs sparse matrix-vector multiplication and returns a new vector
• PCG(A_d, A_pos, A_val, b, x0, step): The main Preconditioned Conjugate Gradient loop. Use the formulas provided above and your helper functions to find

Template code

def spmul(d:list,pos:list,val:list,v:list)->list:
    #TODO
    pass


def dot(v1:list,v2:list)->float:
    #TODO
    pass


def vec_add(v1:list,v2:list)->list:
    #TODO
    pass


def vec_sub(v1:list,v2:list)->list:
    #TODO
    pass


def vec_const_mul(c:float,v:list)->list:
    #TODO
    pass


def PCG(A_d:list,A_pos:list,A_val:list,b:list,x0:list,step:int)->list:
    #TODO
    pass


import sys 
input = sys.stdin.readline 

if __name__=='__main__':
    n,step=map(int,input().split())
    b=list(map(int,input().split()))
    x0=list(map(int,input().split()))
    d=list(map(int,input().split()))
    pos=[ [] for _ in range(n) ]
    val=[ [] for _ in range(n) ]
    for i in range(n):
        tmp_list=list(map(int,input().split()))
        m=tmp_list[0]
        if m ==0 : continue
        tmp=tmp_list[1:]
        pos[i]=tmp[0:m]
        val[i]=tmp[m:2*m]

    ans_x = PCG(d,pos,val,b,x0,step)
    for x in ans_x:
        print(f'{x:.5f}',end=' ')

Input

the first line contains two integers:
N step

The line contains integers, representing the vector b.

The line contains integers, representing the initial guess vector x0.

The line contains integers, representing d(the diagonal elements of ).

The next lines describe the off-diagonal non-zero elements for row to row . Each line follows this format:
M_i pos_i_0 pos_i_1 ... pos_i_{M-1} val_i_0 val_i_1 ... val_i_{M-1}

If the line will just be 0.

Constraints

• The matrix will be a symmetric, positive-definite matrix.

Output

Output the final vector .
Print the elements of the vector separated by a single space. Please format each number to decimal places.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Cabi's lottery

Cabi is a sad I2P TA. He was planning to hold a lottery for the students, wanting to pick a few lucky ones in a special order to give them some rewards. This special order was carefully written on a piece of paper.

However, yesterday he used some of his paper to solve a terrifying math problem, and gave the remaining pieces to students during the lab because some of them were suffering and needed paper to trace their code.

Having no paper left, Cabi only has a chaotic list of student ticket numbers and faintly remembers the sorting rule. Please help Cabi reconstruct the sorted list and find the lucky students.

---

Sorting Rules

Cabi remembers that the tickets are not sorted in the standard alphabetical or numerical order.

Instead, they follow a custom character priority defined by a string ord.

Furthermore, a flag dir dictates the sorting direction.

1. Custom Lexicographical Order: You must compare the strings based on the character priority given in ord (from highest priority to lowest priority).

2. Direction (dir): If dir == 1, sort the tickets in ascending order based on ord, otherwise, sort the tickets in descending order based on ord.

3. Prefix Rule: If two tickets have different lengths but the shorter one is entirely a prefix of the longer one, the shorter one is always considered "smaller".

Input

The first line contains three integers: N Q dir

• N: the total number of students' tickets.
• Q: the number of lucky students Cabi wants to query.
• dir: the sorting direction (1 for ascending, 0 for descending).

The second line contains a string ord, representing the custom order of all possible characters (from smallest to largest).

It is guaranteed that ord contains each of the following characters exactly once:

• digits '0' to '9'
• uppercase letters 'A' to 'Z'
• lowercase letters 'a' to 'z'

The following N lines each contain a string, representing the ticket numbers of the students.

Each ticket consists only of digits (0-9) and English letters (A-Z, a-z).

The following Q lines each contain an integer k (0-indexed). For each query, you need to output the k-th ticket in the sorted list.

Constraints

•  
•  
•  
•  
•  

Output

For each query k, output the ticket string at index k in the sorted list, followed by a newline.

Sample Input  Download

Sample Output  Download

Tags

Discuss