Thanks for taking part in the round. I hope you enjoyed the round. It happens that the statements were really easy to understand (thanks to testers). We've got only 38 questions during a round!
Tutorial is loading...
Code
int n, m;
cin >> n >> m;
int result = -1;
if (m % n == 0) {
result = 0;
int d = m / n;
while (d % 2 == 0)
d /= 2, result++;
while (d % 3 == 0)
d /= 3, result++;
if (d != 1)
result = -1;
}
cout << result << endl;
Tutorial is loading...
Code
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int result = 0;
int len = 0;
for (int i = 0; i < 2 * n; i++) {
if (a[i % n] == 1) {
len++;
result = max(result, len);
} else {
len = 0;
}
}
cout << result << endl;
Tutorial is loading...
Code
int n;
cin >> n;
vector<int> q(n - 1);
long long sum = 0;
long long min_val = 0;
for (int i = 0; i + 1 < n; i++) {
cin >> q[i];
sum += q[i];
if (sum < min_val)
min_val = sum;
}
vector<long long> p(n);
p[0] = 1 - min_val;
forn(i, n - 1)
p[i + 1] = p[i] + q[i];
bool ok = true;
for (int i = 0; i < n; i++)
if (p[i] < 1 || p[i] > n)
ok = false;
if (ok)
ok = set<long long>(p.begin(), p.end()).size() == n;
if (ok) {
forn(i, n)
cout << p[i] << " ";
} else
cout << -1 << endl;
Tutorial is loading...
Code
#define forn(i, n) for (int i = 0; i < int(n); i++)
const int A = 26;
...
int n;
cin >> n;
string l;
cin >> l;
vector<vector<int>> left(A);
vector<int> wl;
forn(i, n)
if (l[i] != '?')
left[l[i] - 'a'].push_back(i);
else
wl.push_back(i);
string r;
cin >> r;
vector<vector<int>> right(A);
vector<int> wr;
forn(i, n)
if (r[i] != '?')
right[r[i] - 'a'].push_back(i);
else
wr.push_back(i);
vector<pair<int,int>> p;
vector<int> cl(A), cr(A);
forn(i, A) {
forn(j, min(left[i].size(), right[i].size()))
p.push_back(make_pair(left[i][j] + 1, right[i][j] + 1));
cl[i] = cr[i] = min(left[i].size(), right[i].size());
}
forn(i, A)
while (cl[i] < left[i].size() && !wr.empty()) {
p.push_back(make_pair(left[i][cl[i]] + 1, wr[wr.size() - 1] + 1));
cl[i]++;
wr.pop_back();
}
forn(i, A)
while (cr[i] < right[i].size() && !wl.empty()) {
p.push_back(make_pair(wl[wl.size() - 1] + 1, right[i][cr[i]] + 1));
wl.pop_back();
cr[i]++;
}
forn(j, min(wl.size(), wr.size()))
p.push_back(make_pair(wl[j] + 1, wr[j] + 1));
cout << p.size() << endl;
for (auto pp: p)
cout << pp.first << " " << pp.second << endl;
Tutorial is loading...
Code
long long H;
int n;
cin >> H >> n;
vector<long long> a(n);
long long sum = 0;
long long gap = 0;
long long h = H;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum -= a[i];
h += a[i];
if (h <= 0) {
cout << i + 1 << endl;
return 0;
}
gap = max(gap, sum);
}
if (sum <= 0) {
cout << -1 << endl;
return 0;
}
long long whole = (H - gap) / sum;
H -= whole * sum;
long long result = whole * n;
for (int i = 0;; i++) {
H += a[i % n];
result++;
if (H <= 0) {
cout << result << endl;
break;
}
}
Tutorial is loading...
Tutorial is loading...
Code
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
map<int, vector<pair<int,int>>> segs;
for (int r = 0; r < n; r++) {
int sum = 0;
for (int l = r; l >= 0; l--) {
sum += a[l];
segs[sum].push_back({l, r});
}
}
int result = 0;
vector<pair<int,int>> best;
for (const auto& p: segs) {
const vector<pair<int,int>>& pp = p.second;
int cur = 0;
int r = -1;
vector<pair<int,int>> now;
for (auto seg: pp)
if (seg.first > r) {
cur++;
now.push_back(seg);
r = seg.second;
}
if (cur > result) {
result = cur;
best = now;
}
}
cout << result << endl;
for (auto seg: best)
cout << seg.first + 1 << " " << seg.second + 1 << endl;
Tutorial is loading...
Code
int n, k, r;
vector<vector<pair<int,int>>> g;
int D;
vector<int> col;
void dfs(int u, int p, int f) {
int color = 0;
for (auto e: g[u])
if (p != e.first) {
if (color == f) {
color = (color + 1) % D;
f = -1;
}
col[e.second] = color;
dfs(e.first, u, color);
color = (color + 1) % D;
}
}
int main() {
cin >> n >> k;
g.resize(n);
vector<int> d(n);
for (int i = 0; i + 1 < n; i++) {
int x, y;
cin >> x >> y;
x--, y--;
g[x].push_back({y, i});
g[y].push_back({x, i});
d[x]++, d[y]++;
}
map<int,int> cnt;
for (int dd: d)
cnt[dd]++;
int kk = n;
D = 0;
for (auto p: cnt)
if (kk > k)
D = p.first,
kk -= p.second;
else
break;
col = vector<int>(n - 1);
dfs(0, -1, -1);
cout << D << endl;
for (int i = 0; i + 1 < n; i++)
cout << col[i] + 1 << " ";
}
MikeMirzayanov, in code of 1141B - Максимальный непрерывный отдых should be
if (a[i % n] == 1)
but there isif (a[i % 2] == 1)
.Thanks, fixed.
The G's STD code is not complete.
Thank you so much MikeMirzayanov for this round... I enjoy the problems a lot...
E can be solved using binary search also .
Yes, see this
can you please explain , how are you applying binary search, I couldn't solve it in contest because I couldn't find sum to be monotonically increasing or decreasing
The answer exists only when H becomes zero in the first round, or $$$\sum_{i=1}^{\ n} d_i <0 $$$ .
If $$$\sum_{i=1}^{\ n} d_i >= 0 $$$ , print "-1".
So, after each round H decreases by some amount, now binary search for the first round in which H becomes negative.
I also thought to use binary search but could not come up with any idea so i did greedy. Also your code uses the similar idea so binary search can be avoided. Anyway nice to see a binary search solution.
Can you tell how are doing the calculations for upper bound of binary search? high = 1e12; high/=(max(1ll,abs(sm)-1)); high+=N;
simply set high =h / sum
giving wa
brother if you are still around please tell why you did high/=(max(1ll,abs(sm)-1)); high+=N
+1 for username.
:)
Yes but its complexity would be high
no
You are doing a binary search and in each search, you are iterating the whole array to find the answer.
nlogn
That's what I am saying. It can be done in O(n)
yes !
Thank you for this good editorial.
take the case of array -8 -5 -10 +22 the entire array sums up to -1 so instead of taking whole array stipulated times we find the max prefix sum we can get so as we can cut down on the number of operations.
In 1141E — Superhero Battle problem, to find x why do we need to add partial prefix sum to H?
Can someone please this, why I'm having Memory Limit Exceeded, on the implementation I did, while editorial says the same.
51582194
Thanks, in advance.
Please see the memory taken by your code, it is more than 250 MB.
Yes, I asked why it's taking more than 2 GB, I can see that from the verdict that it has taken more than the space provided.
:D that is ~250mb not gb.
Yeah thanks, I just wrongly read that.
Whatever dude, who cares, you got the reason why it's getting MLE??
Try using
int
Nothing happened, did give a try.
Do not use deque
Any specific reason??
I have heard that deque uses more memory. I just found this also https://stackoverflow.com/questions/16252183/why-is-deque-using-so-much-more-ram-than-vector-in-c Give it a try I think it should work.
BTW, it got accepted, but it'd be too good if you can explain the reason.
Thanks.
Though this implementation is in Java but I think you can look at this also https://codeforces.com/blog/entry/10444
How should I approach Problem D in Java? I m not able to get the structure of code for this problem in java.
Not sure if you're still looking for a response, but my approach was as follows: Use ArrayDeques for each letter or '?' to store the indices. Then, when matching letters I just polled left and right until either went empty and then matched rest with '?' if I had any '?' remaining. In the meantime, you can track how many pairs you have created and use StringBuilder's insert method to put that at the front of the output. Code: https://codeforces.com/contest/1141/submission/51599198
can someone please explain in detail how we get the value of x in Problem C
Basically, p'[i] + x is the minimum value in the series. So, then it must be equal to 1, as the series can have values from [1,n]. So, x + p'[i] = 1 => x = 1 — p'[i]
thanks buddy now i got it
For problem "Same Sum Blocks (Hard)" for finding all the possible sum if I do the loop like this
then I'm trying to find the maximum number of disjoint set but it doesn't give me the optimal answer as you can see here 51596165 can anyone explain why it isn't working?
It's a famous CS problem- Interval Scheduling.
You sort the pairs by the end points and then greedily choose the disjoint intervals. My solution- https://codeforces.com/contest/1141/submission/51669831
Is there an intended slower solution that was meant to pass F1 but not F2 ?
Sure. I did the following. The idea is much more standard but might be trickier to implement if you lack experience at dp. Find all different sums of the segments. Now for each one you can do $$$dp[i]$$$ — the maximal number of disjoint segments of this sum up to position $$$i$$$. Updates can be done straightforwardly by iterating over all $$$j < i$$$ and checking if the sum between $$$j$$$ and $$$i$$$ is the current one or not. That's $$$O(n^4)$$$ at best ($$$O(n^5)$$$ if no prefix sums). 51606155
Btw you can also AC f2 if you do updates in $$$O(1)$$$ instead of $$$O(n)$$$ lol. That would be $$$O(n^3)$$$. 51606140
Why your $$$O(n^3)$$$ solution passes. :xD. Isn't $$$n=1500$$$ too much for $$$n^3$$$.
Welp, I just believed that there are not that many distinct sums such that each of them appear at least twice) Apparently, the number is less than expected $$$O(n^2)$$$. I'd be glad to hear the countertest)
Hi Mike,
Thanks for your reply. I appreciate you taking the time to explain your solutions. :)
Isn't the dp part just like finding the LIS?
1141A - Игра 23 can be also solved using dfs.
in problem C . can someone explain me why P[1] = the smallest negative number that I can reach from sum+=q[i] ?
What is u,p and f in dfs function in Problem G's code given?
I solved E with the logic of Arithmetic series like nth number of arithmetic series [ a+(n-1)d ].
In 1141D- Coloured boots, i am getting WA in test case #22. Can someone tell me what am i missing??
Check if you flipped your orders for cases where one string has a ? and the other has a letter.
For problem G I thought of first painting the k vertices which have maximum number of neighbors i.e. to paint the k maximum neighbor vertices with color 1 and then paint rest of the vertices. The number of colors required would be then the maximum number of neighbors of remaining n-k vertices. I don't know how to implement this also whether this approach is correct or not.Has someone else followed this strategy.
hello .......
you can find the (k+1)th largest degree let's say 'd' and this is the maximum number of color needed to color the graph. Now, you can use DFS to color the edges by initiating some variable let's say 'c' with some integer in between 0 to d-1(assuming 0 indexed color) and each time when you move to unvisited vertex make c = (c + 1)%d.
I found something interesting when submitting codes on
1141D - Colored Boots
. It's so slow to erase the vector elements usingerase()
funtion comparing topop_back()
. I got AC after replacing allerase()
withpop_back()
. TLE submission, AC submissionIt's not that interesting really. It's O(n) running time to delete the first element of a vector, while removing the last element is constant time.
Thank you for your hint! It's amazing that the running time of deleting a vector's first element is O(n).
It's because all elements of the vector must be shifted left if you delete the first element.
In problem E, why are we subtracting minimum prefix partial sum from H? I solved it with binary-search but cannot understand this logic of subtracting minimal prefix partial sum from H.
In problem c for calculating value of x why we have taken min_val to be summation of all q[i] instead of finding minimum value from q[i]
Anyone else having problem with problem G test 24 ?
Any easier explanation for 1141C
May be this will help, it's more mathematical but can be intuitive.
We know partial sum $$$p_{i}$$$ = $$$\sum\limits_{i=0}^{n-1}q_{i}$$$ and we can get the value of any permutation $$$P_{i}$$$ as, $$$P_{i}$$$ = $$$p_{i} + x$$$.
Next thing to note is that every number from [1,n] is in the permutation, 1 being the minimum of all, so we will have some $$$P_{i}$$$ = 1, i.e, $$$P_{i}$$$ = $$$p_{i} + x$$$ is minimum( which is 1) only when $$$p_{i}$$$ is minimum, Thus we find minimum $$$p_{i}$$$ (minimum partial sum), subtract it from 1 and we get our x as $$$p_{i}$$$ + x = 1, thus x = 1 — $$$p_{i}$$$
1141C
Why we take minimum?
Input
7
-2 6 -3 2 -1 -3
Output
3 1 7 4 6 5 2
If possible can someone explain with the help of above test case?
In code of 1141G — Privatization of Roads in Treeland why was it necessary to set f=-1 after color and f became equal?
I don't understand the working of the code of Problem D.
Can someone explain me what went wrong in this (my solution for problem E)
Please can someone explain why [i%n] in Question E if we are checking last cycle naively, why then it is using circular traversal?
There's an O(n^2 * log(n)) solution for Same Sum Blocks, if you didn't see the greedy algorithm for finding the maximal number of disjoint blocks.
To find the maximal set of blocks for a given sum, you can use dynamic programming. You can either include a block or not. If you do include the current block, you can binary search (in c++, std::upper_bound) the array of blocks to find the next block that starts after the current block ends, since the array is sorted (or can be sorted without changing the runtime).
Solution of Problem E: " to find x just add with H the minimal prefix partial sum and divide the result by minus total sum. "
Explain it please.
Dear Sir, MikeMirzayanov ,
with due to respect, in 1141C - Поликарп восстанавливает перестановку Solution ,
you used your macro
forn(i, n - 1)
andforn(i, n)
which is understandable, but in my opinion, it will be more awesome if you use standard code in the solution.Thank you sir for this awesome platform.
In problem G for (auto p: cnt) if (kk > k) D = p.first, kk -= p.second; else break; how we get that D we get from the above loop is the minimum
Interesting problems, thanks.