### hugopm's blog

By hugopm, 2 years ago,

• +255

 » 2 years ago, # |   +86 Thanks for really fast + detailed editorial :D problem E and F are really interesting too :D
 » 2 years ago, # |   0 Thanks to whoever made this,really helped me out a lot
 » 2 years ago, # |   +3 Thanks
 » 2 years ago, # | ← Rev. 4 →   +35 D can be solved in O(V+E). We do this by first going in increasing order of node index from i...N. In the dfs we query for the node with greatest index that we can visit from a vertex v. This is denoted by f(v). We also color the nodes we visit with i representing their connected component. Then, we essentially have the interval (i, f(i)). Because we iterate in order of node index, it is guaranteed to be the earliest disjoint interval.Now, we iterate through all the nodes j in the interval, and if j is not colored the same as i, we add an edge between them. Dfs on j, and extend the right side of the interval to max(f(i), f(j)). We do this because if we have f(j) > f(i), there might be nodes between f(i) and f(j) that must be connected to i.Once we are done iterating through the interval, it is guaranteed that all nodes to the right are disjoint from all to the left, so we simply set the value of i to f(i) (this makes the next iteration start from f(i)+1).code
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 There can be simpler code for D .....first iterate from 1 to n and in the loop find the maximum of that component using dfs and if some node is unvisited and it is less than maximum just increase your ans ...its as simple as that ...go through the code for clarification 65209450
•  » » » 18 months ago, # ^ |   0 please can you explain in some detail i am not able to understand means why are we calculating max...please can you clarify once more ??
•  » » » » 18 months ago, # ^ | ← Rev. 3 →   +3 we want to 'resolve' all triplets such that there is an edge from L to R and there is no edge from L to M such that L < M < R. since its an undirected graph, every vertex in a component is reachable from each other. this means 'no such triplet can exist whithin a component'. in given testcase components are [1,2,5,7] [3,4,6,8] [9] [10] [11,12] [13] [14] paths which should be there but dont exist 'after visiting first component' => 1-3 1-4 1-6 2-3 2-4 2-6 5-6 when dfs from 1 is over, we see for 3 that already a vertex greater than 3 could be visited by a vertex smaller than it. so we add an edge. adding an edge between any two components makes them into one component. Now see point three. So adding an edge between [1,2,5,7] and [3,4,6,8] removes all issues in point 5. now the claim is for every i you will have to add only one edge. why? suppose two vertices x and y exist such that x < y < i. now, if x could reach a point > i and y too could reach a point > i. Then, we would already have added an edge between y and x. so, x and y are already one component and adding one edge will be sufficient for i.
•  » » » » » 18 months ago, # ^ |   0 thanks shameek,i have solved it, efforts are appreciated
 » 2 years ago, # |   +4 Can someone explain C solution? I'm not sure if I got what is written in the editorial
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 So lets first sort sweets by sugar concentration. — So because of this complexity of program is $O(n$log$n)$Lets think of some number of sweets $k <= m$ therefore all sweets will be eaten on same day — day 1 so sugar penalty is just the sum of them. We want to choose first $k$ sweets after sort because they have lowest $a_i$ so their sum is the smallest (simple greedy)To calculate sum of elements in $O(1)$ we use cumulative sum — we hold sum of first $k-1$ elements and when we come on $k$ we add $k^{th}$ element to it. Now lets think about $k > m$ — some of the sweets will be eaten on day 2, 3, ... So its optimal to sweets with lowest sugar to be eaten as late as possible. Lets remember what happened with $k-m$ sweets — we have some solution using $k-m$ smallest sugar concentration sweets. From then till now we added m sweets — we know they have $a_i$ at least as big as $a_i$ used for $k-m$. So lets eat that m sweets on first day. Now we need to eat $k-m$ sweets starting from day 2. But multiplier is now bigger by one — so we need to solve what is $2 \cdot a_{k-m} + ... x \cdot a_1$ but we know that answer for $k-m$ sweets is $1 \cdot a_{k-m} + ... (x-1)\cdot a_1$ Therefore answer for that part is sum of $a_i$ ($i$ in range $[1$, $k-m]$) + answer for $k-m$And now dont forget about first part — answer is sum of $a_i$ ($i$ in range $(k-m$, $k]$)So — answer is sum of those two parts — sum of numbers $a_i$ ($i$ in range $[1$, $k]$) + answer for $k-m$Sum is still hold as cumulative so that part is $O(1)$ and we can get answer for $k-m$ if we iterated from 1 to $n$ in $O(1)$ — Overall complexity of this part is $O(n)$(my solution — 65182757)
•  » » » 2 years ago, # ^ |   +4 As you have used sort stl .That's why Overall complexity will be O(nlogn)
•  » » » » 2 years ago, # ^ |   0 You are right — thanks! I'll correct it! :)
•  » » » 2 years ago, # ^ |   +4 Great explanation, thanks!
•  » » » 16 months ago, # ^ |   0 Can you more elaborately explain this part Now we need to eat k−m sweets starting from day 2. But multiplier is now bigger by one — so we need to solve what is 2⋅ak−m+...x⋅a1 but we know that answer for k−m sweets is 1⋅ak−m+...(x−1)⋅a1 Therefore answer for that part is sum of ai (i in range [1, k−m]) + answer for k−m And now dont forget about first part — answer is sum of ai (i in range (k−m, k] ) So — answer is sum of those two parts — sum of numbers ai (i in range [1, k]) + answer for k−m Sum is still hold as cumulative so that part is O(1) and we can get answer for k−m if we iterated from 1 to n in O(1) — Overall complexity of this part is O(n)
•  » » » » 8 months ago, # ^ |   0 I understand the relationship between f(k) and f(k-m).The hard part is understanding how they came up with that.Basically f(k) = f(k-m) + sum[1...k]here sum[1...k] indicates sum of all elements in range [1,k]so, f(k) = f(k-m) + sum[1,k-m] + sum[k-m+1,k]This has 2 parts to it day1 + rest-of-the-days as explained below.f(k-m) + sum[1,k-m] : basically this takes f(k-m) and increases its co-efficients(day numbers) by 1. ie, day1 in f(k-1) becomes day2 in f(k) day2 in f(k-m) becomes day 3 and so on... and this gives value required from day2 onwards. sum[k-m+1,k] : which gives value required for day1.the sum of above 2 values gives f(k)
 » 2 years ago, # |   0 D can be solved in $O(n+m)$(my solution for reference — 65186179)So let's construct graph using vectors to represent neighborhood (if a is in vector c[b] then it exists link from b to a and vice versa) We are also using bool array $v[]$ to represent if you visited some node.Let $maks$ be maximum index of node we visited so far — initially is 0.It is enough to check for every node from 1 to $n$ whether we visited it (thats why we have v[]) if answer is yes, then continue to next one if the answer is no if its index is smaller then current maks then we need to add edge to connect maks to current index because maks was connected to some node i whose index is smaller then current index start recursive dfs (in my implementation, bfs or any other algorithm that finds all nodes of segment is ok) to find all nodes connected to node with current index. We keep track of maks while doing this — maks=max(maks, index of node currently being processed with dfs) $O(n)$ to check for every v[i] if is it visited and $O(m)$ to do bfs/dfs -> $O(n+m)$
 » 2 years ago, # |   +18 Intended solution for D was in fact already $O(n + m)$. I was sorting an already sorted array...
 » 2 years ago, # |   0 I have wrong answer on test 13 on problem B, can you please check my submission to see what is wrong with it ?
