# Cheat Code
## Lecture 08: Midterm
### 1. Palindromic Series

#include <bits/stdc++.h>

using namespace std;

int t;

bool isPalindromic(string check)
{
    for (int i = 0; i < check.length() / 2; i++)
        if (check[i] != check[check.length() - i - 1])
            return false;
    return true;
}

int main()
{
    cin >> t;
    while (t--)
    {
        string n;
        int sum = 0;
        cin >> n;
        for (int i = 0; i < n.length(); i++)
            sum += (n[i] - '0');

        string palin = "";
        for (int i = 0; i < sum / n.length(); i++)
            palin += n;
        for (int i = 0; i < sum % n.length(); i++)
            palin += n[i];
        if (isPalindromic(palin))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

### 2. The Sultan's Successors

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define SIZE 8
using namespace std;

bool check(int queens[SIZE], int row, int col) { 
    for (int i = 0; i < row; i++) { 
        if (queens[i] == col) return false; 
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { 
        if (queens[i] == j) return false; 
    } 
    for (int i = row - 1, j = col + 1; j < SIZE && i >= 0; i--, j++) { 
        if (queens[i] == j) return false; 
    }

    return true; 
} 

void NQueen (int chessboard[SIZE][SIZE], int queens[SIZE], int row, int &ans) {
    if (row == SIZE) {
        int sum = 0;
        for (int i = 0; i < SIZE; ++i) {
            sum += chessboard[i][queens[i]];
        }
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < SIZE; ++i) {
        if (!check(queens, row, i)) continue;
        queens[row] = i;
        NQueen(chessboard, queens, row + 1, ans);
    }
}

int main() {
    int k;
    cin >> k;
    while (k-- > 0) {
        int chessboard[SIZE][SIZE];
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                cin >> chessboard[i][j];
            }
        }
        int ans = 0, queens[SIZE];
        NQueen(chessboard, queens, 0, ans);
        cout << setw(5) << ans << endl;
    }
}

### 3. Oliver and the Game

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(vector<vector<int>> &graph, vector<int> &start_time, vector<int> &finish_time, int &t, int v)
{
    start_time[v] = ++t;
    for (int u : graph[v])
    {
        if (!start_time[u])
        {
            dfs(graph, start_time, finish_time, t, u);
        }
    }
    finish_time[v] = ++t;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int a, b, i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int t = 0;
    vector<int> start_time(n, 0);
    vector<int> finish_time(n, 0);
    dfs(graph, start_time, finish_time, t, 0);
    cin >> q;
    for (int s, a, b, i = 0; i < q; ++i)
    {
        cin >> s >> a >> b;
        --a;
        --b;
        if (s == 1)
            swap(a, b);
        if (start_time[a] <= start_time[b] && finish_time[a] >= start_time[b])
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
}

### 4. Polo the Penguin and the XOR

#include <bits/stdc++.h>

using namespace std;

void AddOneBits(vector<int>& q, int x) {
    int j = 0;
    while (x > 0) {
        q[j] += (x & 1);
        x >>= 1;
        ++j;
    }
}

int64_t XorSum(vector<int>& q, int y, int r) {
    int64_t res = 0;

    for (int j = 0; j < 32; j++) {
        if ((y & 1) == 0) {
            res += (1LL << j) * q[j];
        }
        else {
            res += (1LL << j) * (r - q[j]);
        }
        y >>= 1;
    }
    return res;
}

void Solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> p(n + 1);
    p[0] = 0;

    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] ^ a[i];
    }

    int64_t ans = 0;

    vector<int> q(32, 0);

    for (int r = 1; r <= n; r++) {
        AddOneBits(q, p[r - 1]);
        ans += XorSum(q, p[r], r);
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    for (int i = 0; i < t; i++) Solve();

    return 0;
}

### 5. Examination Papers

