DESTCELL - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Rami

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

Given a grid with N rows and M columns, two heroes move from (1, 1) to (N, M), one moving row-wise, and other is moving column-wise. For each K \in [0, N*M-1], both heroes destroy the cell they are standing on, move K cells forward till the move outside the grid. Find the number of cells destroyed by at least one hero for each value of K. Grid is independent for each value of K.

EXPLANATION

Let us consider each value of K separately.

For each K, let us simulate the process of both heroes and mark the cells visited.

If we simulate the process one-by-one cell, it would lead to time complexity O((N*M)^2) which is too much.

For both heroes, let’s directly jump directly to the next cell to be destroyed, since other cells remain unaffected. We can see, we visit exactly (N*M)/K cells. Summing over each K, it gives total N*M*\Big( \displaystyle\sum_{i = 1}^{K}\frac{1}{i}\Big) steps. The summation is approximately equal to ln(N*M) as mentioned here, so overall complexity is O(N*M*ln(N*M)).

So, we directly jump to the next cell to destroy, maintain a counter for the number of cells destroyed as well as marking the destroyed cells (to avoid double-counting). After calculating this for a specific K, we also need to reset visited array in the same manner.

Knowledge of Sieve of Eratosthenes would make the idea crystal clear.

TIME COMPLEXITY

The time complexity is O(N*M*ln(N*M)) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll  long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sc second
#define fr first
using namespace std;

const int NM = 1e6+10;
const int N = 1e3+10;
const int M = 1e3+10;

pii hero1[NM];
pii hero2[NM];
bool vis[N][M];