•  » » 2 years ago, # ^ |   +3 Please read this comment
•  » » » 2 years ago, # ^ |   0 Thank you hugopm! I got it now.
»
2 years ago, # |
-15

This is my code for SWEETS EATING PROBLEM :

# include<bits/stdc++.h>

using namespace std;

# define ll long long

int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,m; cin>>n>>m;

ll arr[100005];

for(ll i=0;i<n;++i){
cin>>arr[i];
}
sort(arr,arr+n);
for(ll i=1;i<n;++i)
arr[i] = arr[i-1] + arr[i];

ll ans[100005];

for(ll i=0;i<n;++i){
if(i<m)
ans[i] = arr[i];
if(i>=m)
ans[i] = arr[i] + ans[i-m];
}
for(ll i=0;i<n;++i){
cout<<ans[i]<<" ";
}

return 0;

}

its giving TLE . Can anyone point out why?

•  » » 2 years ago, # ^ |   +15 Bro array size will be 200000
 » 2 years ago, # |   0 Any source code by editorial on a problem E?
•  » » 2 years ago, # ^ |   +3 Added!
•  » » » 2 years ago, # ^ |   0 Thanks)
•  » » » 17 months ago, # ^ |   0 https://codeforces.com/contest/1253/submission/89391199Can you please tell top-down dp solution from this bottom-up recursive approach.As it is hard for me to do it for 1-d dp array.
 » 2 years ago, # |   +8 A really good contest, thanks
 » 2 years ago, # | ← Rev. 2 →   0 For problem F is there coutertest for not just replacing edge weight but also replacing ends to nearest centrals?I'm wondering because, there can be ambiguity in terms of centrals, because distance to two or more centrals can be same. So, is it always working or there is countertest?
