Geek Corner

[nguyenhongha]

Nguyên văn bởi kitte83

Hôm trước ngồi trông lab, tụi sinh viên đến ít quá nên em với một thằng partner rảnh rỗi ngồi đố vui nhau. Nó đưa ra một bài toán mà nó bảo là từ một cái job interview của tụi MS như thế này:
- Có một tòa nhà cao n tầng và người ta làm thì nghiệm thả bình hoa từ trên các tầng xuống. Đến một độ cao nhất định, giả sử tầng thứ k, thì nếu thả bình hoa từ các tầng đó trở lên thì bình hoa sẽ vỡ còn nếu thả bình hoa từ các tầng dưới tấng đó trở xuống thì bình hoa an toàn.
- Cho 2 bình hoa, tìm một thuật toán để xác định được tầng bắt đầu làm bình hoa vỡ.

Trường hợp có 2 bình hoa:
Khởi tạo biến x = n và y = 0.
Bước 1: Thả bình hoa 1 từ tầng (x+y)/2 xuống. Nếu bình hoa vỡ, sang bước 2. Nếu bình hoa không vỡ, gán y = (x+y)/2 và lặp lại bước 1.
Bước 2: Lần lượt thả bình hoa 2 xuống theo thứ tự tầng (y+1), (y+2), ... đến khi bình hoa vỡ thì xác định được k là tầng đó.

Trường hợp có m bình hoa:
Giữ lại 1 bình hoa, sử dụng m-1 bình hoa cùng thả 1 lúc từ các tầng n/(m-1), 2n/(m-1), ... Giả sử bình hoa vỡ ở tầng thấp nhất là (p+1)*n/(m-1) thì sử dụng tiếp p bình hoa chưa vỡ để chia khoảng tầng p*n/(m-1) và (p+1)*n/(m-1) thành p khoảng đều nhau để thử tiếp. Cứ như vậy tới khi các bình hoa thử vỡ hết thì sử dụng bình hoa để giành từ đầu để thử giống như bước 1 của thuật toán 2 bình hoa đã trình bày ở trên.

Anh không phân tích độ phức tạp của thuật toán vì anh không giỏi cái này. Ai vào phân tích hộ cái.

[kitte83]

Nguyên văn bởi nguyenhongha

Trường hợp có 2 bình hoa:
Khởi tạo biến x = n và y = 0.
Bước 1: Thả bình hoa 1 từ tầng (x+y)/2 xuống. Nếu bình hoa vỡ, sang bước 2. Nếu bình hoa không vỡ, gán y = (x+y)/2 và lặp lại bước 1.
Bước 2: Lần lượt thả bình hoa 2 xuống theo thứ tự tầng (y+1), (y+2), ... đến khi bình hoa vỡ thì xác định được k là tầng đó.

Trường hợp có m bình hoa:
Giữ lại 1 bình hoa, sử dụng m-1 bình hoa cùng thả 1 lúc từ các tầng n/(m-1), 2n/(m-1), ... Giả sử bình hoa vỡ ở tầng thấp nhất là (p+1)*n/(m-1) thì sử dụng tiếp p bình hoa chưa vỡ để chia khoảng tầng p*n/(m-1) và (p+1)*n/(m-1) thành p khoảng đều nhau để thử tiếp. Cứ như vậy tới khi các bình hoa thử vỡ hết thì sử dụng bình hoa để giành từ đầu để thử giống như bước 1 của thuật toán 2 bình hoa đã trình bày ở trên.

Anh không phân tích độ phức tạp của thuật toán vì anh không giỏi cái này. Ai vào phân tích hộ cái.

Giải thuật của anh có độ phức tạp là O(n). Như trường hợp 2 bình hoa, trong tình huống xấu nhất anh sẽ phải thử 1 + n/2 lần thả bình.
Ai có cách nào tốt hơn không?

Hint: Trong cách của anh Hà, tại sao lại chọn n/2 và chưa tận dụng được đặc tính của việc thả bình hoa cho lần thử thứ nhất.

[seeker]

Nguyên văn bởi kitte83

Em ơi, sau lần thả thứ nhất có thể một số bình bị vỡ rồi, làm sao đảm bảo lần thứ 2 có m-1 cái.
Giải bài toán với m=2 trước đã.

Đúng là làm lần sau em quên mất, không để ý là thả m bình cùng lúc thì vỡ cả đống . Ở trên thì mỗi lần em thả có 1 cái mà, cái có độ phức tạp căn bậc m của n ấy :D.

[kitte83]

Nguyên văn bởi seeker

Với trường hợp 2 bình hoa:
Nếu thả một bình hoa theo những tầng cách nhau k tầng thì sau cùng lắm là n/k lần thả xác định được khoảng k tầng chứa tầng cần tìm.
Còn một bình hoa dùng cách thả tuần tự, sau tối đa k lần sẽ tìm ra kết quả.
Vậy sẽ mất k+n/k lần, chọn tối ưu là k=căn n, (lấy phần nguyên). Độ phức tạp căn n

