LATGACH4 – spoj

Đề bài:

Thuật toán:

    Gọi f[i] là số cách xếp gạch
    dùng viên gạch 1×2 => f[i] = f[i – 2];
    dùng viên gạch 2×2 => f[i] = f[i – 1];
    => f[i] = f[i – 1] + f[i – 2];
    Do n quá lớn nên mình có thể dùng nhân ma trận tốn O(log2(n))

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 111539786;
 
map <ll, ll> f;
 
ll get(ll n)
{
    if (f.count(n)) return f[n];
    ll k=n / 2;
    if (!(n % 2))
        return f[n]=(get(k)*get(k) + get(k-1)*get(k-1)) % mod;
    else
        return f[n]=(get(k)*get(k+1) + get(k-1)*get(k)) % mod;
}
main()
{
    int t, n;
    cin>>t;
    while (t--)
    {
        cin>>n;
        f[0]=f[1]=1;
        cout<<get(n)<<endl;
    }
}

Map (ánh xạ) trong C++

Map là một loại associative container. Mỗi phần tử của map là sự kết hợp của khóa (key value) và ánh xạ của nó (mapped value). Cũng giống như set, trong map không chứa các khóa mang giá trị giống nhau.

Trong map, các khóa được sử dụng để xác định giá trị các phần tử. Kiểu của khóa và ánh xạ có thể khác nhau.

Và cũng giống như set, các phần tử trong map được sắp xếp theo một trình tự nào đó theo cách so sánh.

Map được cài đặt bằng red-black tree (cây đỏ đen) – một loại cây tìm kiếm nhị phân tự cân bằng. Mỗi phần tử của map lại được cài đặt theo kiểu pair (xem thêm ở thư viện utility).

Khai báo: 

#include <map>

map <kiểu_dữ_liệu_1,kiểu_dữ_liệu_2>

// kiểu dữ liệu 1 là khóa, kiểu dữ liệu 2 là giá trị của khóa.

 

Sử dụng class so sánh:

Dạng 1:

struct cmp{

bool operator() (char a,char b) {return a<b;}

};

.....

map <char,int,cmp> m;
  • Truy cập đến giá trị của các phần tử trong map khi sử dụng iterator: Ví dụ ta đang có một iterator là it khai báo cho map thì:
  • (*it).first;   // Lấy giá trị của khóa, kiểu_dữ_liệu_1
    
    (*it).second;  // Lấy giá trị của giá trị của khóa, kiểu_dữ_liệu_2
    
    (*it)          // Lấy giá trị của phần tử mà iterator đang trỏ đến, kiểu pair
    
    it->first;  // giống như (*it).first
    
    it->second; // giống như (*it).second
    
    

    Capacity:

    • size : trả về kích thước hiện tại của map. ĐPT O(1)
    • empty : true nếu map rỗng, và ngược lại. ĐPT O(1).

     

    Truy cập tới phần tử:

    • operator [khóa]: Nếu khóa đã có trong map, thì hàm này sẽ trả về giá trị mà khóa ánh xạ đến. Ngược lại, nếu khóa chưa có trong map, thì khi gọi [] nó sẽ thêm vào map khóa đó. ĐPT O(logN)

    Chỉnh sửa

    • insert : Chèn phần tử vào map. Chú ý: phần tử chèn vào phải ở kiểu “pair”. ĐPT O(logN).
    • erase :

    o xóa theo iterator ĐPT O(logN)

      1. xóa theo khóa: xóa khóa trong map. ĐPT: O(logN).
    • clear : xóa tất cả set. ĐPT O(n).
    • swap : đổi 2 set cho nhau. ĐPT O(n).

    Operations:

    • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy iterator trỏ về “end” của map. ĐPT O(logN).
    • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
    • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
    • count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN)

    Chương trình demo:

    #include <iostream>
    
    #include <map>
    
    #include <vector>
    
    using namespace std;
    
    main() {
    
        map <char,int> m;
    
        map <char,int> :: iterator it;
    
        m['a']=1;
        m.insert(make_pair('b',2));
        m.insert(pair<char,int>('c',3) );
    
        // m={{'a',1}}
        // m={{'a',1};{'b',2}}
        // m={{'a',1};{'b',2};{'c',3}}
    
        cout << m['b'] << endl; m['b']++;     // In ra 2
    
        // m={{'a',1};{'b',3};{'c',3}}
    
        it=m.find('c');    // it trỏ tới phần tử khóa 'c'
    
        cout << it->first << endl; 
        cout << it->second << endl;
        // In ra 'c'
        // In ra 3
    
        m['e']=100;
        //m={{'a',1};{'b',3};{'c',3};{'e',100}}
    
        it=m.lower_bound('d'); 
        cout << it->first << endl; 
        cout << it->second << endl;
        // it tỏ tới phần tử khóa 'e'
        // In ra 'e'
        // In ra 100
        system("pause");
    }
    

