Một vài bài toán nhỏ :D

[09520019]

[QUOTE=11520676;34585]Đề nghị đọc kỹ bài trước khi trả lời.

• Bài post ở trên mình chưa nói thuật toán tham lam thì sao đã bảo tôi sai lầm được. Làm sao biết 90% test will be wrong.
• Khái niệm đoạn con, dãy con được định nghĩa rõ ràng trong giải tích cấp 3. Do đó lúc ra đề tôi mặc định là ai cũng biết. Tôi không có ý định đánh đố ai mấy chuyện đó. Tất cả trong tiếng anh đều là subsequence vậy tôi hỏi bạn: Bạn học tin học ở việt nam hay ở 1 nước nào nói tiếng anh? Còn bạn biết rõ 2 khái niệm dễ nhầm lẫn mà vấn hỏi lại, không giải thích. Tôi cho rằng việc đó làm sao nhãng topic này.
• Brute force là rất tự nhiên khi tiếp cận bài này thông qua bài toán trước.
• Quy hoạch động là phân rã bài toán lớn thành các bài toán nhỏ. Tính toán kết quả các bài toán nhỏ, lưu lại các kết quả đó. Sau đó tổng hợp kết quả của các bài toán nhỏ để thu được kết quả bài toán ban đầu. Bạn có thể giải thích các khái niệm tôi không biết:
  Half Brute force attack - Dynamic Programming
  Fully Dynamic Programming - Mathematics
  Với khái niệm quy hoạch động ở trên thì cái thuật toán “Fully Dynamic Programming - Mathematics” được trình bày không được “quy hoạch động” cho lắm: phân rã bài toán ra sao? tổng hợp các bài toán nhỏ thế nào? Mà cái giải thuật này cũng dựa trên dãy tổng trước Si. Mục đích hỏi bài này của tôi cũng là cái dãy Si chứ không phải quy hoạch động hay tham lam. (dãy tổng trước Si được định nghĩa trong toán cao cấp A1).
• Challenging - O(log n) :Có thể chứng minh được không có thuật toán nào đọc 1 dãy N phần tử có độ phức tạp tốt hơn O(N) ~> cái này là không cần thiết.[/QUOTE]
  Trước hết thì vụ dãy con và đoạn con thì mình nói lại lần cuối nhé. Hãy bỏ cái tư tưởng “đoạn con thì chắc chắn là liên tục”, và “dãy con thì chắc chắn là không liên tục” đi mà nó tùy thuộc vào người ra đề. Tất cả các thuật ngữ đều phải được giải thích rõ. Đó là nguyên tắc ra đề. Thậm chí công thức tính vận tốc chuyển động thẳng đều đề cũng phải cho (nếu bài toán có yếu tố vật lý này), trong khi nó thuộc vật lý lớp 7 đấy. Đề nói cho 1 chuỗi DNA bla bla bla thì cũng phải nói rõ là DNA thì có A T G X chứ ko có cái chuyện “cái này thuộc sinh học lớp 9, các em SV đại học mặc định ai cũng biết…”.
  Nếu bạn không phân biệt được “Brute Force” , “Greedy Algorithm” và “Dynamic Programming” thì cứ xem lại cho rõ. G không dựa vào G[x - 1], minG không dựa vào minG[x - 1] thì dựa vào đâu ? Đó là bài toán con. Còn đã là Bottom up DP thì dĩ nhiên là cái tính bài toán lớn = bài toán con + xử lý gì đó, sẽ không rõ ràng như Top down DP, nên việc cài đặt đâu thể nào lúc nào cũng khư khư giữ cái kiểu luôn luôn phải là F = F[x - alpha] + beta đâu ? Ở đây G và minG (các thành phần của F) đều được sử dụng yếu tố G dựa vào G[x - 1] và minG dựa vào minG[x - 1] hết.

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller[1] and optimal substructure (described below). When applicable, the method takes far less time than naive methods.
The key idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often, many of these subproblems are really the same. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations. This is especially useful when the number of repeating subproblems is exponentially large.
Cái đề số 2 bạn có nhanh quá hóa sai không đấy ? Example bị sai rồi kìa / Test case 3 Input = 11, expected output = 11011, given output = 101
Nhận xét: giả sử N = 12 và expected output là 11011 (giả sử thôi nhé, vì thực tế là 21112) dãy A[11] là dãy tìm ra đáp án 11011, còn dãy A[12] có chứa dãy A[11] và kèm theo số 12, như vậy dù đáp án có tìm ra tại A[k], thì nếu xét A[N] với N > k thì ta vẫn tìm ra đáp án. Vậy ta chỉ cần xét A[n] mà không quan tâm tới các TH còn lại.
Vì dãy thứ N lớn nhất là |A[500]| < 500 * 3 = 1500 char, lưu được trong bộ nhớ nên ta sinh dãy này ra luôn cho dễ xử lý. Bài toán trở về: cho 1 chuỗi S độ dài M <= 1500 có 9 loại ký tự a_i, loại bỏ bớt các thành phần của dãy sao cho dãy thu được là palindrome lớn nhất. Tại M có 1500 thôi và tôi đang lười suy nghĩ nên tôi tìm 1 giải thuật tối đa N^2 log N (1500 * 1500 * log 1500 xấp xỉ 10 triệu)
Với mỗi dãy con từ i đến j, viết tắt là P(i,j), P(i,j) = độ dài lớn nhất của dãy palindrome tìm được trong khoảng [i,j], RES(i,j) là dãy palidrome lớn nhất sinh ra trong khoảng [i,j]
Mặc định: P(i,i) = 1,P(i,i + 1) = 2 nếu S* = S[i + 1] và P(i,i + 1) = 0 nếu S* != S[i + 1]
P(i,j) = max(P(i + 1,j),P(i,j - 1),P(i + 1,j - 1) + 2 nếu S* = S[j])
RES(i,j) = RES(i + 1,j) hoặc RES(i,j - 1) hoặc S* + RES(i + 1,j - 1) + S[j] tương ứng với bên trên, ngoài ra trong TH P bằng nhau thì chọn RES lớn nhất (ví dụ 991199 và 911119), để cho tiết kiệm bộ nhớ thì mảng RES là mảng con trỏ char *, chỉ trong TH3 thì mới new mảng mới và lưu. Bài không tới nối thiếu mem đâu, nhưng trong TH là có thiếu memory đi, thì thay vì lưu mảng RES, ta lưu mảng T(i,j) mang nghĩa: palindrome mà nó đến từ, khi P(i,j) = … thì T(i,j) = tương ứng nếu dãy con không phải là palindrome và bằng (ii,jj) nếu dãy con là palindrome. Ví dụ:
1 2 3 3 2 2 thì P(1,4) đến được từ P(2,3), P(2,3) lại là 1 palindrom nên T(1,4) = (2,3); P(0,4) đến từ P(1,4), P(1,4) là palindrome nên T(0,4) = (1,4); còn P(0,5) đến từ P(0,4) chẳng hạn, tuy nhiên P(0,4) không phải là 1 palindrome, nên T(0,5) = T(0,4) = (1,4). Đây là mảng truy vết và dùng nó để so sánh ngay khi độ dài P bằng nhau để chọn chuỗi con nào có giá trị lớn hơn.
Cuối cùng ta chọn ra dãy có vị trí xuất phát sao cho P(x,y) là lớn nhất, nếu có nhiều P(x,y) cùng lớn nhất thì ta dùng mảng T để truy vết xem dãy nào lớn hơn thì ta chọn dãy đó
Bài này dành cho bạn.

