Codeforces round 933 Editorial

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

1941A - Rudolf and the Ticket

Tutorial

Solution

#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;
}

Rate the problem

1941B - Rudolf and 121

Author: Vladosiya

Tutorial

Solution

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()

Rate the problem

1941C - Rudolf and the Ugly String

Author: Mordvin13

Tutorial

Solution

#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;
}

Rate the problem

1941D - Rudolf and the Ball Game

Author: Alexey_Parsh

Tutorial

Solution

#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;
}

Rate the problem

1941E - Rudolf and k Bridges

Author: t0rtik

Tutorial

Solution

#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;
}

Rate the problem

1941F - Rudolf and Imbalance

Author: Vladosiya

Tutorial

Solution

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()

Rate the problem

1941G - Rudolf and Subway

Author: natalina

Tutorial

Solution

#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;
}

Rate the problem

I Have the same idea Like for a vertex , find the set of distinct colors it attached to What it means is , we can go from a color of this set to any other color of this set Now , But i do know how i proceed to implement it Let me check your submission

We need to decrese the max gap right (the one having max A[i] - A[i-1]) Now,we can just insert one element (What it would be!!) Obviously mid , mid = (A[i] + A[i-1]) / 2 So indirectly , Question transform to find (i,j) such that D[i] + F[j] is closest to mid This is two pointer right, (Sort D and F and then find it right)

#include<bits/stdc++.h> using namespace std; #define int long long int n,m; struct edge{ int to,w; }; vector<edge> e[400001]; int dis[400001]; struct node{ int id,dis; bool operator<(const node &A)const{ return dis>A.dis; } }; priority_queue<node> p; bool vis[400001]; void dij(int s){ memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[s]=0; p.push(node{s,dis[s]}); while(!p.empty()){ node u=p.top(); p.pop(); if(vis[u.id]){ continue; } vis[u.id]=true; for(edge i:e[u.id]){ if(dis[i.to]>dis[u.id]+i.w&&!vis[i.to]){ dis[i.to]=dis[u.id]+i.w; p.push(node{i.to,dis[i.to]}); } } } } int tot=0; signed main(){ ios::sync_with_stdio(false); int cases; cin>>cases; while(cases--){ cin>>n>>m; tot=n; map<int,int> mapping; for(int i=1;i<=m;++i){ int x,y,z; cin>>x>>y>>z; if(!mapping.count(z)){ mapping[z]=++tot; } e[x].push_back(edge{mapping[z],1}); e[y].push_back(edge{mapping[z],1}); e[mapping[z]].push_back(edge{x,0}); e[mapping[z]].push_back(edge{y,0}); } int b,eu; cin>>b>>eu; dij(b); cout<<dis[eu]<<endl; for(int i=0;i<=400000;++i){ e[i].clear(); } } }

Comments (109)

Write comment?

avengers2405

7 weeks ago, # |

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.

→ Reply

yeetholmes619

7 weeks ago, # ^ |

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.

ishat_jha

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

← Rev. 2 →

I see... Understood how you have used seg tree here. Thanks very much.

deydhananjoy5

can also be done using minheap.

madhavG

6 weeks ago, # ^ |

It could be used to find minimum elementsin O(logn), however this is absolutely not necessary, I for exmaple got E with a deque.

neatshit

is there a way to solve this problem using topdown dp ? I used brute force method checking for each d using top down approach , got TLE .

Rainbow____

+12

if I want to propose problems to div.3 , how I can do ?

omsincoconut

+24

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?

Tom66

Why not read his submission 250862298

How can this solution distinguish between vertices and colors? For example node 1 is connected to node 2 with edge of color 1. Edit : Ok so this is taking two graphs for that one is pointing to the adjecent color and another is pointing to the adjecent nodes.

AvaraKedavra

+13

I considered myself a pro at binary search and then problem F happended :/ Nevertheless learned something new. Thanks to the authors.

puspendra_09

A similar problem link

Thanks bro!

goku945

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.

tminh_hk20

why my state dijsktra to G problem is TLE? 250857953

bruce_x001

