June 27, 2019 Single Round Match 760 Editorials

NBAFinals

Solution: 

We fill all the missing places greedily. Whenever a character in team is missing its always beneficial to fill it with W because giving some points to Warriors is always better than giving them to Raptors. Now, that we have no missing characters in team, whenever score is missing, if Raptors scored it, we want to give them the minimum possible (i.e 1) and for Warriors maximum possible (i.e 4). This is the best possible way of filling a Warriors fan could have done. So after filling team and score accordingly we can  check if Warriors have more points in this optimistic way of filling. If they have more then answer is 1, otherwise any other filling cannot give Warriors the lead. Hence answer is 0.

Code:

	public int dubsAgain(int[] scores, String team1){
		char[] team = team1.toCharArray();
		int n = scores.length;
		int i;
		for(i=0;i<n;i++){
			if(team[i]=='?')
				team[i]='W';
		}
		int ans=0;
		for(i=0;i<n;i++){
			if(scores[i]==0){
				if(team[i]=='R')
					scores[i]=1;
				else
					scores[i]=4;
			}
			if(team[i]=='R')
				ans-=scores[i];
			else
				ans+=scores[i];
		}
		if(ans>0)
			return 1;
		else
			return 0;
	}

Time Complexity: O(n) where n is number of characters in team

FrogJumps

Firstly we need to observe that we do not need the diagonal moves. We can simulate any diagonal move using two of the moves from (left, right, top, down). Now, we can see that for a frog at (x1,y1) which can jump such that its either coordinates change by k1, all the points it can reach will be of the form (x1 + a*k1, y1 + b*k1) , where a,b are integers.

Similarly frog at (x2,y2) which can jump such that its either coordinates change by k2, all the points it can reach will be of the form (x2 + c*k2, y2 + d*k2) , where c,d are integers.

So now for them to meet, x1+a*k1 = x2+c*k2, and y1+b*k1 = y2+d*k2,

Now x1-x2 = -a*k1 + c*k2 (This is true only when abs(x1-x2) is divisible by gcd(k1,k2))

Similarly abs(y1-y2) must also be divisible by gcd(k1,k2).

So now we can check these two conditions and return appropriate answer.

Code:

	public long gcd(long a,long b){
		if(a<b){
			long temp=a;
			a=b;
			b=temp;
		}
		if(b==0)
			return a;
		return gcd(b,a%b);
	}
	public int canMeet(long x1,long y1,long x2,long y2,long k1,long k2){
		long val = x2-x1;
		if(val < 0){
			val*=-1;
		}
		long gg = gcd(k1,k2);
		if(val%gg!=0){
			return 0;
		}
		val=y2-y1;
		if(val < 0){
			val*=-1;
		}
		if(val%gg!=0){
			return 0;
		}
		return 1;
	}

Time Complexity: O(log(k1) + log(k2) ) for calculating the gcd. Rest are O(1) operations.  

HomeAwayLeague

Solution:

Firstly let us select the n/2 teams which host the home game in first round. This can be done in C(n,n/2) ways.

Next, we need to assign away teams for the home games in the first round. For this we can assume home teams are lined in some order (for example lexicographic). And we can take n! possible orderings of away teams and allot ith home team with ith away team and so on. So now, each of the n! orderings give different schedule for first round. 

Hence , first round can be organised in n! * C(n,n/2) ways.

Now given a first round, home teams for second round are already decided which will be away teams of first round. We can assume there is some ordering among home teams again. Now , we want to take orderings of away teams such no team plays the same team they played in previous round. This is same as counting number of derangements of size n/2 because each one does not go to exactly one place(let us represent by D(n/2) ).

Derangements can be calculated using recursion D(n) = (n-1)*(D(n-1)+D(n-2)).

Therefore , total ways are n! * C(n,n/2)* D(n/2).

Code:

int N = 500005;
	long[] fact = new long[N];
	long[] derang = new long[N];
 	long mod = (1000*1000*1000+7);
 	public long powe(long a, long b){
 		long ans=1;
 		while(b>0){
 			if(b%2==1){
 				ans*=a;
 				ans%=mod;
 			}
 			a*=a;
 			a%=mod;
 			b/=2;
 		}
 		return ans;
 	}
 	public long inver(long val){
 		return powe(val,mod-2);
 	}
 	public long range(int l,int x,int r){
 		if(l<=x && x<=r){
 			return 1;
 		}
 		return 0;
 	}
	public int matches(int n){
		int i;
		fact[0]=1;
		for(i=1;i<N;i++){
			fact[i]=fact[i-1]*i;
			fact[i]%=mod;
		}
		derang[1]=0;
		derang[2]=1;
		for(i=3;i<N;i++){
			derang[i]=(derang[i-1]+derang[i-2])*(i-1);
			derang[i]%=mod;
		}
		long ans=fact[n];
		ans*=inver(fact[n/2]);
		ans%=mod;
		ans*=derang[n/2];
		ans%=mod;
		return (int)ans;
	}

