Автор: daha.002
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
int ans = 0;
vector<int> v1(n);
for (int i = 0; i < n; i++) {
cin >> v1[i];
}
int o;
for (int j = 0; j < m; j++) {
cin >> o;
for (int i = 0; i < n; i++) {
if ((o + v1[i]) <= k) ans++;
}
}
cout << ans << "\n";
}
return 0;
}
Автор: Vladosiya
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
for i in range(n - 2):
if a[i] < 0:
print('NO')
return
op = a[i]
a[i] -= op
a[i + 1] -= 2 * op
a[i + 2] -= op
if a[-1] != 0 or a[-2] != 0:
print('NO')
else:
print('YES')
for _ in range(int(input())):
solve()
1941C - Рудольф и некрасивая строка
Автор: Mordvin13
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
long long t;
cin>>t;
for(long long c=0;c<t;c++){
long long n;
cin >> n;
string s;
cin >> s;
vector<long long> va;
for (string sul : {"mapie", "pie", "map"}) {
for (size_t pos = 0; (pos = s.find(sul, pos)) != string::npos;) {
s[pos + sul.length() / 2] = '?';
va.push_back(pos + sul.length() / 2);
}
}
cout << va.size() << endl;
}
return 0;
}
1941D - Рудольф и игра с мячом
Автор: Alexey_Parsh
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <set>
using namespace std;
int main()
{
int t; cin >> t;
while (t--) {
int n, m, a; cin >> n >> m >> a;
set <int> q[2];
int ix = 0;
q[ix].insert(a);
while (m--) {
int x; char ch; cin >> x >> ch;
while (!q[ix].empty()) {
int u = *(q[ix].begin());
q[ix].erase(u);
if (ch == '?' || ch == '0') {
q[ix ^ 1].insert((u + x - 1) % n + 1);
}
if (ch == '?' || ch == '1') {
q[ix ^ 1].insert((u - x - 1 + n) % n + 1);
}
}
ix ^= 1;
}
cout << q[ix].size() << '\n';
for (auto& x : q[ix]) {
cout << x << ' ';
}
cout << '\n';
}
return 0;
}
Автор: t0rtik
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
int t = 1;
cin >> t;
while (t--) {
int N, M, K, D;
cin >> N >> M >> K >> D;
vector<long long> a(N);
for (int i = 0; i < N; i++) {
vector<long long> dp(M, 1e9);
vector<int> v(M);
multiset<long long> mst = {1};
dp[0] = 1;
cin >> v[0];
for (int j = 1; j < M - 1; j++) {
cin >> v[j];
dp[j] = *mst.begin() + v[j] + 1;
if (j - D - 1 >= 0)
mst.erase(mst.find((dp[j - D - 1])));
mst.insert(dp[j]);
}
cin >> v.back();
dp.back() = 1 + *mst.begin();
a[i] = dp.back();
}
long long cur = 0;
for (int i = 0; i < K; i++)
cur += a[i];
long long mn = cur;
for (int i = K; i < N; i++) {
cur += a[i] - a[i - K];
mn = min(cur, mn);
}
cout << mn << endl;
}
return 0;
}
Автор: Vladosiya
Разбор
Tutorial is loading...
Решение
def solve():
n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
d = [int(x) for x in input().split()]
f = [int(x) for x in input().split()]
d.sort()
f.sort()
m1, m2 = 0, 0
ind = -1
for i in range(1, n):
e = a[i] - a[i - 1]
m2 = max(m2, e)
if m2 > m1:
m1, m2 = m2, m1
ind = i - 1
ans = m1
target = (a[ind] + a[ind + 1]) // 2
for model in d:
l, r = 0, k - 1
while r - l > 1:
mid = (r + l) // 2
if model + f[mid] <= target:
l = mid
else:
r = mid
ans = min(ans, max(m2, abs(model + f[l] - a[ind]), abs(model + f[l] - a[ind + 1])))
ans = min(ans, max(m2, abs(model + f[r] - a[ind]), abs(model + f[r] - a[ind + 1])))
print(ans)
for _ in range(int(input())):
solve()
Автор: natalina
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using LL = long long;
using ld = long double;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(10);
int _ = 0, __ = 1;
cin >> __;
for (int _ = 0; _ < __; ++_) {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n + 1);
map<int, int> clrs;
int idx = n + 1;
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
g[u].push_back({v, c});
g[v].push_back({u, c});
if (!clrs.count(c)) {
clrs[c] = idx;
idx++;
}
}
int s, t;
cin >> s >> t;
if (s == t)
{
cout << 0 << endl;
continue;
}
vector<set<int>> bg(n + clrs.size() + 3);
for (int i = 1; i <= n; ++i) {
for(auto &[to, c] : g[i])
{
int clr_v = clrs[c];
bg[i].insert(clr_v);
bg[clr_v].insert(i);
bg[to].insert(clr_v);
bg[clr_v].insert(to);
}
}
vector<int> used(bg.size());
vector<int> d(bg.size(), -1);
auto bfs = [&](int v)
{
queue<int> q;
q.push(v);
used[v] = 1;
d[v] = 0;
while (!q.empty())
{
auto from = q.front();
q.pop();
for (auto& to : bg[from])
{
if (!used[to])
{
q.push(to);
used[to] = 1;
d[to] = d[from] + 1;
}
}
}
};
bfs(s);
if (d[t] > 0) cout << d[t] / 2 << endl;
else cout << -1 << endl;
}
return 0;
}
I have seen many people code segment tree solutions for E (including tourist).
Can someone please explain how segment tree was used in this question? PS: I understood the solution explained here using dp.
For checking the minimum cost for the previous d cells and the sum of dp starting from the ith row and i+kth row I used a segtree as I had a pretty flexible template and it would pass the TL and be easy to code.
Ooooohhhhh I get it .... That's nice.... thanks for clarifiation.
It is easy to use segment tree just to calculate the minimum in the range where range is D elements before it using segment tree.
See my code maybe you can understand it easily :- Submission Link
I see... Understood how you have used seg tree here. Thanks very much.
It could be used to find minimum elementsin O(logn), however this is absolutely not necessary, I for exmaple got E with a deque.
if I want to propose problems to div.3 , how I can do ?
Alternate G solution:
Use each subway line as nodes and each station as edges. The trick is to process each station only once.
can you explain more.
I saw jiangly using the similar technique but can't understand why process each station only once?
Why not read his submission 250862298
https://codeforces.me/contest/1941/submission/320457861
why does this give tle for G?
I considered myself a pro at binary search and then problem F happended :/ Nevertheless learned something new. Thanks to the authors.
A similar problem link
Thanks bro!
I think this was a typical binary search ques, nothing new
Maybe, I was having a bad day, lol.
uhhhh.. binary search is not necessary for F, 2Pointers would also work.
But anyway, sorry for your loss.
why my state dijsktra to G problem is TLE? 250857953
Problem E (Rudolf and k bridges) Video Editorial : Youtube link -- Click here
E can be solved in O(n) using deque
E can be solved in O(n) using deque
Yes, I think it would be similar to maintaining the sliding window minimum over the dp array for each row, storing the minimum costs, and then finally finding minimum sum over $$$k$$$ consecutive costs for the answer.
fax
I really enjoyed solving problem D. I also think that B wasn't suitable for a div 3 B. C, B or maybe D should've been swapped with each other.
maybe, B had a trick that may have been harder to catch than C which is easier to figure out, but harder to implement. Though, this would be splitting hairs. D, though, in my opinion, is significantly harder than B to implement and earned its spot.
respect your opinion but personally, D was very easy.
I agree. D was easy, but generally Div3 A-D are easy for me. Div3 E/F are medium, and Div3G is hard. This contest fits this mold fairly well.
Problem C can also be solved with Aho Corasick Automaton. Build a $$$dp[n][m]$$$ where $$$n$$$ is the length of the string and $$$m$$$ is the number of states in the automaton, where $$$dp[i][j]$$$ tells us the minimum number of changes needed to be in state $$$j$$$ of the automaton (which represents some partial or complete matching with some pattern) considering the prefix $$$s[0...i]$$$. It's kinda overkill for this problem, but it's an interesting idea to know. Here's my submission 250707601.
For more details, refer to: CP Algorithms
Dislike if you are a ebantuza
Oh I solved prob E with just O(n*m) xD
I saw your code but can you explain it to me please ? iam still learning ,thx.
You can calculate the answer for one row in O(m) by using monotone deque (afterward, you can obviously find the minimum amongst all windows of size k in O(n)).
• Make a deque (storing the indices of the relevant elements amongst the last $$${d + 1}$$$ elements).
• Iterate over array. For $$${i^{th}}$$$ element, pop the back elements of the deque as long as they are greater than the current element. Then push the current element and pop the front element if it doesn't lie in the last $$${d + 1}$$$ elements.
• Now, the front element of the deque is the smallest element amongst the last $$${d + 1}$$$ elements. Update $$${dp_i}$$$.
yeah that's right
the technique I used in that code is to find the nearest element on the left of i (call it j) which a[j]<a[i]
and i learned it in cses book (it's free in web and it's pretty nice so i think you should learn in that book) — To Gordon
Same, O(m) to find max on bridge, O(n) for each bridge
My approach to G was as follows: make a new graph $$$G'$$$ where each node represents an edge in the original graph. There will be an edge between nodes corresponding to $$$(u,v)$$$ and $$$(v,w)$$$, with weight 0 if they have the same color and 1 otherwise. Then I'm doing 0-1 BFS from $$$(b,x)$$$ for all $$$x$$$ which are neighbors of $$$b$$$. Can someone please help me in optimizing the creation of this graph, because currently my method to generate this new graph is giving TLE.
Link to submission — Here
Just look few comments above. Edge graph can easily become $$$n^2$$$
Problem E can be solved using deque to calculate the minimum cost of each bridge in O(m), not O(mlogd); so the final complexity will be O(nm) My submission: https://codeforces.me/contest/1941/submission/250832314
ABC — average, div-4 level problems.
D — bad, why set a problem about naive simulation at this level? Also, editorial code has a $$$\log$$$ factor that is not reflected in the complexity analysis. It may not sound like a big deal to you, but beginners regularly get confused by such things.
E — bad, unusual distance definition. Also, the editorial solution has an extra $$$\log$$$ factor for no reason. Finding minimums/maximums in a sliding window is a well-known monotonic queue problem with equally short implementation. Div 3 rounds are supposed to be educational for beginners, please live up to the name.
F — bad, the unusual 2e9 limit was unnecessary. What are you, fishing for overflows? 1e8 was enough to TLE all convolution-based solutions, but you may as well have used 1e18 if you really wanted to avoid anything unintended. And once again, binary search is not necessary. Just sort both arrays and use two-pointers.
G — Good.
What is a convolution based solution ? Can you explain please ?
Consider a polynomial product $$$P(x) = (x^{d_1} + x^{d_2} + \ldots + x^{d_m}) (x^{f_1} + x^{f_2} + \ldots + x^{f_k})$$$. $$$[x^n]P$$$ is nonzero iff there exist $$$1 \le j \le m$$$ and $$$1 \le l \le k$$$ s.t. $$$d_j + f_l = n$$$.
G : lol
I'm interested in your suggestion to use two-pointers here. Could you explain how that works, when there are two arrays in play?
EDIT: Rather I am wondering a bit if we can prove that following the two pointers approach will give us the correct answer here.
250732405 When looking for $$$d_j + f_l$$$ as close to some
targetas possible, increase the sum if it's less and decrease otherwise (in code all numbers are multiplied by 2 to avoid floating-point math).How can we prove that this will actually give us the closest pair to target as possible? Using binary search it's pretty straight forward but I'm can't prove it for your two pointers approach.
Say both $$$d$$$ and $$$f$$$ are sorted in ascending order (wlog all numbers are unique).
If $$$d_j + f_l \lt x$$$ then $$$d_{j'} + f_l \lt d_j + f_l \lt x$$$ for all $$$j' \lt j$$$ and hence $$$|(d_{j'} + f_l) - x| \gt |(d_j + f_l) - x|$$$. Therefore, no pair $$$(j', l)$$$ with $$$j' \lt j$$$ is optimal. Similarly, no pair $$$(j, l')$$$ with $$$l' \lt l$$$ is optimal.
We already considered all pairs with $$$l' \gt l$$$, so the remaining candidates are pairs with $$$j' \gt j$$$. Hence we should increment $$$j$$$.
Similarly, we should decrement $$$l$$$ if $$$d_j + f_l \gt x$$$.
Alternatively, you may show that this two-pointers algorithm finds the same indices as your binary searches.
Thank you for the neat explanation! Took me some time to fully comprehend but yeah that makes a lot of sense!
Thanks, this was exactly was I was looking for!
Here's a practice problem for you and dekatin: LC 240. Search a 2D Matrix II
If sort is O(n*log(n)) and
m(2**16) is much bigger thank(2**8):Sort
mandk, then two pointers:Sort only
k, then binary search:Bold of you to assume that constant factors are the same.
std::{lower,upper}_boundis a straightforward algorithm that implements binary search exactly how you do. It also makes a lot of jumps in memory. Meanwhile,std::sortis quite heavily optimized, and two-pointers make no jumps whatsoever.Can someone explain me jiangly's solution for problem G ? What was the approach and what does dist[{e, 0}] mean?
The technique he used is 01-BFS
As we arrive at some unvisited color we first travel along it, and only then go to adjacent colors. 0 is the nice trick that means "line processed".
what is wrong in this code : https://codeforces.me/contest/1941/submission/250787705
Is my logic wrong or am I missing some edge cases. Please Help me . Thank you in advance!
In addition to considering breaking down the maximum difference $$$(a_{i+1}-a_i)$$$, the second biggest difference between $$$a$$$ elements should also be factored in. Consider the test case:
Also, when performing binary search (function
fin your code), the boolean that it should answer would be: is there $$$d \in D$$$, $$$f \in F$$$ such that $$$max\left(d+f-a_i \, ,\, a_{i+1}-\left(d+f\right)\right) \leq mid$$$.can you suggest a way to correct the code or is my approach completely. I tried by myself but I am not getting any idea. Thank you
I made modification to your code (251127599) and it runs correctly.
To elaborate on how to binary search on getting an optimal split between $$$[a_i, a_{i+1}]$$$: for $$$d$$$ and $$$f$$$ we would want to minimize $$$|(\frac{a_i+a_{i+1}}{2} - (d+f))|$$$. For a $$$mid$$$, we seek $$$d$$$ and $$$f$$$ such that $$$a_i + a_{i+1}-mid \leq 2 \cdot (d+f) \leq a_i + a_{i+1}+mid$$$ If
resis the minimum such $$$mid$$$ which satisfies, then the required imbalance between newly added problem and $$$a_i, a_{i+1}$$$ would be(a[i+1]-a[i]+res)/2In my opinion the TL on G was very constrained. I had to switch to deque to make it pass. Was an extra logn deliberately disallowed?
Can u please explain me the editorial elaborately.What are the new nodes created and how to make edges between them?
You've got the original nodes (station vertices) and the newly created color vertices (corresponding to all the distinct colored edges possible).
Now you draw an edge from the two groups (station to color and vice versa). An edge is drawn from station vertex a to color vertex b if and only if there is an edge color b incident to station vertex a.
Now you perform simple BFS and report the destination distance/2. Note: You consider the edge weight to be 1. Now think why we divided by 2. Also think how this is a bipartite graph.
can someone explain to me this line of code ? for (string sul : {"mapie", "pie", "map"})
i dont understand the code of the editorial why they alwayes make it hard to read for beginners?
It's a simple combination of range-based for loop and initializer lists. Both are available from C++11 and are very basic.
can someone help with problem E ? i get WA 251001023
just remove this line from your sliding window: int yans = ans; declare yans outside the loop.
refer to my version of this snippet, my win is your yans:
it gives TLE now. i did the dp in a different way but i think it should be fine ?? 251010002
Regarding problem F: It is relatively easy to see that we must decrease the maximal $$$ diff = a_{i}-a_{i-1} $$$, but my question is, what if there are more than 1 such $$$ j's $$$ where $$$ a_{j}-a_{j-1} = diff $$$. How do we choose which difference to take?
if there are more than 1 such that maxDif is same then answer is always maxDif i also had this same doubt during contest and now i feel extremely dumb its over for me
For $$$G$$$, I noticed that if a particular vertex has edges of colors $$$(c_1, c_2, c_3 ... c_k)$$$ then the sub-graphs of these colors can be reached by others of this set through at-most 1 different colored edge. So all we need to do is keep track of which "color" belongs which "clusters" (I call each such set a cluster), and vice versa. Then just expand the cloud of visited colors, till we reach a color which is connected to the destination.
As someone who has little math background and is algorithmically weak. I think it is quite intuitive and easier to come up with. Submission-->251004746
always so fun to read other people's code like
for(auto stuff : remove_assoc)thats crazy
Why is problem F labeled as two-pointers? Can't think of a solution that uses the two pointers technique.
Very real-life G. In reality the answer is seldom greater than 4，at least in Shanghai, 4 applies to a suboptimal route from Fudan to SJTU: source Fudan U, dest Dongchuan Rd, Fudan U -L18> Jiangpu Park -L8> People's Sqr -L1> Xinzhuang -L5> Dongchuan Rd. But you can choose Zizhu Hi-tech Zone(L15 terminal) as the destination if you want to goto SJTU and reduce the answer to 3.
In Tokyo this answer might be larger
I found an interesting solution to the problem G . I reformulate the graph G to G' as follows:
1) Each colour is a node in the graph G'.
2) Each node which is an endpoint of atleast 2 edges of different color is also inserted as a node in my graph. These nodes are special as they "link" 2 different colors. Now for the type (2) nodes I insert an edge E of the original graph , with one endpoint at the node itself and the other endpoint at the color of the edge of our considered type (2) node in the original graph . For example: for the given sample input in the question n = 6 m = 6
(Edge , colour)
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
In the reformed graph G': Nodes : (color1) , (color2), (color3) , (2) , (3) , (6) Edges : (6->color3) , (6->color2),(2->color1),(2->color2) , (3->color1),(3->color3) Note : 2,3,6 were added as they were part of edges of atleast two distinct colors ,and their edges were added as shown above.
The approach seems long in writing but intuitively its quite simple. Each connected component of a colour is treated here as a SUPER NODE and the other nodes were added to simplify how the colours are connected amongst themselves.
As a multisource BFS is sufficient to find number of minimum colors required to go from set of colors to any particular colors the answer can be found easily.
The link to my submission:251061492
Here for type(2) nodes i insert their negatives , so that they dont collide with the colors. Please excuse me for the messy code.
You can also add half weight in the newly formed graph and then apply dijiskstra
Can someone explain me the intuition behind problem G's editorial?
can anyone please help me (i have read editorial & i m still stuck) my approach is getting WA on testcase 2 https://codeforces.me/contest/1941/submission/251049209 thanks in advance
There are two problems here
if (b[i] > md) break;is wrong.consider this test
here is the answer is $$$98$$$, but your output is $$$99$$$. This happens because your code ignores any other value greater than the
mid. However a pair of number might work but their summation is greater thanmid, as in the above testmidvalue wrong. In your code,int md = a[l] + a[r]/2;.Consider, $$$l=3, r = 5$$$, here $$$mid = 4$$$ however your $$$md = 5$$$ which is wrong value
If anything isn't clear please don't hesitate to ask
you are such an amazing person, thank you so much (can thank you enough), you even checked why my answer is not working , thanks a ton mate
nothing to thank for my friend :3.
Have a great day and keep the good spirit :)
that was good bruh ok let's go
В проблеме C, что если нам нужно удалить подпоследовательность вместо подстроки?
Всм?
Можете ли вы разъяснить, что такое BCM
ВСМ = в каком смысле? Я не понял до конца ваш вопрос
D is nice
Can anyone pls help me with my solution .idk wht i am doing wrong https://codeforces.me/contest/1941/submission/251038815
https://codeforces.me/contest/1941/submission/250877308
I implemented this solution but i am getting wrong answer :( i even checked with the editorial its the same :(
Could anyone please help me with the Problem 'C'. I am getting a wrong answer for test 2.
[contest:https://codeforces.me/contest/1941/problem/C]
Please find my submission below: 251308448
Try:
The answer should be 0.
G просто скопипастили старую задачу с Информатикса. Вот это прикол, конечно
.
Nice problem E, got my first DP question correct.
Don't get terrified of G because it's the last problem, it can actually be solved in less than 30lines of code using simple bfs . it really confused me a while to check my solution because it's typically not that easy for the last question :)
Someone pls find the mistake in the code 336416497 for problem 1941F, tried everything