Từ tập các bài có trên SPOJ (oi)
4540. Lâu đài cát
Mã bài: CTNEWS
CTN vừa xây xong 1 lâu đài bằng cát !Cũng giống như tất cả các lâu đài khác,trên đỉnh những bức tường , sẽ có những lỗ trống ( để đặt đại bác cho việc phòng thù chẳng hạn) , và về hai phía của lỗ trống- tất nhiên sẽ có 2 vùng cao hơn (xem hình vẽ).
Tạm gọi các vùng cao hơn này là Merlons.Lâu đài có N (1<=n<=25000) Merlons, để thuận tiện ta đánh số chúng từ 1->N;
Merlon thứ I có chiều cao M_i (1<=M_i<=100 000);
Ngài CTN muốn sửa chữa lâu đài thành một mẫu mới , anh ta đã làm một danh sách N số nguyên B_1…B_N (1<=B_i<=100000) , và anh muốn thay đổi chiều cao của các Merlon từ (A1…An) thành (B1..Bn) theo một thứ tự nào đó. Để làm được điều này, anh ta đã thuê một số kỹ sư để thiết kế những Merlon theo ý muốn của mình.Tất nhiên chi phí cho việc này là rất đắt đỏ.
Theo tính toán sơ bộ thì chi phí để tăng chiều cao của một đơn vị là X $$

• Chi phí để giảm chiều cao của một đơn vị là Y $$
  Hãy giúp CTN tìm ra phương án để có được bức tường mới mà giá phải trả là nhỏ nhất !
  Input
  Dòng đầu :3 số N,X,Y cách nhau ít nhất 1 dấu cách
  Dòng 2..N+1 :mỗi dòng là 2 số Ai, Bi cách nhau ít nhất 1 dấu cách
  Output
  Gồm 1 dòng duy nhất là kết quả.
  Example
  Input:
  3 6 5
  3 1
  1 2
  1 2
  Output:
  11
  Có 40 % số test với n<=9; 60 % số test với n<=18.
  Chúc bạn may mắn :)). Giám thị không giải thích gì thêm :)) Giám khảo không có mặt để giải thích đề :)) Tất cả các câu trong đề đều rất dễ hiểu nên coi như bạn không cần hỏi. Mọi câu hỏi đều xem như ko có liên quan đến đề bài và không trả lời

[11520676]

• Đúng là tôi không có nhiều thời gian nên dễ nhầm lẫn. Nếu phát hiện thì hãy sửa dùm. Sai lầm nghiêm trọng thì tôi sẽ đính chính lại
• Nếu không muốn trả lời thì có thể im lặng, đừng nên gán cho người khác không biết. Câu hỏi của tôi là giải thích 2 khái niệm bạn đưa ra : Half Brute force attack - Dynamic Programming
  Fully Dynamic Programming - Mathematics.
  Không biết trích dẫn mớ tiếng anh đó để làm gì? Nội dung của nó cũng tương tự như phần tôi nói về quy hoạch động.
• Về bài 3: Đây cũng là lời giải ban đầu:
  +Xây dựng đồ thị 2 phía đầy đủ (A, B). |A| = |B| = n. Trọng số của các cung: C(i, j) = X*(bi - aj) nếu ai > bj; Y*(ai - bj) nếu ai < bj.
  +Đặt đỉnh phát S nối với tất cả các đỉnh của A, đỉnh thu nối với tất cả các đỉnh của B với trọng số + vô cùng.
  • Tìm luồng cực đại với cận dưới d(i, j) = c(i, j).
    Nhận xét: 40% test n <= 9, 60% test <= 18 ~> thời gian chạy là ok
    đề bài không cho X, Y cụ thể ~> có thể phải sử dụng số nguyên lớn.
    Đây là lời giải ban đầu. Tôi không thích nó vì quá phức tạp cho chém gió vui vui.
• Xào lại bài 3:
  Thay đổi việc tính chi phí sửa đổi Merlon i từ độ cao ai thành độ cao bi là |ai2^(i+x)-bi2^(i+y)|
  Yêu cầu tương tự.
  Output là một hoán vị p1, p2,…pn của b1, b2,…bn. Tức sửa Merlon thứ i từ độ cao ai thành pi chi phí sẽ là nhỏ nhất.
  Cỡ dữ liệu: 2 dãy ai, bi giữ nguyên. 0<=N <=200; X, Y nguyên: 0<=X, Y <=18.