Giới thiệu về Deep Learning

Thời gian gần đây, AI – Artificial Intelligence (Trí Tuệ Nhân Tạo) nổi lên như một thế lực đang làm thay đổi thế giới. Nào là chuyện VTV nói ra rả về công nghệ 4.0, rồi các báo giật tít về chuyện Facebook phải tắt AI do sợ chúng tạo ra ngôn ngữ riêng. Mới đầu nghe cụm từ Trí tuệ nhân tạo thì có vẻ rất ngầu, hay xuất hiện trong các phim bom tấn của Hollywood như anh chàng Javit của Iron-man hay lũ Ultron định xâm chiến trái đất… Tuy nhiên trí tuệ nhân tạo trong thực tế đang được sử dụng khá rộng rãi và có thể là hàng ngày, hàng giờ bạn đang dùng những ứng dụng như thế. Hệ thống tự tag khuôn mặt trong ảnh của Facebook, trợ lý ảo Siri – Cortana – Google now, google dịch…  chính là một vài sản phẩm của AI/Machine Learning/Deep Learning.

Cuối năm 2017, trí tuệ nhân tạo có bước phát triển mới khi mà một game thủ Dota 2 hàng đầu thế giới bị hạ gục bởi một trí tuệ nhân tạo. Điều này cho thấy trí tuệ nhân tạo có tiềm năng vô cùng lớn và có thể giỏi hơn con người trong một vài lĩnh vực.

OpenAI’s Dota 2 bot đã hạ gục game thủ nổi tiếng nhất thế giới trong trận chiến 1 vs 1 tại chung kết Dota 2 thế giới 2017.

Nguồn gốc trí tuệ của chú bot này chính là Deep Learning. Trong bài viết này tôi sẽ trình bày một vài kiến thức cơ bản về Trí tuệ nhân tạo/Machine Learning, đặc biệt là Deep Learning mà tôi biết. Đầu tiên các bạn hãy xem gia phả của Deep Learning nhé.

Artificial Intelligence

Trí tuệ nhân tạo nghiên cứu về các tác tử thông minh (intelligence agents) có khả năng nhận thức thế giới xung quanh, lập kế hoạch và đưa ra quyết định để đạt được mục tiêu của nó.

Hiểu một cách đơn giản hơn thì trí tuệ nhân tạo là trí tuệ được thể hiện trên các hệ thống nhân tạo. Một chiếc ô tô tự chạy không cần tài xế điều khiển, một trợ lý ảo có trả lời các câu hỏi của bạn… đó đều là những sản phẩm có trí tuệ do con người tạo nên. Người ta tạo ra AI nhằm trợ giúp hoặc thay thế con người trong một lĩnh vực nào đó. Ví dụ như:

  • Google đã và đang ứng dụng AI vào lĩnh vực xe tự hành;
  • Facebook sử dụng trí tuệ nhân tạo trong việc nhận diện hình ảnh;
  • Microsoft đang theo đuổi dự án điều trị ung thư bằng trí trí tuệ nhân tạo;
  • Google ứng dụng AI trong việc nhận diện giọng nói…

Trí tuệ nhân tạo gồm nhiều lĩnh vực con, chẳng hạn như thị giác máy tính, robot, machine learning, và xử lý ngôn ngữ tự nhiên…

Machine Learning

Machine Learning là một lĩnh vực của trí tuệ nhân tạo. Theo định nghĩa của Wikipedia, Machine learning is the subfield of computer science that “gives computers the ability to learn without being explicitly programmed”. Machine Learning là một lĩnh vực nhỏ của Khoa Học Máy Tính, nó có khả năng tự học hỏi dựa trên dữ liệu đưa vào mà không cần phải được lập trình cụ thể.

