2170A - Максимальное соседство
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (Neon)
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
auto get = [&](int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n) return x * n + y + 1;
return 0;
};
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int cur = get(i, j);
for (int d = 0; d < 4; ++d) cur += get(i + dx[d], j + dy[d]);
ans = max(ans, cur);
}
}
cout << ans << '\n';
}
}
Решение 2 (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 1;
if (n == 2) ans = 9;
else if (n == 3 || n == 4) ans = 4 * n * n - n - 4;
else if (n > 4) ans = 5 * n * n - 5 * n - 5;
cout << ans << '\n';
}
}
Идея: FelixArg
Разбор
Tutorial is loading...
Решение (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
int sum = 0;
int cnt_one = 0;
for (int i = 0; i < n; i++){
if (a[i] > 0){
cnt_one++;
}
sum += a[i];
}
int sum2 = sum - cnt_one;
int sub = n - 1 - sum2;
cout << cnt_one - max(0ll, sub) << '\n';
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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())
typedef long long li;
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
inline void solve() {
int n; li k;
cin >> n >> k;
vector<int> q(n), r(n);
fore (i, 0, n)
cin >> q[i];
fore (i, 0, n)
cin >> r[i];
sort(q.begin(), q.end());
sort(r.begin(), r.end());
auto check = [&](int cnt) {
fore (i, 0, cnt) {
if (li(q[i] + 1) * (r[cnt - 1 - i] + 1) - 1 > k)
return false;
}
return true;
};
int lf = 0, rg = n + 1;
while (rg - lf > 1) {
int mid = (lf + rg) >> 1;
if (check(mid))
lf = mid;
else
rg = mid;
}
cout << lf << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t = 1; cin >> t;
while (t--) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int cost(char c)
{
if(c == 'I') return 1;
return 5;
}
int eval(string s)
{
int n = s.size();
int ans = 0;
for(int i = 0; i < n; i++)
if(s[i] == 'I' && i + 1 < n && s[i + 1] == 'V')
ans--;
else ans += cost(s[i]);
return ans;
}
void solve()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
int ans = 0;
for(int i = 0; i < n; i++)
{
if(s[i] == 'X')
{
s[i] = 'V';
ans += 5;
}
}
int inc = 0;
int same = 0;
int qcount = 0;
for(int i = 0; i < n; i++)
{
if(s[i] != '?') continue;
int r = i;
while(r < n && s[r] == '?') r++;
int len = r - i;
if(i > 0 && s[i - 1] == 'I') len++;
if(r < n && s[r] == 'V')
{
inc--;
len++;
}
inc += len / 2;
same += len % 2;
qcount += (r - i);
i = r - 1;
}
for(int i = 0; i < n; i++)
if(s[i] == '?') s[i] = 'I';
ans += eval(s);
for(int i = 0; i < q; i++)
{
int a, b, c;
cin >> a >> b >> c;
int used_v = max(0, min(b, qcount - c));
int used_x = max(0, qcount - c - b);
int cur = ans;
cur += used_v * 4 + used_x * 9;
int rep = used_v + used_x;
cur -= min(inc, rep) * 2;
rep -= (inc + same);
cur += max(0, rep) * 2;
cout << cur << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
2170E - Бинарные строки и блоки
Идея: Roms
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
void solve()
{
int n, m;
cin >> n >> m;
vector<int> max_left(n + 1, -1);
for(int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
--l;
--r;
max_left[r] = max(max_left[r], l);
}
for(int i = 1; i <= n; i++)
max_left[i] = max(max_left[i], max_left[i - 1]);
vector<int> dp(n + 1);
vector<int> prefsum(n + 2);
dp[0] = 2;
prefsum[1] = 2;
for(int i = 1; i <= n; i++)
{
int j = max_left[i - 1] + 1;
dp[i] = add(prefsum[i], -prefsum[j]);
prefsum[i + 1] = add(prefsum[i], dp[i]);
}
cout << dp[n] << "\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++) solve();
}
2170F - Построй XOR на отрезке
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int B = 13;
const int M = (1 << (B - 1));
const int INF = 1e9;
int dp[B][M];
void upd(int& a, int b)
{
if(a < b) a = b;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
vector<vector<int>> id(n);
int q;
cin >> q;
vector<int> l(q), x(q);
for(int i = 0; i < q; i++)
{
int r;
cin >> l[i] >> r >> x[i];
--l[i];
--r;
id[r].push_back(i);
}
for(int i = 0; i < B; i++)
for(int j = 0; j < M; j++)
dp[i][j] = -INF;
dp[0][0] = INF;
vector<int> ans(q, 0);
for(int i = 0; i < n; i++)
{
int val = a[i];
upd(dp[1][val], i);
for(int j = 1; j < B - 1; j++)
{
for(int k = 1; k < M; k++)
{
upd(dp[j + 1][k ^ val], dp[j][k]);
}
}
for(auto qr : id[i])
{
int cur = x[qr];
for(int j = B - 1; j >= 0; j--)
if(dp[j][cur] >= l[qr])
ans[qr] = j;
}
}
for(int i = 0; i < q; i++)
cout << ans[i] << " ";
cout << endl;
}
First.
Good F. At first I thought it needed an XOR basis, but it turned out to be a DP problem :)). Of course, you still need the theory to know that the minimum subset size is at most the number of bits in X
67
In C ,how do we know that we have to take the largest remainder and smallest quotient for the optimal answer.In contest it doesn't comes in mind.
In these type of question i get stuck in these situation,like — whether to sort in increasing or decreasing order, it will be helpful if someone drop down link of some problem like C .
Just greedy observation: 1) If the largest remainder can't form a pair with the smallest quotient, it can't be used at all. 2) Otherwise, the largest remainder can be paired with any suitable quotient, since other remainders have the same prefix or better. We choose the smallest for convenience.
do sorting bro and check if the value doesn't exceed k
356738757
I wonder why Pb A has all tags
Could anyone please explain why my solution for Problem D fails? My logic is to keep track of all the spaces where I can be placed before V (HSi), where V can be placed after I (HSxv), or where either I or V can be placed to form IV (HS). I also count the number of double spaces (DS) and adjust based on how many spaces were used to form IV pairs. I use freeHS to keep track of the number of spaces where an item can be placed to form an IV pair and will not impact the number of double spaces. After all the freeHS spaces are used up, then the number of double spaces will decrease
Submission: 351402607
As a newbie, I'd appreciate a bit more detailed solutions. For example in the solution for B, there's a "magic jump": if
s−c≥n−1, then answer isc, on which the further is reasoning is based, but its not trivial.Not sure if this is helpful, but I struggled with that condition too and this is how I understand it.
We need n actions exactly according to the problem statement. So we need to be able to perform n-1 more actions after doing our first c-length action.
Intuitively, the smallest action we can do is adding 1 to a single element. Hence, given a particular array, we can at most perform S actions, where S is the sum of its elements.
So then we need s-c >= n-1, where s-c is what we need after one c-length action, and n-1 is the actions we need to take.
one another approach for B is to use binary search on answer . Firstly sort the array. Our answer will only lie between 1 to no. of non zero elements so perform a binary search that what is the maximum number of sequence length we can take for each binary search query we make the first mid no. of elements increase by 1 . Then we iterate for all numbers from 0 to mid and add the numbers arr[i] — 1 as these many more operations can be made into these elements at max.
similiarly for elements greater than index mid we add all elements (which gives the maximum operation can be performed) if these operation exceed the n then we can store it in our answer and check for next greater sequence. check submission : 371283481
In 2170D, I don't understand the following explanation in the solution:
Greedy idea: let's use the maximum possible number of Is, then the maximum possible number of Vs, and only then use Xs. It's because if we replace any I with V, it increases the value by at least 3 , and if we replace any V with X, it increases the value by exactly 5.
Why does replacing any I with V increase the value by at least 3?
For instance if we have "II", the value is +2. If we replace the second I with V, we get "IV" and the value is (-1) + 5 = +4. In this case, it seems like the value is increased by 2. Am I missing something here? Thanks!
The wording might be a bit weird, but it's just referring to the net increase per item. So at the very least a V can be worth +4 (if there's an I in front of it) and at the very most an I is worth +1, so it's always better to use an I instead of a V. In other words, the worst case scenario for using an I is still more desirable than the best case scenario for using a V.
ok cool this makes sense tysm for response!
For People who didn't understand Editorial for B:
here is the simple explanation: first, we need to find the number of non-zero components and call it cnt. and find the sum of all the elements in an array and call it sum.
Now, lets take an example: 0 0 1 1 4
to convert it to 0 0 0 0 0 in exactly n operations, we need to know the size of the very first operation lets call size of the first operation to be x, if we do:
0 0 [0 0 3]
then sum — 3*(-1) will be the sum after performing op1, we need to check if the value of new sum >= n-1 or not, if yes then its okay, else it won't be possible to perform remaining n-1 ops
so we need to find the range for the first operation such that sum >= n-1, now since one relation was
original sum — x >= n-1
then original sum — n + 1 >= x thus our final answer is min(x,number of non-zero components (cnt as we declared it earlier));
for reference, check this: https://mirror.codeforces.com/contest/2170/submission/351669568
I hope that helps!
got it!
brother, can you explain this line?
"then original sum — n + 1 >= x thus our final answer is min(x,number of non-zero components (cnt as we declared it earlier));"
how you was able to come up with that expression?
Please someone explain how to think to solution of Problem E?
Problem E: Could anyone please tell what's wrong in this dp — dp[I][j] -> number of binary sequences of length I, ending in j (0 or 1), having at least 1 constraint ending on or before I having only 1 block. 353003771
Its a bit late but I also tried similiar thing initially with power of 2 if you check carefully there will be multiple counting cases here. You are checking for a given r then nearest l, but if you check in between block you have considered its dp too and they will intersect in some cases and you are multiple counting them
why F's solution the dp's j order can don't reverse,what happen here?