# Shopee 2022
###### tags: `Shopee code league`
## Q1

## Q2
https://www.geeksforgeeks.org/find-maximum-subset-sum-formed-by-partitioning-any-subset-of-array-into-2-partitions-with-equal-sum/

// CPP implementation for the above mentioned
// Dynamic Programming approach

#include <bits/stdc++.h>

using namespace std;

// Function to find the maximum subset sum
int maxSum(int a[], int n)
{
	// sum of all elements
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += a[i];

	int limit = 2 * sum + 1;

	// bottom up lookup table;
	int dp[n + 1][limit];

	// initialising dp table with INT_MIN
	// where, INT_MIN means no solution
	for (int i = 0; i < n + 1; i++) {
		for (int j = 0; j < limit; j++)
			dp[i][j] = INT_MIN;
	}

	// Case when diff is 0
	dp[0][sum] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < limit; j++) {

			// Putting ith element in g0
			if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN)

				dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i - 1]]
											+ a[i - 1]);

			// Putting ith element in g1
			if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN)

				dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i - 1]]);

			// Ignoring ith element
			if (dp[i - 1][j] != INT_MIN)

				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	}

	return dp[n][sum];
}

// Driver code

int main()
{
	// int n = 4;
	// int a[n] = { 1, 2, 3, 6 };
	// cout << maxSum(a, n);
	// return 0;
    int n;
    cin >> n;
    int *a = (int *) malloc(n * sizeof(int));
    for(int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        a[i] = tmp;
    }
    int ans = maxSum(a, n);
    cout << ans <<endl;
}

### Reference:
https://www.geeksforgeeks.org/find-maximum-subset-sum-formed-by-partitioning-any-subset-of-array-into-2-partitions-with-equal-sum/

## Q3

## Q4




#include <stdio.h>
#include <vector>
#include <unordered_map>
#include <set>
#include <iostream>

using namespace std;

bool isVarify(int *a, int n, int start)
{
    set<int> set;
    for (int i = 0; i < n * 2; i++)
    {
        int index = (i + start) % n;
        if (set.count(a[index]))
        {
            set.erase(a[index]);
        }
        else
        {
            set.insert(a[index]);
        }
        if (set.size() > 2)
            return false;
    }
    return true;
}

int main()
{
    int test_case;
    cin >> test_case;
    for(int i = 0; i < test_case; i++) {
        int size;
        cin >> size;
        int *a = (int *) malloc(size * 2 * sizeof(int));
        for(int j = 0; j < size * 2; j++) {
            int num;
            cin >> num;
            a[j] = num;
        }
        bool ans1 = isVarify(a, size, 0);
        int first_num = a[0];
        int start = 1;
        while(first_num != a[start]) start++;
        bool ans2 = isVarify(a, size, start);
        if(ans1 || ans2)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
        free(a);
    }
}

#include <stdio.h>
#include <vector>
#include <unordered_map>
#include <set>
#include <iostream>
#include <stack>

using namespace std;

int findIndex(vector<int> vec, int num)
{
    for (int i = 0; i < vec.size(); i++)
    {
        if (vec[i] == num)
            return i;
    }
    return -1;
}

bool isVarify(int *a, int n, int start)
{
    int deep = 0;
    vector<int> vec;
    n *= 2;
    for (int i = 0; i < n; i++)
    {
        int index = (i + start) % n;
        int position = findIndex(vec, a[index]);
        if (position != -1)
        {
            if (position == vec.size() - 1)
            {
                deep--;
                vec.pop_back();
            }
            else
            {
                vec.erase(vec.begin() + position);
            }
        }
        else
        {
            deep++;
            vec.push_back(a[index]);
        }
    }
    if (deep > 2)
        return false;
    else
        return true;
}

int main()
{
    int a[] = {1, 2, 1, 3, 4, 2, 5, 3, 4, 5}; // wrong
    int size = sizeof(a) / (sizeof(int) * 2);
    bool ans1 = isVarify(a, size, 0);
    int first_num = a[0];
    int start = 1;
    while (first_num != a[start])
        start++;
    bool ans2 = isVarify(a, size, start);
    if (ans1 || ans2)
        cout << "yes" << endl;
    else
        cout << "no" << endl;
}

## Q5

Rough idea

class bankUser()
{
    def __init__(self, name, b):
        self.name = name
        self.balance = b
    def transaction(self, dealer, x):
        if self.balance > x:
            self.balance - x
            dealer.balance + x 
}

main():
## t = number of user
## n = number of transaction
t = input()
n = input()
for _ in range(t):
    name, b = input()             
    bankUser(name, b)
             
for _ in range(n):
     name, dealer, x = input()
     name.transaction(dealer, x)
for _ in range(t):
    print(name.balance)

## Code