Algorithms

Segment Tree with Lazy update

Posted on

Bài toán Với bài toán cần thực hiện truy vấn get và update trên đoạn [a,b] liên tiếp. Ví dụ: Đường sắt liên vận Công ty đường sắt Byteotian quyết định giớithiệu tới khách hàng của họ một đường sắt liên vận giữa các thành phố. Đường liên vận chạy qua N thành phố đánh […]

Algorithms

Ada and Indexing

Posted on

SoTong Ada the Lady bug has many things to do and almost notime. She wants to save time while searching for something so she have decidedto make a search engine. She has many words in her TODO list. It costs herprecious time to find out, whether a word is in it so she seeks your […]

Algorithms

[BFS] The gunner

Posted on

SoTong Namvà Hải là hai xạ thủ chuyên nghiệp của đội tuyển quốc gia Việt Nam về bộ mônbắn súng ngắn hơi. Cảhai đều đã nhiều lần được tham dự các kì Olympic và cũng đạt được nhiều thànhtích cao. Namcó sở trường về bắn súng ngắn hơi 10m còn Hải thì có sở trường […]

Algorithms

BST – Tree Map

Posted on

SoTong Tạo một ánh xạ map thực hiện các lệnh sau: put key value: gán ánh xạ của key làvalue remove key: xóa phần tử có giá trị keykhỏi map get key: đưa ra giá trị ánh xạ của key,nếu không tồn tại key trong map thì đưa ra null contains key: kiểm tra xem […]

Algorithms

Hàng đợi có độ ưu tiên [Hash+Heap]

Posted on

Tag: Hashing, Heap Đề bài Cho trước một danh sách rỗng. Người ta xét haithao tác trên danh sách đó: Thao tác “+V” (ở đây V là một số tựnhiên <= 1000000000): Nếu danh sách đang có ít hơn 15000 phần tử thì thaotác này bổ sung thêm phần tử V vào danh sách; nếu […]

Algorithms

Cha Chung Gần Nhất [Disjoin-Set]

Posted on

You are to find the closest common ancestor of two vertices in a binary tree. For example, the common ancestors of vertices 8 and 13 in the figure below are vertices 3 and 1. Among them, vertex 3 is the closest to the vertex 8 and 13. And the size of sub-tree (the number of […]

Algorithms

Xây cầu [Disjoin-Set]

Posted on

Chính phủ quốc đảo Oceani quyết định xây dựng m chiếc cầu nối n đảo của mình, tạo một mạng lưới giao thông đường bộ cho phép đi từ dảo bất kỳ tới đảo khác bằng đường bộ (trực tiếp hoặc qua một số đảo trung gian). Mỗi cây cầu sẽ nối 2 đảo khác […]

Algorithms

[Lý Thuyết] Binary Search Tree

Posted on

ref: https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm   Cây nhị phân tìm kiếm – Binary Search Tree (BST) có đặc điểm sau: – Binary Tree: là một cây nhị phân. – Search: Node con bên trái luôn nhỏ hơn node cha, node con bên phải luôn lớn hơn node cha! => Thông thường các thao tác xử lý chỉ là log(n) […]

Algorithms

Tree Set – Binary Search Tree

Posted on

Xây dựng tập ts có các hàm sau:  add x: thêm x vào trong tập (nếu trong tậpts chưa có x)  remove x: xóa x trong tập ts (nếu x cótrong tập ts)  contains x: đưa ra true nếu x có trong tập ts, ngược lại đưa ra false  lower x: […]

Algorithms

Company

Posted on

Trong tập đoàn Big Soft của MSN, có một công ty nhỏ có nhiều người tài nhưng do giám đốc công ty đó là beo_chay_so đã xây dựng một hệ thống nhân sự rất phức tạp nên công ty không thể phát triển tốt được. Hệ thống nhân sự được bố trí như sau. Đứng […]