Solution UVA: 11428 - Cubes

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11428 - Cubes	Accepted	Python	0.020	0.000	2929	1 mins ago

Suggest:

61^3 - 60^3 > 10000 so x_max <= 60

r = {}

for x in range(1, 61):

    for y in range(1, x):

        if x**3-y**3 in r:

       

            u, v = r[x**3-y**3]

            if (v > y):

                r[x**3-y**3] = (x,y)

       

        else:

           

            r[x**3-y**3] = (x,y)

while True:

    n = int(input())

    if n == 0:

        break

    if n not in r:

        print('No solution')

    else:

        x, y = r[n]

        print(f"{x} {y}")

Solution UVA: 10878 - Decode the tape

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10878 - Decode the tape	Accepted	Python	0.180	0.000	5615	1 mins ago

Suggest:

- In the problems decode, i think we should make doing step:

1/ Look overview and get information easy know like

+ input we have 8 char / line -> now we know need use bit

+ number of line = nuimber of char in string -> now we know every line is a present a char of output

2/ Thinking top down problem 

+ A -> 65 -> 01000001 -> |_o___.__o|

_ = input()

while True:

    s = input()

    if s == '___________':

        break

    k = 0

    n = 0

   

    for i in range(len(s)-1, 0, -1):

       

        if s[i] == 'o':

            n += 1 << k

            k += 1

       

        if s[i] == ' ':

            k += 1

           

    print(chr(n), end='')

Solution Uva: 10338 - Mischievous Children

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10338 - Mischievous Children	Accepted	Python	1.020	0.000	4464	5 mins ago

Suggest:

1/ RESULT = ALL CASE  - SAME CASE

2/ ALL CASE  = n! (n is length string)

3/ SAME CASE = a! * b! * ... * c! (with a,b,c is number of same chars ) 

from functools import cache

@cache

def fac(n):

    if n == 1:

        return 1

    return fac(n - 1) * n

n = int(input())

for i in range(1, n+1):

    s = input()

   

    d = {}

    for c in s:

        if c not in d:

            d[c] = 1

        else:

            d[c] += 1

    r = fac(len(s))

    for key in d:

        r //= fac(d[key])

    print(f'Data set {i}: {r}')

Solution UVA: 10268 - 498-bis

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10268 - 498-bis	Accepted	C++11	0.020	0.000	705	1 mins ago

Susgest:

- Use pow default function couldn't AC so we need code Pow binary function  

#include <bits/stdc++.h>

#define int long long

using namespace std;

string line1, line2;

long long Pow(long long a, long long b) {

    if (!b) return 1;

    long long x = Pow(a, b / 2);

    if (b % 2 == 0)

        return x * x;

    else

        return x * x * a;

}

int32_t main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    while(getline(cin, line1)){

        getline(cin, line2);

               

        stringstream l1(line1);

        stringstream l2(line2);

        int x;  l1 >> x;

       

        vector<int> a;

        int v;

        while(l2 >> v) a.push_back(v);  

        reverse(a.begin(), a.end());

        int s = 0;

        for(int i=1; i<a.size(); i++)

            s += a[i]*i*Pow(x, i-1);

        cout<<s<<"\n";

    }

}

 

Solution UVA: 10943 - How do you add?

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10943 - How do you add?	Accepted	Python	0.160	0.000	4199	35 secs ago

Suggest:

- This problem similar with problem 10721 - Bar Codes

We have fomular f(n, k) = f(n-i, k-1) | i = 0 -> n

- Example: 

f(2,2) = f(2,1) + f(1, 1) + f(0, 1) 

f(0, 1) = 0

f(1, 1) = f(1, 0) + f(0, 0) = 0 + 1 = 1

f(2, 1) = f(2, 0) + f(1, 0) + f(0, 0) = 0 + 1 + 1 = 2

=> f(2, 2) = 0 + 1 + 2 = 3 

from functools import cache

@cache