Problem E (Rudolf and k bridges) Video Editorial : Youtube link -- Click here

NH_

E can be solved in O(n) using deque

5hriom

+10

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.

capricornharsh

I did the same and I'm still getting an error in the second test case. Can anyone point out the mistake? 251067871

fax

can E be solved using topdown appraoch without getting TLE ?

Wasif_Shahzad

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.

joaozao

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

ArtemPod17

Dislike if you are a ebantuza

Yumesekai239

Oh I solved prob E with just O(n*m) xD

Gordon-Freeman

I saw your code but can you explain it to me please ? iam still learning ,thx.

Scyther_07

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)).

How to calculate the answer for a row in O(m)?

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

i will definitely give it a look , thanks for the help

thanks for explain it to me i understood it now :)

Same, O(m) to find max on bridge, O(n) for each bridge

bamogh

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

vstiff

Just look few comments above. Edge graph can easily become $$$n^2$$$

nguyenquocthao00

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.com/contest/1941/submission/250832314

nskybytskyi

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$$$.

Hassan_Fathi

G : lol

rHermes

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 target as possible, increase the sum if it's less and decrease otherwise (in code all numbers are multiplied by 2 to avoid floating-point math).

dekatin

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 < x$$$ then $$$d_{j'} + f_l < d_j + f_l < x$$$ for all $$$j' < j$$$ and hence $$$|(d_{j'} + f_l) - x| > |(d_j + f_l) - x|$$$. Therefore, no pair $$$(j', l)$$$ with $$$j' < j$$$ is optimal. Similarly, no pair $$$(j, l')$$$ with $$$l' < l$$$ is optimal.

We already considered all pairs with $$$l' > l$$$, so the remaining candidates are pairs with $$$j' > j$$$. Hence we should increment $$$j$$$.

Similarly, we should decrement $$$l$$$ if $$$d_j + f_l > 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

0x81

F — ... binary search is not necessary. Just sort

If sort is O(n*log(n)) and m (2**16) is much bigger than k (2**8):

Sort m and k, then two pointers:

2**16 * 16 + 2**8 * 8 + 2**16 + 2**8 = 2**20

Sort only k, then binary search:

2**8 * 8 + 2**16 * 8 = 2**19

Bold of you to assume that constant factors are the same. std::{lower,upper}_bound is a straightforward algorithm that implements binary search exactly how you do. It also makes a lot of jumps in memory. Meanwhile, std::sort is quite heavily optimized, and two-pointers make no jumps whatsoever.

I_Still_Love_haiender288

Slightly less casework required solution for C: count of "map" + count of "pie" — count of "mapie"
For D, state DP is better, has better time complexity, and far more braindead (literally obvious to everyone after enough practice?). May or may not require vector.resize() (note to self: CLEAR THE ENTIRE VECTOR BEFORE RESIZING YOU DUMB FUCK)
For E, multiset has horrendous constant factor (see: My -9 in that Div3 D several contests ago). Use a priority queue instead. To get the minimum "available" value, just throw every value that could no longer be used out of the pq

Can someone explain me jiangly's solution for problem G ? What was the approach and what does dist[{e, 0}] mean?

tonblan

-13

dist is a map which stores pair<int, int> as key, and int is value

So "cout << dist[{e, 0}];" means print the value of {e, 0} key

{e, 0} is a pair, e is first and 0 is second

Citypop

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".

Hisokax2

https://codeforces.com/contest/1941/submission/250749988 could someone help me figure out why this isn't working?

rishichowdhury711

what is wrong in this code : https://codeforces.com/contest/1941/submission/250787705

Is my logic wrong or am I missing some edge cases. Please Help me . Thank you in advance!

Sorlag

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 f in 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 res is 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)/2

MrSavageVS

In 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?

Mayank_Bhakat

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.

PRO_fessor_

-8

Problem D: chatGPT solved this question just by entering question statement in prompt

SuperMo

bro leave me happy it was the first time I solve till D :D

abdur_rahman_41

please anyone can explain the solution of peoblem of B ?

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?

_Kee

It's a simple combination of range-based for loop and initializer lists. Both are available from C++11 and are very basic.

