[Thuật toán] THÁCH THỨC TOÀN THỂ SINH VIÊN UIT

[10520189]

lại 1 nhân tài xuất chúng xuất hiện.UIT dạo này nhùi gạch đá quá

Anh Huy hỏi cho e 1 slot với đc ko? tình hình là cũng đang nghiên cứu thuật mà nhiều cái khó hiểu nên cần tutor =.=

[10520058]

Anh Huy cho e hỏi nhóm Thuật toán đó ở đâu vậy ???

đó là một nhóm tự lập thôi bạn ah, bạn nên hỏi leader của nhóm đó mình chỉ làm định hướng cho nhóm thôi
nếu bạn thấy ai hợp ý về nhóm học t6a5 nên làm một nhóm ^_^

Anh Huy cho e hỏi nhóm Thuật toán đó ở đâu vậy ???

[08520604]

Nhóc Huy nói nhiều làm gì cứ bảo bạn ý nói tên trường ra, rồi vào diễn đàn trường bạn ý post bài "Thách các bạn trường xyz làm được bài này" xem thử gạch đá có ít hơn trường mình không, hay là được nâng cấp lên thành lựu đạn với AK luôn.

Thôi đừng anh , có khi cả trường chúng ta lại nhận phải cái này thì ...

[07520182]

cám ơn góp ý của bạn
mình xin trà lời bạn như sau, tình hình của trường thì mình hok rõ nhưng K6 mới vào đã có nhiều bạn rất đặc biệt, mình đang có ý tập hợp họ lại và đã có một nhóm rất tốt về thuật toán (khời đầu ý tưởng thôi ), nếu đầu tư cho họ có thể những điều bạn nói sẽ không diễn ra
rất cám ơn góp ý của bạn cho trường ^_^

Nhóc Huy nói nhiều làm gì cứ bảo bạn ý nói tên trường ra, rồi vào diễn đàn trường bạn ý post bài "Thách các bạn trường xyz làm được bài này" xem thử gạch đá có ít hơn trường mình không, hay là được nâng cấp lên thành lựu đạn với AK luôn.

[10520058]

cám ơn góp ý của bạn
mình xin trà lời bạn như sau, tình hình của trường thì mình hok rõ nhưng K6 mới vào đã có nhiều bạn rất đặc biệt, mình đang có ý tập hợp họ lại và đã có một nhóm rất tốt về thuật toán (khời đầu ý tưởng thôi ), nếu đầu tư cho họ có thể những điều bạn nói sẽ không diễn ra
rất cám ơn góp ý của bạn cho trường ^_^

[07520182]

Hi. Chào các UIT-er. Mình có 1 số điều muốn tâm sự. Hi. Nói thiệt dù sao thì sau khi đọc tới đây mình cũng thấy vui.
Vì sự thật, mình có bạn học bên UIT, và mình cũng là fan của thuật toán mà trường mình thì hok phong trào không phổ biến. Mình nghĩ trường chuyên về công nghệ thông tin như UIT đây thì chắc chắn sẽ có nhiều nhân tài. Nhưng theo mình biết thì phong trào thuật toán ở UIT chẳng mấy nổi trội nếu không muốn nói là ko có j là phổ biến trong UIT. Mình cũng muốn biết đó chỉ là che mắt người ngoài hay thực sự là vậy, nên mình mới to gan vào đây khiêu chiến. Mình cũng muốn được học hỏi các pro của UIT.
Sau khi mình lập topic này thì cũng có nhiều suy nghĩ muốn bộc bạch cho các UIT biết:
1. Thuật toán là một lĩnh vực thú vị trong ngành công nghệ thông tin. Những ai đã học nhiều về thuật toán ắt hẳn cũng biết những lợi ích của nó. Trong một lớp nếu có một bạn học thuật toán đạt đến trình độ của Olympic thì chắc chắn sẽ khác với một bạn không biết gì về thuật toán, khác về suy nghĩ, phân tích, lập luận vấn đề, khả năng viết code, và hiệu suất.
2. Lúc đầu mình nghĩ trường UIT là trường chuyên về công nghệ thông tin và sắp tới còn được đầu tư để trở thành trường hàng đầu về công nghệ thông tin thì về lĩnh vực thuật toán trong trường chắc cũng mạnh lắm. Nhưng tới giờ thì mình cũng biết sơ rằng: Về thuật toán thì ở UIT chỉ có 1 số bạn học tập và nghiên cứu, và nếu mình không nhầm thì ngoài đội tuyển olympic hiện tại chắc cũng chẳng còn nhân tài nào đâu nhỉ? Mình thấy đội tuyển này đã tham gia nhiều năm, và không có thành viên mới nổi trội. Chắc là trường đang thiếu nhân lực về lĩnh vực này rồi. Một chứng minh đơn giản là bài tập mình cho chỉ có 1 bạn làm được. Haizz
3. Mình nhận thấy một thực tế là có bạn khóa 5, 6 gì đó cũng làm được một phần của bài này. Như vậy nghĩa là có thể còn nhiều bạn khác cũng có trình độ cỡ bạn này (bạn Tú thì phải). Mới vào mà có trình độ đó thì thật là 1 khởi đầu thuận lợi. Nếu tiếp tục đầu tư thì khả năng UIT đứng đầu trong các kì thi về thuật toán như Olympic, ACM/ICPC sẽ trong tầm tay. Hi vọng trường các bạn chú ý đến điểm này và tạo điều kiện cho những bạn đó tiếp tục phát triển tài năng.
4. Gởi Thầy bí thư: Phần quà thì em nghĩ thầy đã hiểu rồi.
Kết luận: UIT đang đứng trước nguy cơ cạn kiệt về nhân tài Olympic để tham gia các kì thi như thế.
Cuối cùng, mình chúc cho UIT ngày càng phát triển về mọi lĩnh vực nói chung và lĩnh vực thuật toán đầy thú vị này nói riêng.
Cám ơn các bạn đã đọc lời tâm sự của mình. Chúc các bạn sức khỏe.
Thân
Anonymous

