A- The Problems Problem
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 12, M = 300, mod = 1e9 + 7;
ll power(int a, int p) {
if (!p) return 1;
return 1ll * (p & 1 ? a : 1) * power(1ll * a * a % mod, p >> 1) % mod;
}
ll inverse(int a) { return power(a, mod - 2); }
ll dp[N + 1][1 << N][M];
int timeToSolve[N], timeToFail[N];
ll getExpectedScore(int rating, int problemsState, int timeLeft) {
if (problemsState == 0 or timeLeft <= 0)
return 0;
auto &me = dp[rating][problemsState][timeLeft];
if (me != -1)
return me;
int numberOfPaths = 0;
ll sumOfPaths = 0;
for (int i = 0; i < N; ++i) {
if (problemsState & (1 << i)) {
numberOfPaths++;
if (i < rating)
sumOfPaths += (timeLeft >= timeToSolve[i]) + getExpectedScore(rating, problemsState ^ (1 << i), timeLeft - timeToSolve[i]);
else
sumOfPaths += getExpectedScore(rating, problemsState ^ (1 << i), timeLeft - timeToFail[i]);
}
}
return me = sumOfPaths % mod * inverse(numberOfPaths) % mod;
}
void solve() {
memset(dp, -1, sizeof dp);
int n, m, t;
cin >> n >> m >> t;
vector<vector<int>> problemRatings(n, vector<int>(3));
for (int j = 0; j < 3; ++j)
for (int i = 0; i < n; ++i)
cin >> problemRatings[i][j];
sort(problemRatings.begin(), problemRatings.end());
for (int i = 0; i < n; ++i) {
timeToSolve[i] = problemRatings[i][1];
timeToFail[i] = problemRatings[i][2];
}
for (int i = 0; i < m; ++i) {
int rating;
cin >> rating;
rating = lower_bound(problemRatings.begin(), problemRatings.end(), vector<int>({rating + 1})) - problemRatings.begin();
cout << getExpectedScore(rating, (1 << n) - 1, t) << " ";
}
cout << endl;
}
int main(int argc, char *argv[]) {
int t = 1;
// cin >> t;
while (t--)
solve();
}
B- Re-Indexing
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 17, mod = 1e9 + 7;
mt19937 rnd(time(nullptr));
void solve() {
int n, q;
cin >> n >> q;
vector<pair<int, string>> chapters(n+1);
for (int i = 0; i < n; ++i)
cin >> chapters[i].second >> chapters[i].first;
chapters[n] = {2'000'000'000, "No More Chapters"};
sort(chapters.begin(), chapters.end());
map<string, string> nextChapter;
for (int i = 0; i < n; ++i)
nextChapter[chapters[i].second] = chapters[i + 1].second;
for (int i = 0; i < q; ++i) {
string s;
cin >> s;
cout << nextChapter[s] << "\n";
}
}
void init() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
}
int main() {
init();
int testCases = 1;
cin >> testCases;
for (int testCase = 1; testCase <= testCases; ++testCase) {
solve();
}
}
C- The Problems Problem
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k, xc[4] = {-1, 1, 0, 0}, yc[4] = {0, 0, -1, 1};
bool valid(pair<int, int> position) {
return position.first >= 0 and position.first < n and position.second >= 0 and position.second < m;
}
void solve() {
cin >> n >> m >> k;
int matrix[n][m];
vector<pair<int, int>> positions[26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char c;
cin >> c;
matrix[i][j] = c - 'a';
positions[matrix[i][j]].emplace_back(i, j);
}
}
int minimumDistance[26][26];
memset(minimumDistance, -1, sizeof minimumDistance);
bool vis[n][m];
for (int c = 0; c < 26; ++c) {
memset(vis, 0, sizeof vis);
queue<pair<int, int>> currentPositions;
for (auto position: positions[c]) {
vis[position.first][position.second] = true;
currentPositions.push(position);
}
int currentDistance = 0;
while (!currentPositions.empty()) {
int size = currentPositions.size();
while (size--) {
auto me = currentPositions.front();
currentPositions.pop();
int myValue = matrix[me.first][me.second];
if (!~minimumDistance[c][myValue])
minimumDistance[c][myValue] = currentDistance;
for (int i = 0; i < 4; ++i) {
pair<int, int> neighbor = {me.first + xc[i], me.second + yc[i]};
if (!valid(neighbor) or vis[neighbor.first][neighbor.second])
continue;
vis[neighbor.first][neighbor.second] = true;
currentPositions.push(neighbor);
}
}
currentDistance++;
}
}
string s;
cin >> s;
ll sum = 0;
for (int i = 0; i < k - 1; ++i)
sum += minimumDistance[s[i] - 'a'][s[i + 1] - 'a'];
cout << sum << endl;
}
int main(int argc, char *argv[]) {
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
D- The FFT Problem
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6;
void solve() {
ll n;
cin >> n;
pair<int, ll> ans = {1, -1};
if (n >= 16)
ans = {1, n - 4}; // 14
if (n % 4 == 0 and n - 4 > 16)
ans = {2, (n - 4) / 4}; // 44 (only case where b > sqrt(n) and number of fours is greater than 1, allowing us to ignore all bases above sqrt(MAX_N))
for (ll b = 2; b <= min(b + 1, N); ++b) {
int digits = 0, fours = 0;
ll current = n;
while (current) {
digits++;
fours += current % b == 4;
current /= b;
}
ans = max(ans, make_pair(fours, b));
if (ans.first >= digits) break;
}
cout << ans.second << endl;
}
int main(int argc, char *argv[]) {
int t = 1;
cin >> t;
while (t--)
solve();
}
E- Tim Game
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
vector<int> adj[N];
int getGrundy(int u = 0, int p = 0) {
int ret = 0;
for (auto v: adj[u])
if (v != p)
ret ^= getGrundy(v, u);
return ret + 1;
}
void solve() {
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (getGrundy() > 1)
cout << "The Secret Partner\n";
else
cout << "Eddard\n";
for (int i = 0; i < n; ++i)
adj[i].clear();
}
void init() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
}
int main() {
init();
int testCases = 1;
cin >> testCases;
for (int testCase = 1; testCase <= testCases; ++testCase) {
solve();
}
}
F- Fibonacci Strings
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX_X = 1000, MAX_K = 1'000'000'000'000'000'000;
void solve() {
ll fibonacci[MAX_X + 1];
cin >> fibonacci[1] >> fibonacci[2];
for (int i = 3; i <= MAX_X; ++i) {
fibonacci[i] = min(fibonacci[i - 1] + fibonacci[i - 2], MAX_K);
}
string fibonacciString[4];
cin >> fibonacciString[1] >> fibonacciString[2];
fibonacciString[3] = fibonacciString[2] + fibonacciString[1];
ll x, k;
cin >> x >> k;
if (x == 1) {
cout << fibonacciString[x][k - 1] << endl;
return;
}
while (k > fibonacci[3]) {
int l = 2, r = x;
while (r - l > 1) {
int mid = (l + r) / 2;
if (k > fibonacci[mid])
l = mid;
else
r = mid;
}
k -= fibonacci[l];
}
cout << fibonacciString[3][k - 1] << endl;
}
int main() {
int t = 1;
cin >> t;
while (t--)
solve();
}
G- Symmetric Subarrays
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
void manacher(vector<int> &v, vector<int> &radii) {
int n = v.size(), last = 0;
for (int i = 1; i < n - 1; ++i) {
if (last + radii[last] > i)
radii[i] = min(last + radii[last] - i, radii[last - (i - last)]);
while (v[i + radii[i]] == v[i - radii[i]])
++radii[i];
if (i + radii[i] > last + radii[last])
last = i;
}
}
void solve() {
int n;
cin >> n;
vector<int> v(2 * n + 1);
v[0] = -2;
v[2 * n] = -1;
for (int i = 0; i < n; ++i)
cin >> v[2 * i + 1];
n = 2 * n + 1;
vector<int> radii(n);
manacher(v, radii);
vector<ll> prefixSum(n + 2);
for (int i = 1; i < n - 1; ++i) {
radii[i] -= (radii[i] & 1) ^ !!v[i];
prefixSum[i - radii[i]] += 1;
prefixSum[i + 1] -= 2;
prefixSum[i + radii[i] + 2] += 1;
}
for (int c = 0; c < 2; ++c)
for (int i = 1; i < n; ++i)
prefixSum[i] += prefixSum[i - 1];
for (int i = 0; i < n; ++i)
prefixSum[i] >>= 1;
ll ans = 0;
for (int i = 1; i < n - 1; ++i)
ans += prefixSum[i] % mod * v[i] % mod;
cout << ans % mod << endl;
}
void init() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
}
int main() {
init();
int t = 1;
cin >> t;
while (t--)
solve();
}
H- Hot Cappuccino
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6;
int xc[4] = {0, 0, -1, 1}, yc[4] = {-1, 1, 0, 0};
void solve() {
int n, m;
cin >> n >> m;
int a[n][m];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int cost[n][m][2];
memset(cost, -1, sizeof cost);
cost[0][0][0] = cost[n - 1][m - 1][1] = 0;
for (int mover = 0; mover < 2; ++mover) {
deque<pair<int, int>> currentBlocks;
currentBlocks.emplace_front((n - 1) * mover, (m - 1) * mover);
while (!currentBlocks.empty()) {
auto currentBlock = currentBlocks.front();
currentBlocks.pop_front();
int x = currentBlock.first, y = currentBlock.second;
int stepCost = !(a[x][y] & (1 << !mover));
for (int i = 0; i < 4; ++i) {
int x1 = x + xc[i], y1 = y + yc[i];
if (x1 < 0 or x1 >= n or y1 < 0 or y1 >= m or
cost[x1][y1][mover] != -1 and cost[x1][y1][mover] <= cost[x][y][mover] + stepCost)
continue;
cost[x1][y1][mover] = cost[x][y][mover] + stepCost;
if (stepCost)
currentBlocks.emplace_back(x1, y1);
else
currentBlocks.emplace_front(x1, y1);
}
}
}
int minCost = 1e8;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
minCost = min(minCost, cost[i][j][0] + cost[i][j][1]);
}
}
cout << minCost << endl;
}
int main() {
int t = 1;
cin >> t;
while (t--)
solve();
}
I- The Vampire Partner
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 17, mod = 1e9 + 7;
mt19937 rnd(time(nullptr));
void solve() {
ll n, fc;
cin >> n >> fc;
ll p[n];
for (int i = 0; i < n; ++i)
cin >> p[i];
ll fp = 0;
for (int i = 0; i < n and fp <= fc; ++i)
fp += p[i] * (i + 1);
if (fp == fc)
cout << "YES\n";
else
cout << "NO\n";
}
void init() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
}
int main() {
init();
int testCases = 1;
cin >> testCases;
for (int testCase = 1; testCase <= testCases; ++testCase) {
solve();
}
}
J- Just One More Bro, I Swear
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 17, mod = 1e9 + 7;
mt19937 rnd(time(nullptr));
void solve() {
int n;
cin >> n;
cout << n;
}
void init() {
}
int main() {
init();
int testCases = 1;
// cin >> testCases;
for (int testCase = 1; testCase <= testCases; ++testCase) {
solve();
}
}
K- The Red Tomato
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
void solve() {
int e;
cin >> e;
pair<ll, ll> w = {0, 1e16};
while (e--) {
int n, m;
cin >> n >> m;
m = n - m;
ll a[n + 2];
a[0] = 0;
for (int i = 1; i <= n; ++i)
cin >> a[i], a[i] += a[i - 1];
a[n + 1] = 1e16;
w.first = max(w.first, a[m]);
w.second = min(w.second, a[m+1]);
}
if (w.first >= w.second)
cout << "False Hypothesis\n";
else
cout << w.first << "\n";
}
int main() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
}
L- Growing Letters
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 17, mod = 1e9 + 7;
mt19937 rnd(time(nullptr));
string generate(int x) {
string ret = "a";
while (x--)
ret += "b" + ret;
return ret;
}
ll fullMask[N];
void solve() {
int n;
cin >> n;
string s;
ll ans = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
for (auto c: generate(min(x, 2))) {
while (!s.empty() and s.back() == c) {
c++, s.pop_back();
}
s.push_back(c);
}
ans += max(0ll, fullMask[x + 1] - fullMask[3]);
}
ans += s.size();
cout << ans << endl;
}
void init() {
for (int i = 1; i < N; ++i)
fullMask[i] = fullMask[i - 1] * 2 + 1;
}
int main() {
init();
int testCases = 1;
cin >> testCases;
for (int testCase = 1; testCase <= testCases; ++testCase) {
solve();
}
}
M- Maximum Subarray Alternating Sum
Hints
Coming soon..
Solution
Coming soon..
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 17, mod = 1e9 + 7;
mt19937 rnd(time(nullptr));
ll kadane(vector<int>& a) {
ll sum = 0, maxSum = 0;
for (int i = 0; i < a.size(); ++i) {
sum += a[i];
if (sum < 0)
sum = 0;
maxSum = max(maxSum, sum);
}
return maxSum;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 1; i < n; i += 2)
a[i] = -a[i];
ll answer = kadane(a);
for (int i = 0; i < n; ++i)
a[i] = -a[i];
answer = max(answer, kadane(a));
cout << answer << endl;
}
void init() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
}
int main() {
init();
int testCases = 1;
cin >> testCases;
for (int testCase = 1; testCase <= testCases; ++testCase) {
solve();
}
}
Auto comment: topic has been updated by Eddard (previous revision, new revision, compare).