•  » » 2 years ago, # ^ | ← Rev. 7 →   0 I'm pretty sure it works, due to key insights (going to nearest central is always possible and will not change set of reachable nodes).More precise proof: note $t_u$ the nearest central to node $u$ (choose any central if there are many closest ones). Add your supplementary edges into the original graph (keeping old ones) and edges $(u \leftrightarrow t_u)$ with weight $d_u$, they will obviously not change answer.Then, take any optimal path from $a_i$ to $b_i$. As long as there is a "bad" edge $u \rightarrow v$ in the path, with ($u > k$ and $t_u \neq v$) or ($v > k$ and $t_v \neq u$), replace $u \rightarrow v$ by $u \rightarrow t_u \rightarrow t_v \rightarrow v$ (it can't be heavier). Each time, number of such edges decrease by one, so it will reach zero. Delete useless $t_u \rightarrow u \rightarrow t_u$ parts : there will be no more non-central nodes. The resulting path will be in your second graph, and will require at most the same capacity.
 » 2 years ago, # |   0 For problem F — Cheap Robot i have one alternative approach 65217904 that not use the observation "replace the weight of each edge $(u,v,w)$ by $w′=du+dv+w$". Run Dijkstra from node 1, when reach other node $u \in [1, k]$ not already seen connect $u$ with the origin of the minimum path that reach $u$ with cost $dist[u]$, set $dist[u] = 0$ and push $u$ again on the queue and continue running Dijkstra. Basically i am doing Prim over the nodes $[1, k]$, so i have a Spanning Tree of the nodes $[1, k]$ on which for every pair of nodes $u, v \in [1, k]$ in the original graph the maximum traveled distance (without recharge) between the nodes $u, v$ is minimized, so the answer for every query is the maximum on the unique path between $u$ and $v$. The most interesting part is the complexity of the modified Dijkstra, I'm 99% sure that the complexity still $O(E log E)$
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Looks like you can't pass test with $q = 1$https://codeforces.com/contest/1253/hacks/598268/testThis test was given in problem 196E - Opening Portals from our round.hugopm please add this test with $q = 300000$ and its reversed / shuffled versions
•  » » » 2 years ago, # ^ |   0 Test added, thanks a lot!
 » 2 years ago, # |   0 In problem F solution 1 can be extended to online queries with persistent DSU
 » 2 years ago, # |   0 I don't understand why I got TLE for D... Can anyone help? 65226875 I basically followed the solution above and implemented myself.
•  » » 2 years ago, # ^ |   +3 I figured it out myself, thanks everyone
 » 2 years ago, # |   +6 I was solving E and came up with the similar solution. but my solution was wrong because I did not take default Transition( dp[x] := (m−x).) after a while I still could not understand the use of the default transition and what it means."If i was the last interval used, we don't care because the default transition will take care of this case."I believe that this sentence is the key but still confused. Can anyone describe it more detailed ? Any help will be appreciated.(Also sorry for not using Latex, I haven't learn it well)
•  » » 2 years ago, # ^ |   0 Oh I get itconsider there is an antenna at i+1 with initial scope 0 and when we are at i and calculating the new value what it will be we extend it by one and get (1 + dp[ i+3 ]) as the cost of choosing it i, i+1, i+2, i+3, i+4...m ,_,____.............m (___ means being covered while ... means not) however if the best choice is to extend it to the end, we cannot get the correct value without setting dp[ i+3 ] to m — (i+3) + 1 when we are setting default dp[x] := (m-x) it is actually the cost of extending the antenna to the end.
•  » » » 2 years ago, # ^ |   0 Do you mean antenna at (i+2) in first line??
 » 2 years ago, # |   0 In problem D : A small change in DSU find algorithm changes TLE to AC. TLEint find(int node){ return par[node]==node ? par[node] = node : find(par[node]); } ACint find(int node){ return par[node]==node ? node : par[node] = find(par[node]); }Submissions : 65229651 65229747Could someone point out why this is happening?