Chẳng qua là nhiều người vô thấy cái tiêu đề xong đi ra chẳng buồn đọc nội dung vì nó quá ư là không chấp nhận được.
Không tin bạn qua diễn đàn mấy trường khác như BK, Tự Nhiên hay SPKT rồi đăng bài với tiêu đề và nội dung thế này xem sẽ nhận được bài giải hay là gạch với đá y chang như bên đây

Hi. Chào các UIT-er. Mình có 1 số điều muốn tâm sự. Hi. Nói thiệt dù sao thì sau khi đọc tới đây mình cũng thấy vui.
Vì sự thật, mình có bạn học bên UIT, và mình cũng là fan của thuật toán mà trường mình thì hok phong trào không phổ biến. Mình nghĩ trường chuyên về công nghệ thông tin như UIT đây thì chắc chắn sẽ có nhiều nhân tài. Nhưng theo mình biết thì phong trào thuật toán ở UIT chẳng mấy nổi trội nếu không muốn nói là ko có j là phổ biến trong UIT. Mình cũng muốn biết đó chỉ là che mắt người ngoài hay thực sự là vậy, nên mình mới to gan vào đây khiêu chiến. Mình cũng muốn được học hỏi các pro của UIT.
Sau khi mình lập topic này thì cũng có nhiều suy nghĩ muốn bộc bạch cho các UIT biết:
1. Thuật toán là một lĩnh vực thú vị trong ngành công nghệ thông tin. Những ai đã học nhiều về thuật toán ắt hẳn cũng biết những lợi ích của nó. Trong một lớp nếu có một bạn học thuật toán đạt đến trình độ của Olympic thì chắc chắn sẽ khác với một bạn không biết gì về thuật toán, khác về suy nghĩ, phân tích, lập luận vấn đề, khả năng viết code, và hiệu suất.
2. Lúc đầu mình nghĩ trường UIT là trường chuyên về công nghệ thông tin và sắp tới còn được đầu tư để trở thành trường hàng đầu về công nghệ thông tin thì về lĩnh vực thuật toán trong trường chắc cũng mạnh lắm. Nhưng tới giờ thì mình cũng biết sơ rằng: Về thuật toán thì ở UIT chỉ có 1 số bạn học tập và nghiên cứu, và nếu mình không nhầm thì ngoài đội tuyển olympic hiện tại chắc cũng chẳng còn nhân tài nào đâu nhỉ? Mình thấy đội tuyển này đã tham gia nhiều năm, và không có thành viên mới nổi trội. Chắc là trường đang thiếu nhân lực về lĩnh vực này rồi. Một chứng minh đơn giản là bài tập mình cho chỉ có 1 bạn làm được. Haizz
3. Mình nhận thấy một thực tế là có bạn khóa 5, 6 gì đó cũng làm được một phần của bài này. Như vậy nghĩa là có thể còn nhiều bạn khác cũng có trình độ cỡ bạn này (bạn Tú thì phải). Mới vào mà có trình độ đó thì thật là 1 khởi đầu thuận lợi. Nếu tiếp tục đầu tư thì khả năng UIT đứng đầu trong các kì thi về thuật toán như Olympic, ACM/ICPC sẽ trong tầm tay. Hi vọng trường các bạn chú ý đến điểm này và tạo điều kiện cho những bạn đó tiếp tục phát triển tài năng.
4. Gởi Thầy bí thư: Phần quà thì em nghĩ thầy đã hiểu rồi.
Kết luận: UIT đang đứng trước nguy cơ cạn kiệt về nhân tài Olympic để tham gia các kì thi như thế.
Cuối cùng, mình chúc cho UIT ngày càng phát triển về mọi lĩnh vực nói chung và lĩnh vực thuật toán đầy thú vị này nói riêng.
Cám ơn các bạn đã đọc lời tâm sự của mình. Chúc các bạn sức khỏe.
Thân
Anonymous

