Chuyên gia thuật toán vô địch Facebook Hacker Cup giờ ra sao?

Facebook Hacker Cup là một kỳ thi Thuật Toán rất nổi tiếng của Facebook, và mỗi năm số người người tham dự ngày một đông. Một số người cho rằng, tham dự những kỳ “thi thố” để làm gì? Thật ra những người trong giới thuật toán tham dự các kỳ thi, nó không đơn thuần mang ý nghĩa “thi thố” hay “thể hiện” mà nó còn là dịp để các họ rèn giũa lại kiến thức của mình. Luyện “não” cũng giống như tập “gym” vậy, bạn luyện đều đặn và đúng cách “não” sẽ khỏe mạnh và làm việc được lâu dài. Ngược lại nếu bạn bỏ bê chúng, một ngày nào đó não sẽ có “bụng bia”
Nhà thơ Vũ Đình Liên trong bài thơ “Ông Đồ” đã từng thốt lên “Những người muôn năm cũ Hồn ở đâu bây giờ?” Khi ông không còn thấy những ông Đồ xuất hiện trong dịp lễ để cho các câu đối hay chơi chữ nữa. Vậy thì bạn có bao giờ tự hỏi rằng những người đạt giải kỳ thi này họ “ở đâu bây giờ?”.
Hãy cùng Big-O Coding tìm hiểu xem những nhà vô địch Facebook Hacker Cup ngày xưa hiện giờ họ ở đâu? làm gì? và công việc của họ như thế nào? nhé.

Petr Mitrichev

Anh là một lập trình viên người Nga, vô địch Facebook Hacker Cup vào các năm 2011, 2013 và 2017. Ngoài ra anh đã đạt rất nhiều thành tích ở những cuộc thi khác như Huy chương vàng IOI (2000, 2002) , huy chương vàng ACM ICPC World Final (2003, 2005), vô địch Google Code Jam(2006) và Topcoder Open (2006, 2013, 2015),… Hiện tại anh đang làm cho Google với vị trí kỹ sư về Google Search.

Tiancheng Lou

Anh là một lập trình viên người Trung Quốc, đoạt giải 3 Facebook Hacker Cup vào năm 2011 và 2012. Anh còn đạt những thành tích khác như vô địch Google Code Jam vào năm 2008 và 2009, đạt thứ hạng cao trên Topcoder và Codechef,.. Anh hiện đang là Software Engineer cho Google.

Khúc Anh Tuấn

Anh là một lập trình viên người Việt Nam,từng du học tại Đại học công nghệ Nayang Singapore, anh đã xuất sắc vượt qua các lập trình viên lừng danh toàn cầu giành vị trí thứ nhì Facebook Hacker Cup năm 2011. Anh hiện đang là Software Engineer cho Uber.

Tomek Czajka

Là một lập trình viên người Mỹ, anh tốt nghiệp ở đại học Purdue với tấm bằng Master of Science năm 2007. Anh đạt nhiều thành tích cao trong các kì thi về lập trình, phải kể đến như hạng nhì cuộc thi Facebook hacker cup năm 2012 và 2014, giải nhất cuộc thi TopCoder Open năm 2008, hạng 5 cuộc thì Google Code Jam năm 2003 và 2004 . Anh hiện đang làm việc tại Tập đoàn Công nghệ Khai phá Không gian (Space Exploration Technologies Corp) viết tắt là SpaceX với vị trí kỹ sư phần mềm. Trước đó anh từng làm việc cho Google (2007 – 2013).

Jakub Pachocki

Anh tốt nghiệp Cử nhân Khoa học máy tinh ở đại học Warsaw (Ba Lan) năm 2013, sau đó anh lấy được tấm bằng Tiên Sĩ về Khoa học máy tinh năm 2016 tại đại học Carnegie Mellon với bài báo “Graphs and Beyond: Faster Algorithms for High Dimensional Convex Optimization”. Anh đã đạt giải nhì tại cuộc thi Facebook Hacker Cup năm 2012, anh đã từng 2 lần thực tập cho Facebook (2011,2012). Năm 2016 – 2017 ,anh làm việc tại đại học Harvard. Hiện tại anh đang nghiên cứu viên về lĩnh vực trí tuệ nhân tạo tại OpenAI (San Francisco)

