Dytechlab Algorithms Battle - Bài của chemthan

View as PDF

Submit solution

Points: 1.80 (partial)
Time limit: 4.0s
Memory limit: 256M

Problem source:
Dytechlab Algorithms Battle 2021
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ma trận ~X[n\times d]~ và vector ~y[n]~, tìm vector ~c[d]~ sao cho:

  1. Đặt ~E=X\times c-y~, thì ~\sqrt{\sum{E_{ij}^2}}~ là nhỏ nhất (còn gọi là norm ~l_2~ của ~E~)
  2. ~\sqrt{\sum{c_i^2}}~ là nhỏ nhất (còn gọi là norm ~l_2~ của ~c~).

Ưu tiên vector ~c~ tối ưu bước ~1~ trước, trong trường hợp có nhiều vector ~c[d]~ có giá trị norm ~l_2~ của ~E~ bằng nhau thì chọn vector ~c~ có norm ~l_2~ nhỏ nhất theo bước ~2~.

Input

Dòng thứ nhất chứa ~n, d~.

~n~ dòng tiếp theo, mỗi dòng chứa ~d~ số nguyên của ma trận ~X~.

Dòng tiếp theo chứa ~n~ số nguyên của vector ~y~.

Output

In ra ~c_1, c_2, ..., c_d~ trên một dòng. Kết quả của bạn được xem là đúng nếu như kết quả của bạn có chênh lệch không quá ~10^{-6}~ với đáp án.

Giới hạn: ~1\leq N,D\leq 500,\ |X_{ij}|\leq 10^3,\ |y_i|\leq 10^3~, dữ liệu được tạo ra ngẫu nhiên (trừ test ví dụ).

Subtask #1: ~50\%~ ~1\leq N,D\leq 50~.

Subtask #2: ~50\%~ ~1\leq N,D\leq 500~.

Ví dụ:

Input:

1 2
1 1  
1

Output:

0.500000000 0.500000000

Comments

Please read the guidelines before commenting.


There are no comments at the moment.