•  » » 2 years ago, # ^ |   0 The first one is equivalent to return par[node]==node ? node : find(par[node]); This is just normal unionfind (O(logN) with union by rank/size, or O(N) without)The second one is unionfind with path compression ((1) with union by rank/size, or O(logn) without)
•  » » 2 years ago, # ^ |   0 I think the first code may be run in this way: if (par[node] == node) { return par[node] = node; } else { return find(par[node]); } So you can see every time you call find(u) for any node u, it will cost O(distance to the root) time, in the worst case the distance to the root could be n (think about a chain), so your first code caused TLE.And for your second code, the biggest difference with the first code is that whenever you called find(u) for any node u, the every per[node], node between u and root, will be changed to the root.For example, if par[1]=1, per[2]=1, per[3]=2, per[4]=3, we call find(4), and after the call par[1]=1, par[2]=1, par[3]=1, par[4]=1.So your second code got AC.
•  » » 2 years ago, # ^ |   0 Oh my bad, I was thinking that par[node] would be updated to either one the returned values in the first case. Thanks, both.
•  » » 2 years ago, # ^ |   +8 if/else exist for a reason...
 » 2 years ago, # |   +11 It's a really interesting contest, thanks to all the contributors :D
 » 2 years ago, # |   0 Problem p1253B — Silly Mistake, please help does not able to find what is wrong in code my submission
•  » » 2 years ago, # ^ |   0 It seems you have a "Silly Mistake" in your code
•  » » » 2 years ago, # ^ |   0 Any suggestions?
 » 2 years ago, # |   +1 In tutorial E: "If position x+1 is initially covered, dpx:=dpx+1" , I wonder if it's wrong, maybe it should be "If position x is initially covered, dpx:=dpx+1".
•  » » 2 years ago, # ^ |   0 No. The state $dp_x$ suppose that the position $x$ is covered.
 » 2 years ago, # | ← Rev. 4 →   0 what should be the question A ans on this input?1210 2015 25
•  » » 2 years ago, # ^ |   0 It should be "Yes" as you can choose l=0, r=1, k=5.
•  » » » 2 years ago, # ^ |   0 Thanks
 » 2 years ago, # | ← Rev. 2 →   0 .
•  » » 2 years ago, # ^ |   0 I think it's very similar to my own implementation (but in reverse order), which is available in the editorial. You should look at it.
 » 2 years ago, # |   0 I have a question about E's editorial — why does this "If position x+1 is initially covered, dp[x]=dp[x+1]" work ? How are we sure that if x+1 is covered x is ready too without the need to add 1 coin for the distance from x to x+1?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 If position x is initially covered, dp[x]=dp[x+1],i think it's right after the change and i have passed it.
•  » » » 2 years ago, # ^ |   0 Ye I know it should be right , I was just asking why is it like that
•  » » » » 2 years ago, # ^ |   0 I mean you should replace x+1 with x to understand...if(cover(x)dp[x]=dp[x+1];
•  » » » » » 2 years ago, # ^ |   0 Aham I think I get it , thanks a ton
 » 2 years ago, # |   0 Can anyone explain the edoitorial of D in some other way???