[09520234]

Chúc mừng các bạn, vậy là cuối cùng đã có người giải được, mình cũng chỉ là kẻ vô danh tiểu tốt, sau này khi mình mạnh hơn sẽ thách đấu tiếp, hy vọng đến lúc đó vẫn có người giải được. Thank tất cả những bạn tích cực đóng góp cho topic này. Xin phép được close topic tại đây, mọi gạch đá về sau mình don't care.

Topic hot quá, ngồi đọc từ page 1 -> 7
Chủ topic nói rằng sau khi có người giải xong thì nói chuyện tiếp mà, sao lại xin close topic rồi :S

[BiThuDoan]

Chúc mừng các bạn, vậy là cuối cùng đã có người giải được, mình cũng chỉ là kẻ vô danh tiểu tốt, sau này khi mình mạnh hơn sẽ thách đấu tiếp, hy vọng đến lúc đó vẫn có người giải được. Thank tất cả những bạn tích cực đóng góp cho topic này. Xin phép được close topic tại đây, mọi gạch đá về sau mình don't care.

Hơ ! Bạn ơi! Quà đâu?

[10520058]

thật ra thì bạn dùng từ khiêm tốn hơn chút có lẽ đã có đáp án từ lâu rồi hi vọng lần thách đấu sau bạn dùng từ ngữ khiêm tốn hơn

Chúc mừng các bạn, vậy là cuối cùng đã có người giải được, mình cũng chỉ là kẻ vô danh tiểu tốt, sau này khi mình mạnh hơn sẽ thách đấu tiếp, hy vọng đến lúc đó vẫn có người giải được. Thank tất cả những bạn tích cực đóng góp cho topic này. Xin phép được close topic tại đây, mọi gạch đá về sau mình don't care.

[10520365]

cái này giống trang web con của vnoi.info quá. các bạn,anh,chị em có thể qua vnoi.info tập giải thuật cho vui. hi. mình qua hoài mà không làm d0ược gì. vì quá gà

[09520019]