Gennady Korotkevich

Còn được biết đến với biệt danh “tourist”, anh hiện đang học ở đại học tổng hợp ITMO ở Nga. Korotkevich tham gia nhiều cuộc thi và đã đạt được rất nhiều thành tích, như vô địch Facebook Hacker Cup năm 2014 và 2015, vô địch TopCoder Open năm 2014, vô địch Google Code Jam trong 4 năm liên tiếp (2014 – 2017), vô địch ACM-ICPC World Finals năm 2013 và 2015.

Dmytro Soboliev

Anh là người Ukraine, anh tốt nghiệp thạc sĩ về lĩnh vực toán học ứng dụng ở Viện Bách khoa Kiev. Anh đã xuất sắc giành được Giải nhì Facebook Hacker Cup 2015. Anh từng là Junior C++ Developer ở công ty Luxsoft (2012 – 2014). Hiện anh đang làm ở Amazone Web Services với ví trí Software Development Engineer.

Gleb Evstropov

Anh tốt nghiệp khoa Khoa học máy tinh và điểu khiển học tại Đại học Tổng hợp Quốc gia Moskva , anh đạt nhiều thành tích cao trong các cuộc thi lập trình như Huy chương vàng tại ACM ICPC World Finals 2014 và 2015, giải ba cuộc thi Facebook Hacker Cup 2015, huy chương vàng IOI 2010. Hiện anh đang là giảng viên tại trường đại học nghiên cứu quốc gia ở Moskva, Nga.

Tiếng Anh chuyên ngành Công nghệ thông tin

Computer science: Khoa học máy tính

 

Graphs (Đồ thị)

 

Directed Graphs

Undirected Graphs

Shortest Paths

Spanning Trees: Cây khung

Một số lưu ý khi viết bài trên YeuLapTrinh

1 – Sử dụng Latex

Website có hỗ trợ công cụ viết công thức toán học Latex. Mình xin được giới hiệu cách sử dụng ở dưới đây

  • Bài viết nào dùng đến Latex thì bắt buộc phải thêm một dòng ở trên cùng
    • Viết cùng trên một dòng thì dùng: $...$
    • Viết công thức trên cả một dòng thì dùng: $$...$$

Thí dụ:

[mathjax]

Bài viết này sử dụng Latex. Test...

$a^2 + b_i^3 \ge c_{i+1}^5 + d_{x+1}^{y+1}$

2 – Tránh lỗi khi chèn code

Hầu hết các bài viết các bạn đều chèn code vào, nhưng nhiều bạn chèn code vẫn chưa đúng cách, gây lỗi. Nên mình xin được hướng dẫn cách chèn code và chú ý khi chèn code để không bị lỗi.

viet-bai-yeulaptrinh

Tab “Trực quan” và Tab “Văn bản”

Khi soạn thảo, bạn có 2 tab là “Trực quan”” và “Văn bản”.

  • Tab “Trực quan” là soạn thảo văn bản tương tự như Word
  • Tab “Văn bản” là chỉnh sửa văn bản dạng HTML. Đây là tab mà bạn chèn code

Lỗi khi soạn thảo các bạn cần chú ý ở đây là:

  • Không viết chèn code ở tab “Trực quan”, phải chèn ở trong Tab “Văn bản”
    • Bươc 1: Mở tab “Văn bản”
    • Bước 2: Chèn đoạn HTML với mẫu: <pre lang=”ten_ngon_ngu_lap_trinh”>Viết code ở đây</pre>
      • ten_ngon_ngu_lap_trinh là c, cpp, python, php, java, … Xem thêm ở GeSHi

Vd:

<pre lang="cpp">
int a, b;
int c,d;
  • Chú ý 2: Sau khi chèn code, việc chuyển đổi giữa 2 tab “Trực quan” và “Văn bản” sẽ gây lỗi. Ví dụ:
    • < thành &lt;
    • > thành &gt;
  • Vì vậy nên soạn thảo trên tab “Trực quan” xong xuôi thì mới chuyển sang tab “Văn bản” để chèn code. Tránh hành động chuyển đổi giữa 2 tab sẽ gây lỗi cho code.

 

 

 

 

 

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.