•  » » 2 years ago, # ^ |   0 First of all, the problem is about undirected graph. For them there are following properties: $u$ is reachable from $u$ if $v$ is reachable from $v$, then $u$ is reachable from $v$ if $v$ is reachable from $u$ and $w$ is reachable from $v$ then $w$ is reachable from $u$ In other words, for undirected graph reachability is Equivalence relation (google if you don't know what it is). So, for each node $v$ you can define Equivalence class $C(v)$ — set of all nodes within the same Equivalence class of $v$. Why do I name it by $C(v)$? Because for undirected graph this Equivalence classes called components. Thing that I wan't to stress out: components of undirected graph is equivalence classes of reachability relation. So, if $v$ is reachable from $u$ then $C(u) = C(v)$ and $u \in C(u)$ and $v \in C(u) = C(v)$.Now, from the statement: For every triple of integers $(l,m,r)$ such that $1\leq l< m < r\leq n$, if there exists a path going from node $l$ to node $r$, then there exists a path going from node $l$ to node $m$. Obvious key observation: pick any node $v$, find minimum node $l_v = \min \{u : u \in C(v)\}$ and maximum node $r_v = \max \{u : u \in C(v)\}$ that is reachable from node $v$, then for each $m$ that is $l_v < m < r_v$ should be reachable from $l$. This is so obvious, so it's not described in details. We're not allowed to delete edges, the only thing we can do is to add edges. When we add edge $(u, v)$ within the same component then $l_u = l_v, r_u = r_v, C(u) = C(v)$ and reachability doesn't change, so nothing change and we just waste edge, we should not do that. So we should add edges $(u, v)$ from different components $C(u) \neq C(v)$. When we do that, components merge. New component is $C(u) \cup C(v)$ — union of sets. That's why we need DSU (Disjoint set union). New $l'_v = \min (l_u, r_v),\;r'_v = \max(r_u, r_v)$. The problem is: new $l'_v$ can be lower than previous. We wan't to avoid that.From now on should be obvious that answer is set of segments $[l_v, r_v]$, so we can order them by increasing $l$. Idea is to make components in exact this order: from lowest $l_v$ to highest. It's just loop by $v$ in increasing order. Then $l_v = v$. Previous components is complete, so $l_v$ will never change, the only thing that will change is $r_v$. So we run loop by $m$ from fixed $l_v = v$ to changing $r_v$ until we reach $r_v$. And what we do in the loop? We always join $m$ to $v$ if they are in different components. Important to note: when $m$ reach $r_v$, component is complete, so we don't need to check $v \in [l_v, r_v]$ and we should skip all $v$ within that range and continue from $r_v + 1$. Otherwise we'll get $O(n^2)$ solution.
•  » » » 2 years ago, # ^ |   0 Now i got it bro, Thanks a lot for so much effort.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +5 Another way to use DSU for this problem: Modify your DSU to also keep track of the maximum-indexed vertex in each component. This can be done by keeping a new array $max$ alongside $parent$ / $rank$ / $size$ or whatever you use in your DSU implementation, then changing the $join$ function to update it as well. Add a function $max(v)$ (internally max[root(v)]) for easy retrieval of the maximum-indexed vertex connected to $v$.Now read the graph as input and connect components as usual. Then iterate through the vertices from $1$ to $n - 1$. If $max(v) > v + 1$ and $v$ is not connected to $v + 1$, connect $v$ to $v+1$ (making sure to update the DSU online) and increment the answer.Sample: 65261938
 » 2 years ago, # |   +4 In problem E,why are we not considering the transition for x>ri?
•  » » 23 months ago, # ^ |   0 if [x, m] has been covered, extending this interval [x, m] towards ri is not worse than extending the antenna i from ri to x.
 » 2 years ago, # |   0 What is "B" in editorial of D ??
 » 2 years ago, # | ← Rev. 2 →   0 Can someone explain why this idea doesn't work for problem D?: -sort all the antennas by position (part1) -eliminate all antennas that have all their signal area overridden by another antenna(but only one), so that if antenna a and antenna b has xa x+s just ignore it(since the entirety of this antenna is covered) -else if bord>=x-s and bord<=x+s make bord x+s+1(since you know for sure that all positions between bord and x+s are covered) -if the above cases are false then bord #define x first #define s second typedef long long ll; ll n, m, i, j, l, bord=1, sol; std::pair cin[85], list[85]; int main() { scanf("%lld%lld", &n, &m); for(i=1; i<=n; ++i) scanf("%lld%lld", &cin[i].x, &cin[i].s); ///part 1 std::sort(cin+1, cin+n+1); ///part 2 for(i=1; i<=n; ++i){ ///if the present antenna is overriden by the closest antenna ignore the present antenna if(l && cin[i].x+cin[i].s<=list[l].x+list[l].s) continue; ///while the present antenna overrides the closest antenna eliminate the closest antenna while(l && list[l].x-list[l].s>=cin[i].x-cin[i].s) --l; list[++l]=cin[i]; } ///part 3 if(m>list[l].x+list[l].s){ sol+=(m-(list[l].x+list[l].s)); list[l].s+=(m-(list[l].x+list[l].s)); while(l-1 && list[l].x-list[l].s<=list[l-1].x-list[l-1].s){ list[l-1]=list[l]; --l; } } ///part 4 for(i=1; i<=l; ++i){ if(bord>list[i].x+list[i].s) continue; else if(bord>=list[i].x-list[i].s) bord=list[i].x+list[i].s+1; else{ sol+=std::max(0LL, (list[i].x-list[i].s-bord)); list[i].s=list[i].x-bord; bord=list[i].x+list[i].s+1; } } printf("%lld", sol); return 0; }