Làm bài xong....tình hình là mấy bữa nay đã ức chế vì ế hành rồi.....need someone or something to cool me down....
Bạn Tú làm bài không sai....không ai dám nói vét cạn sai vì nó luôn đúng. Cái điểm yếu duy nhất của vét cạn là nó quá lâu.
Còn lâu bao lâu huh ? Để mình nói cho bạn biết: bạn cài dởm nhât thì n^n, tốt hơn thì n! và tốt nhất là 2^n
Giả sử bạn code cứng chút thì T = n!, 32! = 2.6313083693369353016721801216e+35, với 1 máy vi tính hiện đại cho rằng xử lý được 1 tỷ phép tính trên giây (thật ra mình chạy vòng for (i = 0 to 1 tỷ) ko bao giờ kịp trong 1s cả. thì bạn sẽ tốn 263130836933693530167218012.16s tương đương 8343824103681301692.26 năm.
Nếu bạn code vét tốt nhất trên lý thuyết là là T = n * 2^n (vét không đệ quy) thì 2^32 * 32 = 128 tỷ, nếu trên máy mình giả sử thì chạy trong 42s, nhưng thực tế thì phải mất hơn 2', bài này mình đã gặp đề cho n = 40, 40*2^40 = 4398046511104, tức là khoảng nửa ngày bạn mới chạy xong 1 test.

Cho các bạn khác: cách làm như sau:
bài này không tránh khỏi việc vét, nhưng mình vét khôn ngoan hơn tí: chia ra 2 tập (bất kỳ) gọi là a và b
vét cả 2 set và lưu tất cả các tổng vào trong 2 mảng set1 và set2. Thời gian vét chỉ tốn O((n/2) * 2^(n/2))
sort lại set2 tốn O(2^(n/2) log (2^(n/2)) = O((n/2) * 2^(n/2))
với mỗi phần tử ở set1, tìm phần tử ở set2 sao cho : tổng của chúng chênh lệch ít nhất có thể , vì set2 đã được sort nên mình chọn tìm kiếm nhị phân. Đô phức tạp: O(2^(n/2) * log(2^(n/2))
Với mỗi lần tìm như thế, mình so sánh với min của mình, nếu bằng thì mình tăng số cách lên 1, nếu bé hơn thì mình sẽ cho min = kết quả hiện thời, reset số cách = 1 tốn O(1)
Cuối cùng: độ phức tạp bài này là O(2^(n/2) * (n/2) + 2^(n/2) * (n/2) + (n/2) * 2^(n/2) * O(1)) = O((n /2) * 2^(n/2))
Với n = 32, bài này tốn hơn 16 * 2^16 = 1 048 576 bước tính < 100 000 000 => an toàn để nộp


Mà buồn thiệt....hình như cả UIT có mỗi mình làm thôi, pro thì đi Thái hết rồi, còn lại toàn cầm gạch ném :|....kiểu này K5 K6 cố lên chứ K4 cũng già rồi sắp ra trường hết rồi

Code : http://pastebin.com/PcrVKsfW

#include <iostream>
#include <algorithm>
using namespace std;
long long int set1[70000],set2[70000];
long long int a[40],b[40],n,na,nb,ns1,ns2,mini,nummini,Tsum,nset;
long long int getsum(long long int *a,long long int id)
{
    long long int res = 0,i;
    for (i = 0;id != 0;++i,id >>= 1)
        if (id & 1) res += a[i];
    return res;
}
void solution()
{
    long long int dif,val,finder,i,j,lowb,uppb;
    ns1 = (1 << na);
    for (i = 0;i < ns1;++i) set1[i] = getsum(a,i);
    ns2 = (1 << nb);
    for (i = 0;i < ns2;++i) set2[i] = getsum(b,i);
    sort(set2,set2 + ns2);
    mini = -1;
    for (i = 0;i < ns1;++i)
    {
        if (mini != -1) lowb = (Tsum - mini) / 2 - set1[i]; else lowb = 0;
        uppb = Tsum / 2 + 1 - set1[i];
        lowb = lower_bound(set2, set2 + ns2, lowb) - set2;
        uppb = upper_bound(set2, set2 + ns2, uppb) - set2;
        for (j = max(lowb - 1,0LL);j < uppb;++j)
        {
            val = set1[i] + set2[j];
            dif = abs(Tsum - val - val);
            if ((dif == mini) && (nset == val)) ++nummini;
            else if ((dif < mini) || (mini == -1))
            {
                nset = val;
                mini = dif;
                nummini = 1;
            }
        }
    }
    if (mini == 0) nummini = nummini / 2;
}
int main()
{
    int i;
    cin >> n;
    na = n/2;
    nb = n - na;
    Tsum = 0;
    for (i = 0;i < na;++i) {cin >> a[i];Tsum += a[i];}
    for (i = 0;i < nb;++i) {cin >> b[i];Tsum += b[i];}
    solution();
    cout << mini << ' ' << nummini << endl;
    return 0;
}

@Anonymous1:
5905341 2011-10-26 01:41:53 Annonymous Đạt yêu cầu 2.20 5.6M C++ 4.0.0-8
5908569 2011-10-26 14:05:18 Chau Nguyen Đạt yêu cầu 1.36 3.7M C++ 4.3.2
Ai nhanh hơn, Ai nhanh hơn, Ai thắng cuộc hôm nay ^_^....hơn cả 1 giây đấy bác

Pro đi Thailand dự ACM/ICPC khu vực hết rồi bạn ơi, mình mới gà thôi, bạn thông cảm ^_^ Mà bạn nói mình làm xong rồi nói chuyện, vậy bạn muốn nói cái chi chi ?

@Mr Quốc:Em cũng tu cả tháng rồi kỳ sau tới lượt anh nhé. Giờ em lên núi tu tiếp.

Góc chí phèo:

[Thuật toán] THÁCH THỨC TOÀN THỂ SINH VIÊN UIT

Cả làng UIT đều tự nhủ: chắc nó chừa mình ra =))

Update 100% completed....windows is shutting down
It's now safe to "ném đá" your computer