2051A - Preparing for the Olympiad
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
int ans = a[n - 1];
for (int i = 0; i < n - 1; ++i)
ans += max(0, a[i] - b[i + 1]);
cout << ans << '\n';
}
}
Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n, a, b, c = map(int, input().split())
sum = a + b + c
d = n // sum * 3
if n % sum == 0:
print(d)
elif n % sum <= a:
print(d + 1)
elif n % sum <= a + b:
print(d + 2)
else:
print(d + 3)
2051C - Preparing for the Exam
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
for _ in range(int(input())):
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
q = list(map(int, input().split()))
used = [False for i in range(n + 1)]
for i in q:
used[i] = True
l = len(q)
for i in range(m):
if l == n or (l == n-1 and not used[a[i]]):
print(1, end='')
else:
print(0, end='')
print()
Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (BledDest)
def calcLessThanX(a, x):
n = len(a)
s = sum(a)
j = 0
ans = 0
for i in range(n-1, -1, -1):
while j < n and s - a[i] - a[j] >= x:
j += 1
ans += (n - j)
for i in range(n):
if s - a[i] - a[i] < x:
ans -= 1
return ans // 2
for _ in range(int(input())):
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
print(calcLessThanX(a, y+1) - calcLessThanX(a, x))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
vector<pair<int, int>> ev;
for (int i = 0; i < n; ++i) {
ev.emplace_back(a[i], 1);
ev.emplace_back(b[i], 2);
}
sort(ev.begin(), ev.end());
long long ans = 0;
int cnt = n, bad = 0;
for (int i = 0; i < 2 * n;) {
auto [x, y] = ev[i];
if (bad <= k) ans = max(ans, x * 1LL * cnt);
while (i < 2 * n && ev[i].first == x) {
bad += (ev[i].second == 1);
bad -= (ev[i].second == 2);
cnt -= (ev[i].second == 2);
++i;
}
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}});
while (q--) {
int x;
cin >> x;
bool ins = false;
for (auto& [l, r] : segs) {
if (x < l) l = max(1, l - 1);
else if (x > r) r = min(n, r + 1);
else {
ins = true;
if (l == r) l = n + q, r = -q;
}
}
if (ins) {
segs[0] = {1, max(segs[0].second, 1)};
segs[2] = {min(segs[2].first, n), n};
}
int lf = 0, rg = -1, ans = 0;
for (auto [l, r] : segs) {
if (l > r) continue;
if (l > rg) {
ans += max(0, rg - lf + 1);
lf = l; rg = r;
}
rg = max(rg, r);
}
ans += max(0, rg - lf + 1);
cout << ans << ' ';
}
cout << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
const int INF = int(1e9);
int n, q;
vector<int> id, ch;
bool read() {
if (!(cin >> n >> q))
return false;
id.resize(q);
ch.resize(q);
fore (i, 0, q) {
char c;
cin >> id[i] >> c;
id[i]--;
ch[i] = c == '+' ? 1 : -1;
}
return true;
}
int getDist(int s, int t) {
int pSum = 0, cMin = 0;
fore (e, 0, q) {
if (id[e] == t)
pSum += ch[e] < 0;
if (id[e] == s)
pSum -= ch[e] > 0;
cMin = min(cMin, pSum);
}
return -cMin + 1;
}
inline void solve() {
vector<vector<int>> minDist(n, vector<int>(n, INF));
fore (i, 0, n) fore (j, 0, n)
minDist[i][j] = getDist(i, j);
vector<int> len(n, 0);
fore (e, 0, q)
len[id[e]] += ch[e] > 0;
vector< vector<int> > d(1 << n, vector<int>(n, INF));
fore (i, 0, n)
d[1 << i][i] = 1;
fore (mask, 1, 1 << n) fore (lst, 0, n) {
if (d[mask][lst] == INF)
continue;
fore (nxt, 0, n) {
if ((mask >> nxt) & 1)
continue;
int nmask = mask | (1 << nxt);
d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]);
}
}
int ans = INF;
fore (lst, 0, n)
ans = min(ans, d[(1 << n) - 1][lst] + len[lst]);
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
If tutorials for some problems aren't loading, they should be up in about 3-4 minutes.
The E problem is really well designed. Initially, my understanding of the scanline algorithm was focused on processing points within a two-dimensional range. Therefore, when analyzing the E problem, I enumerated all the values of $$$~a_i~$$$ and $$$~b_i~$$$ and treated them as prices, which we denote as val. At this point, the number of buyers among those who would not leave negative reviews is the count of $$$~a_i~$$$ that are greater than or equal to val. The number of buyers who would leave negative reviews is the count of $$$~b_i~$$$ that are greater than or equal to val, under the condition that $$$~a_i~$$$ for that $$$~b_i~$$$ is greater than val. Thus, I viewed this problem as counting points within a two-dimensional range, applying a scanline approach combined with offline processing using a Fenwick tree. However, the complexity of this approach prevented me from implementing it during the competition. After the contest, I was able to see a similar application of the scanline thinking, and the profound understanding of it truly opened my eyes. This also led me to reflect on the essence of the scanline preprocessing, which is to update all necessary states in a legal time complexity according to a certain order. It made me reconsider that in my code design, I should focus on specific implementation steps rather than just thinking about which algorithm to apply. This experience has been very educational and helpful for me! I really appreciate the design of the problems you created!
I think E problem has some ambiguity because if the price advances bi ,that someone may dont buy it and also dont leave a negative review
all right, i am wrong sorry
For problem D, I felt so pathetic, if I would have realised earlier that there is no distinction between index i and j. I have solved same kind of question earlier, I would have solved it in contest as well as:(
E, input:
Why the answer is not 18 (2 * 9)?
1st customer: 9 <= b (negative review), 2nd customer: 9 <= a (positive review).
The thrid customer will give a negative review as well (9 <= 9)
In E, a third method to optimize would be using PBDS, 297960644
Is it possible to use PBDS to solve D?
Yes, I used it 297849167
Hi is there anyone able to solve G with python? My TSP seems too slow (currently at 7000ms). Also, it there any reason for the strict contraints, making it just a library check as even some C++ solutions are TLEing?
UPD: Got it AC
E is simple binary search on answer right? Or am I missing something?
Binary search wont work because total earning w.r.t cost of the tree is not monotonus or unimodal.
Why is it not unimodal?
Why are O(nlogn) solutions getting hacked in E ?
Maybe they get TLE? My O(nlogn) c++ solution barely fits in TL. 297985458
why the testcases of the problems are opened?
Problem D is same to LeetCode 2563. Count the Number of Fair Pairs