Thanks for really fast + detailed editorial :D problem E and F are really interesting too :D

Thanks

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

Can someone explain C solution? I'm not sure if I got what is written in the editorial

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

Intended solution for D was in fact already $$$O(n + m)$$$. I was sorting an already sorted array...

I have wrong answer on test 13 on problem B, can you please check my submission to see what is wrong with it ?

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?

Any source code by editorial on a problem E?

A really good contest, thanks

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?

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

In problem F solution 1 can be extended to online queries with persistent DSU

I don't understand why I got TLE for D... Can anyone help? 65226875 I basically followed the solution above and implemented myself.

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)

In problem D : A small change in DSU find algorithm changes TLE to AC.

    return par[node]==node ? par[node] = node : find(par[node]);

    return par[node]==node ? node : par[node] = find(par[node]);

Submissions : 65229651 65229747

Could someone point out why this is happening?

It's a really interesting contest, thanks to all the contributors :D

Problem p1253B — Silly Mistake, please help does not able to find what is wrong in code my submission

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

what should be the question A ans on this input?

1

2

10 20

15 25

.

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?

Can anyone explain the edoitorial of D in some other way???

In problem E,why are we not considering the transition for x>ri?

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<xb, then xa+sa<xb+sb and xa-sa<xb-sb (part2)
-since the last antenna's signal is now the closest to m, add to the signal the remaining distance to m and, again, eliminate all the antennas to it's left that it will now override (part3)
-get a variable called bord=the last position which I don't know for sure if it's covered or not(so all the positions from 1 to bord-1 are covered 100%)
-from the first to the last antenna: (part 4)
-if bord > 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<x-s, so add to both the solution and s the distance between bord and x-s-1, which is x-s-bord, so now both the areas between bord and x-s-1 AND x-s and x+s are covered, so make bord x+s+1
I got the 10th test wrong so I made a mistake in my code or in my understanding of the problem, but since it passed 9 tests it mustn't be that bad.

#include <bits/stdc++.h>
#define x first
#define s second
typedef long long ll;
ll n, m, i, j, l, bord=1, sol;
std::pair<ll, ll> 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;
}

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

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 <bits/stdc++.h>
using namespace std;

void func() {
	int n, x;
    cin >> n;

    vector<int> a(n);
    vector<int> d(n);
    set<int> 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()

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 4

the correct answer should be Yes. but if you use custom invocation, the result is: Yes (c++11) NO (c++14)

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?

I think Problem E can be solved with shortest path algorithms.It's necessary to add some edges with 0 weight.

See my code

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?

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

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 Mistake

My Solution

Solution for F is so beautiful...

Hey guys, does anyone know why my solution 1253F — Cheap Robot

TLE by using "priority_queue<pair,vector,greater>"

but AC by using "priority_queue<pair>" in 670 ms

TLE code

AC code

I tried problem D using the same idea as explained in tutorial and still getting error. https://codeforces.net/contest/1253/submission/65542541

For Problem D, I used the following approach —

1. Firstly, I initialized all the pairs of vertices in an adjacency list.
2. 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 — link

Submission Link — link

in the F solution, you DO NOT need a Kruskal algorithm.

You can just use a dsu with weights as a replacement.

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