def f(n, k, m):

    if n < 0 or k < 0:

        return 0

    if n == 0 and k == 0:

        return 1

   

    r = 0

    for i in range(0, n+1):

        r = (r + f(n-i, k-1, m) % m) % m

    return r

while True:

    n, k = map(int, input().split())

    if n==0 and k==0:

        break

    print(f(n, k, 1000000))

Solution UVA: 10819 - Trouble of 13-Dots

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10819 - Trouble of 13-Dots	Accepted	C++11	0.040	0.000	415	1 mins ago

Suggest:

- DP knapsack range m+200

- Get result with 3 case:

+ m <= 1800

+ 1801 <= m <= 2000

+ m >= 2001

Code implenment by suggest:

#include<bits/stdc++.h>

using namespace std;

int n, m;

int a[1000111];

int b[1000111];

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    while(cin >> m >> n){

        for(int i=1; i<=n; i++) cin >> a[i] >> b[i];

       

        vector<int> f(m+201, 0);

           

        for(int i=1; i<=n; i++)

            for(int j=m+200; j>=a[i]; j--)

                if (f[j - a[i]] > 0 || j == a[i])

                        f[j] = max(f[j], f[j - a[i]] + b[i]);

       

        int res = 0;

        for(int i=0; i<=m; i++)

            res = max(res, f[i]);

   

        if (1801 <= m <= 2000){

            for(int i=2001; i<=m+200; i++)

                res = max(res, f[i]);

        }

           

        if (m >= 2001){

            for(int i=0; i<=m+200; i++)

                res = max(res, f[i]);

        }

                           

        cout<<res<<"\n";

    }

}

Solution UVA: 11413 - Fill the Containers

 

Last Submissions
Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11413 - Fill the Containers	Accepted	C++11	0.000	0.000	1972	5 mins ago

Suggest:

- Use binary search to determine the capacity (Once the capacity is determined, simulate and calculate the number of containers)

Note: I use a binary search algorithm along with a while + a for.

#include<bits/stdc++.h>

using namespace std;

int n, m;

int a[1000111];

int main(){

    while(cin >> n >> m){

       

        m = min(n, m);

       

        for(int i=1; i<=n; i++)

            cin >> a[i];

       

        int r = 0;

        for(int i=1; i<=n; i++)

            r += a[i];  

       

       

        int l= 1;

       

        while(r-l+1 >= 3){

           

            int mid = (r + l) / 2;

            int s = 0;

            int container= 0;

            bool bl = false;

           

            for(int i=1; i<=n; i++)

            if (a[i] + s <=  mid){

                s += a[i];  

                bl = true;

            }

            else{

                if (not bl) {

                    container = m + 1;

                    break;  

                }

                if (bl) container++;

                bl = false;

                s = 0;

                i--;

            }

           

            if (bl) container++;

           

        //  cout<<"mid container: "<<mid<<" "<<container<<"\n";

           

            if (container > m) l = mid;

            else

                r = mid;

        }

       

        for(int mid=l; mid<=r; mid++){

           

            int s = 0;

            int container= 0;

            bool bl = false;

           

            for(int i=1; i<=n; i++)

            if (a[i] + s <=  mid){

                s += a[i];  

                bl = true;

            }

            else{

                if (not bl) {

                    container = m + 1;

                    break;  

                }

                if (bl) container++;

                bl = false;

                s = 0;

                i--;

            }

           

            if (bl) container++;

           

            if (container <= m){

                cout << mid <<"\n";

                break;

            }          

           

        }

       

       

    }

   

       

}

Solution UVA: 10114 - Loansome Car Buyer

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10114 - Loansome Car Buyer	Accepted	Python	0.020	0.000	5752	1 mins ago

Suggest:

You only need forcus: (for output 1)

Consider the first example below of borrowing $15,000 for 30 months. As the buyer drives off the

lot, he still owes $15,000, but the car has dropped in value by 10% to $13,950. After 4 months, the

buyer has made 4 payments, each of $500, and the car has further depreciated 3% in months 1 and 2

