Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int solveSingle(int best, int other1, int other2)
{
return max(0, max(other1, other2) + 1 - best);
}
int main()
{
int t;
cin >> t;
while (t--)
{
int a, b, c;
cin >> a >> b >> c;
cout << solveSingle(a, b, c) << ' ' << solveSingle(b, a, c) << ' ' << solveSingle(c, a, b) << '\n';
}
return 0;
}
1593B - Make it Divisible by 25
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const string subseqs[] = { "00", "25", "50", "75" };
const int INF = 100;
int solve(string& s, string& t)
{
int sptr = s.length() - 1;
int ans = 0;
while (sptr >= 0 && s[sptr] != t[1])
{
sptr--;
ans++;
}
if (sptr < 0) return INF;
sptr--;
while (sptr >= 0 && s[sptr] != t[0])
{
sptr--;
ans++;
}
return sptr < 0 ? INF : ans;
}
int main()
{
int t;
cin >> t;
while (t--)
{
string n;
cin >> n;
int ans = INF;
for (auto e : subseqs)
ans = min(ans, solve(n, e));
cout << ans << '\n';
}
return 0;
}
Idea: ITMO student team
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<int> x(k);
for (int i = 0; i < k; i++) cin >> x[i];
sort(x.rbegin(), x.rend());
int cnt = 0;
long long sum = 0;
while (cnt < x.size() && sum + n - x[cnt] < n)
{
sum += n - x[cnt++];
}
cout << cnt << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
bool inf = true;
int minval = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] != a[0])
{
inf = false;
break;
}
minval = min(minval, a[i]);
}
if (inf)
{
cout << "-1\n";
continue;
}
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0; i < n; i++)
ans = gcd(ans, a[i] - minval);
cout << ans << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
set<int> divs(int n) {
set<int> d;
for (int dd = 1; dd * dd <= n; dd++)
if (n % dd == 0) {
d.insert(n / dd);
d.insert(dd);
}
return d;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
int k = -1;
forn(i, n) {
int minv = a[i];
int same = 0;
vector<int> d;
forn(j, n) {
if (a[j] == minv)
same++;
else if (a[j] > minv)
d.push_back(a[j] - minv);
}
if (same >= n / 2) {
k = INT_MAX;
continue;
}
map<int,int> div_counts;
for (int di: d)
for (int dd: divs(di))
div_counts[dd]++;
for (auto p: div_counts)
if (p.second >= n / 2 - same)
k = max(k, p.first);
}
cout << (k == INT_MAX ? -1 : k) << endl;
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<vector<int>> g(n, vector<int>());
vector<int> rem(n, 0);
vector<int> layer(n, 0);
for (int i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
x--;
y--;
g[x].push_back(y);
g[y].push_back(x);
rem[x]++;
rem[y]++;
}
queue<int> q;
for (int i = 0; i < n; i++)
if (rem[i] == 1)
{
q.push(i);
layer[i] = 1;
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v : g[u])
{
if (rem[v] != 1)
{
rem[v]--;
if (rem[v] == 1)
{
layer[v] = layer[u] + 1;
q.push(v);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
if (layer[i] > k)
ans++;
cout << ans << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 64;
bool dp[MAX_N][MAX_N][MAX_N][MAX_N]; // (taken, red, mod A, mod B) -> may be
pair<bool, int> sert[MAX_N][MAX_N][MAX_N][MAX_N]; // the same -> (true (red) | false(black), prev red/black)
int main()
{
int t;
cin >> t;
while (t--)
{
int n, a, b;
string x;
cin >> n >> a >> b >> x;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k < a; k++)
for (int l = 0; l < b; l++)
dp[i][j][k][l] = false;
dp[0][0][0][0] = true;
for(int taken = 0; taken < n; taken++)
for(int red = 0; red <= taken; red++)
for(int remA = 0; remA < a; remA++)
for(int remB = 0; remB < b; remB++)
if (dp[taken][red][remA][remB])
{
// red transition
dp[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = true;
sert[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = { true, remA };
// black transition
dp[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = true;
sert[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = { false, remB };
}
int bestRed = 0;
for (int red = 1; red < n; red++)
if (dp[n][red][0][0] && abs(red - (n - red)) < abs(bestRed - (n - bestRed)))
bestRed = red;
if (bestRed == 0)
{
cout << "-1\n";
}
else
{
int taken = n;
int red = bestRed;
int remA = 0;
int remB = 0;
string ans = "";
while (taken > 0)
{
auto way = sert[taken][red][remA][remB];
if (way.first)
{
red--;
remA = way.second;
ans.push_back('R');
}
else
{
remB = way.second;
ans.push_back('B');
}
taken--;
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
}
return 0;
}
Idea: nastya_ka
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1'000'000;
int psumOdd[MAX_N + 1];
int psumEven[MAX_N + 1];
void solve()
{
string s;
int q;
cin >> s >> q;
int n = s.length();
psumOdd[0] = psumEven[0] = 0;
for (int i = 0; i < n; i++)
{
psumOdd[i + 1] = psumOdd[i];
psumEven[i + 1] = psumEven[i];
if (s[i] == '[' || s[i] == ']')
{
if (i & 1)
psumOdd[i + 1]++;
else
psumEven[i + 1]++;
}
}
while (q--)
{
int l, r;
cin >> l >> r;
l--;
int odd = psumOdd[r] - psumOdd[l];
int even = psumEven[r] - psumEven[l];
cout << abs(odd - even) << '\n';
}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Can someone explain the solution to F pls
F is a dynamic programming problem. You can use
taken amount
red digits count
the rem of red number mod a
the rem of black numer mod b
to describe a state.The taken amount is phase of the dp. If you use enumeration method to find all states, the amount of states is $$$2^{40}$$$. But if you use dp to descibe all states, the amount of states is only $$$40^4$$$.
Here is my code, written in Python3, but it get TLE. https://codeforces.net/contest/1593/submission/132439261
Here is the same code rewritten by C++, it get AC. https://codeforces.net/contest/1593/submission/132442220
I think the python code is more clearly than C++ code.
Cool! Thanks
d2 is really intresting.
It seems that in the tutorial for A, the answer should be max(0, max(b,c) + 1 — a) (as in the solution code), instead of min(0, max(b,c) + 1 — a).
We don't need that extra array to recover answer string. We can store masks in DP and recover the answer from that. Submission with comments : 131983798
Thanks a lot! Cool explanation.
Your dp is so messy.(F) -__-
Good problemset btw.
Video Editorial of E
Thank you very much, I was having a bug for a long time and I had no idea what it could be (눈‸눈)
Feeling nice to hear that it helped.
For the E problem, will the standard graph bfs not work? I pushed all the leaves ( adjacency list size == 1 ) to a queue and assigned them a distance of 1 ( distance = number of times the operation has to be performed to cut off that node ). Then I performed a bfs assigning increasing distance. Answer is simply all the nodes whose distance is greater than k. This is failing though. Please if somebody could help me out. Thanks in advance
https://codeforces.net/contest/1593/submission/132264294
UPD : I changed the visited logic to an in-degree logic while preserving the bfs (AC : 132341078). Hope somebody finds this helpful. Thank you dedsec_29
Once you mark a node visited, your code will never update its distance. But this is incorrect. You have to mark a node visited only when it becomes a leaf. If you mark it before it becomes a leaf, d[i] will no longer denote iterations after which the node is no longer part of tree
"If you mark it before it becomes a leaf, d[i] will no longer denote iterations after which the node is no longer part of tree."
Can you justify this with a counter-example please? I tried a lot of manual cases (Sample cases passed too), every time the node gets marked as visited, it is correctly assigned the distance from the closest leaf. Say the distance of the node is 3 from the closest leaf and k=3, so that node will be cut off at the end of all k operations, right? Or am I missing something? Thanks again.
Take this test case for example:
1
8 2
1 2
2 3
3 4
4 5
5 6
6 7
8 3
Your output: 2
Correct output: 3
Your code deletes node 3 as you mark the distance 2 for it, but it will be deleted in the 3rd iteration, so d[3] should be 3, not 2
Oh.. Yeah I found my mistake. Thank you so much.
Thnks for your help
Thanks man
You're welcome :)
Can anyone explain the reason for this???
Did anyone solve F using meet in the middle idea ?
I'm trying to do it here but I need a way to combine the answer faster, I'm doing it in O(2^(n/2)*a*b) but it didn't pass.
My idea for E was to look at one diameter of the tree and take a middle point in that diameter. After that i root the tree in this middle point and after that it's easy but unfortunately i got memory limit exceeded. Is this idea works?
yes this idea works, be careful on how you are finding middle point(s) when diameter is even or odd. code
CAN F QUESTION DE DONE USING MEET INT THE MIDDLE?
Yes, but you need to write it with very low constant factor. You can check my submission here
deleted
Because maximum difference is 1e6 — (-1e6) = 2 * 1e6; not 1e12
Can anycody give a counter case in which this approach fails for the problem E (link to problem)? I am not able to think about a counter case thanks Submission
Can anyone help me with this WA on test 2 please 241674222
Hey everyone!! I have done E with another approach. Idea : First , I push all the leafs into a queue, then iterate through the queue. when I find a element adjacent to the leaf, which is also leaf, then push it into queue.(here no need of two arrays)260642079
problem C can be solved using max heap. This is my code 290521714