Идея: kbats183
Решение
Tutorial is loading...
Код
def solve():
n, m = [int(i) for i in input().split()]
ans = 0
for i in range(n):
l = input()
if len(l) <= m:
m -= len(l)
ans += 1
else:
for i in range(i + 1, n):
input()
break
print(ans)
t = int(input())
for i in range(t):
solve()
Идея: AVdovin
Решение
Tutorial is loading...
Код
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
long long ods = 0, evs = 0;
for (int i = 0; i < n; i++) {
if (i & 1) ods += a[i];
else evs += a[i];
}
int odc = n / 2, evc = n / 2;
if (n & 1) evc++;
if (ods % odc != 0 || evs % evc != 0 || ods / odc != evs / evc) {
cout << "NO";
return;
}
cout << "YES";
}
int main() {
int TESTS; cin >> TESTS;
while (TESTS --> 0) {
solve();
cout << '\n';
}
return 0;
}
Идея: DanGolov
Решение
Tutorial is loading...
Код
def solve():
s = [int(x) for x in list(input())]
sm = sum(s)
twos = s.count(2)
threes = s.count(3)
for i in range(min(10, twos + 1)):
for j in range(min(10, threes + 1)):
if (sm + i * 2 + j * 6) % 9 == 0:
print('YES')
return
print('NO')
t = int(input())
for _ in range(t):
solve()
2050D - Максимизация цифровой строки
Идея: AVdovin
Решение
Tutorial is loading...
Код
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s; cin >> s;
for (int i = 0; i < s.size(); i++) {
int best = s[i] - '0', pos = i;
for (int j = i; j < min(i + 10, (int) s.size()); j++) {
if (s[j] - '0' - (j - i) > best) {
best = s[j] - '0' - (j - i);
pos = j;
}
}
while (pos > i) {
swap(s[pos], s[pos - 1]);
pos--;
}
s[i] = char(best + '0');
}
cout << s;
}
int main() {
int TESTS = 1; cin >> TESTS;
while (TESTS --> 0) {
solve();
cout << '\n';
}
return 0;
}
Решение
Tutorial is loading...
Код
#include <iostream>
#include <algorithm>
static const int inf = 1e9;
void solve() {
std::string a, b, res;
std::cin >> a >> b >> res;
int n = (int) a.size(), m = (int) b.size();
int dp[n + 1][m + 1];
std::fill(&dp[0][0], &dp[0][0] + (n + 1) * (m + 1), inf);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
dp[i + 1][0] = dp[i][0] + (a[i] != res[i]);
}
for (int j = 0; j < m; j++) {
dp[0][j + 1] = dp[0][j] + (b[j] != res[j]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = std::min(dp[i - 1][j] + (a[i - 1] != res[i + j - 1]),
dp[i][j - 1] + (b[j - 1] != res[i + j - 1]));
}
}
std::cout << dp[n][m] << std::endl;
}
int main() {
int tests;
std::cin >> tests;
while (tests--) {
solve();
}
}
2050F - Максимальное модульное равенство
Идея: AVdovin
Решение
Tutorial is loading...
Код
#include <bits/stdc++.h>
using namespace std;
const int LOGN = 20;
vector<vector<int>> stGCD;
int get_gcd(int l, int r) {
int k = __lg(r - l + 1);
return __gcd(stGCD[k][l], stGCD[k][r - (1 << k) + 1]);
}
void solve() {
stGCD.clear();
int n, q; cin >> n >> q;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> b;
for (int i = 1; i < n; i++)
b.push_back(abs(a[i - 1] - a[i]));
stGCD.resize(LOGN, vector<int>(b.size(), 1));
for (int i = 0; i < b.size(); i++)
stGCD[0][i] = b[i];
for (int i = 1; i < LOGN; i++)
for (int j = 0; j + (1 << (i - 1)) < b.size(); j++)
stGCD[i][j] = __gcd(stGCD[i - 1][j], stGCD[i - 1][j + (1 << (i - 1))]);
while (q--) {
int l, r; cin >> l >> r;
if (l == r) {
cout << 0 << " ";
continue;
}
l--; r -= 2;
int gcd = get_gcd(l, r);
cout << gcd << " ";
}
}
int main() {
int TESTS = 1; cin >> TESTS;
while (TESTS --> 0) {
solve();
cout << "\n";
}
return 0;
}
Идея: AVdovin
Решение
Tutorial is loading...
Код
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
void dfs(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &dp){
dp[v].x = sl[v].size();
int m1 = -1, m2 = -1;
for(int u: sl[v]){
if(u == p){
continue;
}
dfs(u, v, sl, dp);
dp[v].x = max(dp[v].x, dp[u].x + (int)sl[v].size() - 2);
m2 = max(m2, dp[u].x);
if(m1 < m2) swap(m1, m2);
}
dp[v].y = dp[v].x;
if(m2 != -1){
dp[v].y = m1 + m2 + sl[v].size() - 4;
}
}
void solve(int tc){
int n;
cin >> n;
vector<vector<int>> sl(n);
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
sl[--u].emplace_back(--v);
sl[v].emplace_back(u);
}
vector<pair<int, int>> dp(n);
dfs(0, 0, sl, dp);
int ans = 0;
for(int i = 0; i < n; ++i){
ans = max(ans, max(dp[i].x, dp[i].y));
}
cout << ans;
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
evc = n / 2; if (n & 1) evc++; Is the same as evc = ( n + 1 ) / 2;
Task G is almost identical to a task from the Polish Olympiad in Informatics called Parade. The only difference is in the POI task, you can not choose $$$a = b$$$.
is the same as
No. For example, $$$n = 6$$$. In the first case
6 / 2 = 3, then3 & 1is true andevc = 6 / 2 + 1 = 4. But in the secondevc = (6 + 1) / 2 = 3.I think you are incorrect, because if $$$n = 6$$$, then it is be 6 & 1 not 3 & 1, so for $$$n = 6$$$ it should give $$$3$$$, so Karim__2 formula is indeed correct.
Oh, ok. Idk, I saw $$$n / 2$$$ instead of $$$n$$$
oh sorry , stupid mistake
for C I'm getting different outputs on my system than the codeforces judge?
for C output is either "YES" or "NO", if you are getting different means there is something wrong in you solution.
in codeforces judge its outputting YES for cases where its outputting NO on my system and that is messing the ans up. U can view the code on ky latest submissions ig.
The $$$|n|$$$ is atmost $$$10^5$$$. Please do not use an integer or, a long to store it, as it will round off to undesired values, due to cyclic nature of these data types in C++. Use a string to take the input instead.
damn I mistook the range for the length of the number for the actual value of the number lol. You confused me a second time by typing |n| but yea I checked it, thx.
https://mirror.codeforces.com/contest/2050/submission/295396526 why is this wrong for problem C?
For C, will not be time complexity O(x*x) in the worst-case scenario where x is the length of the number? When the count of both 2s and 3s becomes equal to x/2. How is it getting accepted for a constraint of 10^5 on number length? Can you please clarify?
В решении задачи F сказано что m должно дедиться на разности соседних элементов. Это же ошибка, верно? Правильно будет "m должно делить". Там же разреженная таблица названа разряженной.
Where is the formal proof of correctness to the editorial solution of D?
I was hoping to see the cleanest solution and proof to the problem, now the editorial for this problem is very unhelpful.
Maximum digit can be 9. After each operation digit will decrease by 1, so we can do at most 9 operations. What is unclear?
Why isn't the editorial's solution clean?
My understanding of the editorial’s argument is as follows:
First, we aim to maximize the digit at index $$$0$$$, and it’s clear that we need to choose a digit from the first 10 indices. The goal is to find the maximum value of $$$S_i−(i−j)$$$, where $$$j$$$ is the index we are currently maximizing (starting with zero). In case of ties, we select the smallest $$$i$$$. We swap $$$i$$$ and $$$j$$$, and then repeat from the next index. This ensures that $$$s$$$ is maximized.
Is this reasoning incorrect, or is it just informal?
this is incorrect
The editorial solution is clean. However, I cannot see a potential clean proof.
Baiscally, the first step is defintiely correct, but the tie breaking is hard. You must show that among all future paths, you can select one to commit to, and it gives the best result (due to one reason or another).
This cannot be done without any statements about the future situations, what you can do/comparing future situations.
That said, the proof given by _Kee below is correct and clean enough. Thanks.
I think the hard part is how to handle tiebreaking.
Let's say we have an array $$$[a, b, 6, c, d, 9, \ldots]$$$ where $$$a < 4$$$, $$$b < 5$$$, $$$c < 7$$$ and $$$d < 8$$$, that is, $$$6$$$ and $$$9$$$ are the only digits that we can bring to the front. If we bring $$$6$$$ to the front, we get $$$A = [4, a, b, c, d, 9, \ldots]$$$. If we move $$$9$$$, we have $$$B = [4, a, b, 6, c, d, \ldots]$$$. So the problem here is: which is better?
Let's think about the selection of later digits. First of all, the parts $$$[a, b]$$$ and $$$[\ldots]$$$ are shared in the same place between $$$A$$$ and $$$B$$$, so they equally affect the final result. Next, regarding the part $$$[c, d]$$$, $$$A$$$ has that part earlier than $$$B$$$, so $$$A$$$ will give a better result. Finally, about the parts $$$[9]$$$ and $$$[6]$$$, if we move $$$9$$$ back to the digit where $$$6$$$ resides, it will become $$$7$$$, so $$$A$$$ will give a better result, too. Therefore, taking $$$A$$$ is always advantageous for us overall.
I think we can get a general proof out of this sketch, though it can be very tedious to do.
I have a question about how to arrive at the correct conclusion for a problem, for example, Problem B. That is, how to reach that solution—what was the clue in the problem that led to solving it in that way? I find it difficult to arrive at such a conclusion.
What I mean is, how should I study to improve this? Is it just about practicing problems, or does it require a more mathematical way of thinking? If anyone reads this, I would appreciate it if they could recommend a book or any resource. :(
Well, when I first came up with this problem, I thought about what will happen, if I will aim to make all the elements = 0, then I found out, that we can transfuse all the values to the first and the second elements, so after that we need to transfuse from these two elements back to othe elements and also now aim to make them all equal. Maybe it was a little bit messy idea, but it helped to solve this one out
For Problem C, can anyone tell why we need 8 repetition of 3 and not 3 repetition of 3, because after 3 instance of 3, pattern will repeat
6 % 9 = 6 12 % 9 = 3 18 % 9 = 0 24 % 9 = 6 ...
I am unable to understand the language of E and cant think of any approach i thought may be 3 loops as time is 2.5S but still dont understood minimum number of characters of C w.r.t to all strings we can make ? how can i know there can be many string can be formed. Anyone pls just point me in right direction. thanks
I feel that his code is totally messy, and this code could help you understand that. 295017055
A fact we know is that $$$\vert C \vert = \vert A \vert + \vert B \vert$$$, so for every character of $$$C$$$, you can know it must come from $$$A$$$ or $$$B$$$. Then we only need to use state $$$A$$$ and $$$B$$$ to calculate the answer.
Let $$$dp[i][j]$$$ denote the minimum times of transforming with used first $$$i$$$ characters of $$$A$$$ and first $$$j$$$ characters of $$$B$$$. If $$$C[i + j]$$$ could be $$$A[i]$$$ or $$$B[j]$$$, we don't need to transform. Otherwise, raise $$$1$$$ by transforming a letter.
So the main idea is to represent more states with fewer state measures. Hope this will help.
Who can help me why I had a WA2, problem E? https://mirror.codeforces.com/contest/2050/submission/295355937
why did you do dp[0][1] = 0;
I think that means that a[0] = c[0] in your code which is not true.
At the start we don't know what to choose so " i " needs to start from 0 and in each cell we need to choose between c[i+j] = a[i] and c[i+j] = b[j].
For problem D, I used
insert()anderase()functions to modify the string and it gave me TLE on testcase 7, later, I changed my solution to keep track of what characters from the original string are moved to their left using an array and kept adding such characters to an empty string. I think my current solution isO(n)but it got a TLE on testcase 8. Can someone tell why I got TLE? Submission linkYou have to stop checking next element if current element checked is 9 as it would be max value possible
like you did for mp[i]==1 continue
Also you don't need vector it can be done by manipulating string taken as an input only
My Code
We can use
__gnu_cxx::rope<char>instead ofstd::stringand it passes: 295422598. Rope is a non-standart string implementation based on the treap with implicit keys. Forstd::string,insert()anderase()work in $$$O(n)$$$ in the worst case, where $$$n$$$ is a length of string. For__gnu_cxx::rope<char>,insert()anderase()work in $$$O(\log n)$$$ in the worst case, where $$$n$$$ is a length of string.Damn, I didn't know about this. Thanks!
Can I please get some help in G? Wrong answer on test 2 — 295368314
My approach:
Navigate all the possible paths from the root node (0) to all the leaf nodes using DFS. For each such path, store the values of their degrees in an array $$$a$$$. If we consider some subarray [L, R] of $$$a$$$ (basically, a path) and remove all the nodes in this subarray then the number of components = $$$(\sum_{i=L}^R a_i) - 2 \cdot (R - L)$$$
The above equation can be rewritten in terms of prefix sum as:
$$$p[r + 1] - p[l] - 2 \cdot (r - l)$$$
$$$p[r + 1] - p[l] - 2 \cdot (r + 1) + 2l + 2$$$
$$$(p[r + 1] - 2 \cdot (r + 1)) - (p[l] - 2l) + 2$$$
Compute the array p using the equation above. Iterate from the left, maintain a current minimum variable, compute the value for $$$R + 1 = i$$$ and update result. The final answer will be maximum of such results in all possible paths from root node to leaf node.
Note: I am computing the prefix sum array in a different way. To get the sum of subarray [L, R] I would have to query $$$p[R + 1] - p[L]$$$
For C, will not be time complexity O(x*x) in the worst-case scenario where x is the length of the number? When the count of both 2s and 3s becomes equal to x/2. How is it getting accepted for a constraint of 10^5 on number length?
Can anyone clarify?
You don't have to consider nine or more $$$2$$$s or $$$3$$$s because the effect of those digits loop after the ninth one (because we calculate numbers modulo $$$9$$$). So you only need to consider $$$9^2 = 81$$$ cases at most.
Thanks a lot that clarifies my doubt.
I understood this approach, but I have tried another approach as well. Please look into it-
Here is the approach used in the else part of the code-
1. As I have count for both 2s and 3s, I will use these 2s and 3s to adjust the sum to check whether it becomes divisible by 9 at any point.
2. A single 2 will contribute 2 and a single 3 will contribute 6 to the initial sum.
3. So, I am basically starting from the minimum sum we can form using these available 2s and 3s. ~~~~~
void solve() {
string n; cin>>n; ll sum=0, twos=0, threes=0; for0(i,n.size()){ sum+=(n[i]-'0'); if(n[i] == '2') twos++; if(n[i] == '3') threes++; } if(sum%9==0) { cout<<"YES"<<endl; } else { ll count = twos*2 + threes*6; for(ll curr=2;curr<=count;curr+=2) { ll rem = sum+curr; if(rem%9!=0) continue; if(threes>0) { ll req = curr/6LL; curr -= (min(threes, req)*6LL); } ll twos_req = curr/2LL; if(twos_req<=twos) { cout<<"YES"<<endl; return; } } cout<<"NO"<<endl; }} ~~~~~
It is giving me TLE. Can you please check this? Your insights will be helpful.
Task G solution 295409653
Could you guys help me with question G? I got the wrong answer for test case 17. https://mirror.codeforces.com/contest/2050/submission/295318789
https://mirror.codeforces.com/contest/2050/submission/295436206
Your solution with a slight change.
Do let me know if you can't figure it out.
I got it now. Thanks a bunch!
2050C — Uninteresting Number he said" We can choose how many of the available digits 2and 3we will transform. Transforming more than 8 twos and more than 8 threes is pointless because remainders modulo 9 their transformation adds to the sum will repeat." in fact Transforming more than 8 twos and more than 3 threes is pointless
because 3*3=9,than their transformation adds to the sum will repeat.
Can anyone please tell me the recursive approach of solving problem E, as directly telling the dp approach doesn't takes the intuition under consideration and writing correct recurrence relation makes it very easy to optimise from memoisation to space optimisation.
Below is my incorrect and complex solution with too much of if and else condition.
Idea: Take three pointers i,j,k pointing to a,b,c respectively, if a[i] matches c[k] then increment i and k, if b[i] matches with c[k] then increment j and k, if none of them matches with c[k] then check by incrementing i first then k and vice versa and then increment j and k and viceversa
You're mistake is assuming that you take the one that matches c[k].You can take the one that doesn't match too.
Also what if both match c[k] you need to check both cases but you are only taking from " a " in your code
Hi, I have a doubt in a different approach of problem G (may be wrong)
This approach involves getting the diameter, removing the vertices along the diameter and then calculating the number of component (nc)
The final answer will be nc+2.
I wan't to know if it is a right approach and if it is possible to implement it in the time limit.
Thanks
i have a counter testcase image
your algorithm will return 1 component but the answer is 6 by removing the path from 1 to 5
Got it, thanks.
template contest.
In C, I am getting error in test case 3 in 401th case which is 9223372036854775807. It is showing that expected "NO" but got "YES" instead. But this number can be converted to 9's multiple if one of the 2 is changed. Can someone pls explain ?
nvm
Problem C:The only extra piece of proof that I wish should be added is that, after calculating thenum2s and num3sin the string. We can loopat most 9 times for each of twos, threes. As anything after this would be rudimentary as it would be divisible by 9 directly, so the loop should run fromi = [1 to min(num2, 10LL)), j = [1 to min(num3, 10LL)). As, someone might think why running loop(num2*num3)times per test case doesn't add up toTLE, this is cause we would be checking for atmost81 different states, which is of constant time complexity, and breaking out after it.Implementation: 296305754
can someone hack me please Problem G 296473359
I Solved It greedly by picking node lca(a,b) which called root which have max number of edges
After that I Picked greedly node a which the node that have max number of connected components with lca(a,b)
After that I pick node b which have max number of connected components with node b
That's also one of the correct solutions. In the editorial it is said, that this problem is kinda similar to finding the diameter of the tree, so your solution is just another way to find a diameter.
But for number B, why should we go more than 8 times? That's the main confusion for me.