[09520019]

[QUOTE=11520676;34642]- Đúng là tôi không có nhiều thời gian nên dễ nhầm lẫn. Nếu phát hiện thì hãy sửa dùm. Sai lầm nghiêm trọng thì tôi sẽ đính chính lại

• Nếu không muốn trả lời thì có thể im lặng, đừng nên gán cho người khác không biết. Câu hỏi của tôi là giải thích 2 khái niệm bạn đưa ra : Half Brute force attack - Dynamic Programming
  Fully Dynamic Programming - Mathematics.
  Không biết trích dẫn mớ tiếng anh đó để làm gì? Nội dung của nó cũng tương tự như phần tôi nói về quy hoạch động.
• Về bài 3: Đây cũng là lời giải ban đầu:
  +Xây dựng đồ thị 2 phía đầy đủ (A, B). |A| = |B| = n. Trọng số của các cung: C(i, j) = X*(bi - aj) nếu ai > bj; Y*(ai - bj) nếu ai < bj.
  +Đặt đỉnh phát S nối với tất cả các đỉnh của A, đỉnh thu nối với tất cả các đỉnh của B với trọng số + vô cùng.

• Tìm luồng cực đại với cận dưới d(i, j) = c(i, j).
  Nhận xét: 40% test n <= 9, 60% test <= 18 ~> thời gian chạy là ok
  đề bài không cho X, Y cụ thể ~> có thể phải sử dụng số nguyên lớn.
  Đây là lời giải ban đầu. Tôi không thích nó vì quá phức tạp cho chém gió vui vui.

• Xào lại bài 3:
  Thay đổi việc tính chi phí sửa đổi Merlon i từ độ cao ai thành độ cao bi là |ai2^(i+x)-bi2^(i+y)|
  Yêu cầu tương tự.
  Output là một hoán vị p1, p2,…pn của b1, b2,…bn. Tức sửa Merlon thứ i từ độ cao ai thành pi chi phí sẽ là nhỏ nhất.
  Cỡ dữ liệu: 2 dãy ai, bi giữ nguyên. 0<=N <=200; X, Y nguyên: 0<=X, Y <=18.[/QUOTE]
  Sai lầm nghiêm trọng là bạn gán cho Greedy 1 thứ mà nó không bao giờ thuộc về Greedy. Từ trước tới giờ tôi thích greedy algorithm nhất và dĩ nhiên là tôi tìm hiểu rất kỹ. Bạn gán 1 bài DP cho greedy là hết sức bậy bạ. Ở đây cách của tôi làm trong giải thuật có độ phức tạp O(n) là QHĐ. Tôi trích dẫn từ wiki bởi vì bạn nói:

Với khái niệm quy hoạch động ở trên thì cái thuật toán “Fully Dynamic Programming - Mathematics” được trình bày không được “quy hoạch động” cho lắm: phân rã bài toán ra sao? tổng hợp các bài toán nhỏ thế nào? Mà cái giải thuật này cũng dựa trên dãy tổng trước Si.
Tôi cũng đã giải thích là cách của bạn 1 nửa là brute force attack, 1 nửa là QHĐ. Tôi đặt tên như thế chứ tôi không đưa ra khái niệm mới. Bạn đừng nhầm lẫn về chuyện đó.
Bài CTVNEWS: thực ra bài này cực kỳ dễ chỉ cần hiểu đề. Xài 1 mảng tính toán và độ phức tạp O(n^2) là đủ không cần hổ báo tới mức đồ thị 2 phía đầy đủ xyzabc. Đi thi thì nên theo tôn chỉ “as simple as possible”. Tôi ra bài này để bạn thấy đề phát biểu linh tinh thì thường không được hay cho lắm mà nên có lời giải thích từ người ra đề.
Nó quá phức tạp ? Ồ không. Tôi sử dụng 1 mảng 1 chiều A[N] dùng để track các request của lão vua. Vì ta chỉ có N query, mỗi query update tốn O(n) để cập nhật , thực hiện N lần tốn O(n^2), sau đó duyệt mảng A[N] này, nếu A* khác i thì ta tiến hành tính toán giá trị xây tường tương ứng. Còn nếu muốn cả bài làm trong O(n) thì đọc hết tất cả các query, sau khi đọc xong thì update bằng đệ quy. Cách này được chứng minh là chỉ tốn O(n) (Reference: Competitive Programming).
Bài cuối: Sai đề rồi bạn hiền :D. Để ý: Đề bài gốc không đề cập tới từng cá thể Merlon, nên công thức |ai2^(i+x)-bi2^(i+y)| là sai hoàn toàn bởi vì i không xác định. Bài gốc chỉ quan tâm tới việc Merlon có độ cao ai => bi thôi nhé, chỉnh lại thì có thể |ai2^(ai+x)-bi2^(ai+y)|. Với lại bạn cho công thức |2^| … là để đánh đố nhau về cài đặt số nguyên lớn đó hả. Tips: trong khi thi Olympic đề không bao giờ có số nguyên lớn. Tips #2: ACM / ICPC cho đem 25 trang tài liệu vào phòng thi. Và dĩ nhiên đội nào cũng có bignum => bignum là 1 thứ không cần quan tâm. Tip #3: thường thì nên biết tí Java vì Java hỗ trợ bignum sẵn. Nếu bài này bignum thì chúng ta chuyển sang Java vậy =)). Công thức cứ như bên trên mà xử lý. Đầu tiên tôi xét vấn đề “độ cao cuối cùng” của các loại merlon là bao nhiêu, sau đó tôi mới tính tổng chi phí
Thực tế thì mới khởi động tí cho vui thôi. Bạn cứ xào bài người khác cho vấn đề phức tạp lên chán quá. Tôi lại cho bạn bài mới:

Problem
Sean and Patrick are brothers who just got a nice bag of candy from their parents. Each piece of candy has some positive integer value, and the children want to divide the candy between them. First, Sean will split the candy into two piles, and choose one to give to Patrick. Then Patrick will try to calculate the value of each pile, where the value of a pile is the sum of the values of all pieces of candy in that pile; if he decides the piles don’t have equal value, he will start crying.
Unfortunately, Patrick is very young and doesn’t know how to add properly. He almost knows how to add numbers in binary; but when he adds two 1s together, he always forgets to carry the remainder to the next bit. For example, if he wants to sum 12 (1100 in binary) and 5 (101 in binary), he will add the two rightmost bits correctly, but in the third bit he will forget to carry the remainder to the next bit:

1100
+ 0101
------
1001

So after adding the last bit without the carry from the third bit, the final result is 9 (1001 in binary). Here are some other examples of Patrick’s math skills:

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

Sean is very good at adding, and he wants to take as much value as he can without causing his little brother to cry. If it’s possible, he will split the bag of candy into two non-empty piles such that Patrick thinks that both have the same value. Given the values of all pieces of candy in the bag, we would like to know if this is possible; and, if it’s possible, determine the maximum possible value of Sean’s pile.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described in two lines. The first line contains a single integer N, denoting the number of candies in the bag. The next line contains the N integers Ci separated by single spaces, which denote the value of each piece of candy in the bag.
Output
For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1). If it is impossible for Sean to keep Patrick from crying, y should be the word “NO”. Otherwise, y should be the value of the pile of candies that Sean will keep.
Limits
1 ≤ T ≤ 100.
1 ≤ Ci ≤ 106.
Small dataset
2 ≤ N ≤ 15.
Large dataset
2 ≤ N ≤ 1000.
Sample
Input
Output
2
5
1 2 3 4 5
3
3 5 6
Case #1: NO
Case #2: 11
Nguồn: Google code jam 2011 qualification round - bài C - http://code.google.com/codejam/contest/dashboard?c=975485#s=p2
Google dạy cho tôi điều gì ? Sáng tạo trong đề thi. Mỗi lần tôi nghĩ ra mấy cái bài này (và xem đáp án), tôi luôn học được vài mẹo mới, hoặc phải phì cười vì cái đề quá dễ nhưng tự bản thân lại suy nghĩ phức tạp lên.
Sẵn thêm 1 vài thông tin cho bạn: Sinh viên CNTT nói chung thường không hào hứng lắm với giải thuật. Và nó cũng đúng trong thực tế khi các soft nhiều chức năng nhưng xấu lại ít được xài, các soft đẹp đẽ ít chức năng lại đc nhiều người xài. Bạn cho đề càng khó thì càng ít người tham gia. Tôi trả lời bài của cậu cũng chỉ là đam mê giải bài Olympic thôi. Chứ hiện tại tôi đang tạm gác Olympic qua 1 bên nên tôi không giải bài thêm nữa nhé :D. Trả topic này cho chủ thớt.

[11520399]

11520676
Phạm Quốc Tuấn
Không ngờ lớp KHMT của mình lại có nhân tài giỏi thế này!
I like you… =]]

[11520676]

• Xin nhắc lại: Thuật toán tham lam ở bài 1 tôi chưa trình bày. Do đó đừng nhận xét nó đúng hay sai là tham lam
  Trong bài 1 mỗi cái gạch đầu dòng là một thuật toán. Ở đó không có thuật toán lai tạp giữa quy hoạch động và vét cạn.
• 2 cái thuật toán tiếng anh kia tôi hỏi lại lý do là: Bạn nghĩ ra một cái tên thuật toán bằng tiếng anh; đưa ra1 loại tiếng anh trong bài viết mà không giải thích. Trong khi đó bạn chỉ trích tôi đố chữ. Nếu có thể, xin hãy viết = tiếng Việt. Không phải ai vào topic này cũng hiểu được những gì bạn viết.
• Về cái bài CTNews:
  +

Ngài CTN muốn sửa chữa lâu đài thành một mẫu mới , anh ta đã làm một danh sách N số nguyên B_1…B_N (1<=B_i<=100000) , và anh muốn thay đổi chiều cao của các Merlon từ (A1…An) thành (B1…Bn) theo một thứ tự nào đó.
. Ở đây, tôi hiểu là tìm giá trị bé nhất trong các chi phí của N! hoán vị của (B1…Bn). Tôi chưa tìm thêm được lời giải nào tốt hơn đã đưa ra. Nếu có, xin hãy chỉ ra.

• Do hạn chế thời gian nên đã có mấy chỗ post bậy:D Vì mạng đựng trên đồ thị 2 phía nên điều kiện cận dưới là không cần thiết. Nên cộng thêm một số đủ lớn sao cho trọng số các cạnh đều lớn hơn 0(Để đưa về đúng dạng phát biểu lý thuyết của luồng). Tất nhiên dùng luồng trong mạng là phức tạp. Bài toán luồng có cận dưới cũng vậy. Và cũng không có ý định bàn đến các thuật toán cỡ này trong 1 topic chém gió.

• Tôi chưa tham gia ACM / ICPC gì gì đó, cũng không có ý định tham gia. Việc nói số nguyên lớn là khi yêu cầu không nói rõ, ta phải lường trước trường hợp xấu nhất. Bạn nên dịch ra tiếng Việt khi ra bài từ các cuộc thi. Không phải ai cũng hiểu đề bài. Tất nhiên là tôi không có ý định giải mấy bài đó.
• Bạn nói đúng khi bảo it người quan tâm đến giải toán Olympic. Nhưng phân tích sâu bài toán từ dễ đến khó thì rất có lợi. Đặc biệt là các bạn năm nhất. Ví dụ cái tổng trước trong bài 1: http://en.wikipedia.org/wiki/Prefix_sum. Không biết KHMT trường mình có học tính toán song song không?

-À quên, cái bài xào lại chỉ hỏi 1 thuật toán tham lam loại bỏ trường hợp các số nguyên lớn trong C

