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

[09520157]

=)) tự nhiên mình thấy mắc cười quá , hình như trường hắn có mình hắn học IT thôi hay sao ấy =))

[09520685]

UIT nhiều nhân tài cũng có nhiều người chém tốt nữa, chủ topic zô nhầm chỗ rồi )

[07520004]

Cái trang vn.spoj.pl/ hết vào được rồi, UIT-er nào là thủ phạm thế =))

[09520019]

Cái trang vn.spoj.pl/ hết vào được rồi, UIT-er nào là thủ phạm thế =))

Em còn vào đc mà ? Đang sub liên tục đây ^_^

China thì có ACRush
VN thì có SubmitRush :P

[07520004]

Em còn vào đc mà ? Đang sub liên tục đây ^_^

China thì có ACRush
VN thì có SubmitRush :P

Ờ, vẫn còn vào được, chắc tại mạng mẽo nó chập chờn

[09520134]

Chậc, mới đầu đọc cái này em cứ nghĩ là gà nhà khích tướng các bạn để phát hiện nhân tài hay khích lệ các bạn học thuật toán thôi, mà xem tình hình tới giờ thì có vẻ không phải vậy. Mà nếu là không phải như em nghĩ thì bạn kia sử dụng tiếng Việt hơi tệ ^^

[09520396]

Chỉ 1 chữ thôi "Sồn"

[BiThuDoan]

Ờ, vẫn còn vào được, chắc tại mạng mẽo nó chập chờn

Dùng hidemyass thì vào được

[06520166]

Muốn thách thức người khác trước tiên phải tỏ ra tôn trọng đối thủ . Lời lẽ của bạn chủ topic có vẻ không tôn trọng UITers thì không có lý do gì UITers phải đón tiếp nồng hậu. Copy 1 câu hay ho trên mạng "don't feed the troll" )

[11520673]

Bạn đã sử dụng thuật toán tham lam và đệ quy nhưng :
a. Thuật toán tham lam trong trường hợp này là không chính xác.
b. Dùng đệ quy trong bài này sẽ bị quá thời gian cho phép.
Xem ra các bạn vẫn chưa đủ "trình độ" để accept bài này, các bạn code xong thì gửi lên VOJ, nếu accept thì xem như đã làm xong.

Mình vừa vào trường học đc 1 tháng.Cách làm của mình chỉ là dựa vào những kiến thức cơ bản và mò sách... Có lẽ nó chưa đc chuẩn xác nhưng mình nghĩ cũng giải đc đa phần bài toán r.Khóa 6 vừa vào học đã làm đc ( bạn vừa post lên chừng 1 lúc là mình giải xong đó thôi), cần chi các anh chị chuyên ngành phải ra tay :|

[11520124]

nói thiệt cái này em chịu thua, chả làm đc. Nhưng nếu mà bác chủ thớt thật sự làm đc bằng đôi tay của mình thì công nhận bác ấy tài, còn k thì trình độ của bác cũng ngang em mà thôi.

[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

[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à

[anonymous1]

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.

[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