THÔNG BÁO: Đợt huấn luyện tăng cường cho đội tuyển OLP tin học SV 2017

[truonganpn]

Thời gian: 13h-16h30 - chiều thứ 7 hàng tuần, bắt đầu từ 14/10/2017. Kéo dài TÁM TUẦN
Địa điểm - A217
Nội dung:

• Giải đề ACM quốc gia 2015 (14/10/2017)
• Quy hoạch động nâng cao (21/10 - a. Thông phụ trách)
• flow, scheduling (4/11/2017 - thỉnh chuyên gia).
• LCA, graph traversal và ứng dụng, Biểu diễn đồ thị cây dạng nén ()
• Các giải thuật tìm đường đi ngắn nhất trên đồ thị.
• Hình học
• Cấu trúc dữ liệu nâng cao: Prefix tree,
• Thi chọn đội hình chính thức

Kết quả bài tập làm tại chỗ trong quá trình huấn luyện kết hợp với kết quả các kỳ thi sẽ là cơ sở để chọn đội hình chính thức.

[17520180]

Tên đội: Oh!
- Lê Thủy Triều : 17520180@gm.uit.edu.vn
- Nguyễn Hữu Phong : 17520015@gm.uit.edu.vn
- Trần Kim Sen : 17520144@gm.uit.vn

[truonganpn]

Do cuối tuần này có một số hoạt động dùng phòng máy lớn nên lớp huấn luyện tăng cường của chúng ta sẽ tạm dời qua phòng C110 trong buổi thứ 7 21/10/2017 nhé các bạn.

Gửi các bạn bảng tổng kết điểm contest #440 trên codeforce tuần rồi:

15520197	1134
16521257	1016
15520940	694
16521170	1328
14520903	1358
14520820	1306
16521530	960
17520490	0
17520180	1152
17520144	1106

[14520903]

Gửi các bạn điểm dynamic programming contest chiều nay (https://www.hackerrank.com/uitdp, đã mở lại để các bạn có thể submit tới cuối tháng 11)

minhthienapag	240
anhthi2103	240
nghethuat102	140
thai3896	110
trankimsen168191	10
dongxoaytr	10
ngToan1107	10
h17520490	10

Đề thi:
qhd.pdf

Code mẫu:
anhthong_381996.zip
Code của các bạn đã làm bài chiều nay:
code_uitdp.zip

[17520144]

vì công thức lúc chiều f[i]=f[i-1]*a+f[i-2]*b+f[i-3]*c+d*i+e vì i này biến thiên chạy từ 1->n nên trong ma trần lúc chiều a= {{0,0,c1,0,0},{1,0,b1,0,0},{0,1,a1,0,0},{0,0,n,1,0 },{0,0,1,0,1}}; sẽ lỗi vì n này luôn k đổi :3
nếu trong công thức có n nó sẽ lỗi :3 A thông nói lại cái ma trận a vs :| e thấy sai sai r

[14520903]

Đây nhé bạn:
Capture1.PNG

Bạn nhìn vào màu sắc và công thức trong ảnh phía trên thì sẽ rõ cách tạo ma trận này

[17520144]

công thức của anh số n mặc định là số 4 mới đúng vì đã có f1 f2 f3 t tính từ f4 nên n=4 . nếu thay n như đề sẽ sai :v
b= {{0,0,c,0,0},
{1,0,b,0,0},
{0,1,a,0,0},
{0,0,d,1,0},
{0,0,e,1,1}
};
a= {{f[1],f[2],f[3],4,1},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0}};

[14520903]

Anh không hiểu ý em lắm.

Trường hợp của anh, X3={1,1,1,4,1}

Anh đã viết một chương trình duyệt thử và nó cũng cho ra một kết quả tương ứng

Em tham khảo chương trình thứ 2 này (lưu ý chỉ chạy cho trường hợp N<=1000000)

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL MOD=1000000007;

LL a,b,c,d,e;
LL n;
LL F[1000010]={0,1,1,1};
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d,&e);

    if(n>1000000)
        return true;

    for(long long i=4;i<=n;i++)
        F[i]=(a*F[i-1]+b*F[i-2]+c*F[i-3]+d*i+e  )%MOD;

    printf("%lld",F[n]);
}

Em cũng có thể tham khảo bộ test của bài này và thông báo lại với anh nếu thấy test sai

2.zip

[14520903]

Em nhìn kỹ từ X(n-1) sang X(n) đã có thay đổi giá trị từ n tới n+1 rồi mà chứ có cố định là số 4 đâu?

[17520144]

code e sub full r ạ mặc đinh nó là số 4 a xem thử :v

https://ideone.com/DySI1D

bài của a k có sai do cách nhân ma trận e khác thôi ạ

[14520903]

số 4 bởi vì em mặc định chọn công thức là A^(n-3)*X3 = Xn. nếu em chọn lại công thức là A^(n-4)*X4 = Xn thì trong ma trận X4 sẽ có số 5 thôi

Em nhìn kỹ lại công thức chỗ vòng tròn màu đỏ (hình dưới). Anh chọn hai ma trận khởi tại là A và X(i=3) mà, nên dòng thứ 4 của X3 mới có giá trị là: i+1=4

Capture1.PNG

Công thức và đề anh xem lại kỹ rồi không sai đâu.

[17520144]

Dạ k sai đâu

[truonganpn]

Chào các bạn.

Thứ 7 tuần này 28/10/2010 là vòng online miền Trung. Chúng ta sẽ tập trung làm bài tại phòng A217 cho giống điều kiện thi offline thực tế. Sau buổi thi (từ 8:00 đến 13:00) chúng ta sẽ trao đổi, đúc kết một số kinh nghiệm trong buổi thi.

[toannv]

Chào các bạn.

Thứ 7 tuần này 28/10/2010 là vòng online miền Trung. Chúng ta sẽ tập trung làm bài tại phòng A217 cho giống điều kiện thi offline thực tế. Sau buổi thi (từ 8:00 đến 13:00) chúng ta sẽ trao đổi, đúc kết một số kinh nghiệm trong buổi thi.

Các bạn đăng ký thi gấp trong hôm nay nhé.
Chi tiết các bạn xem cách đăng ký và DS ở https://forum.uit.edu.vn/threads/674...-thang-10-2017

[14520903]

Bàn thêm về vòng online miền Trung chiều nay:

* Problem B:
Captureaa.PNG

Để tính được G[t] các bạn tham khảo ở các link sau:

• MỘT SỐ PHƯƠNG PHÁP TÌM SỐ HẠNG TỔNG QUÁT CỦA DÃY SỐ FIBONACCI: https://docs.google.com/viewer?url=h...&embedded=true
• Một số phương pháp xác định công thức tổng quát của dãy số: https://diendantoanhoc.net/index.php...ttach_id=23292

Sau đó sử dụng nhân ma trận để giải

* Problem C:
Sử dụng Persistent IT: http://vnoi.info/wiki/algo/data-stru...ata-structures