[11520676]

@Vũ Phú Thức: Lớp mình nhiều nhân tài lắm

[09520019]

[QUOTE=11520676;34779]- Xin nhắc lại: Thuật toán tham lam ở bài 1 tôi chưa trình bày. Do đó đừng nhận xét nó đúng hay sai là tham lam
Trong bài 1 mỗi cái gạch đầu dòng là một thuật toán. Ở đó không có thuật toán lai tạp giữa quy hoạch động và vét cạn.
[/QUOTE]
Đây là giải bài toán, chứ không phải là phát biểu 1 thuật toán mới. Vì bạn giải 1 bài toán thì bạn được phép sử dụng nhiều thuật toán. Ví dụ - Chia để trị + chặt nhánh
Tham lam + QHĐ

[QUOTE=11520676;34779]

• 2 cái thuật toán tiếng anh kia tôi hỏi lại lý do là: Bạn nghĩ ra một cái tên thuật toán bằng tiếng anh; đưa ra1 loại tiếng anh trong bài viết mà không giải thích. Trong khi đó bạn chỉ trích tôi đố chữ. Nếu có thể, xin hãy viết = tiếng Việt. Không phải ai vào topic này cũng hiểu được những gì bạn viết.
  [/QUOTE]
  Tôi nói cách làm của bạn, chứ tôi không nói tên 1 thuật toán. Bạn vẫn không hiểu hay cố tính không hiểu đấy ?

[QUOTE=11520676;34779]

• Về cái bài CTNews:
  +. Ở đây, tôi hiểu là tìm giá trị bé nhất trong các chi phí của N! hoán vị của (B1…Bn). Tôi chưa tìm thêm được lời giải nào tốt hơn đã đưa ra. Nếu có, xin hãy chỉ ra.
  [/QUOTE]
  Vậy xin mời bạn giải thích test
  Input:
  3 6 5
  3 1
  1 2
  1 2
  Output:
  11
  Tại sao lại ra 11 ?

[QUOTE=11520676;34779]

• Do hạn chế thời gian nên đã có mấy chỗ post bậy:D Vì mạng đựng trên đồ thị 2 phía nên điều kiện cận dưới là không cần thiết. Nên cộng thêm một số đủ lớn sao cho trọng số các cạnh đều lớn hơn 0(Để đưa về đúng dạng phát biểu lý thuyết của luồng). Tất nhiên dùng luồng trong mạng là phức tạp. Bài toán luồng có cận dưới cũng vậy. Và cũng không có ý định bàn đến các thuật toán cỡ này trong 1 topic chém gió.

• Tôi chưa tham gia ACM / ICPC gì gì đó, cũng không có ý định tham gia. Việc nói số nguyên lớn là khi yêu cầu không nói rõ, ta phải lường trước trường hợp xấu nhất. Bạn nên dịch ra tiếng Việt khi ra bài từ các cuộc thi. Không phải ai cũng hiểu đề bài. Tất nhiên là tôi không có ý định giải mấy bài đó.
  [/QUOTE]
  Ngắn gọn thế này: Đề không nói rõ nên tôi xài Java đấy. Java có sẵn thư viện bignum. Bài tôi cho bạn xài int(C++) / longint(C++) là đủ rồi :))
  [QUOTE=11520676;34779]
• Bạn nói đúng khi bảo it người quan tâm đến giải toán Olympic. Nhưng phân tích sâu bài toán từ dễ đến khó thì rất có lợi. Đặc biệt là các bạn năm nhất. Ví dụ cái tổng trước trong bài 1: http://en.wikipedia.org/wiki/Prefix_sum. Không biết KHMT trường mình có học tính toán song song không?[/QUOTE]
  Đôi khi không học mà người ta biết hết rồi đấy bạn. A,B,C thẳng hàng, B nằm giữa A C, đã biết AB AC, tính BC = AC - AB

[QUOTE=11520676;34779]

• Tôi chưa tham gia ACM / ICPC gì gì đó, cũng không có ý định tham gia. Bạn nên dịch ra tiếng Việt khi ra bài từ các cuộc thi. Không phải ai cũng hiểu đề bài. Tất nhiên là tôi không có ý định giải mấy bài đó.
  [/QUOTE]
  O_o Thế mà hôm trước có người nói “- Còn việc phân biệt đoạn con và dãy con thì ai học tin được vài năm đều rõ.” “Giải tích 11 chương trình cũ.” =)), Trong khi tiếng anh thì bộ GD & ĐT cho học từ năm lớp một đến lớp 12…

Mà thôi kệ chúng ta không nên làm khó nhau chứ nhẩy ^_^, ngắn gọn về đề bài:

• Sean và Patrick được cho 1 bao kẹo to, và 2 đứa muốn chia kẹo sao cho công bằng
• Patrick là đứa em, rất dở làm phép tính cộng, gần như là biết làm phép cộng nhị phân, tuy nhiên khi cộng hai số 1 với nhau thì Patrick luôn luôn quên nhớ phần dư 1 để cộng vào bit tiếp theo. Ví dụ nếu Patrick làm phép cộng 12 (1100 trong hệ nhị phân) và 5 (101 trong hệ nhị phân) thì làm đúng 2 bit bên phải, nhưng đến 2 bit bên trái thì làm sai

  1100
+ 0101
------
  1001

Vậy là kết quả cuối cùng của Patrick trong phép tính đó là 9 (1001 hệ nhị phân). Sau đây là vài ví dụ khác về khả năng tính toán của Patrick:

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

• Sean là anh trai, làm phép cộng rất giỏi và muốn chiếm kẹo của em sao cho Patrick không khóc, và nếu được thì Sean muốn chia ra thành 2 phần sao cho 2 phần không đều nhau, nhưng Patrick lại tưởng là 2 phần này đều nhau.
• Như vậy chúng ta sẽ cho biết giá trị của tất cả các cục kẹo, và muốn biết là cách chia có khả thi hay không, nếu khả thi thì hãy cho biết tổng giá trị số kẹo của Sean

