Solution UVA: 10940 - Throwing cards away II

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10940 - Throwing cards away II	Accepted	Python	1.260	0.000	3706	5 mins ago

Suggest:

- After readed problem, We feel problem need find a rule to solve

- How to find a rule in competitive programming ?

- Often we need show many result from min n

Col: A = input, B = output

Rule:

- If input is 2^x, we have output = input

- Else output is y_current = y_previous + 2  

Code Python:

b = 0

a = 2

d = {}

while True:

    e = a**b

    if e > 500000:

        break

   

    d[e] = True

    b += 1

v = 2

r = {}

for i in range(1, 500000):

    if i in d:

        v = 2

        r[i] = i    

    else:

        r[i] = v

        v += 2

while True:

    n = int(input())

    if n == 0:

        break

    print(r[n])

   

   

Deploy django project use nginx on vm azure

Step1: SSH to vm on CLI azure

Step2: Install nginx and config

sudo touch /etc/nginx/sites-available/20.2.90.6.conf

nano  /etc/nginx/sites-available/20.2.90.6.conf

server {

  server_name 20.2.90.6;

    location / {

    proxy_pass http://localhost:8000;

    proxy_http_version 1.1;

    proxy_set_header Upgrade $http_upgrade;

    proxy_set_header Connection 'upgrade';

    proxy_set_header Host $host;

    proxy_cache_bypass $http_upgrade;

  }

}

sudo ln -s /etc/nginx/sites-available/20.2.90.6.conf /etc/nginx/sites-enabled/20.2.90.6.conf

Step 3: Run django server

python manage.py runserver

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)