#include <cstdio>
const int MOD = 1e9 + 7;
long long power(int n) {
    if (n == 0) {
        return 1;
    }

    long long temp = power(n / 2);

    if (n % 2 == 0) {
        return (temp * temp) % MOD;
    }
    else {
        return (temp * temp * 2) % MOD;
    }
}

int main() {
    int test_case;
    scanf("%d", &test_case);
    while (test_case--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", power(n) - 1);
    }
    return 0;
}

## Lecture 09: Hash Table
### 1. The Monk and Prateek

#include <bits/stdc++.h>
using namespace std;

#define fastIO cin.tie(0);ios_base::sync_with_stdio(0)
map<int,int> mp; // store <hash_value,number_of_frequency>

int SumOfDigit(int n){
    int res = 0;
    while(n > 0){
        res += n%10;
        n = n/10;
    }
    return res;
}

int HashFunc(int n){
    return n^SumOfDigit(n);
}

int main(){
    fastIO;
    int n, num;
    int nCollision = 0;
    int MaxHashValue = -1;
    int MinHashValueCollision = 1e9;
    int MaxFrequency = -1;
  
    cin >> n;
    for(int i = 0 ; i < n;i++){
        cin >> num;
        int hash_value = HashFunc(num);
        MaxHashValue = max(MaxHashValue,hash_value);
        mp[hash_value]++;
 
    }
  
    map<int,int>::iterator it;
  
    for(it=mp.begin(); it!=mp.end(); it++){
        nCollision += it->second - 1;
        MaxFrequency = max(MaxFrequency, it->second);
    }
  
    if(mp.size() == n){
        cout << MaxHashValue <<" "; 
    } else{
        for(it=mp.begin(); it!=mp.end(); it++){
            if(it->second == MaxFrequency ){
                MinHashValueCollision = min(it->first,MinHashValueCollision);
            }
        }
        cout << MinHashValueCollision <<" ";
    }
  
    cout << nCollision;
  
    return 0;
}

### 2. Suffix Equal Prefix

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const long long MOD = 1e9 + 7;
const int MAXN = 1e6 + 1;
unsigned long long f[MAXN];
unsigned long long mul[MAXN];

void polyHash(string keys) {
    unsigned long long hashValue = 0;
    int n = keys.size();
    for (int i = 0; i < n; i++) {
        hashValue = (keys[i] - 'a' + (26 * hashValue) % MOD) % MOD;
        f[i + 1] = hashValue;
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int test;
    string s;
    mul[0] = 1;
    for (int i = 1; i < MAXN; i++)
        mul[i] = (mul[i - 1] * 26) % MOD;
    cin >> test;
    for (int t = 1; t <= test; t++) {
        cin >> s;
        f[0] = 0;
        int n = s.size();
        polyHash(s);
        int res = 0, len = 1;
        while (len < n) {
            if (f[len] == ((f[n] - (f[n - len] * mul[len]) % MOD) + MOD) % MOD)
                res++;
            len++;
        }
        cout << "Case " << t << ": " << res << "\n";
    }
    return 0;
}

### 3. Good Substrings

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    string s, b;
    int k;
    cin >> s >> b >> k;

    const int BASE = 29;

    unordered_set<uint64_t> good_strings;
    for (int i = 0; i < s.length(); ++i) {
        uint64_t hash = 0;
        for (int j = i, bad = 0; j >= 0; --j) {
            hash = hash * BASE + s[j] - 'a' + 1;
            bad += (b[s[j] - 'a'] == '0');
            if (bad <= k) {
                good_strings.insert(hash);
            }
            else {
                break;
            }
        }
    }

    cout << good_strings.size();
}

### 4. Cipher

#include <bits/stdc++.h> 

using namespace std; 

string s; 
int n, k; 
vector <int> ans; 

int main () {
	//freopen("input.txt", "r", stdin); 
	//freopen("output.txt", "w", stdout);

	cin >> n >> k; 
  cin >> s; 
	
	
	int c = 0; 

	for (int i = 0; i < n; i++) {
		if (i >= k) {
			c ^= ans[i - k];	
		}

		int x = s[i] - '0'; 
		ans.push_back(c ^ x); 
		c ^= ans.back(); 
	}

	for (int i = 0; i < n; i++) {
		cout << ans[i]; 
	}

	return 0; 
}