Input:
Dòng đầu chứa số T là số test. T test sau, mỗi test chiếm 2 dòng.
Với mỗi test, dòng một chứa số N là số kẹo trong bịch
Dòng thứ hai chứa N số nguyên Ci, cách nhau bởi 1 dấu cách, Mỗi số nguyên Ci đại diện cho giá trị 1 viên kẹo trong bịch

Output
Với mỗi test, output 1 dòng ghi : “Case #x: y”, với x là số thứ tự của test (bắt đầu từ 1)
Nếu việc chia kẹo là bất khả thi, y sẽ là chữ “NO”, ngược lại, y sẽ là tổng giá trị các viên kẹo mà Sean sẽ có

giới hạn:

1 ≤ T ≤ 100.
1 ≤ Ci ≤ 106.

Test nhỏ: 2 ≤ N ≤ 15.
Test lớn: 2 ≤ N ≤ 1000.

Ví dụ:

Input

2
5
1 2 3 4 5
3
3 5 6

Output

Case #1: NO
Case #2: 11

Bonus: Giải thích test cho bạn tí (lỡ bạn bảo là không hiểu test xD, phần này không có trong đề gốc)
Test 1: cho 1 2 3 4 5, không có cách chia
Test 2: cho 3 5 6, patrick có 3, sean có (5 6) = 11, Patrick làm phép toán 5 + 6 = 3 nên Patrick nghĩ là 2 phần bằng nhau

[11520676]

• Tôi không nói 2 cách làm ban đầu là tham lam. Sao bạn cứ cố tình nói sai về điều đó.

Mình mới chỉ nghĩ ra thuật toán tham lam thế này:

Ơ lười trình bày, hôm nào có hứng viết tiếp
Tức là thuật toán tham lam dựa trên việc xây dựng dãy prefix sum sẽ được trình bày khi khác. Nói thêm điều làm tôi khó chịu vì đoạn con, dãy con mà giải thích 2, 3 lần bạn vẫn cố tình không hiểu. Nói thêm nếu bạn muốn nói dùng nhiều thuật toán thì sử dụng gì đó như the combination of brute force and dynamic programming viết như bạn nghe buồn cười lắm.

• Cái kết quả 11 là do 3 - 2 chi phí 6; 1- 1 chi phí 0; 1 - 2 chi phí 5. Cách xây dựng ở đây b2, b1, b3 là hoán vị của b1, b2, b3.
• Bạn thích dùng bignum thì tùy bạn. Khi đó như đề bài, bạn cứ việc giải quyết bài toán cặp ghép có trọng số với dữ liệu N <= 25000, còn trọng số tăng theo hàm mũ.
• Lời cuối, tôi lập topic này mong mấy bạn năm nhất (KHMT nói riêng) quen với việc giải toán. Không phải để làm mấy bài Olympic hay nghe bạn đi thi nhiều, càng không phải đôi co với bạn. Mục đích thì đã không đạt được rồi, bạn muốn nói thêm gì thì tùy. Khuyên bạn nên coi lại cách tranh luận của mình. Muốn phản bác thì ít ra cũng chắc chắn mình hiểu ng ta muốn nói gì trước.

[09520019]

[QUOTE=11520676;34788]- Tôi không nói 2 cách làm ban đầu là tham lam. Sao bạn cứ cố tình nói sai về điều đó. Tức là thuật toán tham lam dựa trên việc xây dựng dãy prefix sum sẽ được trình bày khi khác. Nói thêm điều làm tôi khó chịu vì đoạn con, dãy con mà giải thích 2, 3 lần bạn vẫn cố tình không hiểu. Nói thêm nếu bạn muốn nói dùng nhiều thuật toán thì sử dụng gì đó như the combination of brute force and dynamic programming viết như bạn nghe buồn cười lắm.
[/QUOTE]

• Bạn nên xem lại tôi hỏi bao nhiêu lần ? Tôi chỉ hỏi 1 lần duy nhất ở #5 và không hỏi lần thứ 2. Đừng ngậm máu phun người thế
• Sao lại buồn cười nhỉ ? Không chấp nhận được à. Thế thì làm tốt hơn xem sao.

[QUOTE=11520676;34788]

• Cái kết quả 11 là do 3 - 2 chi phí 6; 1- 1 chi phí 0; 1 - 2 chi phí 5. Cách xây dựng ở đây b2, b1, b3 là hoán vị của b1, b2, b3.
  [/QUOTE]
  Tôi không nhìn thấy hoán vị nào ở đây cả. Bạn làm ơn chỉ rõ giùm.
  3 1 1 với 2 1 2 không liên quan gì tới hoán vị của 1 2 3 cả.
  [QUOTE=11520676;34788]
• Bạn thích dùng bignum thì tùy bạn. Khi đó như đề bài, bạn cứ việc giải quyết bài toán cặp ghép có trọng số với dữ liệu N <= 25000, còn trọng số tăng theo hàm mũ.
  [/QUOTE]
  Bạn không thèm đọc bài giải của tôi nên việc nhận xét của bạn thật sự thừa thải :)). Trong trường hợp tốt nhất tôi vẫn giải được với độ phức tạp dao động từ O(n log n) tới O(n), bạn cứ lên google search “Disjoint set” :)). Nên N <= 25k vẫn không làm khó được tôi :)).

[QUOTE=11520676;34788]