and 0.2% in months 3 and 4. At this time, the car is worth $13,073.10528 and the borrower only owes

$13,000 

AND note

month_pay = loan / months (15000 / 30 = 500) 

I lost many time because think down_payment is month_payment ($500)

while True:

    months, down_pay, loan, n = map(float, input().split())

    months = int(months)

    n = int(n)

    if months < 0:

        break

    depreciations = [-1]*(months+1)  

    for _ in range(n):

        month, depreciation = map(float, input().split())

        month = int(month)

        depreciations[month] = depreciation

   

    car_money = (down_pay + loan)*(1-depreciations[0])

    owe = loan  

    if (owe < car_money):

        print("0 months")

    else:

        month_pay = loan / months

        for i in range(1, months+1):

            if depreciations[i] == -1:

                depreciations[i] = depreciations[i-1]

            owe -= month_pay

            car_money -= car_money * depreciations[i]

           

            if (owe < car_money):

                if (i>1):

                    print(i, 'months')

                else:

                    print(i, 'month')

                break      

   

# 30 500.0 15000.0 3

# 0 .10

# 1 .03

# 3 .002

# 12 500.0 9999.99 2

# 0 .05

# 2 .1

# 60 2400.0 30000.0 3

# 0 .2

# 1 .05

# 12 .025

# -99 0 17000 1

I lost many time because down_payment is month_payment

Trust its is diff

Pram formula RNN, LSTM, BiLSTM, Dense

pram formula 

RNN = in * out + out * out + out 

LSTM = 4 * (in * out + out * out + out) 

biLSTM= 2 * (4 * (in * out + out * out + out)) 

dense = in * out + out

Phân cụm K-Means (học máy không giám sát)

Thuật toán K-means:

<1> Chọn ngẫu nhiên K điểm làm trung tâm của K cụm

<2> Gán các điểm gần với mỗi cụm, nếu không có phép gán nào thì dừng

<3> Tính lại trung tâm của mỗi cụm

<4> Lặp lại bước 2

Khoảng cách euclid: 

A(a1, a2) và B(b1, b2) => AB = sqrt(sqr(a1-b1) + sqr(a2-b2))

Khoảng cách manhattan:

A(a1, a2) và B(b1, b2) => AB = abs(a1-b1) + abs(a2-b2)

Đề bài – Example

Giả sử có 4 sinh viên A, B, C, D. Mỗi sinh viên được biểu diễn bởi hai đặc trưng X, Y.

Sinh viên	Sở thích (X)	Quê quán (Y)
A	1	1
B	2	1
C	4	3
D	5	4

 Mục đích là nhóm các sinh viên đã cho vào 2 nhóm/phòng (K=2) dựa vào các đặc trưng của chúng. 

Giải

Chọn điểm A là tâm của cụm 1, điểm B là tâm của cụm 2. 

Khoảng cách euclid các điểm đến tâm của mỗi cụm:

                A    B    C    D

Cụm 1     0    1    3.6    5

Cụm 2     1    0    2.8    4.2

Gán các điểm cho gần với mỗi cụm:

Cụm 1 (A)

Cụm 2 (B, C, D)

Tính tâm của mỗi cụm:

Cụm 1 tâm (1,1)

Cụm 2 tâm ((2+4+5)/3 , (1+3+4)/3 )  = (3.6 , 2.6)

Khoảng cách euclid các điểm đến tâm của mỗi cụm:

                A    B    C    D

Cụm 1     0    1    3.6    5

Cụm 2     3.05    2.2    0.5    1.9

Gán các điểm cho gần với mỗi cụm:

Cụm 1 (A, B)

Cụm 2 (C, D)

Tính tâm của mỗi cụm:

Cụm 1 tâm (1.5, 1)

Cụm 2 tâm (4.5, 3.5)

Khoảng cách euclid các điểm đến tâm của mỗi cụm:

                A    B    C    D

Cụm 1     0.5    0.5    3.2    4.6

Cụm 2     4.3    3.5    0.7    0.7

Gán các điểm cho gần với mỗi cụm:

Cụm 1 (A, B)

Cụm 2 (C, D)

Vì phép gán lần này giống với lần trước nên thuật toán dừng 

Vậy ta được 2 cụm (A, B) và (C, D)

  

 

 

Thuật toán xây dựng cây quyết định (bằng tập thô)

Ví dụ 1

POSoutlook(PlayTennis) = {D3, D7, D12, D13}

POStemp(PlayTennis) = POShumidity(PlayTennis) = POSwind(PlayTennis) = {null}

=> Chọn thuộc tính chia là Outlook, xây dựng 3 bảng quyết định (root Outlook)

T0 (brand overcast)

U1	Temp	Humidity	Wind	Playtennis
D3	Hot	High	Weak	Yes
D7	Cool	Normal	Strong	Yes
D12	Mild	High	Strong	Yes
D13	Hot	Normal	Weak	Yes

 T1 (brand sunny)

U0	Temp	Humidity	Wind	Playtennis
D1	Hot	High	Weak	No
D2	Hot	High	Strong	No
D8	Mild	High	Weak	No
D9	Cool	Normal	Weak	Yes
D11	Mild	Normal	Strong	Yes

 T2 (brand rain)

U1	Temp	Humidity	Wind	Playtennis
D4	Mild	High	Weak	Yes
D5	Cool	Normal	Weak	Yes
D6	Cool	Normal	Strong	No
D10	Mild	Normal	Weak	Yes
D14	Mild	High	Strong	No

                                  Outlook

           /                          |                            \

overcast                      sunny                        rain

Xét bảng T0: 

Là hệ quyết định thuần khiết vì các đối tượng đều có kết quả là Yes (Brand Overcast have leaf is YES)

overcast                  

       /                             

    YES

Xét bảng T1:

Từ bảng T1 ta có

- POSwind(Playtennis) = {null}

- POStemp(Playtennis) = {D1, D2, D9}

- POShumidity(Playtennis) = {D1, D2, D8, D9, D11}

=> Chọn thuộc tính chia chính là Humidity, chia 2 bảng quyết định T10 và T11 (brand sunny have node Humidity)

Bảng T10:

U1	Temp	Humidity	Wind	Playtennis
D1	Hot	High	Weak	No
D2	Hot	High	Strong	No
D8	Mild	High	Weak	No

Bảng T11:

U1	Temp	Humidity	Wind	Playtennis
D9	Cool	Normal	Weak	Yes
D11	Mild	Normal	Strong	Yes

=> T10 là hệ thuần khiết vì các đối tượng có Humidity = High đều cho kết quả PlayTennis là No (brand High have leaf NO)

=> T11 là hệ thuần khiết vì các đối tượng có Humidity = Normal đều cho kết quả PlayTennis là Yes (brand Normal have leaf YES)

                                       sunny

                                        |                            

                               Humidity                       

                                    /    \                         

                               high    normal          

                                /            \                    

                            NO            YES

Xét bảng T2:

Từ bảng T2 ta có:

POSwind(playtennnis) = {D4, D5, D6, D10, D14}

POStemp(playtennnis) = {null}

POShumidity(playtennnis) = {null}

=> Chọn thuộc tính chia chính là Wind, chia 2 bảng quyết định T20 và T21 (brand rain have node Wind)

Bảng T₂₀:

U1	Temp	Humidity	Wind	Playtennis
D4	Mild	High	Weak	Yes
D5	Cool	Normal	Weak	Yes
D10	Mild	Normal	Weak	Yes

 

Bảng T₂₁:

U1	Temp	Humidity	Wind	Playtennis
D6	Cool	Normal	Strong	No
D14	Mild	High	Strong	No

=> T20 là hệ thuần khiết vì các đối tượng có Wind = Weak đều cho kết quả PlayTennis là Yes (brand weak have leaf YES)

=> T21 là hệ thuần khiết vì các đối tượng có Wind = Strong đều cho kết quả PlayTennis là No (brand strong have leaf  NO)

             rain

                \ 

               wind

              /        \

     weak       strong 

       /                \