### 5. Camp schedule

#include <bits/stdc++.h>

using namespace std;

#define hash fwpqenofqwoipngq

const int BASE = 29;
const int MOD = 1e9 + 7;
const int maxn = 5e5 + 100;
string s, t, sb, st;
int n, m;
int cnt[2], cntNeed[2];
long long power[maxn], hash[maxn];

void CreateHash(string s){
    power[0] = 1;
    for (int i = 0; i < s.size(); i++){
        hash[i + 1] = (hash[i] * BASE + s[i]) % MOD;
        power[i + 1] = (power[i] * BASE) % MOD;
    }
}

long long GetHash(int l, int r){
    return ((hash[r] - (hash[l - 1] * power[r - l + 1]) % MOD + MOD) % MOD);
}

int main(){
    getline(cin,s);
    getline(cin,t);
    n = s.size();
    m = t.size();
    for (int i = 0; i < n; i++){
        cnt[s[i] - '0']++;
    }
    for (int i = 0; i < m; i++){
        cnt[t[i] - '0']--;
    }
    if (cnt[0] < 0 || cnt[1] < 0){
        cout << s;
        return 0;
    }
    CreateHash(t);
    int MaxPrefixDuplicate = 0;
    for (int len = m - 1; len >= 0; len--){
        if (GetHash(1, len) == GetHash(m - len + 1, m)) {
            MaxPrefixDuplicate = len;
            break;
        }
    }

    for (int i = MaxPrefixDuplicate; i < m; i++){
        cntNeed[t[i] - '0']++;
        st.push_back(t[i]);
    }

    int mNeed = m - MaxPrefixDuplicate;
    sb = t;
    while (cnt[0] >= cntNeed[0] && cnt[1] >= cntNeed[1]){
        cnt[0] -= cntNeed[0];
        cnt[1] -= cntNeed[1];
        for (int i = 0; i < mNeed; i++){
            sb.push_back(st[i]);
        }
    }

    for (int i = 0; i < cnt[0]; i++){
        sb.push_back('0');
    }

    for (int i = 0; i < cnt[1]; i++){
        sb.push_back('1');
    }

    cout << sb;
}

### 6. Watto and Mechanism

#include <iostream>
#include <string>
#include <vector>
#include <set>

/******* HASHING VARS ********/
const int A = 3;
const int MAX_POWER_OF_A = (int)(6e5); // max of 6e5 chars in whole input(input string & queries)
std::vector<long long> powers_of_A1(MAX_POWER_OF_A, 1);
std::vector<long long> powers_of_A2(MAX_POWER_OF_A, 1);
const long long MOD1 = (long long)(1e18 + 7);
const long long MOD2 = (long long)(1e18 + 9);

/******* PROBLEM VARS ********/
int num_init_strings, num_queries;
std::vector<std::pair<std::pair<long long, long long>, std::string>> queries;
std::set<std::pair<long long, long long>> init_strings_hashes;

/******* HASHING INITIALIZATION FUNCTIONS ********/
void populate_powers_of_A()
{
    for (int i = 1; i < MAX_POWER_OF_A; i++)
    {
        powers_of_A1[i] = (powers_of_A1[i - 1] * A) % MOD1;
        powers_of_A2[i] = (powers_of_A2[i - 1] * A) % MOD2;
    }
}

/******* INITIALIZATION FUNCTIONS ********/
void clear_init_strings_hash()
{
    init_strings_hashes.clear();
}

void clear_queries()
{
    queries.clear();
}

std::pair<long long, long long> polynomial_hash_string(std::string &s)
{
    long long hash1 = 0;
    long long hash2 = 0;
    for (char c : s)
    {
        hash1 = ((long long)(c) + ((1LL * A * hash1) % MOD1)) % MOD1;
        hash2 = ((long long)(c) + ((1LL * A * hash2) % MOD1)) % MOD2;
    }
    return {hash1, hash2};
}