Time Complexity: O(n).

CatAndMice (author : misof)

Solution:

Firstly let us handle case C = N, then the only rays are either diagonals or vertical or horizontal. We will prove soon that for other rays, number of lattice points is less than N.

So from here on lets assume C!=N. 

We can first see that we can calculate the number of rays in first quadrant and see that due to symmetry it will be same in the rest of the quadrants.And since C!=N,each ray uniquely belongs to a single quadrant. So we can find number of rays in first quadrant and multiply answer with 4.

Now, we have reduced to counting rays in first quadrant. We can further use symmetry along line x=y and reduce question to finding number of rays in the first 45 degrees. And multiply it by 2.

Now any ray equation in the first 45 degrees looks like  y = a*x/b where (0<a<b and a and b are co prime). Different pairs of (a,b) give different rays. (we are not considering diagonal and horizontal directions because for them C=N).

Now, we can notice from 0<a<b constraint that b>=2.  (remember this we will use later).

Next number of lattice points on the ray y = a*x/b. x can take values b,2*b and so till floor(n/b). Since a<b, y will always be less than x and hence if x is in the range then y is also in the range. Hence number of lattice points on the ray will be floor(n/b). 

Now , since b>=2, maximum number of lattice points on such a ray will be floor(N/2) (< N) (Proof that C=N cases are completely described above).

Since number of lattice points on a ray does not depend on a, we can iterate on b. And see what for all values of b we have floor(N/b) = C.

Now we want to count for a particular b , number of values possible for a such that a>=1 and a<b and a is co prime to b. This is exactly phi(b) (euler totient function).

So now answer will be sum of phi(b) over all b that satisfy floor(N/b) = C.