mustafaeren

can someone help with problem E ? i get WA 251001023

shengyomin

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:

	win = 0; res = 0;
	f(i,0,k) win+=costs[i]; res = win;
	f(i,k,n) 
	    win += costs[i] - costs[i-k],
	    res = min(res, win);

it gives TLE now. i did the dp in a different way but i think it should be fine ?? 251010002

larush

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?

ALESTA

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

The5threich

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

Snapper_001

MaxWelll

6 weeks ago, # |

Why is problem F labeled as two-pointers? Can't think of a solution that uses the two pointers technique.

ramentaneja

I would love to contribute problems for Div 3. Is there a way I can do that?

tanishgoyal16

Ref B tutorial, What does the following mean

applying the operation to a more leftward element is either impossible or will make some elements less than zero

shiftForCaps

We are iterating from left to right. We'll apply the operation to i+1th element. Since op=a[i] and a[i]=-op, the elements to the left would already have been 0

So, it's implying to only move left to right. Got it, thanks!

helloworld404

Can someone please tell me what's wrong with this (https://codeforces.com/contest/1941/submission/251042147) approach for 'E'? Why do I get the wrong answer?

Fork512Hz

+14

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

Thelearned

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.

Verma_26

5 weeks ago, # ^ |

You can also add half weight in the newly formed graph and then apply dijiskstra

aayein__O_O

E problem was beautiful.

ritesh160193

https://codeforces.com/contest/1941/submission/250969634

This is my code for Problem E using memoization which is giving TLE on test case 6 (obviously because Time Complexity is O(n.m.d). I saw various optimised iterative DP approaches used by people with multiset/dequeue/priority queue, but cant find a memoized solution. Can anyone help me out with optimising my memoized approach. Thanks.

Aryannn09

can anyone please help me (i have read editorial & i m still stuck) my approach is getting WA on testcase 2 https://codeforces.com/contest/1941/submission/251049209 thanks in advance

__Waled

There are two problems here

the line 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 than mid, as in the above test

you are also getting the mid value 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 :)

Kolyanchick

D is nice

Rachuu_uwu

Can anyone pls help me with my solution .idk wht i am doing wrong https://codeforces.com/contest/1941/submission/251038815

https://codeforces.com/contest/1941/submission/250877308

I implemented this solution but i am getting wrong answer :( i even checked with the editorial its the same :(

variety-jones

Take a look at Ticket 17418 from CF Stress for a counter example.

akshaypatade

Could anyone please help me with the Problem 'C'. I am getting a wrong answer for test 2.

[contest:https://codeforces.com/contest/1941/problem/C]

Please find my submission below: 251308448

Try:

1
3
amp

The answer should be 0.

Ohh, makes sense. I will have a look into it. Thank you

heyguysitsme

can g be solved by this approach. Basically we will visit the vertices in a bfs fashion firstly at a distance of 1(this includes all the vertices that are connected by the same color of subway line to src). Then we will take all those visited vertices at a distance of 1 and visit the next vertices. Also unlike the trivial bfs we won't mark the vertex visited the 1st time we reach it but only when all the edges incident on the vertex are traversed.

ploplo

This question is pretty similar to https://leetcode.com/problems/bus-routes/description/, one of the most asked questions in Google.

HaneDaniko

help about c++17 in problem G at test 3's wa

i_love_Ruchi_Singh

5 weeks ago, # |

Can any one help me please ,why i am getting WA in F
(https://codeforces.com/contest/1941/submission/253003605)

mohdayat

9 days ago, # |

In problem D TCx is written n*m however at worst case there can be n elements inserted in set so the complexity should be something like O(m*nlogn) (bcoz insertion in set is log(n)).I am not getting it plz somebody explain.

ArafHasan

8 days ago, # |

← Rev. 5 →

Have anyone managed to complete D using recursion? I tried but I am getting TLE.

Here is my submission: https://codeforces.com/contest/1941/submission/257239620.

I dont know any other languages as efficiently as python so I tried using python. But IDK how to optimize it further. Can someone help me?

natalina's blog