void get_clean_init_strings_hashes()
{
    clear_init_strings_hash();
    for (int i = 0; i < num_init_strings; i++)
    {
        std::string init_string;
        std::cin >> init_string;
        std::pair<long long, long long> hash_of_init_string = polynomial_hash_string(init_string);
        init_strings_hashes.insert(hash_of_init_string);
    }
}

void get_clean_queries()
{
    clear_queries();
    for (int i = 0; i < num_queries; i++)
    {
        std::string query;
        std::cin >> query;
        std::pair<long long, long long> hash_of_query = polynomial_hash_string(query);
        queries.push_back({hash_of_query, query});
    }
}

void get_clean_inputs()
{
    get_clean_init_strings_hashes();
    get_clean_queries();
}

/******* QUERY PARSING FUNCTIONS ********/
bool match_init_string(std::pair<long long, long long> &hash, std::string &query)
{
    return (init_strings_hashes.find(hash) != init_strings_hashes.end());
}

long long recalculate_hash(long long old_hash, int position_power, char old_char, char new_char)
{
    long long adjustment_in_hash = (((long long)(new_char - old_char) * powers_of_A1[position_power]) % MOD1) + MOD1;
    long long new_hash = (old_hash + adjustment_in_hash) % MOD1;

    return new_hash;
}

bool parse_query(std::pair<long long, long long> &string_hash, std::string &str)
{
    for (int i = 0; i < str.size(); i++)
    {
        for (char c = 'a'; c <= 'c'; c++)
        {
            if (c != str[i])
            {
                long long alt_str_hash1 = recalculate_hash(string_hash.first, str.size() - 1 - i, str[i], c);
                long long alt_str_hash2 = recalculate_hash(string_hash.second, str.size() - 1 - i, str[i], c);

                std::pair<long long, long long> alt_str_hash = {alt_str_hash1, alt_str_hash2};
                if (match_init_string(alt_str_hash, str))
                {
                    return true;
                }
            }
        }
    }
    return false;
}

void parse_queries()
{
    for (std::pair<std::pair<long long, long long>, std::string> hash_query : queries)
    {
        std::string res = (parse_query(hash_query.first, hash_query.second)) ? "YES" : "NO";
        std::cout << res << std::endl;
    }
}

int main()
{
    populate_powers_of_A();

    std::cin >> num_init_strings >> num_queries;
    get_clean_inputs();

    parse_queries();

    return 0;
}

### 7. N meetings in one room

#include <bits/stdc++.h>
#define  io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define ALL(a) a.begin(),a.end()

typedef long long ll;
const double PI = acos(-1.0);
const int N = 333333;
const int oo = 1e9;

using namespace std;
struct ii{
    int index, startT, finishT;
};

bool cmp(ii a, ii b){
    return (a.finishT < b.finishT);
}

//Khai bao

void read(){
    freopen("inp.inp", "r",stdin);
    freopen("out.out", "w", stdout);
}
vector<ii> meetings;
vector<bool>Chosen;
int main(){
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        meetings.assign(n + 1, ii{0, 0, 0});
        Chosen.assign(n + 1, false);
        for (int i = 1; i <= n; i++){
            cin >> meetings[i].startT;
            meetings[i].index = i;
        }
        for (int i = 1; i <= n; i++){
            cin >> meetings[i].finishT;
        }
        sort(meetings.begin() + 1, meetings.begin() + 1 + n, cmp);
        int curTime = meetings[1].finishT;
        Chosen[1] = true;
        for (int i = 2; i <= n; i++){
            if (meetings[i].startT > curTime){
                curTime = meetings[i].finishT;
                Chosen[i] = true;
            }
        }
        for (int i = 1; i <= n; i++){
            if (Chosen[i]){
                cout << meetings[i].index << " ";
            }
        }
        cout << "\n";
    }
}