• Lời cuối, tôi lập topic này mong mấy bạn năm nhất (KHMT nói riêng) quen với việc giải toán. Không phải để làm mấy bài Olympic hay nghe bạn đi thi nhiều, càng không phải đôi co với bạn. Mục đích thì đã không đạt được rồi, bạn muốn nói thêm gì thì tùy. Khuyên bạn nên coi lại cách tranh luận của mình. Muốn phản bác thì ít ra cũng chắc chắn mình hiểu ng ta muốn nói gì trước.[/QUOTE]
• Tốt thôi. Thế thì đừng cho bài khó quá, người khác làm không được và bạn lại chứng minh được sự tài giỏi của mình (thông qua việc không ai thèm giải). Mà nhìn như do bạn thấy không ai thèm giải nên muốn chứng tỏ gì đó nên khi có người giải được thì bực bội và cho đề khó hơn :)). Nếu bạn muốn mục đích của người khác quen với việc giải toán, trước hết bạn hãy cho người khác cái gì đó để họ tham khảo. Bạn kêu 1 người không biết gì vào làm 1 việc, bắt họ thất bại để thành công à ? Xin lỗi chứ trên thực tế nếu người hướng dẫn không cẩn thận thì đôi khi sẽ làm cho người khác mất căn bản.

[11520676]

• Bạn bắt bẻ tôi đoạn con, dãy con trong mấy bài viết?
• (b2 b1 b3) = (2, 1, 2) có phải là hoán vị của (b1 b2 b3) = (1, 2, 2) không? Tôi đã ghi rõ ràng ở ngay trong câu trích dẫn.
• Làm tốt hơn là cái phần in đậm mà bạn trích dẫn đó.
• Bài 1 chỉ yêu cầu đến cái bạn gọi là brute force. Thế thì có gọi là khó không? Còn có thêm quy hoạch động thì ai đề xuất đầu tiên? Ai lôi bài tập Olympic vào đánh đố mọi người?

Post thêm bài này vì thấy hiểu sai ý tôi nhiều quá.

[07520118]

Bạn Tuấn ơi, mình không nhớ khái niệm đoạn con và dãy con (nói thật mọi người đừng hiểu nhầm), bạn giải thích giúp mình với, mình đọc mãi bài của hai bạn mà không hiểu gì hết, hic, gà quá. Nhìn vô giải thích thấy toàn tiếng Anh không, lùng bùng cả đầu :(.

(Xin lỗi trước vì câu hỏi hơi ngoài lề, nhưng tại đọc mãi không hiểu nên hỏi lại :">, mọi người thông cảm).

[11520676]

Vâng trả lời bạn là tôi không post 1 câu tiếng anh khó hiểu nào.
Đoạn con của dãy a bắt đầu từ i độ dài l là dãy{ai, ai+1,… ai+l-1}
còn đoạn con l phần tử của dãy a là dãy thu được bằng cách bỏ n - l phần tử nào đó của dãy ban đầu(n là số phần tử ban đầu).
Cái này không phải định nghĩa. Nhưng chắc với MSV 07520118 không khó để bạn hiểu.
Đây là bài post cuối cùng của tôi trong topic này.

[07520118]

[QUOTE=11520676;34793]Vâng trả lời bạn là tôi không post 1 câu tiếng anh khó hiểu nào.
Đoạn con của dãy a bắt đầu từ i độ dài l là dãy{ai, ai+1,… ai+l-1}
còn đoạn con l phần tử của dãy a là dãy thu được bằng cách bỏ n - l phần tử nào đó của dãy ban đầu(n là số phần tử ban đầu).[/QUOTE]

À, chắc tại thấy tiếng Anh nhiều quá nên mình đọc nhầm, xin lỗi bạn, hic.

Mình không hiểu lắm, thấy bạn bảo đoạn con == subsequence, có google thử, nó ra cái này: http://en.wikipedia.org/wiki/Subsequence, đọc không hiểu lắm, bạn giải thích hộ mình được không?

Hic hic, xin lỗi, mình hơi gà, bạn thông cảm, học hết cơm hết gạo mà có mấy cái khái niệm mãi không hiểu :(.

[09520019]

[QUOTE=11520676;34791]- Bạn bắt bẻ tôi đoạn con, dãy con trong mấy bài viết?[/QUOTE]
=)) Buồn cười
Hồi nãy bảo là “Nói thêm điều làm tôi khó chịu vì đoạn con, dãy con mà giải thích 2, 3 lần bạn vẫn cố tình không hiểu.”, bây giờ lại hỏi câu “Bạn bắt bẻ tôi đoạn con, dãy con trong mấy bài viết”. Tôi bắt bẻ trong 2 ~ 3 bài đấy. Bạn sỉ vả người khác bằng mấy bài viết thế nhỉ ?

[QUOTE=11520676;34791]

• (b2 b1 b3) = (2, 1, 2) có phải là hoán vị của (b1 b2 b3) = (1, 2, 2) không? Tôi đã ghi rõ ràng ở ngay trong câu trích dẫn.
  [/QUOTE]
  À được rồi. Có 2 ý hiểu đề khác nhau, cách hiểu của bạn nghe cũng hợp lý, tuy nhiên code đúng sai mới là quan trọng Có thể tôi sai chăng, cái này chưa biết được, mà hiện tại tôi không code được nên tôi sẽ submit thẳng lên spoj sau. Nếu bạn không chờ được thì cứ sub trước đi để tôi đỡ mất công

[QUOTE=11520676;34791]

• Làm tốt hơn là cái phần in đậm mà bạn trích dẫn đó.
  [/QUOTE]
  O(n^2) tốt hơn O(n) ư ? Chuyện mới nghe O_o

[QUOTE=11520676;34791]

• Bài 1 chỉ yêu cầu đến cái bạn gọi là brute force. Thế thì có gọi là khó không? Còn có thêm quy hoạch động thì ai đề xuất đầu tiên? Ai lôi bài tập Olympic vào đánh đố mọi người?
  [/QUOTE]
  Thế ai lôi tham lam ra trước nhỉ ? O_o

[QUOTE=11520676;34793]Vâng trả lời bạn là tôi không post 1 câu tiếng anh khó hiểu nào.[/QUOTE]
Prefix sum, what is it ?
Wiki English luôn

[QUOTE=11520676;34793]
Nhưng chắc với MSV 07520118 không khó để bạn hiểu.[/QUOTE]

Bạn nên nhớ 1 điều rằng có những người đặt chân vào trường và không học thuật toán. Trong 2 năm đầu rất ít thuật toán bá đạo tới mức nào là tham lam, nào là cặp ghép, nhưng tôi đảm bảo với bạn: trong vòng 1.5 ngày bạn không thể (hoặc rất cố gắng) để code 1 soft ngon lành cành đào (các pro CNPM), hay bạn không giỏi cấu hình mạng, không thể quản trị mạng, không thể hack bất kỳ web nào
(MMT), hay cài đặt tối ưu tới mức cộng trừ nhân chia 1 phép tính trên số nguyên có tốc độ bằng với xử lý số thực (KTMT), hay bạn không thể … vào ngân hàng làm việc (HTTT) :)). Bạn chỉ có thể bá đạo khu KHMT thôi, nhưng bạn có chắc bạn dám làm được 1 chương trình nhận dạng chữ viết ? Bạn có chắc làm được chương trình nhận dạng hành động ? Bạn có thể xử lý ngôn ngữ như Siri ? Với kiến thức hiện nay và tầm 2 năm nữa, bạn chỉ bá đạo được khu vực Olympic thuật toán mà thôi (Olympic mã nguồn mở bạn cũng khôngcó cửa đâu). Nên biết chỗ của bạn, của người khác, ngồi xuống và bớt cho rằng ai cũng phải hiểu bạn đi. Tại sao không thêm ví dụ:
7 8 9 6 2 3 5 4 1 2 là 1 dãy
9 6 2 3 5 là đoạn con của dãy bên trên ?
Đọc lại các sách và xem thử có sách nào không có ví dụ đằng sau các phát biểu hay không