•  » » 2 years ago, # ^ |   0 Part 3 seems wrong. Consider the following test: 2 50 25 0 40 1 Best choice is to increase the scope of the middle antenna by 25. You should not increase the scope of the last antenna.
 » 2 years ago, # |   0 I have use Disjoint Data Structure in problem D. In union function i did not change the value of size after joining it. And got wrong answer. But got accepted when i change the value of size[parent_a] or size[parent_b] to 0 or 1 or any int. why it happen?Accepted 65228886 changing value of size[root] to 0 after joining in join()Accepted 65247284 changing value of size[root] to 1 after joining in join()Wrong ans 65228524
•  » » 2 years ago, # ^ |   +9 In your DSU join function, you should return if parent_a = parent_b (already connected nodes).Otherwise, you will be joining a node to itself, and it will artificially multiply the size of the component by 2, and doing this like 65 times will be enough to overflow with long long.
•  » » » 2 years ago, # ^ |   0 Thanks hugopm
 » 2 years ago, # |   0 i have written exactly the same code in both the languages but c++ code is giving wrong answer on test 2 while python code is giving correct answer and is accepted. could anyone explain me why this is happening, if both the logic are same only syntax change is there. Your code here... C++ #include using namespace std; void func() { int n, x; cin >> n; vector a(n); vector d(n); set s; bool cond = false; for(int i = 0; i < n; ++i) { cin >> x; a[i] = x; } for(int i = 0; i < n; ++i) { cin >> x; d[i] = (x - a[i]); if(d[i] > 0) s.insert(d[i]); if(d[i] < 0) { cond = true; break; } } if(s.size() > 1 || cond == true) cout << "NO\n"; else { for(int i = 1; i < n-1; ++i) { if(d[i] == 0) { if(d[i-1] > 0 && d[i+1] > 0) { cond = true; break; } } } if(cond == true) cout << "NO\n"; else cout << "YES\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; while(t--) { func(); } return 0; } Your code here... Python def func(): n = int(input()) a = list(map(int,input().split())) b = list(map(int,input().split())) d = [] s = set() cond = False for i in range(n): x = b[i] - a[i] d.append(x) if x > 0: s.add(x) if x < 0: cond = True break if len(s) > 1 or cond == True: print("NO") else: for i in range(1,n-1): if d[i] == 0: if d[i-1] > 0 and d[i+1] > 0: cond = True break if cond == True: print("NO") else: print("YES") t = int(input()) for i in range(t): func()
•  » » 2 years ago, # ^ |   0 In your C++ code, you're doing a "break" without having completly read the input of the current testcase. You will not start at the right place when you'll be reading the next testcase.
•  » » » 2 years ago, # ^ |   0 Thanks a lot you saved me✌
 » 2 years ago, # |   0 Can some one explain why the same code could run different result with different compiler? 65170371 here's one input: 1 6 3 7 1 4 1 2 3 7 3 6 3 4the correct answer should be Yes. but if you use custom invocation, the result is: Yes (c++11) NO (c++14)
•  » » 2 years ago, # ^ |   +1 Local variables pos and pos2 are uninitialized, their default value is undefined and may depend on the compiler and the environment (it's not always 0 for local variables).
•  » » » 2 years ago, # ^ |   0 got it, thank you sir.
 » 2 years ago, # |   0 What's wrong with problem A's 9th test? I can't my mistake. Here is my submission 65207960 Can anyone help me with this?
•  » » 2 years ago, # ^ |   0 Your solution fails on that test 1 3 1 2 3 1 2 3 Note that you should do at most one operation, so if arrays are initially equal, the answer is YES.
 » 2 years ago, # |   +15 I think Problem E can be solved with shortest path algorithms.It's necessary to add some edges with 0 weight.See my code