Với trường hợp m bình hoa, chọn khoảng cách đều k1 để tìm ra khoảng k1 tầng chứa tầng cần tìm, trong k1 tầng đó chọn khoảng cách đều k2 để tìm ra khoảng gồm k2 tầng có chứa tầng cần tìm. Cứ tiếp tục cho đến km.
Số lần thử là:
n/k1 +k1/k2 +...+km-1/km + km, đạt min khi n/k1 = k1/k2 = ... =km-1/km = căn bậc m của n. Vì k1, ... ,km nguyên nên lấy phần nguyên.
Độ phức tạp là m nhân căn bậc m của n.

Sorry em, anh chưa đọc cái này, không biết em mới edit lại hay có từ trước.
Cách này hiện tại là cách tốt nhất mà tụi anh có thể tìm được (có thể chứng mình nó là cách tốt nhất không?). Có lẽ trong thời gian trả lời cho một câu hỏi phỏng vấn thì cách này có lẽ là Ok rồi.
Nếu so sánh giữa m và n, trong một số trường hợp có thể thực hiện tìm kiếm nhị phân.

[seeker]

Vừa post thì thấy cái anh post, thời gian sửa là trước mấy cái post sau mà :D

[d_ht_john]

Với 2 bình hoa, anh thấy câu hỏi gốc là cho n=100. Tìm kiếm nhị phân trong trường hợp này không tốt.
Cứ thả tuần tự từ dưới lên cũng được O(n) rồi. Anh nghĩ câu này tricky ở chỗ hằng số cụ thể là bao nhiêu.
Chọn k= 10-14 sẽ ra worst case là 19 lần thả. Có thể ra ít hơn được không ?

[d_ht_john]

Đây là best bound anh biết: chỉ mất 14 lần.
Tầng thử : 14, 14+13=27, 27+12= 39, 50, 60, 69, 77,84, 90, 95, 99,100

[seeker]

Nguyên văn bởi d_ht_john

Đây là best bound anh biết: chỉ mất 14 lần.
Tầng thử : 14, 14+13=27, 27+12= 39, 50, 60, 69, 77,84, 90, 95, 99,100

Sửa bài toán thành cho 2 bình hoa và a lần thử. Với tòa nhà cao nhất là bao nhiêu thì vẫn đảm bảo việc tìm ra được tầng bình hoa bắt đầu vỡ?
Với cách làm trên thì a = 14 được n = 105.

[seeker]

Nếu là m bình hoa, với a+m-1 lần thử:
Với 1 bình hoa: a lần thử thì tòa nhà cao nhất là a tầng.

Với 2 bình hoa: a+1 lần thử thì tòa nhà cao nhất là
(1+a) + (1+(a-1)) + ... + (1+0) = a(a+1)/2 + (a+1)

Với 3 bình hoa: a+2 lần thử thì tòa nhà cao nhất là
(1+(a+1)a/2+(a+1)) + (1+a(a-1)/2+a)+ ... + (1+2*1/2+2) + (1+0+1) + (1+0+0) = a(a+1)(a+2)/3! + (a+1)(a+2)/2! + (a+2)

...

Với m bình hoa: a+m-1 lần thử thì tòa nhà cao nhất là
(1+a(a+1)(a+2)...(a+m-2)/(m-1)! +(a+1)(a+2)...(a+m-2)/(m-2)! + ... + (a+m-2)) + ... + ( (1+(m-1)(m-2)...2*1/(m-1)! + (m-1)(m-2)...2/(m-2)!+ ... + (m-1)) + ... + (1+0+...+0) = a(a+1)...(a+m-1)/m! + (a+1)...(a+m-1)/(m-1)! + (a+2)...(a+m-1)/(m-2)! + ... + (a+m-1)

Thay lại biến, với m bình hoa, a lần thả được tòa nhà cao nhất là:
a(a-1)(a-2)...(a-m+1)/m! + a(a-1)(a-2)...(a-m+2)/(m-1)! + ... + a/1! tầng

Vậy độ phức tạp căn m của n là tốt nhất.

[Chau Hong Linh]

Có một bài toán, thực ra cũng cơ bản, nhưng cái chính là làm sao cài đặt các yêu cầu của nó một cách hay nhất và ít trùng lặp nhất:

Problem: The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.'
That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!

The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.

Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.

Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).

1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops.
In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

Test Input:

For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

Expected Output:

Output #1: 9
Output #2: 5
Output #3: 13
Output #4: 22
Output #5: NO SUCH ROUTE
Output #6: 2
Output #7: 3
Output #8: 9
Output #9: 9
Output #10: 7
==========

[kitte83]

A simple question:
What is the limitation of CPU speed?

[seeker]

1. Tính toán độ dài một đường đi có vẻ đơn giản, cứ đi từng bước.
2. Tìm đường đi ngắn nhất, dùng thuật toán Dijtra vì các trọng số đều dương.
3. Tìm số đường đi với giới hạn về số lần dừng và chiều dài chặng đường, dùng thuật toán breadth first search rồi đếm số lần đi qua.

[Chau Hong Linh]

Chú seeker trả lời, như một nhà văn vĩ đại nào đó đã từng nói: "Cái gì hay thì không đúng, mà cái gì đúng lại không hay."

