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

18/06/2018 by Leave a Comment
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.
Chủ đề: Khác

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

09/06/2018 by Leave a Comment

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

 

Graphs (Đồ thị)

 

Directed Graphs

Undirected Graphs

Shortest Paths

Spanning Trees: Cây khung

Chủ đề: Khác

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

30/05/2018 by Leave a Comment

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.

 

 

 

 

 

Chủ đề: Khác

MULONE – spoj

26/03/2018 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';//MULONE.INP';
  fo = '';//MULONE.OUT';
  maxn = 10000000;
var
  n,test,t : longint;
  kq : array[1..maxn] of longint;
 
procedure sol;
var
  i,nho,tong : longint;
  count : longint;
begin
  tong:=0; nho:=0; count:=0;
  for i:=1 to n do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=n-1 downto 1 do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=count downto 1 do write(kq[i]);
  writeln;
end;
 
BEGIN
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
  readln(T);
  for test:=1 to T do
    begin
      readln(N);
      sol;
    end;
  close(input);
  close(output);
END.
Chủ đề: Toán học Mức độ:

C11PNUM – spoj

26/03/2018 by Leave a Comment

Đề bài:

Thuật toán:

  • Sàng nguyên tố
  • Tính các tích k số nguyên tố liên tiếp để cập nhập cho kết quả

Code:

const   fi='';
        fo='';
        oo=3000000;
var     k,t,i,j,tt:longint;
        tam,n,res:qword;
        f:text;
        tmp:array[2..oo] of boolean;
        ngto:array[1..oo] of longint;
        d	:longint;
function max(a,b:qword):qword;
begin
        if a>b then exit(a) else exit(b);
end;
procedure xl;
var     i,j :longint;
begin
	for i:=1 to d-k+1 do
		begin
			tam :=1;
			for j:=i to i+k-1 do
			begin
				tam := tam*ngto[j];
			end;
                        if tam>n then break else res := max(res,tam);
		end;
end;
procedure init;
begin
        for i:=2 to trunc(sqrt(oo)) do
                if tmp[i]=false then
                        begin
                            j:=i*i;
                            while j<=oo do
                                begin
                                    tmp[j]:=true;
                                    j:=j+i;
                                end;
                        end;
        d:=0;
        for i:=2 to oo do
                if tmp[i]=false then begin inc(d); ngto[d]:=i; end;
        j:=d;
end;
procedure nhap;
begin
    assign(f,fi);reset(f);
    assign(output,fo);rewrite(output);
    read(f,t);
    for tt:=1 to t do
        begin
            read(f,n,k);
            res := 0;
            xl;
            if res=0 then writeln(-1) else writeln(res);
        end;
    close(f);close(output);
end;
begin
    init;
    nhap;
end.
Chủ đề: Sàng nguyên tố

Ứng dụng của đồ thị

26/03/2018 by Leave a Comment

Ta đang sống trong một thế giới mà mọi vật được liên kết, các thành phố được liên kết với nhau bởi các con đường, con người liên kết với nhau trên mạng xã hội… những liên kết như vậy chính là hình hài của đồ thị. Một trong những đồ thị lớn mà ai trong chúng ta cũng biết đó chính là Internet hay là mạng tìm kiếm Google.

Đồ thị được sinh ra từ nhu cầu giải quyết những vấn đề thực tế của đời sống. Ví dụ như là bài toán ‘7 cây cầu Königsberg’ từ những năm 1720. Đồ thị là một phần quan trọng trong Toán học rời rạc, là cơ sở của Tin học. Ứng dụng của nó vô cùng rộng, áp dụng vào trong nhiều lĩnh vực. Trong phạm vi bài viết, tác giải chỉ đề cập đến một vài ứng dụng thực tế cơ bản.

Bài toán bảy cây cầu

Tìm đường đi ngắn nhất

Trong thực tế, ta luôn phải lựa chọn đường đi ngắn nhất để đi sao cho tiết kiệm xăng. Đầu tiên là biểu diễn mạng giao thông dưới dạng đồ thị rồi sử dụng thuật toán tìm đường đi ngắn nhất. Thường thì mọi người sử dụng thuật toán Dijkstra nhưng giả dụ với dữ liệu không lồ như của Google Map thì thuật toán này không thể đáp ứng. Google đang sử dụng một thuật toán có tộc độ nhanh hơn nhiều thuật toán Dijkstra.