int main()  {
	int t;
	cin>>t;
	while(t--){
	    int n,m;
	    scanf("%d%d",&n,&m);

	    int k =0;
	    for(int i=0 ; i<n ;i ++){
	        for(int j=0 ;j <m ;j ++){
	            hero1[k++] = {i,j};
	        }
	    }
	    k =0;
	    for(int j=0 ; j<m ;j ++){
	        for(int i=0 ;i <n ;i ++){
	            hero2[k++] = {i,j};
	        }
	    }


	    for(int i=1;i <=n*m ; i++){
	        if(i-1)printf(" ");
	        int res =0;
	        for(int j=0; j <n*m ; j+= i){
	            vis[hero1[j].fr][hero1[j].sc] = 1;
	            res++;
	        }

	        for(int j=0; j <n*m ; j+= i){
	            if(!vis[hero2[j].fr][hero2[j].sc])
	                res++;
	        }

	        printf("%d",res);

	        for(int j=0; j <n*m ; j+= i){
	            vis[hero1[j].fr][hero1[j].sc] = 0;
	        }

	    }

	    printf("\n");
	}
	return 0;
}
Tester's Solution
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#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 sz(a) a.size()
#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 > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);
vii a,b;
vii vec;
int vis[1005][1005];
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t,t1;
	cin>>t;
	t1=t;
	while(t--){
		int n,m,i,j,ans,id;
		a.clear();
		b.clear();
		cin>>n>>m;
		f(i,1,n+1){
			f(j,1,m+1){
				a.pb(mp(i,j));
			}
		}
		f(i,1,m+1){
			f(j,1,n+1){
				b.pb(mp(j,i));
			}
		}
		f(i,0,n*m){
			vec.clear();
			ans=0;
			id=0;
			while(id<n*m){
				vis[a[id].ff][a[id].ss]=1;
				vec.pb(a[id]);
				id+=i+1;
				ans++;
			}
			id=0;
			while(id<n*m){
				if(vis[b[id].ff][b[id].ss]==0){
					ans++;
				}
				id+=i+1;
			}
			rep(j,vec.size()){
				vis[vec[j].ff][vec[j].ss]=0;
			}
			cout<<ans<<" ";
		}
		cout<<endl;
	}
	return 0;
} 
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class DESTCELL{
	//SOLUTION BEGIN
	int[][] factors;
	void pre() throws Exception{factors = factors((int)1e6);}
	void solve(int TC) throws Exception{
	    int n = ni(), m = ni();
	    int[] ans = new int[1+n*m];
	    for(int i = 0; i< n; i++){
	        for(int j = 0; j< m; j++){
	            int x = i*m+j, y = i+j*n;
	            int g = gcd(x, y);
	            for(int v:factors[x])ans[v]++;
	            for(int v:factors[y])ans[v]++;
	            for(int v:factors[g])ans[v]--;
	        }
	    }
	    for(int i = 1; i<= n*m; i++)p(1+ans[i]+" ");pn("");
	}
	int[][] factors(int MAX){
	    MAX++;
	    int[][] fact = new int[MAX][];
	    fact[0] = new int[]{};
	    int[] spf = new int[MAX];
	    for(int i = 2; i<MAX; i++)if(spf[i]==0)for(int j = i; j< MAX; j+=i)if(spf[j]==0)spf[j] = i;
	    for(int i = 1; i< MAX; i++){
	        int cnt = 1, x = i;
	        while(x>1){
	            int p = spf[x],c= 1;
	            while(x%p==0){x/=p;c++;}
	            cnt*=c;
	        }
	        fact[i] = new int[cnt];
	        fact[i][0] = 1;int cur = 1;
	        x = i;
	        while(x>1){
	            int p = spf[x], c = 1;
	            while(x%p==0){x/=p;c++;}
	            for(int j = 0; j< cur; j++)for(int k = 1; k< c; k++)fact[i][k*cur+j] = fact[i][(k-1)*cur+j]*p;
	            cur*=c;
	        }
	    }
	    return fact;
	}
	int gcd(int x, int y){
	    return x == 0?y:gcd(y%x, x);
	}
	class Pair implements Comparable<Pair>{
	    int r, c;
	    public Pair(int R, int C){
	        r = R;c = C;
	    }
	    public int compareTo(Pair p){
	        if(r != p.r)return Integer.compare(r, p.r);
	        return Integer.compare(c, p.c);
	    }
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new DESTCELL().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

6 Likes

What I did in contest----->code
After optimization—>code
:stuck_out_tongue: but optimized it after the contest…

2 Likes

i did it using the observation that if we can directly go to the points which should be visited for any ‘k’ then their numbers(count of operations) varies as (nm)/1, (nm)/2, (nm)/3…(nm)/(nm) for k=0,1,2…(nm)-1. In this manner summation of operation comes out nmlog(n*m) which will pass, to make this smooth for checking the common points i used a global matrix which have its points visited by row-wise move and they can be cross checked on fly with points visited by col-wise moves.
https://www.codechef.com/viewsolution/26177751
oh! editorialist solution is also same :stuck_out_tongue:

1 Like

Can someone point out any error in this -> https://www.codechef.com/viewsolution/26189967. It is resulting in a TLE though I feel that I have implemented the exact same idea as above. The while loop inside destroy cell function runs MN/k times and in the main the function is called MN times. What is causing the TLE then?

This is the code I submitted during the contest -> https://www.codechef.com/viewsolution/26178842.

I can’t see the difference between my solution (30 pts) and tester’s solution. They have the same complexity and mine seems better. Any ideas ?
My submission during contest : https://www.codechef.com/viewsolution/26180835

you are redeclaring a vast size array

its not necessary to declare a 2d visited array,u could use 1d visited array and using hash function => 1000*x+y , this trick i once used in tree question for storing edges in tree dp question.like x<<20+y, it will generate unique values, but greater than size range of array,so i used unordered map for that.

1 Like

@nvdrag123 I did this trick during contest with :

hash_set : https://www.codechef.com/viewsolution/26179914
unordered_map :https://www.codechef.com/viewsolution/26179284

Just a few minutes ago, i did a solution without redeclaring a vast array :https://www.codechef.com/viewsolution/26190989

still bitset reset complexity, why dont u just make the true value false,btw in this case hash set or unordered map, it will not work,its increasing complexity by factor of log.make const size array.

hash_set or unordered_set has average case O(1) in almost all operations (source) : http://www.cplusplus.com/reference/unordered_set/unordered_set/emplace/

https://www.codechef.com/viewsolution/26191086 i changed your code

1 Like

my solution is quite different.
For each cell let’s count two numbers: the time when each of the heroes comes to this cell counting from zero(for example the (0, 0) cell will have numbers (0, 0) and (0, 1) will have (1, n))
Now it’s obvious that all the cells we visit with some of the heroes with fixed k has a view (k + 1) \cdot q for an integer q.
So all we have to do is for cell with numbers (x, y) find all numbers that divide x or y.
We can split out this problem into three easier: find all numbers that divide x and add 1 to answers for this k's, find all numbers that divide y and add 1 to answers for this k's, and find all numbers for gcd(x, y) and substract 1 from all the answers for this k's.
The only thing remains is to learn how to find all divisors of some x faster than in stupid \sqrt{n}. For this let’s calc for each x in range [2, 1e6] the least prime divisor(this can be done in O(n) or O(n loglogn) with Eratosphene sieve. After that let’s factorize each number in this diapason and save it like a pair <int, int> array, for example, we’ll save 5 as (5,1) and 100 as [(2, 2), (5, 2)], because 2^2 \cdot 5^2 = 100.
Now we can write a simple recursion function to brute force all divisors.
That is the main idea, I’m not sure if it’s that clear, but you can check my solution and ask some questions.
here it is: https://www.codechef.com/viewsolution/26184040

1 Like

thanks @nvdrag123 ! :grinning:

Nice Editorial. Thank You.

1 Like

Hello everyone,

The following is my 18 lines C++14 solution of the problem.

https://www.codechef.com/viewsolution/26191999

The solution is based on the idea of down-sampling the trajectory of each hero in the M \times N grid by factor K+1. For mathematical convenience, 0-indexed cell representation (r,c) is used, where r \in \{0,1,\ldots,M-1\} and c \in \{0,1,\ldots,N-1\}, respectively.

Let us assume that both heroes start to traverse the grid from the first cell (0,0) at time 0 with constant speed in the same row/column of one cell per time unit. Let us also assume that wrapping around from the last cell in each row/column to the first cell in the next row/cell column is done in one time unit.

\bf Observation~1

Both heroes destroy cells only at time instants z[i] = i \times (K+1), where i is the integer down-sampling index whose valid domain is i \in \{0,1,\ldots,\lfloor(M\times N -1)/(K+1)\rfloor\}, and both K and z[i] \in \{0,1,\ldots,M\times N-1\}. Therefore, each M\times N trajectory is down sampled by factor K+1. It follows that each hero destroys exactly 1+\lfloor(M\times N -1)/(K+1)\rfloor cells in the grid.

\bf Observation~2

The first hero reaches cell (r,c) at time instant g[r][c] = r \times N + c, while the second hero reaches the same cell at time instant h[r][c] = r + c \times M. The cell can be destroyed if and only if either g[r][c] or h[r][c] is divisible by K+1, or both.

\bf Observation~3

If both g[r][c] and h[r][c] are divisible by K+1, then cell (r,c) is destroyed by both heroes.

\bf Observation~4

The number of cells destroyed by at least one hero for a given K is equal to the summation of the number of cells destroyed by the first hero and the number of cells destroyed by the second hero only (i.e. not destroyed by both heroes).

\bf TIME-COMPLEXITY

O(p\log(p)) per test-case, where p = M \times N.

\bf UPDATE

The following is another code optimized C version of the proposed solution with less memory.

https://www.codechef.com/viewsolution/26227888

The expression for the number of cells destroyed by each hero is updated to

\lceil(M\times N)/(K+1)\rceil

14 Likes

Cool. It’s not even 18 lines. It’s 11 lines.

Hey guys! Can you pls check my code and pls tell why I am getting TLE.

`#include <bits/stdc++.h>
 using namespace std;

 int main()
 {
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    int t;
    cin>>t;

    for(int idx = 0; idx < t; idx++)
    {
	int n,m;
	cin>>n>>m;

	for(int i = 0; i < m*n; i++)
	{
		vector<int> v(n*m,0);
		int count = 0;
		for(int j = 0; j < m*n; j+=(i+1))
		{
			int k = j/m;
			int l = j%m;
			if(v[j] == 0)
			{
				v[j] = 1;
				count++;
			}
			if(v[l*n+k] == 0)
			{
				v[l*n+k] = 1;
				count++;
			}
		}
		cout<<count<<" ";
	}

	cout<<"\n";
	
   }
      return 0;
}

`
I am getting TLE for original constraints. Pls, help me !!
Thanks !!

Editorials have not come yet for Equal Average…

for each i you create a n \cdot m sized vector. It works in O(n \cdot m) and so your overall asimptotic is O(nm \cdot (nm)).
Actually you don’t need to always create a new vector. You can simply create a static one and after each iteration make all positions you have changed on the previous iteration equal to zero.

https://www.codechef.com/viewsolution/26194092
That’s your solution, I just added a function clean garbage and remembered positions we have changed using stack

1 Like