A — Alternating Sum of Numbers
This can be solved in many ways. One of the easiest ways is to use a for-loop and add $$$ a_i $$$ if $$$ i $$$ is odd (1-based indexing) and subtract $$$ a_i $$$ otherwise.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int32_t main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
if(i & 1) ans += x;
else ans -= x;
}
cout << ans << "\n";
}
}
This can be solved using sets and simple conditional statements. There is an interesting solution with $$$ \oplus $$$ (bitwise-xor). Note that $$$ 1 \oplus 2 = 3 $$$. Similarly, $$$ 2 \oplus 3 = 1$$$. Hence, the result is just $$$ a \oplus b $$$.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int32_t main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int a, b;
cin >> a >> b;
cout << (a ^ b) << "\n";
}
C1 and C2 — Message Transmission Error(Hard Version)
Think of how can we verify if some prefix $$$ i $$$ of string $$$ t $$$ is a valid message or not.
If we're at index $$$ i $$$ in string $$$t$$$, then let $$$ x $$$ be the length of current message. It is nothing but $$$ i + 1 $$$ (0-based indexing). Then we just have to check if prefix of length $$$ x $$$ is equal to suffix of length $$$ x $$$. This can be checked in $$$ O(1) $$$ using String Hashing.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int getRandomNumber(int l, int r) {
std::random_device rd; // Seed generator
std::mt19937 gen(rd()); // Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> dis(l, r); // Distribution in range [l, r]
return dis(gen);
}
struct Hash{
int h1 = 0, h2 = 0;
int m1 = 1e9+7, m2 = 1e9+9;
int p;
vector<int> pref1, pref2, power1, power2;
Hash(int base): p(base) {}
void build(string& a){
power1.push_back(1);
while(power1.size() < a.size()){
power1.push_back((power1.back() * p) % m1);
}
power2.push_back(1);
while(power2.size() < a.size()){
power2.push_back((power2.back() * p) % m2);
}
pref1.resize(a.size() + 1, 0ll); pref2.resize(a.size() + 1, 0ll);
int j = 0;
for(int i = 0; i < a.size(); i++){
h1 = (h1 * p % m1 + (a[i] - 'a' + 1)) % m1;
pref1[i + 1] = h1;
h2 = (h2 * p % m2 + (a[i] - 'a' + 1)) % m2;
pref2[i + 1] = h2;
j++;
}
}
pair<int, int> getHash(int i, int j){
int raw1 = pref1[j + 1] - ((pref1[i] * power1[j - i + 1]) % m1);
int raw2 = pref2[j + 1] - ((pref2[i] * power2[j - i + 1]) % m2);
return {(raw1 + m1) % m1, (raw2 + m2) % m2};
}
};
int32_t main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
string s;
cin >> s;
int n = s.size();
int base = getRandomNumber(55, 1e8);
Hash hash(base);
hash.build(s);
int ans = -1;
for(int i = 0; i + 1 < n; i++){
int len = max(n - i - 1, i + 1);
if(len == i + 1) continue;
pair<int, int> pref = hash.getHash(0, len - 1);
pair<int, int> suff = hash.getHash(n - len, n - 1);
if(pref.first == suff.first && pref.second == suff.second){
ans = len - 1;
break;
}
}
if(ans == -1) cout << "NO" << "\n";
else{
cout << "YES" << "\n";
for(int i = 0; i <= ans; i++) cout << s[i];
}
}
Also if someone has solved C1 and C2 with KMP, please explain your solution.
Awesome
I actually used Z-Algorithm for C1+C2. The core concept of Z made it pretty intuitive: "check if prefix of length $$$x$$$ is equal to suffix of length $$$x$$$" can be rewritten as "check if $$$z_{n-x} = x$$$" in Z.
Also for B, I hope I was not the only one being absurdly lazy and typed $$$6 - a - b$$$ as answers.
Actually in Unix you can control file access permissions with same idea:
1 + 2 + 4 = 7
So it's not lazy it is common practice.
For the kmp solution in C
the prefix function returns an array $$$pi$$$, where $$$pi_i$$$ is the maximum length of a prefix which equals the suffix of the same length in the prefix of size $$$i$$$.
so for a prefix of size $$$n$$$ (the entire string) if $$$pi_n$$$ is less than or equal $$$n / 2$$$ even if the part that will be merged is of minimal length, we still can't use this string to form the given string. However if it's greater than $$$n / 2$$$ then after merging we always get the given string.
My Implementation of the same: 278562557