Bạn đưa cho Machine Learning rất nhiều dữ liệu – 5000 ảnh chó mèo và mong muốn chương trình của bạn thể đoán 1 bức ảnh chưa gặp bao giờ là chó hay mèo. Mỗi lần xem qua một ảnh, Machine Learning sẽ cố “ghi nhớ” đặc trưng của con chó hoặc con mèo: màu lông, vóc dáng, kích thước… Không chỉ dừng lại ở ghi nhớ, Machine Learning phải có khả năng tổng quát hóa những ảnh nó đã xem để có thể dự đoán cho những bức ảnh chưa bao giờ thấy.

Khả năng tổng quát là một khả năng tự nhiên và kì diệu của con người: bạn không thể nhìn thấy tất cả các khuôn mặt người trên thế giới nhưng bạn có thể nhận biết được một thứ có phải là khuôn mặt người hay không với xác suất đúng gần như tuyệt đối. Đỉnh cao của machine learning sẽ là mô phỏng được khả năng tổng quát hóa và suy luận này của con người. – anh Nguyễn Xuân Khánh (Machine Learning là gì?)

Bạn có thể tìm hiểu thêm về các kiến thức, thuật toán Machine Learning tại Blog Machine Learning cơ bản của anh Vũ Hữu Tiệp. Đây là nguồn kiến thức bằng tiếng Việt rất hữu ích với các bạn có ý định tìm hiểu sâu hơn về Machine Learning/Deep Learning.

Deep Learning

Deep Learning là một kỹ thuật trong Machine Learning, liên quan đến các thuật toán lấy cảm hứng từ cấu trúc và hoạt động của bộ não động vật gọi là Mạng nơ-ron nhân tạo (artificial neural networks).

Theo Wikipedia, An ANN is based on a collection of connected units or nodes called artificial neurons (analogous to biological neurons in an animal brain). Each connection (analogous to a synapse) between artificial neurons can transmit a signal from one to another. The artificial neuron that receives the signal can process it and then signal artificial neurons connected to it. Mạng nơ-ron nhân tạo được tạo nên từ một tập hợp các nơ-ron nhân tạo (tương tự nơ-ron sinh học trong não động vật) liên kết với nhau. Mỗi liên kết (tương tự một xi-náp) giữa các nơ-ron nhân tạo có thể truyền tín hiệu từ một nơ-ron đến các nơ-ron khác. Nơ-ron nhân tạo nhận tín hiệu, xử lý rồi laị truyền tín hiệu đã qua xử lý đến các nơ-ron mà nó liên kết.

Mạng nơ-ron nhân tạo có 3 lớp: input, hidden, output.

Cái gì Deep trong Deep Learning?

Các mạng nơ-ron nhân tạo truyền thống có rất ít lớp, hầu hết chỉ là 2 lớp. Cấu trúc như vậy không thích hợp với việc tính toán trên các mạng lớn hơn. Vì vậy các mạng có nhiều hơn 10 hoặc thậm chí đến 100 lớp được sử dụng. Trong Deep Learning thì mạng nơ-ron nhân tạo được chia ra thành rất nhiều lớp tạo ra một mạng nơ-ron sâu và lớn.

Tại sao vài năm nay Deep Learning mới trở thành hot trend?

Ý tưởng về mạng nơ-ron nhân tạo xuất hiện từ rất sớm, những năm 50 thế kỷ trước. Nhưng việc tạo ra những mạng nơ-ron hoạt động hiệu quả là không hề dễ dàng, nhìn chung, mạng nơ-ron sẽ cho kết quả tốt hơn khi:

  • Nhiều dữ liệu đầu vào hơn +
  • Mạng lớn hơn +
  • Khả năng tính toán của máy tính tốt hơn

Results Get Better With More Data, Larger Models, More Compute
Slide by Jeff Dean, All Rights Reserved.

Khả năng tính toán của máy tính ngày càng mạnh mẽ hay việc sử dụng các thuật toán tối ưu hơn trong Deep Learning đã góp phần vào thành công của Deep Learning như ngày nay. Bên cạnh đó là nguồn dữ liệu khổng lồ mà chúng ta có thể thu thập được dựa vào sự bùng nổ internet. Facebook có thể dễ dàng có được các bức ảnh chụp khuôn mặt của bạn từ đó tạo nên hệ thống tự động tag ảnh, hay Google biết mỗi ngày bạn tìm kiếm thứ gì, xem gì trên youtube, từ đó gợi ý cho bạn các quảng cáo hay video thú vị… Mà Deep Learning lại chính là “con quái vật” lớn lên từ những núi dữ liệu, khi chúng ta có rất nhiều dữ liệu thì Deep Learning có hiệu quả hơn hẳn các thuật toán khác.

MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.