Нам очень жаль, что раунд пришлось сделать нерейтинговым. Мы в очередной раз приносим свои извинения и надеемся, что вам понравились задачи!
Идея: shishyando
Разбор
Tutorial is loading...
Реализация
// один манул
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end());
vector<int> b;
for (int i = 0; i < n; i++) {
if (i == 0 || a[i] != a[i - 1]) {
b.emplace_back(a[i]);
}
}
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1]) {
b.emplace_back(a[i]);
}
}
for (auto x : b) cout << x << ' ';
cout << '\n';
}
return 0;
cout << "amogus";
}
Идея: Artyom123
Разбор
Tutorial is loading...
Реализация
//два манула
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
map<int, int> cnt;
while (n--) {
int x;
cin >> x;
cnt[x % m]++;
}
int ans = 0;
for (auto &c : cnt) {
if (c.first == 0) ans++;
else if (2 * c.first == m) {
ans++;
} else if (2 * c.first < m || cnt.find(m - c.first) == cnt.end()) {
int x = c.second, y = cnt[m - c.first];
ans += 1 + max(0, abs(x - y) - 1);
}
}
cout << ans << '\n';
}
return 0;
}
1497C1 - k-НОК (простая версия)
Идея: shishyando
Разбор
Tutorial is loading...
Реализация
// три манула
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n, k;
cin >> n >> k;
if (n % 2) cout << 1 << ' ' << n / 2 << ' ' << n / 2 << '\n';
else if (n % 2 == 0 && n % 4) cout << 2 << ' ' << n / 2 - 1 << ' ' << n / 2 - 1 << '\n';
else cout << n / 2 << ' ' << n / 4 << ' ' << n / 4 << '\n';
}
return 0;
}
1497C2 - k-НОК (сложная версия)
Идея: isaf27
Разбор
Tutorial is loading...
Реализация
// четыре манула
#include <bits/stdc++.h>
using namespace std;
vector<int> solve3(int n) {
if (n % 2 == 1) return {1, n / 2, n / 2};
if (n % 4 == 0) return {n / 2, n / 4, n / 4};
if (n % 2 == 0) return {2, n / 2 - 1, n / 2 - 1};
}
int main() {
int T;
cin >> T;
while (T --> 0) {
int n, k;
cin >> n >> k;
vector<int> added = solve3(n - k + 3);
for (int i = 0; i < k; ++i) {
cout << (i <3 ? added[i] : 1) << ' '; // <3
}
cout << '\n';
}
return 0;
}
Идея: shishyando
Разбор
Tutorial is loading...
Реализация
// пять манулов
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
vector<long long> s(n), tag(n), dp(n, 0);
for (int i = 0; i < n; ++i) cin >> tag[i];
for (int i = 0; i < n; ++i) cin >> s[i];
for (int j = 1; j < n; ++j) {
for (int i = j - 1; i >= 0; --i) {
if (tag[i] == tag[j]) continue;
long long dpi = dp[i], dpj = dp[j], p = abs(s[i] - s[j]);
dp[i] = max(dp[i], dpj + p);
dp[j] = max(dp[j], dpi + p);
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
return 0;
}
1497E1 - Бесквадратное разбиение (простая версия)
Идея: Artyom123
Разбор
Tutorial is loading...
Реализация
// шесть манулов
#include <bits/stdc++.h>
using namespace std;
const int MAXA = 1e7;
vector<int> primes;
int mind[MAXA + 1];
int main() {
for (int i = 2; i <= MAXA; ++i) {
if (mind[i] == 0) {
primes.emplace_back(i);
mind[i] = i;
}
for (auto &x : primes) {
if (x > mind[i] || x * i > MAXA) break;
mind[x * i] = x;
}
}
int T;
cin >> T;
while (T --> 0) {
int n, k;
cin >> n >> k;
vector<int> a(n, 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
int cnt = 0, last = 0;
while (x > 1) {
int p = mind[x];
if (last == p) {
++cnt;
} else {
if (cnt % 2 == 1) a[i] *= last;
last = p;
cnt = 1;
}
x /= p;
}
if (cnt % 2 == 1) a[i] *= last;
}
int L = 0, ans = 1;
map<int, int> last;
for (int i = 0; i < n; ++i) {
if (last.find(a[i]) != last.end() && last[a[i]] >= L) {
++ans;
L = i;
}
last[a[i]] = i;
}
cout << ans << '\n';
}
return 0;
}
1497E2 - Бесквадратное разбиение (сложная версия)
Идея: isaf27
Разбор
Tutorial is loading...
Реализация
// семь манулов
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 1;
const int MAXA = 1e7;
vector<int> primes;
int mind[MAXA + 1];
int main() {
for (int i = 2; i <= MAXA; ++i) {
if (mind[i] == 0) {
primes.emplace_back(i);
mind[i] = i;
}
for (auto &x : primes) {
if (x > mind[i] || x * i > MAXA) break;
mind[x * i] = x;
}
}
vector<int> cnt(MAXA + 1);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k; // уже k манулов
vector<int> a(n, 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
int cnt = 0, last = 0;
while (x > 1) {
int p = mind[x];
if (last == p) {
++cnt;
} else {
if (cnt % 2 == 1) a[i] *= last;
last = p;
cnt = 1;
}
x /= p;
}
if (cnt % 2 == 1) a[i] *= last;
}
vector<vector<int>> mnleft(n, vector<int>(k + 1));
for (int j = 0; j <= k; j++) {
int l = n, now = 0;
for (int i = n - 1; i >= 0; i--) {
while (l - 1 >= 0 && now + (cnt[a[l - 1]] > 0) <= j) {
l--;
now += (cnt[a[l]] > 0);
cnt[a[l]]++;
}
mnleft[i][j] = l;
if (cnt[a[i]] > 1) now--;
cnt[a[i]]--;
}
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
for (auto &c : dp[0]) c = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (j > 0) dp[i][j] = dp[i][j - 1];
for (int lst = 0; lst <= j; lst++) {
dp[i][j] = min(dp[i][j], dp[mnleft[i - 1][lst]][j - lst] + 1);
}
}
}
int ans = INF;
for (auto &c : dp.back()) ans = min(ans, c);
cout << ans << "\n";
}
return 0;
}
SpeedForces
Point distribution was weird imo but Questions were really good tho.
For C2 — legend+ary
Problem A — Implementation based
Problem B — Implementation | Constructive (Great Problem)
Problem C1,C2 — Intuitive | Constructive (Make Cases and you are done with both problems)
Problem E1 — Simply Math | Implementation (Prime factorization)
A great Round shishyando and Artyom123 with great and interesting problems. Hope to see your next round soon !!
E2 and D are interesting problems overall.
I think so. I am not able solve the problems, but reading the resulotion helps me a lot in understanding usage of DP. Love this round so much!
Really liked the problems.
Though I'm a tester, I want to say that C1 is the very beautiful hint for C2! Without C1, C2 can be the hardest problem in the contest.
Agreed, I literally copied my code from C1, made minor changes, then submitted C2.
Can someone explain in detail math behind C1?
It was simple first if n is odd then just print 1 n/2 n/2
if n is even then check for if n/2 is even then print n/2 n/4 n/4 if n/2 is odd then print (n/2)-1 (n/2)-1 2
we can extend this same logic in C2 by simply printing 1 , (k-3) times then taking n=n-(k-3) in C1
n can be of the form 4*k , 4*k+1 , 4*k+2 , 4*k+3 (for some k>=0) case 1: n = 4*k ans = k ,k, 2*k LCM = 2*k
case 2: n = 4*k+1 ans = 1 ,2k ,2k LCM = 2k
case 3: n= 4*k+2 ans = 2 , 2k , 2k LCM = 2k
case 4: n = 4k+3 ans = 1 , 2k+1 , 2k+1 LCM = 2k+1
Great Round by shishyando and Artyom123
Very sad that it got unrated , as it was first ever contest I participated, where 4 question were solvable by any programmer who have knowledge of basic math and preparing frequency array
I went straight to C(hard) without looking at C(easy) since I didn't want to be misled by some simple solution that only worked for simple testcases but not hard ones... instead I fumbled around for an hour looking for a general solution without realizing the k=3 case is all you need. That really backfired on me.
The scoring distribution: 500 — 750 — (750 + 500) — 1750 — (1500 + 1500) It was pretty much clear, C1 was supposed to be harder
At the risk of my submission soon being systested, I think E2 can be solved greedily.
Construct the greedy intervals from E1. Then, at most K times, consider all pairs of adjacent intervals. Compute the number of changes needed to merge all pairs of adjacent intervals in $$$O(n)$$$ and then just merge the best one, and update the array so that excess is put at impossible values.
It works because in the solution you will never remove a value completely from an interval. So taking suboptimal merger will never help since it isn't actually going to reduce a merging cost.
Since you always make at least one change, you repeat at most $$$k$$$ times so it is $$$O(nk)$$$. I think it can be optimised to $$$O(n)$$$.
UPD: I think it cannot be optimised to $$$O(n)$$$, sorry. I thought that maybe you could save computation by only calculating the effect of the merger rather than recalculating every cost, but that's still $$$O(n)$$$.
UPD2: WA47, I wonder if greedy is just wrong here or it's a problem with the code...
UPD3: Assuming that you are merging intervals, the solution is optimal. However, it is also possible to split up an interval, so it does not work.
Can you explain a bit more in detail about splitting intervals? I had the same reasoning and (theoretical) solution as you as well as WA47 and would like to know what the logical error is.
Say there are just three intervals originally. The greedy solution wants to subsume the middle interval into either the left or the right interval. However, it is also possible to subsume the left part of the middle interval into the left interval and the right part of the middle interval into the right interval. It is possible that this is less costly.
That's perfect, thank you!
what do you mean by best one? does it mean that bigger the interval, the better it is? or anything else? btw approach is nice. Thank you !!
Thank you for the problems!
even despite unrated, this was the best round ive taken in a while. clean and concise problem statements. thank you so much for the round. :D
Checkout this problem for a variant on problem A.
I recalled the problem while giving the round today, lovely coincidence.
What are "constructive" problems? can anyone tell. how to become good at these?
Basically, it is related to problems which is asking you to find any answer(of possibly many) that satisfies the constraints of the question. You can practice these here
Thanks dude! I'll save this reply.
Constructive Problems asks you to build something like array, graph or matrix which satisfies the given condition in problem. Usually these type of problems have multiple correct solutions and asks you to output any one. For problems you can refer this and this blog.
"...it is easy to see that..."
Writing that sentence is like begging for downvotes. Remember, editorials are written for those not able to solve the problem. Telling them how easy it is is no good idea.
From problem D: "Then in binary form weight has its k-th bit set true if and only if j < k < i" Shouldn't it be j <= k < i ? Because we have for example 10000 — 00100 = 01100
From problem D: "Then in binary form weight has its k-th bit set true if and only if j < k < i" Shouldn't it be j <= k < i ? Because we have for example 10000 — 00100 = 01100
Seems true, thank you. Fixed now.
Seriously C2 was nice af!!
Thanks for the round, although I couldn't participate.
Problem D is beautiful.
Is it ok that i got TL in E2 with O(nk log n + max(a_i)) complexity ?
Is your max(a_i) per test case, or in total? If it's per test case, then it would be O(nklogn+max(a_i)t) which is too much
it's in total, I need it to precalculate prime numbers which are less than 1e7, I passed E1 that way.
Help needed 110230087 for problem 1497B - M-arrays
Your Solution is failing for testcase:
Corrected 110257624,
Just changed m/2 to (m+1)/2 in FOR loop
thanku
You also have one more mistake.
If i=0 => m-i=m, but m can not be a reminder by mod m. So you have to check v[i] and v[(m-i)%m].
no, I started i from 1.
For me C2 strikes so fast even I hadn't thought of it...it just dropped from the sky :)
Simply, considering 1 1 1 1 ... upto k-3 and the C2 becomes C1
I think if there was no C1 then people may have a hard time coming to this solution for C2.
The dp of E2 can be solved in O(nk). https://codeforces.net/contest/1497/submission/110252728
What is the reason for the unusual memory limit in Problem D?
I'm assuming the reason was to prevent the more obvious solution with a dp[n][n] table, which would need to store up to 25,000,000 ints = 100 megabytes.
igz Can you please explain the dp[n][n] solution?
Why it is necessary to use map instead of unordered_map in 1497B - M-arrays? I submitted both versions but only map got AC but unordered_map one got WA on test 3. map version-> 110262091 unordered_map version-> 110262159
Using cnt[i] may create a new element (cnt[i]=0) in map. And it may cause rehashing of unordered_map, iterators are invalidated (see "Iterator invalidation" here), and for-loop continues working with invalid iterators, which causes undefined behaviour. In usual map creating new element does not invalidate iterators, so UB won't happen. But u still got lucky that these extra zeroes in your map don't change result of your program.
I really like how C1 is a hint for C2.
C1 750pts
C2 500pts
Problem E is similar to this problem.
If Only I submitted C1 after My C2 was accepted!
i am curious while doing C1,C2 problem how people were able to come up with the idea of for n%2 == 0 ans is n/2,n/2,2 and for n%4 == 0 ans is n/2-1,n/2-1,2 and so on.During the contest I made a pattern for 1 to 11 but i was unable to intutively guess this solution .Can anyone recommend the problems that i can do for increasing my intution for doing this type of problems thanks
sorry for late response.I made a patter up to 23 before getting the right answer. My cases was if n is a multiple of 3 we done (n / 3, n / 3, n / 3), and it was difficult after that. I sais to myself it the limit is n / 2 i will try to be near to n / 2. and for each number i put n / 2 and see what can be done. I think the best is to go up to a limit (say 50) and if you don't see a pattern maybe it's not the right solution.
There is an $$$O(nk)$$$ dp solution in Problme E2.
At first, we can let $$$a[i]=mask(a[i])$$$. Assume $$$dp[i][j]$$$ denotes we consider the first $$$i$$$ positions, after making $$$j$$$ changes, the minimum answer we can get and the maximum position where the begining of the last segment at. So we can just maintain $$$last[i]$$$ which denotes the maximum position $$$j$$$ where $$$a_j=a_i$$$ (expecially, if $$$a_i=0,last[i]=i-1$$$) and make transfers.
The key observation in the solution is that if we change the number $$$a_i=x$$$, and for the first $$$j>i,a_j=x$$$, we should let $$$last[j]=last[i]$$$. But actually, there is no need to do that, we can still get the right answer.
See the code for details.
Stuck in E1. In sample test case 1, should't answer be 2 ? Isn't it valid -> (18, 6, 4), (2, 1) ?
We can't change the order of the sequence while dividing.
Can anyone tell me how to reach to the solution for $$$C2$$$. I am asking this because $$$C1$$$ made a path for $$$C2$$$. So, can someone give some mathematical proof or logical way to approach such problem
Achieving lcm of n / 2 lead intuitively (to me) to take n / 2 everywhere. now we can see that we can put n / 2 at most 2 time and i will remain a 1 case left.(that leads to k = 3 case). you can also think i put the same number some number of time and i put 1 everywhere since 1 does not increase the lcm. But i think it's very difficult to figure out alone without a hint.
for the tutorial for c2,
shouldn't it be (k-3) + n-(k-3) or (k-3) + n — k + 3?
Here is another $$$\mathcal{O}(nk)$$$ solution to 1497E2 - Square-Free Division (hard version).
For the first part, after normalization, instead of
left[i][j]which is a bit bothering, we only need to findpre[i], which is the rightmost index to the left of the current index that shares the same value as the current index. This is very simple.Then for the second part, for each change number
j, we storebest[j]denoting the minimal pair(segs,-last_start), andsecond_best[j]denoting the second minimal pair(segs,-last_start). Herelast_startis the start index of the last open segment, andsegsis the number of segments.During the DP, if the last open segment can contain the new element, everything remains the same. Otherwise, we choose either to start a new segment (so that
jdoes not change), or to change the current element (so thatjbecomesj+1).Note that there would be cases that
second_bestbecomes better thanbest, in which they should be swapped.Code: 110279809
Can we solve it using binary search + greedy?
I do not know whether it is possible, but I think that would be hard.
You may solve our problem here using your observation.
For C1 wasn't there suppose to be a case when n % 3 == 0.The answear would be then n / 3 , n / 3, n / 3?
You could analyze that, but that is not needed. The solution explained in the editorial says if n is odd you do A and if n is even you do B, no need to add more cases. This is a typical bad practice from beginners.
If n is a multiple of 13 you could answer 6*n/13, 6*n/13, n/13. But it would be silly to add such a case
Now let's relax dp values. When we consider an edge {i,j},tagi≠tagj we try to solve problem i after solving dpj problems ending with j, and problem i after solving dpi problems ending with i. It means that dpi=max(dpi,dpj+p), dpj=max(dpj,dpi+p) at the same time, where p=|si−sj|.
Can anyone explain this part of the editorial of problem D?
Even i am not able to get this part....
восемь манулов
Guys I'm really sorry I know posting your code and asking why it's giving me an error is a sure-fire way to get downvoted but I really have no choice, I have commented neatly and explained the code for problem D, but I keep getting a run-time error on TC-2, can anyone please help me out
Here is the code : Python 3
Thank you in advance :)
it's because in your code first of all you didn't memoized all the states and 2ndly recursion tree for your code does not form a DAG(because yours is cyclic) which is necessary condition for any dp/recursion problem. In simpler words you end up calling a state which initially made you call these states.
For a case where n = 3z ,z being an odd natural number, isn't the answear (z, z ,z), not (1, n / 2, n/ 2) as it is specified in the editorial ?
Guys is there an algorithm involved in B problem. Or is it an only math based problem? What should be said ?
Both i guess
which algorithm ?
Hello Everyone, Can some one tell me, where I am getting wrong in problem E2? I am getting WA on 8th testcase.
My solution.
Thank you in advance !!
Can someone provide better explanation for D and E2?
C1, C2 sucks :((
Omg. I was amazed when I read the tutorial for Problem C2. I accepted C1. After that, I tried to think and find solution for C2 for 1 hour before I gave up. That's amazing. That's unbelievable. That's incredible.
Can someone please help me understand why this solution for E2 works on all tests except 47?