Идеи задач: MikeMirzayanov.
Разбор
Tutorial is loading...
Решение
for i in range(0, int(input())):
n = int(input())
c1 = n // 3;
c2 = c1;
if n % 3 == 1:
c1 += 1
elif n % 3 == 2:
c2 += 1
print(c1, c2)
1551B1 - Wonderful Coloring - 1
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int L = 26;
int cnt[L];
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
memset(cnt, 0, sizeof(cnt));
for (auto c : s) cnt[c - 'a']++;
int cnt1 = 0;
int cnt2 = 0;
for (int i = 0; i < L; i++)
if (cnt[i] == 1)
cnt1++;
else if (cnt[i] > 0)
cnt2++;
cout << (cnt2 + cnt1 / 2) << endl;
}
return 0;
}
1551B2 - Wonderful Coloring - 2
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200 * 1000 + 13;
int ans[MAX_N];
map<int, vector<int>> indices;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
indices.clear();
memset(ans, 0, n * sizeof(ans[0]));
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (indices[x].size() < k)
indices[x].push_back(i);
}
int m = 0;
for (auto e : indices) m += e.second.size();
m -= m % k;
int color = 0;
for (auto e : indices)
for (auto i : e.second)
{
ans[i] = ++color;
color %= k;
if (--m == 0) goto _output;
}
_output:
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2 * 100 * 1000 + 13;
const int L = 26;
vector<int> balance[L];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 0; i < L; i++)
balance[i].clear();
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
int initBalance = -(int)s.length();
for (int j = 0; j < L; j++)
balance[j].push_back(initBalance);
for (auto c : s)
balance[c - 'a'].back() += 2;
}
int bestCount = 0;
int bestLetter = 0;
for (int i = 0; i < L; i++)
{
auto& b = balance[i];
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
if (b[0] <= 0) continue;
int sumBalance = b[0];
int j = 1;
for (; j < n && sumBalance > 0; j++)
sumBalance += b[j];
if (sumBalance <= 0) j--;
if (j > bestCount)
{
bestCount = j;
bestLetter = i;
}
}
cout << bestCount << endl;
}
return 0;
}
1551D1 - Domino (easy version)
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m, kh;
cin >> n >> m >> kh;
int kv = n * m / 2 - kh;
if (n & 1)
{
kh -= m / 2;
if (kh < 0)
{
cout << "NO\n";
continue;
}
}
else if (m & 1)
{
kv -= n / 2;
if (kv < 0)
{
cout << "NO\n";
continue;
}
}
if ((kh & 1) || (kv & 1))
{
cout << "NO\n";
continue;
}
cout << "YES\n";
}
return 0;
}
1551D2 - Domino (hard version)
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
char field[128][128];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m, kh;
cin >> n >> m >> kh;
int kv = n * m / 2 - kh;
if (n & 1)
{
kh -= m / 2;
if (kh < 0)
{
cout << "NO\n";
continue;
}
for (int i = 0; i < m / 2; i++)
field[n - 1][i * 2] = field[n - 1][i * 2 + 1] = ((i & 1) ? 'x' : 'y');
}
else if (m & 1)
{
kv -= n / 2;
if (kv < 0)
{
cout << "NO\n";
continue;
}
for (int i = 0; i < n / 2; i++)
field[i * 2][m - 1] = field[i * 2 + 1][m - 1] = ((i & 1) ? 'x' : 'y');
}
if ((kh & 1) || (kv & 1))
{
cout << "NO\n";
continue;
}
for(int i = 0; i < n / 2; i++)
for (int j = 0; j < m / 2; j++)
{
if (kh)
{
kh -= 2;
field[2 * i][2 * j] = field[2 * i][2 * j + 1] = (((i + j) & 1) ? 'a' : 'b');
field[2 * i + 1][2 * j] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
}
else
{
field[2 * i][2 * j] = field[2 * i + 1][2 * j] = (((i + j) & 1) ? 'a' : 'b');
field[2 * i][2 * j + 1] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
}
}
cout << "YES\n";
for (int i = 0; i < n; i++)
{
field[i][m] = 0;
cout << field[i] << '\n';
}
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 6000;
int dp[MAX_N][MAX_N];
int a[MAX_N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
dp[i][j] = 0;
for(int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
{
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ((a[i + 1] == j + 1) ? 1 : 0));
}
int ans = -1;
for(int i = n; i >= 0; i--)
if (dp[n][i] >= k)
{
ans = n - i;
break;
}
cout << ans << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 128;
typedef long long ll;
const ll mod = 1000 * 1000 * 1000 + 7;
ll add(ll x, ll y) { return (x + y) % mod; }
ll mul(ll x, ll y) { return x * y % mod; }
vector<int> g[MAX_N];
bool used[MAX_N];
int cnt[MAX_N];
ll dp[MAX_N][MAX_N];
ll rundp(int m, int k)
{
for (int i = 0; i <= m; i++)
for (int j = 0; j <= k; j++)
dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j <= k; j++)
{
dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], cnt[i]));
}
return dp[m][k];
}
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
g[i].clear();
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[--a].push_back(--b);
g[b].push_back(a);
}
if (k == 2)
{
cout << n * (n - 1LL) / 2 % mod << '\n';
return;
}
ll ans = 0;
for (int center = 0; center < n; center++)
{
memset(used, 0, n);
used[center] = true;
vector<pair<int, int>> layer;
int m = g[center].size();
for (int i = 0; i < m; i++)
{
int y = g[center][i];
layer.emplace_back(y, i);
cnt[i] = 1;
used[y] = true;
}
while (!layer.empty())
{
ans = add(ans, rundp(m, k));
vector<pair<int, int>> newlayer;
for (auto p : layer)
{
cnt[p.second]--;
for (auto y : g[p.first])
if (!used[y])
{
newlayer.emplace_back(y, p.second);
used[y] = true;
cnt[p.second]++;
}
}
layer = newlayer;
}
}
cout << ans << '\n';
}
int main()
{
int t;
cin >> t;
while (t--) solve();
return 0;
}
good contest for "try of pen",i like it,thanks.waiting soon for your div 2 and div 1 contests.
Even though the DIV3 was harder than the last few DIV3's, I think the problem set was way more enjoying and educational for a lot of people. I hope you set more DIV3's MrPaul_TUser
But please, make it easier, as a person with <1600 rating,I can say, that at least 4-th problem was very and very hard for actual div3 participants.MrPaul_TUser Thank you anyway. ;)
actually,i dont think that this contest was harder than standart div 3
Transposing the table in D2 was a nice idea! Saves a lot of casework.
A slightly shorter branchless alternative implementation of A, which does the same job (adding 1 to n before division by 3 is the same as incrementing the result by 1 in the case if the remainder was 2):
Please help me in this code (problem B2).
I'm not able to figure out where I'm doing wrong.
This code is failing on tescase-185 of test-2.
My submission
Please help me in this code (problem B2).
I'm not able to figure out where I'm doing wrong.
This code is failing on tescase-185 of test-2.
My submission
when ur are considering the nos having frequency less than k the order also matters suppose there are 4 colors. and 1,2,3 are having count less than 4. if the arrangement is like : 1 2 2 3 1 nos in array. 1 2 3 4 1 coloring . the no 1 is getting the same color.
got it. Thanks!
why this solution for b2 isgiving tle pls help ~~~~~ void _paint_the_town_red() { ll n, k; cin >> n >> k; vl v(n); fa(v) cin >> val; vl temp2 = v; vl cnt(1e6); for (int i = 0; i < n; i++) cnt[v[i]]++; vector temp(k); ll t = 0; sort(all(v)); ll i = 0; while (i < n) { ll j = min(k, cnt[v[i]]); while (j--)//this is main problem { temp[t].pb(v[i]); t = (t + 1) % k; } i += cnt[v[i]]; }
ll maxi = 1e18; for (int i = 0; i < temp.size(); i++) maxi = min(maxi, (ll)temp[i].size());//o(n) for (int i = 0; i < sz(temp); i++) { while (sz(temp[i]) > maxi) temp[i].pp; } map<ll, vl> mp; for (int i = 0; i < sz(temp); i++) { for (int j = 0; j < sz(temp[i]); j++) { mp[temp[i][j]].pb(i + 1); } } for (int i = 0; i < n; i++) { if (mp[temp2[i]].size() > 0) { cout << mp[temp2[i]].back() << " "; mp[temp2[i]].pp; } else cout << 0 << " "; } cout << _endl;} ~~~~~
Really enjoyed A and B! Thanks for a great contest.
https://mirror.codeforces.com/contest/1551/submission/123610411 This is my submission for problem F. According to me the complexity of my solution is of degree 4 so how did this not give TLE?
you are lucky
Yeah but still the runtime is just 62ms
clear $$$n^3k$$$ time for $$$n,k<=100$$$
The O(n^3k) part of your code is setting the dp table to -1, which has a small constant and runs very quickly (10^8 operations). Your recursive solve function for every root and distance runs in O(n^2k) time since every edge can only be connect to 2 vertices. Iteration to find combination over each edge happens at most twice each edge.
What if problem C was changed a bit and one letter should have more occurence than other letters taken individually, and not in total, how should we proceed then?
I misread the problem as you described during contest and was banging my head to get a solution :(.
Same story :(
Not sure whether this is correct, but here is what came to my mind.
We can calculate the maximum number of words we can take considering every character as the 'dominant' character.
Let us say we want to have 'a' as the dominant character. We iterate over all the words one by one, taking all of them in our collection (for now) and keeping track of the total frequency of every character till now. We also maintain separate sets for F(s, 'a', c2), where F(s, 'a', c2) represents this — In word s, frequency('a') — frequency(c2).
So now, suppose we encounter a word due to which 'a' is no longer our dominant character, but instead 'b' is. We refer to our set for F(s, 'b', 'a') and remove the the word s which has the largest F(s, 'b', 'a') from our collection (and also from other sets).
The idea is, take all words as you encounter them. But if a certain words causes 'a' to lose its dominancy to some other character (say 'b'), we will remove such a word which will reduce the total frequency of 'b' as much as possible while not hurting 'a' much, thus restoring dominancy of 'a'.
bro, just realized i read the problem wrong,thnks
The contest was great! It would be better if the editorial for C, would be more explained!
It is possible to solve E with a 1D dp. Details in spoiler.
(Everything below is considered to be 1-indexed)
Note that in your solution, if $$$a_i$$$ is the last fixed point you have, the number of elements you must have deleted is $$$i-a_i$$$.
Let us say $$${dp}_i$$$ is the maximum number of fixed points you can have if you keep the $$$i^{th}$$$ element. Initially, set all $$${dp}_i=-\infty$$$. Now we need to update it by traversing $$${dp}_{1...i-1}$$$. We need to check some conditions.
If $$$a_1==1$$$, $$${dp}_1:=1$$$.
If $$$a_i>i$$$, we can skip computing it.
Now, $$${dp}_i:=1$$$ at least for sure. Suppose we are considering $$${dp}_j$$$ right now, so $$$a_j$$$ is going to be our previous fixed point. Obviously, $$${dp}_j>0$$$. Next, the number of elements you are required to delete for $$$a_j$$$ to be a fixed point mustn't be more than the number required for $$$a_i$$$, so $$$j-a_j \leq i-a_i$$$. And finally, there must be enough elements in between to make $$$a_i$$$ a fixed point. So, $$$(i-a_i)-(j-a_j) \leq i-j-1$$$. If all the conditions are satisfied, $$${dp}_i:=\max({dp}_i, {dp}_j+1)$$$.
Now all we need to find is the minimum of $$$i-a_i$$$ over all $$$i$$$ such that $$${dp}_i \geq k$$$.
Submission: 123519134
seems to be just
right?
Yeah...you can simplify the condition like that. I just thought it made more sense to present it the way I did.
Tutorial for D2 seems complecated.
We can reduce to two cases: Number of rows is odd or is even.
In case odd we need to place one row of horz dominoes, max k dominoes. In case even we do not.
Then we place allways two rows of dominoes at once, until k dominos are placed. Then fill all other fields with vert dominoes.
Finding a useable letter foreach dominoe is not hard, simply check the surrounding cells. 123518743
In case odd we need to place one row of vert dominoes
I think there should be horizontal dominoes instead of vert..as in one row only horizontal dominoes can come.
Yes, sorry, that is a typo. I changed "vert" to "horz".
If anybody is interested and have enough time to help me, please do. I understand their are better approaches for B2 then this, but I am not able to understand why did this approach failed.
Approach :
Here is the link for the submission — fails on tc 554 123566013
Also show no mercy if the code is bad, so that I get to learn how to code better than what I have done.
Peace out!
use this tc 1 6 3 1 2 5 3 3 3 your solution will output 1 1 2 2 3 0 but one of the correct ans will be in the form 1 2 3 1 2 3 I think your solution will also give tle for larger value of n. if you till have any doubt feel free to ask me.
Thank you Astro-naut! Understood due to the tc! Now will go for the better approach thanks a lot !
Is it possible to solve Equidistant Vertices in faster than O(N^2 K) (maybe with some optimization in the dp)?
Here's what I think. If you fixed the root, and then you fixed the depth of the nodes from the root, you want to find the number of ways to pick $$$k$$$ nodes from them so that their pairwise LCA is the root. Naturally, this splits up our set into some $$$m$$$ groups, from which we can fix $$$k$$$ groups and then the number of ways would be the product of the sizes of those groups. Let's say the group sizes are $$$g_1, g_2,...,g_m$$$. If we consider the polynomial $$$(x+g_1)(x+g_2)...(x+g_m)$$$, then the value we want is the $$$k^{th}$$$ coefficient starting from the largest term ($$$0$$$-indexed). Now, this product can probably be computed in $$$\mathcal{O}(n {\log}^2 n)$$$ with divide-and-conquer+FFT/NTT for an overall complexity of $$$\mathcal{O}(n^2{\log}^2 n)$$$. I haven't implemented it myself, so please point out the error if you think I'm wrong.
Oh that's a nice idea. How is Kth coefficient computed in O(N log^2(N)) though?
Well, I think the following: If we split our product into two halves and compute each half, we'll get two polynomials of roughly equal degree, which we can then multiply with FFT/NTT. The recurrence relation would look like $$$T(n)=2T(\frac{n}{2})+ \mathcal{O}(n\log n)$$$, and we can use the master theorem for divide-and-conquer to get that this works out to $$$\mathcal{O}(n{\log}^2 n)$$$. We can simply extract the required coefficient from the final answer presented in the form of a list of coefficients.
Ah I see. Nice solution! Could this be done faster with generating functions?
Sorry, no idea.
I am getting TLE for test case two for prob B2. Can someone tell me is my approach wrong as I am getting TLE even though tc is NlogN. My solution https://mirror.codeforces.com/contest/1551/submission/123636719
When the number of test cases is equal to 10000 your vectors hsh[200005] and prev[200005] initializations take too much time. Try the size of vectors N like in your v[] and ans[] vectors.
But your greedy idea to take the first vacant color is incorrect. Try test:
1
9 3
1 2 3 4 5 6 6 7 7
Your answer is:
1 1 1 2 2 2 3 3 0
The correct answer may be:
1 2 3 1 2 3 1 2 3
Thanks a lot ! I got it where I was going wrong.
You Should upvote him for helping.
Problem B2:
let's calculate for each of k colors the number of elements painted in the color — all calculated numbers must be equalI am not understanding how are we managing this condition in given tutorial. Please anybody explain
Take k occurrences of the numbers whose frequency is greater than or equal to k. For all other numbers, take the total sum of frequencies of these numbers (let say the sum is s), and color a*k of these occurrences s.t. (a+1)*k>s .
Another approach for B2 would be doing binary search on how many elements can be painted in one color.
Can you please elaborate your idea of binary search because I was trying to do it through binary search but got tle on tc5.Although B1 passes due to low constraints . Here's my submission https://mirror.codeforces.com/contest/1551/submission/124039451 Can I improve my code or do I need to think of solving it through another approach ?
You need to change your good() function. You should use something like set which will keep the pairs sorted. You can seelink my check() function
147410960 Hii! can someone check why is it failing on test case 1, even when everything is correct according to me. Thanks!
If you look at the output, you have a situation where two vertical dominos, sharing a side have same color. This is not allowed, as mentioned in problem as well.
Could anyone check why this submission of mine get WA for this test case (wrong answer invalid table description) :
When I change the line $$$38$$$ from
char ans[n][m]tovector<string> ans(n, string(m, 'x'))as in this submission I get AC. So it probably has something to do with iterate through anans[i][j]that hasn't been initialized, but I manually checked the result and didn't see anything wrong.Hey guys, did you realise that in problem B2 the example was referring to the irrational number (pi) in the last three test cases? Nice one :D