Code (By misof ):

    public long countDirections(int N, int C) {
        int[] primeDivisor = new int[N+1];
        for (int n=2; n<=N; ++n) if (primeDivisor[n] == 0) for (int i=n; i<=N; i+=n) primeDivisor[i] = n;
        int[] phi = new int[N+1];
        phi[1] = 1;
        for (int n=2; n<=N; ++n) {
            int x = n, p = primeDivisor[n];
            phi[n] = p - 1;
            x /= p;
            while (x % p == 0) {
                phi[n] *= p;
                x /= p;
            phi[n] *= phi[x];
        if (C == N) return 8;
        long answer = 0;
        for (int b=2; b<=N; ++b) if (1L*C*b <= N && 1L*(C+1)*b > N) answer += 8*phi[b];
        return answer;

Time Complexity:

O(nlogn) to calculate euler totient function for the first n natural numbers.  

ComponentsForever

Solution:

First thing is (x+y)modulo 2 value is constant across hops. So a frog at (x1,y1) cannot reach a frog (x2,y2) in any number of hops if (x1+y1) modulo 2  != (x2+y2) modulo 2.

So let us separate the frogs based on (x+y)modulo 2 and add the answers of the both cases. Because there will not be any common promise among both groups because they cannot talk to each other ever.

Case 1:

Now, we will work with group where all the frogs have (x+y)modulo 2 =0. From now on, in this case whenever we refer to a frog,we assume its coordinates are such that sum of them is even.

For, two frogs at (x1,y1) and (x2,y2)

if (x2-x1) modulo 2 =1, then frog 1 can reach second frog only after odd number of hops. Similarly, for (x2-x1)modulo 2 =0, we can reach only in even number of hops.

Minimum number of hops needed for frog 1 to reach frog 2 is max(abs(x2-x1),abs(y2-y1)).  

Proof: this minimum cannot be less than this because each hop x and y coordinate will change atmost by 1. Now, we will show a construction. Lets assume abs(x2-x1) > = abs(y2-y1). Now, first abs(y2-y1) moves we move y1 towards y2 and x1 towards x2. For rest of the moves we oscillate y1 near y2 (like move from y2 to y2+1 and back from y2+1 to y2) and move x1 to x2.

Also now we can see that if minimum number of hops is d, there always exist a path of length d+2k for any whole number k because after minimum hops we can move to adjacent vertex and back. And we have proved above that parity of path lengths is always same. Hence, these are the only path lengths possible.

So now,  Let us take a walkie talkie with range (L<R) . Now this can connect frog 1 and 2 only if 

R>=max(abs(x2-x1),abs(y2-y1)) because [L,R] will consist of atleast two consecutive integers and in every two consecutive integers above minimum hops one of them can be path lengths. So now, connectivity does not depend on L.

Since L is not important for us. We will just focus on R and for each R , for every valid L answer will be same.

Now, for each R, we will construct a connectivity graph and compute number of components in it. Since in each component we can make different promise,we  need expected number of components in the graph.

We can start from R = a, and keep increasing R gradually and add edges as they become eligible (an edge becomes eligible only when min hops between the two frogs <= R). If you can see this procedure is very close to kruskal algorithm to finding MST. Also another parallel is only when an MST edge is added, count of components changes. So, the only important R values where number of components change will be the edge weights of MST edges. 

So now, we will have n-1 important R values and between each pair of adjacent R values components do not change. So we can count number of [L,R] pairs with that number of components and use it for finding expectation.

Finally we are left with finding MST in this graph. Now, there will be O(n*n) edges. Hence, it is not feasible to construct the graph and use kruskal algorithm.

For two points (x1,y1) and (x2,y2), max(abs(x2-x1),abs(y2-y1)) is called Chebyshev distance .

Let us consider transformation of point (x,y) to ((x+y)/2,(x-y)/2)

Now, if we take ((x1+y1)/2,(x1-y1)/2) and ((x2+y2)/2,(x2-y2)/2),  manhattan distance between them will turn out to be max(abs(x2-x1),abs(y2-y1)). Hence, graph constructed with edge length as manhattan distance between the transformed points will be same as previous graph. Now since the graph is same, MST will also be same. So we need Manhattan MST between these transformed points which is a standard problem (Link here). 

Hence, we can now construct the MST fastly and solve the problem. 

A small trick to avoid doubles, the case where points have (x+y)modulo 2 as odd, we can move all the points 1 unit right. This will not change anything in the problem since all distances will remain same.

counting number of pairs of [L,R] such that R is between R1 and R2 . Assume a<=R1<=R2<=b.

Number of pairs will be (R1-a)+(R1+1-a)+…(R2-a) = R2*(R2+1)/2 – (R1-1)*R1/2 – a*(R2-R1+1).

Code (C++):

	//teja349
	#include <bits/stdc++.h>
	#define f(i,a,b) for(i=a;i<b;i++)
	#define rep(i,n) f(i,0,n)
	#define fd(i,a,b) for(i=a;i>=b;i--)
	#define pb push_back
	#define mp make_pair
	#define vi vector< int >
	#define vl vector< ll >
	#define ss second
	#define ff first
	#define ll long long
	#define pii pair< int,int >
	#define pll pair< ll,ll >
	#define inf (1000*1000*1000+5)
	#define all(a) a.begin(),a.end()
	#define tri pair<int,pii>
	#define vii vector<pii>
	#define vll vector<pll>
	#define viii vector<tri>
	#define mod (1000*1000*1000+7)
	#define pqueue priority_queue< int >
	#define pdqueue priority_queue< int,vi ,greater< int > >
	ll xx[212345],yy[212345];
	const int maxn = 2e5 + 5;
	const int oo = (int) (1e9+10);
	struct Point {
	    int x, y, idx;
	    Point() {x = y = idx = 0;}
	    Point(const Point& rhs) : x(rhs.x), y(rhs.y), idx(rhs.idx) {}
	    int operator < (const Point& rhs) const {
	        return make_pair(x, make_pair(y, idx)) < make_pair(rhs.x, make_pair(rhs.y, rhs.idx));
	    }
	};
	pair<int, int> fen[maxn];
	void upd(int p, pair<int, int> val) {
	    p++;
	    for (; p > 0; p -= p & -p) fen[p] = min(fen[p], val);
	}
	int query(int p) {
	    p++;
	    pair<int, int> res = make_pair(oo, -1);
	    for (; p < maxn; p += p & -p) {
	        res = min(res, fen[p]);
	    }
	    return res.second;
	}
	int dj[maxn];
	void init() {
	    for (int i = 0; i < maxn; i++) dj[i] = i;
	}
	int find(int u) {
	    return dj[u] == u ? dj[u] : dj[u] = find(dj[u]);
	}
	int join(int u, int v) {
	    int p = find(u);
	    int q = find(v);
	    if (p != q) {
	        dj[p] = q;
	        return 1;
	    }
	    return 0;
	}
	int n;
	Point p[maxn];
	priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > pq;
	int dist(Point a, Point b) {
	    return abs(a.x - b.x) + abs(a.y - b.y);
	}
	void add(int u, int v, int d) {
	    pq.push(make_pair(d, make_pair(u, v)));
	}
	void manhattan() {
		while(!pq.empty())
			pq.pop();
	    for (int i = 0; i < n; i++) p[i].idx = i;
	    for (int dir = 0; dir < 4; dir++) {
	        for (int i = 0; i < maxn; i++) {
	            fen[i] = make_pair(oo, -1);
	        }
	        if (dir == 1 || dir == 3) {
	            for (int i = 0; i < n; i++) swap(p[i].x, p[i].y);
	        }
	        else if (dir == 2) {
	            for (int i = 0; i < n; i++) p[i].x = -p[i].x;
	        }
	        sort(p, p + n);
	        vector<int> v; static int a[maxn];
	        for (int i = 0; i < n; i++) v.push_back(a[i] = p[i].y - p[i].x);
	        sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
	        for (int i = 0; i < n; i++) a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
	        for (int i = n - 1; i >= 0; i--) {
	            int pos = query(a[i]);
	            if (~pos) add(p[i].idx, p[pos].idx, dist(p[i], p[pos]));
	            upd(a[i], make_pair(p[i].x + p[i].y, i));
	        }
	    }
	}
	ll getgg(ll a,ll b,ll Llo,ll Rhi){
		a=max(a,Llo);
		b=min(b,Rhi);
		if(b<a){
			return 0;
		}
		ll ans=b*(b+1)/2-a*(a-1)/2 - Llo*(b-a+1);
		ans%=mod;
		return ans;
	}
	ll solve(int nn,int Llo,int Rhi){
		n=nn;
		manhattan();
		ll comps=n;
		init();
	    ll ans = 0;
	    ll prevr=1;
	    while (pq.size()) {
	        int u = pq.top().second.first;
	        int v = pq.top().second.second;
	        int w = pq.top().first;
	        pq.pop();
	        if (join(u, v)) {
	            ans+=comps*getgg(prevr,w-1,Llo,Rhi);
	            ans%=mod;
	            comps--;
	            prevr = w;
	        }
	    }
	    ans+=comps*getgg(prevr,Rhi,Llo,Rhi);
	    ans%=mod;
	    return ans;
	}
	ll powe(ll a,ll b){
		ll ans=1;
		while(b){
			if(b%2){
				ans*=a;
				ans%=mod;
			}
			b/=2;
			a*=a;
			a%=mod;
		}
		return ans;
	}
	class ComponentsForever{
	public:
		int countComponents(int nn, vector<int> Xprefix, vector<int> Yprefix, int seed, int Xrange, int Yrange, int Llo, int Rhi){
			int sz=Xprefix.size();
			int i;
			for(i=0;i<sz;i++){
				xx[i] = Xprefix[i];
				yy[i] = Yprefix[i];
			}
			ll state = seed;
			ll bigmod = (1LL<<31);
			for(i=sz;i<nn;i++){
				state = (1103515245 * state + 12345);
				xx[i] = state%Xrange;
				state=state%bigmod;
				state = (1103515245 * state + 12345);
	    		yy[i]=state%Yrange;
	    		state=state%bigmod;
			}
			int cnt=0;
			int j=0;
			for(i=0;i<nn;i++){
				if((xx[i]+yy[i])%2==0){
					p[j].x = (xx[i]+yy[i])/2;
					p[j].y = (xx[i]-yy[i])/2;
					j++;
					cnt++;
				}
			}
			ll ans=0;
			if(cnt)
				ans = solve(cnt,Llo,Rhi);
			cnt=0;
			j=0;
			for(i=0;i<nn;i++){
				if((xx[i]+yy[i])%2==1){
					xx[i]--;
					p[j].x = (xx[i]+yy[i])/2;
					p[j].y = (xx[i]-yy[i])/2;
					j++;
					cnt++;
				}
			}
			if(cnt)	{
				ans += solve(cnt,Llo,Rhi);
			}
			ll val=getgg(Llo,Rhi,Llo,Rhi);
			ans*=powe(val,mod-2);
			ans%=mod;
			return ans;
		}
	};

Time Complexity: Constructing Manhattan MST takes O(nlogn) time.

counting number of pairs of [L,R] such that R is between two consecutive change points (that is for all these R number of components is constant) is O(1). Since its just some formulas. And there are O(n) such intervals . So O(n) complexity

Hence, total time complexity is O(nlogn).