Tìm đường trên Google Maps

Nhưng nếu muốn tìm đường giữa Hà Nội và New York thì sao? Giữa chúng có hàng tỉ tỉ giao lộ thì phải làm thế nào?

 

Tô màu đồ thị

Ứng dụng điển hình của tô màu đồ thị là bài toán tô màu bản đồ. Làm sao để tô màu bản đồ sao cho không có hai vùng kề nhau có cùng màu và số màu cần dùng là ít nhất.

Biểu diễn bài toán dưới dạng đồ thị:

  • Coi mỗi vùng là một đỉnh
  • Hai đỉnh có cạnh nối với nếu hai vùng tương ứng kề nhau

Bài toán trở thành tô màu các đỉnh của đồ thị, giải quyết sẽ đơn giản hơn bài toán ban đầu.

Bài toán tô màu bản đồ

Một ứng dụng khác là trong bài toán xếp lịch ở UET, làm sao để xếp lịch thi cho sinh viên sao cho nếu sinh viên học môn A và môn B thì hai môn này không thi cũng lúc, ngoài ra kì thi cần kết thúc sớm nhất.

Với bài này ta giải quyết thế nào?

Gọi mỗi môn học là một đỉnh, hai đỉnh được nỗi với nhau nếu tồn tại học sinh học cả 2 môn này. Bài toán giờ trở thành bài toán tô màu cho các đỉnh.

 

Đồ thị hai phía

graph-yeulaptrinh.pw

Đồ thị ghép cặp hẹn hò

Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp, quan hệ hôn nhân giữa tập những người đàn ông và tập những người phụ nữ, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v…

 

Chủ đề: Đồ thị Mức độ:

NKLUCK – spoj

22/03/2018 by Leave a Comment

Đề bài:

Thuật toán:

    Để giải bài toán này, ta giải bài toán trung gian khác như sau
    Gọi

    • A là số đoạn nhận X là phần tử trung vị
    • B là số đoạn nhận X + 1 là phần tử trung vị

    => Result = (A – B) / (n * (n + 1) / 2) ;

    Để tính số đoạn nhận X là phần tử trung vị ta chuyển đổi mảng A về, nếu A[i] >= X => A[i] = 1 ngược lại A[i] = 0.

    Một đoạn nhận X là trung vị khi và chỉ khi tổng của đoạn đó ko âm. Đến đây, ta dùng cây BIT để tính toán .

Code:

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define long long long
 
const int N = 1e6+10;
 
class FenwickTree {
private:
    long t[N][2];
public:
    void update(int x, int type) {
        for (; x <= N; x += x & -x)
            t[x][type]++;
    }
    long get(int x, int type) {
        long res = 0;
        for (; x > 0; x -= x & -x)
            res += t[x][type];
        return res;
    }
} BIT;
 
int n, m, k;
int a[N], f[N], b[N];
 
void Enter() {
    scanf("%d%d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
}
 
long calc(int x, int type) {
    m = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i-1] + (a[i] >= x);
        b[++m] = 2 * f[i] - i - 1;
        b[++m] = 2 * f[i-1] - i;
    }
 
    sort(b + 1, b + m + 1);
 
    long res = 0;
    FOR(i, 1, n) {
        int cur = lower_bound(b + 1, b + m + 1, 2 * f[i - 1] - i) - b;
        BIT.update(cur, type);
        cur = lower_bound(b + 1, b + m + 1, 2 * f[i] - i - 1) - b;
        res += BIT.get(cur, type);
    }
    return res;
}
 
void Process() {
    long res = calc(k, 0) - calc(k + 1, 1);
    double ans = 1ll * n * (n + 1) / 2;
    ans = res / ans;
    printf("%.6lf", ans);
}
 
int main() {
 //   freopen("input.in", "r", stdin);
 
    Enter();
    Process();
 
    return 0;
}
Chủ đề: BIT, Tìm kiếm nhị phân