•  » » 2 years ago, # ^ |   +8 Wow, that's actually pretty insane.
•  » » 2 years ago, # ^ |   0 could you explain your approach?
 » 2 years ago, # |   0 Thanks for the round :D! Kudos it was very interesting
 » 2 years ago, # |   0 For the problem F, why should we go to the nearest central, then go back to u, if x≥du?if we just from another central(the distense may be longer then du)gone to the u,so go to the nearest central then back to u makes the x≤c−du.But if not, may be the x>c−du and x≥du, so why we must go to the nearest cnetarl and go back?
•  » » 2 years ago, # ^ |   0 oh， i got it! the source is a central.
 » 2 years ago, # |   0 For problem A, can't we used a set which contains only '0's and elements(distance b/w b[i] — a[i]). And then if the size of the set is 2 then, we print "yes" otherwise "no"?
•  » » 2 years ago, # ^ |   0 k > 0
•  » » 2 years ago, # ^ |   0 A: 2 1 2B: 1 1 1This test involves the two problems your solution has
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 What problem this test case would have? Won't there be only two elements in the set (i.e 0 and 1) as b[i] — a[i] will yield on only 1 and 0 and they will be pushed back into the set. Correct me if I am wrong. thanks in advance :)
•  » » » » 2 years ago, # ^ |   0 No. b[0]-a[0] is -1.And remember that you can apply the update at most once, so checking if the set is of size two is not enough.A: 1 1 1B: 2 1 2Here your set will have size two but you need two updates with k=1
•  » » » » » 2 years ago, # ^ |   0 Ohh. I get it now! Thankyou very much :) I misinterpreted the question
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Hey! for test case A: 3 3 3 3 3 and B: 3 3 6 6 6, should not the answer be yes? As for l = 3, r = 5 , we can add add k = 3 which makes a and b equal
 » 2 years ago, # |   0 hey, i need a help in silly mistake. i am getting wrong answer but i dont know the reason. i have simply implemented the code. can anyone please help me to find out my error.Problem : Silly MistakeMy Solution
 » 2 years ago, # |   0 Solution for F is so beautiful...
 » 2 years ago, # |   0 Can anyone explain me token part in solution part of problem F?? Thanks..
 » 2 years ago, # | ← Rev. 3 →   0 Hey guys, does anyone know why my solution 1253F — Cheap Robot TLE by using "priority_queue" but AC by using "priority_queue" in 670 msTLE codeAC code
•  » » 2 years ago, # ^ |   +3 Both priority queue code are wrong, just that the test cases are not strong enough to handle the other code. You need to have int v = pq.top().S; if ( /* - */ pq.top().F != d[v]) continue; pq.pop(); to avoid the code to have O(n^2 log n) worst case.
»
2 years ago, # |
0

. python code (question — D) i just applied the find the connected component in a graph which is O(n+m) and in those functions i just made some small changes like if the newly added component clashes with the previous one (largest b seen till now ) then it will increment . This is simply O(n+m) then why TLE on testcase 10 . . . .

# components in an undirected graph

class Graph:

# init function to declare class variables
def __init__(self,V):
self.V = V
self.adj = [[] for i in range(V)]

def DFSUtil(self, temp, v, visited):

# Mark the current vertex as visited
visited[v] = True

# Store the vertex to list
if v<temp[0]:
temp[0]=v
if v>temp[1]:
temp[1]=v

# Repeat for all vertices adjacent
# to this vertex v
if visited[i] == False:

# Update the list
temp = self.DFSUtil(temp, i, visited)
return temp

# method to add an undirected edge

# Method to retrieve connected components
# in an undirected graph
def connectedComponents(self):
visited = []
cc = []
for i in range(self.V):
visited.append(False)
b = 0
ans = 0
for v in range(self.V):
if visited[v] == False:
temp = [n,0]
cc.append(self.DFSUtil(temp, v, visited))
#print(cc)

if (len(cc)>1):

if cc[-2][1]>b:
b = cc[-2][1]
if cc[-1][0]<=b:
ans+=1
return ans

# Driver Code

if name=="__main__":

n,m = map(int,input().split())
g = Graph(n)
for i in range(m):
a,b = map(int,input().split())
print(g.connectedComponents())