[QUOTE=11520676;34788]Khuyên bạn nên coi lại cách tranh luận của mình. Muốn phản bác thì ít ra cũng chắc chắn mình hiểu ng ta muốn nói gì trước.[/QUOTE]
Xem bạn đã dùng những từ ngữ gì ha:
[QUOTE=11520676;34591]
[QUOTE=07520004;34587]Anh học lâu rồi nhớ mãi không ra được, có lẽ tết nhất rảnh rỗi cần xem lại một tí, em nhắc hộ anh xem mấy khái niệm này định nghĩa ở sách nào, chương mấy, bài nào vậy em?[/QUOTE]
Giải tích 11 chương trình cũ.
Nếu không học thì học mảng các thầy cũng chỉ cho. Nếu chưa học mảng thì đừng làm bài này.
PS: Từ giờ mình không trả lời các câu hỏi nằm ngoài chủ đề topic thế này.[/QUOTE]
Bạn dùng từ ngữ thế nào, tôi dùng từ ngữ thế ấy. ở #14 (trước khi bạn post cái comment như thế), tôi sử dụng từ ngữ rất nhã nhặn với bạn. Đừng nói là bạn cho rằng K2 mà chưa học mảng thì tôi thấy buồn cười lắm đấy.

[QUOTE=11520676;34793]
Đây là bài post cuối cùng của tôi trong topic này.
[/QUOTE]
Đừng cư xử như 1 đứa trẻ.

[07520350]

07520118
-> thằng này đi thi olympic mà xạo hả mạy! Các bạn chém em nó dữ quá, post bài lên thảo luận theo hướng tích cực thôi, hết bắt bẽ lại vạch chỗ này khích chỗ kia. Thằng nào ngon ra đây tay đôi câu này:

• Có 2 chiếc xe ô tô cùng chạy song song trên đoạn đường dài 15km, vận tốc 2 xe ngang nhau 90km/h. Phía sau, 2 xe cùng kéo một vật nặng 1,5 tấn. Sau đó nữa, 20 chiếc xe cảnh sát chạy với vận tốc 100km/h. Trên đoạn đường đó, cứ cách 5km lại có 1 dốc cong dài 1km. Tính phương án tốt nhất để 2 xe qua khỏi đoạn đường đó mà không bị bắt. Biết bề ngang đoạn đường chỉ vừa đủ cho 3 xe chạy song song.
• Giải thích một chút: bài này nhìn sơ qua cứ tưởng tính toán đơn thuần, nhưng thực tế sử dụng thuật toán “chia để trị”. Gợi ý rồi đó. Ai rảnh rỗi thử viết chương trình mô phỏng xem.

[09520019]

[QUOTE=07520350;34802]Gợi ý rồi đó. Ai rảnh rỗi thử viết chương trình mô phỏng xem.[/QUOTE]

Sao anh ra đề giống thầy Đăng thế ^^, ra đề là phải có chương trình mô phỏng ^^

[QUOTE=07520350;34802]

• Có 2 chiếc xe ô tô cùng chạy song song trên đoạn đường dài 15km, vận tốc 2 xe ngang nhau 90km/h. Phía sau, 2 xe cùng kéo một vật nặng 1,5 tấn. Sau đó nữa, 20 chiếc xe cảnh sát chạy với vận tốc 100km/h. Trên đoạn đường đó, cứ cách 5km lại có 1 dốc cong dài 1km. Tính phương án tốt nhất để 2 xe qua khỏi đoạn đường đó mà không bị bắt. Biết bề ngang đoạn đường chỉ vừa đủ cho 3 xe chạy song song.
  [/QUOTE]
  “Sau đó nữa, 20 chiếc xe cảnh sát chạy với vận tốc 100km/h.” ==> Sau đó là bao xa vậy anh ?
  Dốc cong dài 1km => ý anh là leo dốc thì vận tốc bị giảm hả hay có ràng buộc gì khác không anh ? (Ví dụ lên dốc phải làm gì đó, xuống dốc phải làm gì đó O_o, chẳng hạn như bị đứt dây).
  Vì xe chứa trọng lượng khá lớn (15 tấn), nên độ trễ của việc tăng/giảm tốc là bao lâu ? Hay giả sử vận tốc sẽ tăng ngay lập tức ?
  Trong trường hợp có độ trễ đi, thì khoảng cách giữa xe và vật nặng là bao xa ?