Ryan's blog
0%

2022/12/13 CPE

Posted on Edited on In , Views:

UVA-10931 Parity

A simply bit-wise operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    ll x;
    while (cin >> x && x)
    {
        ll res = 0;
        cout << "The parity of ";
        bool y = false;
        for (int i = 32; i >= 0; i--)
            if ((x >> i) & 1)
            {
                res++;
                cout << 1;
                y = true;
            }
            else if (y)
                cout << 0;
        cout << " is " << res << " (mod 2).\n";
    }
}

UVA-10789 Prime Frequency

Since every case can only put 2001 size of string, I just pre-calculate every case.(from exist 1 ~ 2001 times).
Then, use map to calculate individual alphabat exist n times, and it will auto sort too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main()
{
    bool nums[2002];
    nums[0] = nums[1] = false;
    for (int i = 2; i < 2002; i++)
    {
        nums[i] = true;
        for (int j = sqrt(i); j > 1; j--)
            if (i % j == 0)
                nums[i] = false;
    }
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cout << "Case " << i + 1 << ": ";
        string s;
        cin >> s;
        map<char, int> mp;
        for (char c : s)
            mp[c]++;
        bool isEmpty = true;
        for (auto it : mp)
            if (nums[it.second])
            {
                isEmpty = false;
                if (it.first < 10)
                    cout << int(it.first);
                else
                    cout << it.first;
            }
        if (isEmpty)
            cout << "empty";
        cout << "\n";
    }
}

UVA-10903 Rock-Paper-Scissors Tournament

Firstly, I define rock paper scissors to 0,1,2, respectfully. (call it t1, t2, for person 1, 2, respectfully.)
We observed that this game has 3^2 = 9 ways to perform, to get result.
To get result, I use a 3*3 matrix to store result, 1 for win, -1 for loss, 0 for even.
result = pos[t1][t2], so to speak.
Then, I put result into arrays ,and therefore get answers we wanted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main()
{ // rock scissors paper
    map<string, int> mp;
    mp["rock"] = 0;
    mp["scissors"] = 1;
    mp["paper"] = 2;
    int pos[3][3] = {{0, 1, -1}, {-1, 0, 1}, {1, -1, 0}};
    int n, k;
    bool start = true;
    while (cin >> n && n)
    {
        if (start)
            start = false;
        else
            cout << endl;
        cin >> k;
        int games = k * (n * (n - 1)) / 2;
        vector<int> pw(n + 1, 0); // players win times
        vector<int> pl(n + 1, 0); // loses
        for (int i = 0; i < games; i++)
        {
            int p1, p2, t1, t2;
            string s1, s2;
            cin >> p1 >> s1 >> p2 >> s2;
            t1 = mp[s1];
            t2 = mp[s2];
            if (pos[t1][t2] == 0)
                continue;
            else if (pos[t1][t2] == 1)
                pw[p1]++, pl[p2]++;
            else if (pos[t1][t2] == -1)
                pw[p2]++, pl[p1]++;
        }
        for (int i = 1; i <= n; i++)
        {
            if (pw[i] + pl[i] == 0)
                cout << "-\n";
            else
                cout << fixed << setprecision(3) << ((double)pw[i] / (double)(pw[i] + pl[i])) << endl;
        }
    }
}

UVA-10336 Rank the Languages

This is trying to find numbers of component in a map.
So we apply simply dfs on it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int dir[5] = {0, -1, 0, 1, 0};
int m, n;
vector<vector<char>> v;

void dfs(int x, int y)
{
    if (v[x][y] == 0)
        return;
    char val = v[x][y];
    v[x][y] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i];
        int ny = y + dir[i + 1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && v[nx][ny] == val)
            dfs(nx, ny);
    }
}

int main()
{
    int t;
    cin >> t;
    for (int cnt = 1; cnt <= t; cnt++)
    {
        cin >> m >> n;
        v.resize(m, vector<char>(n));
        map<char, int> mp;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                cin >> v[i][j];
        int res = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (v[i][j] != 0)
                    mp[v[i][j]]++, dfs(i, j);
        cout << "World #" << cnt << "\n";
        vector<pair<int, char>> ans;
        for (auto &it : mp)
            ans.push_back(make_pair(it.second, it.first));
        sort(
            ans.begin(), ans.end(), [](const pair<int, char> &it1, const pair<int, char> &it2) -> bool
            {
            if(it1.first != it2.first)
                return it1.first > it2.first;
            return it1.second < it2.second; });
        for (auto &it : ans)
            cout << it.second << ": " << it.first << "\n";
    }
}

UVA-11584 Partitioning by Palindrome

same leetcode question: 132. Palindrome Partitioning II