. . . .

 » 2 years ago, # |   0 I tried problem D using the same idea as explained in tutorial and still getting error. https://codeforces.com/contest/1253/submission/65542541
 » 2 years ago, # |   0 Can anyone give me any idea how to reduce time limit in PROBLEM-B? Here is my code https://ideone.com/JBTcop
 » 2 years ago, # |   0 Need some critical test cases. I've tried by dfs but get wrong on test case 6.
 » 22 months ago, # |   0 For Problem D, I used the following approach — Firstly, I initialized all the pairs of vertices in an adjacency list. I used DFS to create an array of components along with visited boolean array for tracking which vertices are visited, we can use DSU to do the same. This step takes O(V+E) time complexity.So after the DFS/DSU, we arrive at the following - [[1,2,7,5],[3,4,6,8],[9],[10],[11,12],[13],[14]] Now, we can compute the max/min range for each components, so we would get — [[1,7],[3,8],[9,9],[10,10],[11,12],[13,13],[14,14]] Now, the logic for counting how many edges have to be added if we have a path from a->b and we want a path a->c where a<=c<=b is such that, if we have an intersection between two ranges, then we need to have an edge between those two components.Note that we don't need to sort the range array as it is pre-sorted.Now, we can keep a prevRange for storing the previous range, and if we find that the just next range intersects with the prevRange, we have to connect both the components and we increase the count of extraEdge by 1. If we don't have any intersection, we can set prevRange = currRange and then move to next range. For the interval logic, please refer — linkSubmission Link — link
 » 21 month(s) ago, # |   0 In E implementation, it is possible that "left <= pos+1 && pos+1 <= right" but "pos < left". So how can we do "minCost[pos] = minCost[pos+1]" ? I think it should go into below if condition and there should not be break statement. Help me where I am getting wrong. Thanks :)
 » 19 months ago, # | ← Rev. 2 →   0 For Sweets Eating (problem C) java solution was getting TLE no matter how I changed the code. I suspect it was due to sorting. I tried all techniques from this article and submitted the code for both Java 8 and 11 but nothing helped. Ended up submitting the code in C++. Java submission — 83711179.
•  » » 17 months ago, # ^ |   0 Same i am facing 6th test case TLE
 » 16 months ago, # |   0 Why there are so many successful submissions for problem C? 8000+ is a huge number is it a standard technique or is there any another way to do more easily?
 » 16 months ago, # |   0 in the F solution, you DO NOT need a Kruskal algorithm.You can just use a dsu with weights as a replacement.
 » 15 months ago, # |   0 Can anyone tell how the time complexity of B is calculated to be O(n+e)?
 » 15 months ago, # |   0 What could be the max value of e(in the editorial) for problem B
 » 15 months ago, # |   0 i have wrong answer on test case 4 in problem A can anyone please help me with my approach, the link to my submission is here Submission
 » 15 months ago, # |   0 A simple approach to problem D: Use DSU with value of parent deciding the dominant parent during union operation. Then run a simple loop from 1 to n and check if the root of the node is greater than node and then check if the next node root is same as that of this node and if not increase ans by 1. see my submission
»
10 months ago, # |
0

Here is the nlogn solution.i have used set in this problem, have a look on it.

# include<bits/stdc++.h>

using namespace std; int main() { int n; cin>>n; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; sets;

int flag=0;
vector<int>v;
int ind=-1;
int i;
for( i=0;i<n;i++)
{
if(arr[i]>0)
{
if(s.find(abs(arr[i]))!=s.end())
{
flag=1;
break;
}else
s.insert(arr[i]);
}
else
{

if(s.find(abs(arr[i]))==s.end())
{
flag=1;
break;
}
int d=i-ind;
if(d==2*s.size() && (arr[i]!=arr[i-1] && i>0))
{
v.push_back(d);
s.clear();
ind=i;
}
}

}
i--;

int d=i-ind;
if(d!=2*s.size() || (arr[i]==arr[i-1] && i>0))
flag=1;
if(flag==1)
cout<<"-1\n";
else
{
cout<<v.size()<<"\n";
for(auto k:v)
cout<<k<<" ";
}

}

 » 4 months ago, # |   0 DSU approach for solving problem D: https://codeforces.com/contest/1253/submission/129133003Initially: Rank of every vertex equals to it's value. Rank of a component is always equal to rank of bigger vertex i.e; rank of bigger value.if a.....b (rank[b]>rank[a])are connected by a path then if we are checking if a and c can be connected. Let's say x=find(a) y=find(b)Then if x>y => y is in between x and other vertex since find(x)>x because union is done based on vertex value, so root vertex is always bigger value = rank of component.
 » 6 weeks ago, # | ← Rev. 3 →   0 .