Nếu như chú nghĩ rằng các vấn đề tìm kiếm có lời giải đơn giản như thế, thì hàng năm các trường Đại học Mỹ như MIT, Standford, Brown ... đã không nhận nghiên cứu sinh làm về search. Cũng như các công ty du lịch, bán vé máy bay trên mạng ... như Orbitz, Travelocity ... đã không trả hàng triệu dollars cho một công ty startup của sinh viên MIT có tên gọi là ITA, để mua Search Backend Service.

Đây là một số trong (vô số kể) các vấn đề các chú cần suy nghĩ nhé:
1) Nếu thỏa mãn tất cả các yêu cầu search đề ra trong bài, thì ít nhất phải có các kiểu search như sau:
- find exact route
- find shortest route(s)
- find routes with max stop count
- find routes with exact stop count
- find routes with max distance

Nếu các chú viết nhiều hàm, mỗi hàm thực ra phần duyệt các city và route là gần giống nhau, chỉ có điều kiện duyệt và điều kiện dừng là khác. Thế thì đâu là DRY?
Hay các chú dùng các OOP design pattern, ví dụ như visitor hay command design pattern để reuse phần code duyệt city và route?
Hay là dùng functional programming để tránh trùng lặp code?

Đâu là cái hay của dùng imperative programming hoặc functional programming?

2 - Trong các thuật toán tìm đường đệ quy, thường điều kiện dừng là (start == end), hoặc start.equals(end).
Nhưng ở đây thì không thể thế được, vì có đường đi circle, ví dụ CEBC, hoặc lặp nhiều lần, như CEBCEBC.
Vậy điều kiện dừng của đệ quy là gì?

3 - Dùng cấu trúc dữ liệu nào để biểu diễn tập các city-route một các hiệu quả nhất cho việc search. Các chú thử nghĩ ra ngoài các điều đã viết trong sách xem. Anh có cách để làm cho searching và matching là constant time, 1 computation for all access cases. Các chú nghĩ xem đấy là gì.

4 - Dùng breadth search rồi đếm số lần dừng ( hoặc tính tổng khoảng cách) như chú seeker nói, tức là vét cạn, rất kém hiệu quả. Thế nào là heuristic? Thế nào là genetic algorithm và evolution programming?

5 - Trong thực tế, có thể có hàng triệu người tìm đường lái ô tô từ Boston đến New York trong một ngày, thậm chí một giờ (Mapquest hoặc GoogleMap). Thế thì thế nào là data caching? Thế nào là query caching? Thế nào là heuristic caching?

Đại khái cái sự thông minh không phải là biết nhiều hay biết ít, mà là nhìn vào một sự vật, một hiện tượng, một câu hỏi, con người ta nghĩ ra cái gì, suy luận về những vấn đề gì.

Ở Hy lạp, hơn 2000 năm trước, Aristotle nhìn cánh buồm khuất trên mặt biển mà suy ra rằng trái đất hình cầu, thậm chí còn tính ra bán kính trái đất.
Ngày nay, đa số trí thức ở cái nước mà chúng ta ai cũng biết là nước nào, khi nhìn thấy cánh buồm khuất trên mặt biển, thì chỉ nghĩ ra là ngày mai nên đi bán cá ở đâu mà thôi.

[seeker]

Nguyên văn bởi Chau Hong Linh

Đại khái cái sự thông minh không phải là biết nhiều hay biết ít, mà là nhìn vào một sự vật, một hiện tượng, một câu hỏi, con người ta nghĩ ra cái gì, suy luận về những vấn đề gì.

Ở Hy lạp, hơn 2000 năm trước, Aristotle nhìn cánh buồm khuất trên mặt biển mà suy ra rằng trái đất hình cầu, thậm chí còn tính ra bán kính trái đất.
Ngày nay, đa số trí thức ở cái nước mà chúng ta ai cũng biết là nước nào, khi nhìn thấy cánh buồm khuất trên mặt biển, thì chỉ nghĩ ra là ngày mai nên đi bán cá ở đâu mà thôi.

Có thể đây là nguyên nhân em học Computer Science mà chẳng thấy nó có gì hứng thú , không thấy được cái hay của nó. Vẫn nhớ câu nói của anh Lĩnh: khi đọc ít ra cũng phải biết để làm gì (ko nhớ chính xác lắm).

[Chau Hong Linh]

Nói thật với chú seeker là nếu làm CNTT mà không đam mê thì khó mà làm hay được. Tất nhiên là vẫn làm ra tiền, thậm chí ra nhiều tiền, nhưng mà vẫn là không hay.

Nhưng mỗi người sinh ra thì đam mê những thứ khác nhau, nên không nhất thiết là phải đam mê CNTT.

Như anh bây giờ, lúc làm thì thích, nhưng cứ nghĩ đến lúc phải mang sản phẩm của mình đi bán, phải nịnh mấy thằng khách hàng ngu ngu với lại giao lưu với bọn IT vênh váo, đần độn, là lại thấy tởm. Vì thế có khi anh bỏ nghề, đi làm việc khác.

Có khi anh lại đi làm Khoa học Xã hội . Chú đọc cái bài này anh mới viết cho vui.