We use Dynamic Programming to address this problem.
That is, dp[i] means from s[0] to s[i-1], the minimum partition.
Therefore, dp[s.size()] or dp.back() is the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 999999

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        vector<int> dp(s.size() + 1);
        for (int i = 0; i <= s.size(); i++)
            dp[i] = i; // that is, dp 1 ~ s.size() is s: 0 ~ s.size()-1
        for (int i = 1; i < s.size(); i++)
        {
            // even numbers of characters kind of palindrome
            int x = i - 1, y = i;
            while (x >= 0 && y < s.size() && s[x] == s[y])
            {
                dp[y + 1] = min(dp[y + 1], dp[x] + 1);
                x--, y++;
            }
            // odd
            x = y = i;
            while (x >= 0 && y < s.size() && s[x] == s[y])
            {
                dp[y + 1] = min(dp[y + 1], dp[x] + 1);
                x--, y++;
            }
        }
        cout << dp.back() << endl;
    }
}

UVA-10635 Prince and Princess

A Longest Common Subsequence (LCS) Problem.

Fairly hard problem tho, mainly because it will TLE on the 2d DP solution.

Also, there’s a same problem on leetcode, up and running for those leetcode grinder. By the way, the 2d DP approach will pass on leetcode, and it’s fairly fast on those test case. No wonder it’s mark medium on leetcode. haha.

link: 1143. Longest Common Subsequence

2D DP or DFS + memorization (TLE)

Provide both 2-d Dynamic Programming and dfs solution at lcs().
But It will TLE in the judge, so I will not talk too much in this slope.

Time Complexity : O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 999999

vector<vector<int>> dp;

int dfs(vector<int> &t1, vector<int> &t2, int x, int y)
{
    if (dp[x][y] != -1)
        return dp[x][y];
    if (x >= t1.size() || y >= t2.size())
        return 0;
    int y1 = y, x1 = x;
    for (; y < t2.size(); y++)
        if (t1[x] == t2[y])
            break;
    if (y >= t2.size())
        return 0;
    int res = 0;
    for (int i = x + 1; i < t1.size(); i++)
        res = max(res, dfs(t1, t2, i, y + 1) + 1);
    return dp[x1][y1] = res;
}

int lcs(vector<int> &t1, vector<int> &t2)
{
    // dfs memoization method
    // return dfs(t1, t2, 0, 0) + 1;

    // top down dp method
    // where dp[x][y] means
    for (int x = 0; x < t1.size(); x++)
    {
        for (int y = 0; y < t2.size(); y++)
        {
            dp[x][y] = 0;
            if (y - 1 >= 0 && x - 1 >= 0)
                dp[x][y] = dp[x - 1][y - 1];
            if (t1[x] == t2[y])
                dp[x][y]++;
            else
                dp[x][y] = max(x - 1 >= 0 ? dp[x - 1][y] : 0, y - 1 >= 0 ? dp[x][y - 1] : 0);
        }
    }
    return dp[t1.size() - 1][t2.size() - 1];
}

int main()
{
    int t;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        int n, p, q, temp;
        cin >> n >> p >> q;
        vector<int> t1, t2;
        for (int i = 0; i <= p; i++)
        {
            cin >> temp;
            t1.push_back(temp);
        }
        for (int i = 0; i <= q; i++)
        {
            cin >> temp;
            t2.push_back(temp);
        }
        dp.assign(t1.size(), vector<int>(t2.size(), -1));
        cout << "Case " << tt << ": " << lcs(t1, t2) << endl;
    }
}

Method 2 : LCS to LIS

Actually, if you really look into LCS, it can be devide into a LIS, which has a best practice of complexity O(nlgn).

Just like this, where * and x means t1[i] == t2[j].

ref: ntnu algo

But, it just not this case, right?
Since elements in our list is unique, so our thing will not alike some normal LCS graph. Rather, it’s more easy.

According to this rule, we can confidently say that same row or column will have no more than 1 value. Therefore, it reduce the complexity that we don’t have to use pairs… sorting … stuff. All we have to do is:

  1. map t1 value to t1 index.
  2. through t2 iteration, add (if t1 get the same value) it’s t1 index to a vector.
  3. Since vector is already in t2’s iteration, do LIS on vector’s value.

same as the code below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 999999

// map t1 sequential index into 1 ~ 62501 (number)
int board[62501];

int lcs(vector<int> &t1, vector<int> &t2)
{
    fill(board, board + 62501, -1);
    for (int i = 0; i < t1.size(); i++)
        board[t1[i]] = i;
    vector<int> v;
    for (int i = 0; i < t2.size(); i++)
        if (board[t2[i]] != -1)
            v.emplace_back(board[t2[i]]);
    // Then apply LIS on v
    vector<int> dp(v.size() + 1, 100000);
    for (int i = 0; i < v.size(); i++)
        *lower_bound(dp.begin(), dp.end(), v[i]) = v[i];
    return lower_bound(dp.begin(), dp.end(), 99999) - dp.begin();
}

int main()
{
    int t;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        int n, p, q, temp;
        cin >> n >> p >> q;
        vector<int> t1, t2;
        for (int i = 0; i <= p; i++)
        {
            cin >> temp;
            t1.push_back(temp);
        }
        for (int i = 0; i <= q; i++)
        {
            cin >> temp;
            t2.push_back(temp);
        }
        cout << "Case " << tt << ": " << lcs(t1, t2) << endl;
    }
}

Time complexity: O(n*log(n))

Welcome to my other publishing channels