YES            NO

Do các hệ quyết định cuối cùng đều là các hệ thuần khiết nên thuật toán xây dựng cây quyết định RDT dừng.

                                  Outlook

           /                          |                            \

overcast                      sunny                        rain

       /                                |                                \ 

    YES                    Humidity                       wind

                                    /    \                            /        \

                               high    normal           weak       strong 

                                /            \                     /                \

                            NO            YES          YES            NO

Ví dụ 2Armatage Shanks

Cho tập dữ liệu huấn luyện như sau :

RID	age	income	student	credit_rating	Class: bugs_computer
1	youth	high	no	fair	no
2	youth	high	no	excellent	no
3	middle_aged	high	no	fair	yes
4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no
7	middle_aged	low	yes	excellent	yes
8	youth	medium	no	fair	no
9	youth	low	yes	fair	yes
10	senior	medium	yes	fair	yes
11	youth	medium	yes	excellent	yes
12	middle_aged	medium	no	excellent	yes
13	middle_aged	high	yes	fair	yes
14	senior	medium	no	excellent	no

Giải

POSage(bugs_computer) = {D3, D7, D12, D13}

POSincome(income) =  POSincome(student) = POS(credit_rating) = {null}

=> Chọn age làm thuộc tính chính và xây dựng các bảng quyết định (chọn age làm root)

T0: (middle_aged)

3

middle_aged

high

no

fair

yes

7

middle_aged

low

yes

excellent

yes

12	middle_aged	medium	no	excellent	yes
13	middle_aged	high	yes	fair	yes

T1: (youth)

1	youth	high	no	fair	no
2	youth	high	no	excellent	no

8	youth	medium	no	fair	no
9	youth	low	yes	fair	yes

11

youth

medium

yes

excellent

yes

T2: (senior)

4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no

10

senior

medium

yes

fair

yes

14

senior

medium

no

excellent

no

Xét T0:

 Toàn bộ đội tượng đều trả về kết quả YES nên đây là hệ thuần khiết (nhánh middle_aged sẽ trả về node lá YES)

Xét T1:

POSincome(bugs_computer) = {D1, D2, D9}

POSstudent(bugs_computer) = {D1, D2, D8, D9, D11}

POScredit_rating(bugs_computer) = {null}

=> Chọn student làm thuộc tính chính, và xây dựng các bản quyết định (node student)

T10: (no)

1	youth	high	no	fair	no
2	youth	high	no	excellent	no

8

youth

medium

no

fair

no

T11: (yes)

    

9

youth

low

yes

fair

yes

11

youth

medium

yes

excellent

yes

Xét T10:    

- Toàn bộ đối tượng đều trả về kết quả no => Đây là hệ thuần khiết (node student có node lá NO)

Xét T11:    

- Toàn bộ đối tượng đều trả về kết quả yes => Đây là hệ thuần khiết (node student có node lá ÝES)

Xét T2: 

POSincome(bug_computer) = {null}

POSstudent(bugs_computer) = {null}

POScredit_rating(bugs_computer) = {D4, D5, D6, D10, D14}

=> Chọn credit_card làm thuộc tính chính, và xây dựng các bản quyết định (node credit_card)

T20:

4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes

10

senior

medium

yes

fair

yes

T21:

6

senior

low

yes

excellent

no

14

senior

medium

no

excellent

no

Xét T20:    

- Toàn bộ đối tượng đều trả về kết quả yes => Đây là hệ thuần khiết (nhánh fair có leaf YES)

Xét T21:    

- Toàn bộ đối tượng đều trả về kết quả no => Đây là hệ thuần khiết (nhánh excellent có leaf  NO)

                                    Age

           /                          |                            \

Middle_aged              youth                    senior

       /                                |                                \ 

    YES                    Student                    credit_card

                                    /    \                            /    \

                               no        yes                fair       excellent 

                                /            \                     /            \

                            NO            YES          YES            NO