Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n, m, k = map(int, input().split())
max_color = (n + m - 1) / m
if max_color + k >= n:
print('NO')
else:
print('YES')
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
lst = -1
ans = n
for i in range(n):
if a[i] != a[0]:
ans = min(ans, i - lst - 1)
lst = i
ans = min(ans, n - lst - 1)
if ans == n:
print(-1)
else:
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string x, y;
cin >> x >> y;
int n = x.size();
bool f = false;
for (int i = 0; i < n; ++i) {
if ((x[i] > y[i]) == f) swap(x[i], y[i]);
f |= (x[i] != y[i]);
}
cout << x << '\n' << y << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
return x;
}
int mul(int x, int y) {
return x * 1LL * y % MOD;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int s = accumulate(a.begin(), a.end(), 0);
vector<int> dp(s + 1);
dp[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = s - a[i]; j >= 0; --j)
dp[j + a[i]] = add(dp[j + a[i]], dp[j]);
int ans = 0;
for (int j = 0; j <= s; ++j)
ans = add(ans, mul((j + 1) / 2, dp[j]));
for (int i = 0; i < n; ++i)
for (int j = 0; j < a[i]; ++j)
ans = add(ans, mul(a[i] - (a[i] + j + 1) / 2, dp[j]));
cout << ans << '\n';
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int divup(int a, int b){
return (a + b - 1) / b;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
forn(i, n) cin >> a[i];
int mx = *max_element(a.begin(), a.end());
vector<long long> ans(mx + 1);
forn(i, n){
int coef = 0;
if (i == 0 || a[i] > a[i - 1]) ++coef;
if (i + 1 < n && a[i] < a[i + 1]) --coef;
int r = a[i];
ans[r] += coef;
while (r > 0){
int val = divup(a[i], r);
int l = divup(a[i], val);
ans[l - 1] += coef * val;
ans[r] -= coef * val;
r = l - 1;
}
}
forn(i, mx) ans[i + 1] += ans[i];
forn(i, mx) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
Solution 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
forn(i, n) cin >> a[i];
int mx = *max_element(a.begin(), a.end());
vector<long long> pr(mx + 1);
forn(i, n){
int coef = 0;
if (i == 0 || a[i] > a[i - 1]) ++coef;
if (i + 1 < n && a[i] < a[i + 1]) --coef;
pr[a[i]] += coef;
}
forn(i, mx) pr[i + 1] += pr[i];
for (int k = 1; k <= mx; ++k){
long long ans = 0;
for (int l = 1, val = 1; l <= mx; l += k, ++val)
ans += val * 1ll * (pr[min(mx, l + k - 1)] - pr[l - 1]);
cout << ans << ' ';
}
cout << '\n';
return 0;
}
Idea: adedalic
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())
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
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 MOD = int(1e9) + 7;
int add(int a, int b) {
a += b;
while (a >= MOD)
a -= MOD;
while (a < 0)
a += MOD;
return a;
}
void upd(int &ans, int val) {
ans = add(ans, val);
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while (k > 0) {
if (k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int N = 3055;
int f[N], invf[N];
void precalcFact() {
f[0] = invf[0] = 1;
fore (i, 1, N) {
f[i] = mul(f[i - 1], i);
invf[i] = binPow(f[i], MOD - 2);
}
}
int C(int n, int k) {
if (k < 0 || k > n)
return 0;
return mul(f[n], mul(invf[k], invf[n - k]));
}
int n, c, k;
inline bool read() {
if(!(cin >> n >> c >> k))
return false;
return true;
}
int d[N][N], sum[N][N];
// d[z][l] - number of strings of length l, with z zeroes and blocks of 1-s shorter than mx
void precalcShort(int mx) {
memset(d, 0, sizeof d);
d[0][0] = 1;
fore (z, 0, n) {
fore (l, 0, n) {
if (d[z][l] == 0)
continue;
upd(d[z + 1][l + 1], +d[z][l]);
upd(d[z + 1][min(n, l + mx) + 1], -d[z][l]);
}
fore (l, 0, n + 1)
upd(d[z + 1][l + 1], d[z + 1][l]);
}
memset(sum, 0, sizeof sum);
fore (z, 0, n + 1) fore (l, 0, n + 1)
sum[z][l + 1] = add(sum[z][l], d[z][l]);
}
//[lf, rg)
int getSum(int z, int lf, int rg) {
if (z < 0 || z > n || lf >= rg)
return 0;
return add(sum[z][rg], -sum[z][lf]);
}
// cnt[g] is a number of x <= n with gcd(x, n) = g
vector<int> precalcCnt(int n) {
vector<int> cnt(n + 1, 0);
fore (x, 1, n + 1)
cnt[gcd(x, n)]++;
return cnt;
}
int calcFixedPoints(int g) {
if (c >= g)
return c + k >= n;
int cntOnes = (c + k) / (n / g);
int cntZeros = g - cntOnes;
int all = 0;
fore (ones, 0, cntOnes + 1)
upd(all, C(g, ones));
int bad = 0;
fore (pref, 0, c) {
int minZeros = max(0, cntZeros - 1);
int minMid = g - c;
int sufLen = g - pref - 1;
fore (z, minZeros, sufLen + 1)
upd(bad, getSum(z, minMid, sufLen + 1));
}
return add(all, -bad);
}
inline void solve() {
precalcFact();
precalcShort(c);
auto cnt = precalcCnt(n);
int ans = 0;
fore (g, 1, n + 1) {
if (n % g != 0)
continue;
int cntFP = calcFixedPoints(g);
// cerr << "g = " << g << " += " << cnt[g] << " * " << cntFP << endl;
upd(ans, mul(cnt[g], cntFP));
}
// cerr << "ans/n = " << ans << " " << n << endl;
cout << mul(ans, binPow(n, MOD - 2)) << 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);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
why unrated?
UPD:I understand
It is rated. It has been announced that rating will be changed for educational round after div 2.
why unrated?
if you read the blog for latest div 2 contest it states that "UPD: The rating changes for Educational Codeforces Round 164 will be applied after this round."
In what order will the ratings be filed? Ratings for div 2 will be filed after applying changes for editorial round?
Alternative solution for E: transpose the array (find indices of each value), then iterate from $$$a_{max}$$$ to $$$1$$$ and count $$$islands[k]$$$ — the number of groups of connected monsters after doing $$$k$$$ dmg. Then just sieve $$$ans[k] = \sum_{i=1,2,3,..,\lceil \frac{a_{max}}k\rceil} islands[i \cdot k] $$$. 256372546
is the contest unrated
Correct me if I'm wrong, Educational contest will not effect the rating, right?
It was supposed to be rated for div2 people..I donot know why it is unrated though
Oh yeah, that's weird
Don't worry,he says this contest is also rated.
Sorry,I watch blog Edu 163.
It is a rated contest and it will affect your rating
Talking about the complexity of E — do we need to multiply it by 1+1/2+...+1/A? Or should we count it as a constant?
That's where log(A) factor is coming from.
My bad. I had a solution similar to authors' one, but I used a binary search for counting, so that I got O(n + A * (log(A) ^ 2)) complexity
F has almost linear (O(n*log log n)) solution: The high-level idea is the same, but I managed to calculate FixedPoints(g) in O(g). Since sum of divisors grows as O(n*log log n), the overall time complexity is the same.
How to become GM in 3 months like you , having solved only 74 problems.
may be that's his alternate account, if not then he is talented gem
I used to be on GM level before retiring over 5 years ago, this year I decided to make a comeback.
Problem D, are there any similar problems with the idea of the 'standard problem' said in the solution?
Check this one out. It is based on that standard problem. FYI, editorial for this does a good job of explaining it. If you still have confusions on how it works think Bipartite Graphs.
Thank you!
For those interested in a formal proof, I think this might help: https://en.wikipedia.org/wiki/Tutte_theorem
The problem of maximizing the number of pairs can be reformulated as determining whether graph has a perfect matching (or near perfect matching if |V| is odd).
As for the theorem, the only way to create >1 connected components is to remove all colors except one (i). Theorem says that a[i] <= number of removed vertices, which is sum(a[j]) for all j except i.
Hope this helps anyone :)
maybe also mention that we should connect each vertice with all vertices whose color is different from it at first.
problem E
Whats the coefficient thing? I understand that we need to have some coeff for all ai so that its easier to sum over, and then formula is given to find coeff, whats the intuitive rational on what are we trying to achieve?
The coefficient comes from expanding the equation. We can see when max(0, a[i] — a[i — 1]) contributes to the sum.
For this a[i-1] should be less than a[i]. Then if a[i-1] < a[i], a[i] adds to the formula ( (+1) * a[i], where +1 is the coefficient). Now notice that a[i] also appears in the next consecutive difference, namely a[i+1]-a[i]. So if a[i] < a[i+1], as you see we should subtract a[i]. Thus ( (-1) * a[i] ) should be added. So for example, coefficient is (+1) + (-1) = 0 when both if's hold
that helps
thanks :)
For problem D, O(N * V) solution works. Actually when upsolving I didn’t notice the restriction on the sum of a[i] but still solved with all core ideas which are in the official solution. The idea is that for an element to be > (sum of other elements), sum of elements is bounded by 2V.
In problem D, during the contest, I did not notice a limit on the sum of all the elements of the array. However, even without this limitation, the problem can be solved in O(N* maxA). In my solution, I keep a knapsack for sums less than 5000, and separately store the number of possible even/odd sums, as well as the sum of all possible even/odd sums of subsets. There is my code for this task: 256335037
I did the same. But u dont have to calculate number of subsets with odd sum using dp. Number of subsets with odd sum for n numbers is 2^(n — 1), if there is at least one odd number.
Hey guys, can you suggest some problems similar to "D" in here. I am seeing too many different implementations of the same exact ideas with massive variations in runtime & memory. I implemented the same idea with a take / not-take dp where I consider both possibilities of taking/not-taking current element in a set : 256634006.
I want to make sure if this method is enough for such problems or should I consider other implementation too. Hence, if you know any similar problems, please reply.
I just wrote the exact same solution which looks intuitive to me
Can you tell why sorting the array of colors is required?
To calculate the minimum number of groups formed in a set, it is either the biggest element or ceil(half of total sum). Now why is that? Its because if the biggest element is bigger than or equal to the sum of the rest of the elements, you can completely pair up every other element with it, if it is less than the sum of rest of the elements in that set, then you will do random pairing which will result in ceil(sum/2) teams.
To avoid calculating the biggest element, I have sorted it. So that the last element in a set is automatically the biggest element in it.
Refer to dry running sample case 3 for complete understanding.
Got it. Thank you very much
so easy dude. thank you.
I created a video talking about the optimal placement for the balls in D: Colored Balls.
Very good video and nice proof by using pigeon-hole principle! Can you share some insights on using contribution technique to solve this problem? Like in these solns : 256348397 , 256465864
Sure, you can take a look at my submission where I do the same thing, but with explicit DP arrays.
For a prerequisite, watch this video timestamp 10:50 to 14:30
As stated in the video, in iterative DP problems, you should always think about how you can "refresh" the answer when you append an element to the already constructed answer.
Suppose you are processing elements in increasing order, and you've already created all the subsets possible so far, denoted by
dp[sum]
. Now, what happens when you append a new element? There will be 2 new class of subsets : Those which are already created, and those where you compulsorily add the current element in all of the already created subsets.SoBut if you keep on constructing the subsets and wait to compute the answers at the end, it'll be too late, because by that time, you might not know that maximum element of the subset. So, we'll impose a rule : Construct the answer for all the subsets necessarily containing $$$a[i]$$$ when you see $$$a[i]$$$ for the first time.
So, in order to avoid mixing the subsets, we will first compute the answer when we add $$$a[i]$$$. Let's create a temporary DP $$$ndp$$$, which will contain all possible subsets that have $$$a[i]$$$. It's clear that
Note that we intentionally removed the addition since we don't want to pollute our subsets. Now, what is special about the subsets represented by $$$ndp$$$? All these subsets would have max element as $$$a[i]$$$. Therefore, we can compute the answer as $$$max(sum/2, a[i])*ndp[sum])$$$
Once we've computed the sum, we can finally mix these subsets, because we no longer need to track the max info anymore. Therfore,
Brilliant solution. We can't store the value of mx so we immediately calculate the answer for that element. Thanks.
This approach & one mentioned in tutorial seem to faulter in case of suppose input is 3 balls with count 7 7 7 respectively, the approach mentioned gives 53 as output but manually checking it gives 56 as output.
Is input I mentioned valid, if valid then kindly someone guide why is this happening. tutorial approach:
singleton sets {7}*3 value=7*3
sets with two elements {7,7}*3 value=7*3
sets with three elements {7,7,7} value=11 because no element is greater than half of sum of balls (21+1)/2, but actually value should be 14 as two colored balls 7 each will be paired together & form 7 groups and 3rd colored ball will also form 7 groups so total is 14 not 11.
BledDest pls guide.
Call the colors as A, B, C. Here is an arrangement that only requires 11 boxes and not 14 boxes.
Each box contains one ball from the top line and one ball from the bottom line. It uses the same strategy from the video, i.e arrange all balls of the same color in a cyclic manner.
By your reasoning, answer for 2 2 2 with 3 elements should be 4, because you pair up the first 2 balls with each other. But if you don't be greedy and instead pair up the first and last color, you only need 3 box
thanks for guiding,I should have used cyclic approach before posting, will be careful in future
There's a typo in editorial for F. Formula for $$$all$$$ should be $$$\sum_{i=0}^{on}\binom{g}{i}$$$ instead of $$$\sum_{i=0}^{on}\binom{g}{on}$$$.
Thanks, fixed.
Can author explain me why "It means that if gcd(i,n)=gcd(j,n) then FixedPoints(i)=FixedPoints(j) since in both cases we'll get exactly the same group division. So, we can rewrite the answer as following" true ? while FixedPoint(i) depend on "no more than c+k ones and at least c consecutive ones" and group of 2 case different. Thank.
Thank you for fast editorial
I was wondering if there is a way to find $$$min$$$ groups that can be formed if we are allowed to have atmost $$$k$$$ different balls in one group in general. Is there a way to find that in $$$o(n)$$$ time just like the tutorial states for $$$k <= 2$$$.
Can I know what's the mistake — 46th case failed!! submission
What about the case when n is a multiple of m?
why did i find the link to this song https://www.youtube.com/watch?v=kSjj0LlsqnI
in the A problem ? XD
Additional constraint on input: the total number of balls doesn't exceed 5000
I didn't read this line in div2D and end up solving little harder (but interesting) problem where there is no constraint on total number of balls. 286468671
D is one of the most beautiful question I've seen on here in a while!