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

[09520567]

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ế.
Anonymous

mình thấy bạn đó nói điều trên ko có j sai cả :|

[09520019]

Chiều nay có vài nhóc pm tớ là đã đăng ký thi codeforces tối nay rồi, codeforces vừa chấm bài xong (hic ngồi chờ 40' căng thẳng). Cho link profile xem kết quả đi nào...

[09520434]

Thực tế mà nói thì việc nghĩ ra được thuật giải, và code theo thuật giải là 2 vấn đề hoàn toàn khác nhau.
Có lẽ bạn là 1 coder giỏi, nhưng UIT lại đi sâu vào việc nghĩ ra phương pháp để giải quyết vấn đề.
Mình đoán bạn là sv năm 1 (cùng lắm là năm 2), mới bước lên từ THPT, nên thấy bài toán trên là khá mới mẻ, nên khi giải xong có cảm giác như đang nhìn bầu trời khi ở sâu dưới giếng. =)) [Cái giai đoạn này mình cũng đã từng trải qua]

Mình có tiếp xúc với bài tập lớp CNTT của trường BK, và mình có so sánh với trường mình, mình thấy 2 phương pháp này hoàn toàn khác nhau. (vd như trong môn cấu trúc dữ liệu)
BK : Cố gắng làm cho học sinh làm càng nhiều bài tập càng tốt
UIT : Cố gắng làm cho học sinh hiểu sâu cấu trúc dữ liệu là gì, nó bao gồm những gì, và nó hoạt động như thế nào.
Tất nhiên mỗi phương pháp đều có điểm riêng của nó.
Bởi vậy, mình thừa nhận UIT không nhiều coder giỏi, nhưng mình nghĩ khả năng giải quyết vấn đề của UITer là không tồi.

Thông cảm vì những dòng suy nghĩ của mình khá muộn màng.

[11520145]

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

cho em hỏi chữ O trong O(( là gì vậy

[07520004]

cho em hỏi chữ O trong O(( là gì vậy

Big O notation, em có thể vào wiki để đọc hoặc từ từ chờ học tới.

[09520155]

ai ra mặt đi

[08520059]

cho em hỏi chữ O trong O(( là gì vậy

Đơn giản là độ phức tạp của thuật toán, chi tiết thì từ từ sẽ học, nếu không thì wiki là có ngay.

[10520061]

Chiều nay có vài nhóc pm tớ là đã đăng ký thi codeforces tối nay rồi, codeforces vừa chấm bài xong (hic ngồi chờ 40' căng thẳng). Cho link profile xem kết quả đi nào...

em làm bài 1, xong submit cái báo wrong, loay hoay mãi thì ra sai chữ "yes" với "YES".hjhj

[11520145]

Hỏi về bài toán

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;
}

Anh cho em hỏi muốn sử dụng cái này thì làm sao ạ, copy vô đâu ấy mà. Còn lập trình C em chưa đụng bao giờ nên không biết down sao hết ạ.

[11520145]

Mấy anh chị ơi ! mọi người ơi ! tình hình là em biết cái topic này lâu rùi và tựa đề không ưa nhìn cho lắm - nhưng có ai chỉ em cách test hoặc test dùm em cái program này với. Em quên pascal rùi và cũng không biết sài C nên có đoạn này thui ah. Nếu không thể thì cho em bik nha

local $set2[10]
$set1[1]=1
$set1[2]=2
$set1[3]=3
$set1[4]=4
$set1[5]=5

$set2[2]=1
;--------so luoc----------
$n=5
$dem=0
$s=tong($n)
$sum=floor($s/2)
$b=mod($s,2)
if $b<>0 then
$sum=$sum+1
$d=1
Else
$d=0
EndIf
;-------Tinh d-------------
$decoy=$sum
for $i=$n To 1 Step -1
if $set1[$i]<=$decoy then $decoy=$decoy-$set1[$i]
Next
;-------Xac dinh d ----------
$d=$d+$decoy
;-------Begin---------------
if $set1[$n]=$sum Then
MsgBox(0,"Result",1)
Exit
EndIf
$l=0
for $k=1 to $n
$b=gt($n)/(gt($n-$k)*gt($k))
$l=$l+$b
Next
;------------------------
for $i=3 to $l-1
nhiphan()
;MsgBox(0,$l,$set2[1]&" "&$set2[2]&" "&$set2[3]&" "&$set2[4]&" "&$set2[5])
$s=sum($n)
if $s=$sum then $dem=$dem+1
;MsgBox(0,"Sum",$s)
Next

MsgBox(0,"Result",$dem)
MsgBox(0,$sum,$d)
;---------function----------
func sum($n)
Local $i
$s=0
for $i=1 to $n
if $set2[$i]=1 then
$s=$s+$set1[$i]
EndIf
Next
Return $s
EndFunc
Func nhiphan()
Local $j,$k
for $j=1 to $n
if $set2[$j]=0 Then
$set2[$j]=1
for $k=1 to $j-1
$set2[$k]=0
Next
ExitLoop
EndIf
Next
EndFunc
func gt($n)
if $n=0 then
Return 1
Else
Return $n*gt($n-1)
EndIf
EndFunc

set1 là mảng chứa dãy số cho vào - set2 là mảng dãy số không có cùng số phần tử như mảng 1 và phần tử thứ 2 =1

[11520477]

em ko giỏi thuật toán nhưng mà ném gạch hơi bị chuẩn đấy! chém gió quá! toàn thể UIT