UNITGCD - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Ashish Lal
Tester: Felipe Mota
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Pigeonhole principle

PROBLEM:

There are N pages in a book Chef is reading, numbered from 1 to N. Chef wants to finish this book in minimum days possible. However, for all pages read on the same day, there shouldn’t be two different pages having GCD greater than 1. Find this minimum number of days and distribution of pages among

QUICK EXPLANATION

  • The number of days is decided by the number of multiples of 2 up to N. The number of days is given by \big\lfloor \frac{N}{2} \big\rfloor.
  • One possible construction is to read the first three pages on day one and then keep reading two pages until the book is finished.
  • N = 1 is a special case.

EXPLANATION

This problem can become super easy just by noticing the fact that there are \big\lfloor \frac{N}{2} \big\rfloor even numbers. So, by pigeonhole principle, we cannot put any pair of these pages on the same day, since that day would violate the validity condition.

The minimum number of days can never be less than D = \big\lfloor \frac{N}{2} \big\rfloor. Further, let us check whether there actually exist some way to read book in D days. Consider the following cases.

  • N is even
    In this case, we can just read the whole book in order from 1 to N, reading two pages every day.
    (Since two adjacent numbered pages can never have a prime dividing both of them)
  • N is odd
    In this case, we need to read three pages someday. We can easily choose to read N-th page on day one itself. This would mean reading page 1, 2 and N on day one. Since N is odd, page 2 and page N doesn’t conflict. We can read the remaining pages in the same order as in the previous case.

Hence, we have found a way to read book in D days.

There is a special case where N = 1 where you can read the one-page book in one day.

Alternative construction: We can choose to read the first three pages on day one, and keep reading two pages until we read the whole book. On the last day, it is possible we read only one page in case N is even. It is easy to check the validity of this construction.

Feel free to share your construction.

TIME COMPLEXITY

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

SOLUTIONS:

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		/**
			if the n is 1 the answer is 1

			else
			the lower bound of the answer is floor(N / 2), because no two even numbers can be in the same set
			this bound can be achieved by creating pair of adjacent numbers (i.e (1, 2) (3, 4) (5, 6) ...)
			if N is odd, the number N will be unused, but it can be put in the tuple (1, 2)
			as it's an odd number the GCD(2, N) = 1
		 * */
		if(n == 1){
			cout << 1 << '\n';
			cout << 1 << ' ' << 1 << '\n';
		} else {
			cout << n / 2 << '\n';
			if(n % 2){
				cout << 3 << ' ' << 1 << ' ' << 2 << ' ' << n << '\n';
			} else {
				cout << 2 << ' ' << 1 << ' ' << 2 << '\n';
			}
			for(int i = 4; i <= n; i += 2){
				cout << 2 << ' ' << i - 1 << ' ' << i << '\n';
			}
		}
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class UNITGCD{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni();
	    if(N == 1){
	        pn("1\n1 1");
	    }else if(N == 2){
	        pn("1\n2 1 2");
	    }else{
	        int days = N/2;
	        pn(days);
	        pn("3 1 2 3");
	        for(int d = 2; d <= days; d++){
	            if(d*2 == N)pn("1 "+N);
	            else pn("2 "+(d*2)+" "+(d*2+1));
	        }
	    }
	}
	//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 UNITGCD().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. Suggestions are welcomed as always. :slight_smile:

13 Likes

i have try same approch but it shows TLE errorhttps://www.codechef.com/viewsolution/31403506

1 Like

If you want detailed solution then check this blog out.

2 Likes

I have used same approach , can someone check why time limit exceeded?
https://www.codechef.com/viewsolution/31610875

2 Likes

can someone check why time limit exceeded?
https://www.codechef.com/viewsolution/31791939

@rishabh1705 Use “\n” instead of endl …

Instead of endl use “\n” or try cout.tie(NULL);

Thanks it worked , but can you tell why ??
i mean both endl and \n are same?

Thanks it worked , but can you tell why ??
i mean both endl and \n are same?

endl and \n do the same work but they have some difference in their working mechanisms.
Check this
https://codeforces.com/blog/entry/43780

endl flushes the output stream which comsumes more time but in case of ‘\n’ it doesnot flush the stream just moves to the next line and flushes at the end thus saving time.

Here, read this.

Can someone tell me why my answer is wrong? I have read all prime pages on day 1 itself and then read one or two pages depending on the condition of co prime pages.
https://www.codechef.com/viewsolution/31816312
I tried running every test case possible but acc to me it gives correct output.
Please help, I am stuck on this!

2 Likes

Can anyone tell what’s wrong in my code for N <= 100.
Here is my code :
#include <bits/stdc++.h>
#include
#include
#include
#define ll long long
using namespace std;

const ll MAX_SIZE = 1e6 + 1;

vector isprime(MAX_SIZE , true);
vector prime;
vector SPF(MAX_SIZE);
std::map<ll, vector > m;

// function generate all prime number less then MAX_SIZE in O(n)
void manipulated_seive()
{
isprime[0] = isprime[1] = false ;
// SPF[1] = 1;
// prime.push_back(1);

for (ll int i=2; i<MAX_SIZE ; i++)
{
	if (isprime[i])
	{
		prime.push_back(i);
		SPF[i] = i;
	}

	for (ll int j=0; j < (int)prime.size() && i*prime[j] < MAX_SIZE && prime[j] <= SPF[i]; j++)
	{
		isprime[i*prime[j]]=false;
		SPF[i*prime[j]] = prime[j];
        // cout << i*prime[j] << " " << prime[j] << endl;
		m[prime[j]].push_back(i * prime[j]);
	}
}
// for(int i = 0; i < MAX_SIZE; i++)
	// cout << SPF[i] << " ";

//Reversing all the vectors of SPF
// for(int i = 1; i < MAX_SIZE; i++)
// {
//     reverse(m[i].begin(), m[i].end());
// }
return;

}

void print_answers(vector<vector > ans, ll it)
{
cout << it << endl;
for(int i = 0; i < it; i++)
{
cout << ans[i].size() << " ";
for(int j = 0; j < ans[i].size(); j++)
cout << ans[i][j] << " ";
cout << endl;
}
return ;
}

void schedule(ll n)
{
ll visited = 1;

int l = 0;
while(prime[l] <= n and l < prime.size())
{
	visited++;
	l++;
}
std::vector<vector<ll> > ans(MAX_SIZE); //vector to store answers

//pushing those numbers
ans[0].push_back(1);
for(int i = 0; i < visited - 1; i++)
	ans[0].push_back(prime[i]);

ll idx = 0;
ll it = 1;
while(!m.empty() and visited != n)
{
	bool flag = false;
    for(ll i = 2; i * i <= n; i++)
    {
        if(m.count(i) == 0)
            continue;

        if(idx < m[i].size() and m[i][idx] <= n)
        {
        	flag = true;
            ans[it].push_back(m[i][idx]);
            visited++;
            // m[i].erase(m[i].begin());
        }
        else
        	continue;

        if(visited == n)
        	break;
    }

    idx++;
    if(flag)
    	it++;
}
print_answers(ans, it);
return;

}

// ll find_largest_diff()
// {
// ll diff = -1;
// for(ll i = 0; i < prime.size() - 1; i++)
// {
// diff = max(diff, prime[i + 1] - prime[i]);
// }
// return diff;
// }

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

manipulated_seive();
// cout << prime.size() << endl;
// cout << find_largest_diff() << endl;
int t;	cin >> t;
while(t--)
{
	ll n;	cin >> n;
	schedule(n);
}
return 0;

}

#include
using namespace std;

int main() {
int test;
cin>>test;
while(test–)
{
int n;
cin>>n;

if(n==1)
printf("%d",n);
else
printf("%d ",n/2);

printf("\n");


if(n<=3)
{
    int ans=min(n,3);
    printf("%d ",ans);
    for(int i=0;i<min(3,n);i++)
    {
        printf("%d ",i+1);
    }
    printf("\n");
}
else
{
    int count=0;
    printf("3 ");
    for(int i=0;i<3;i++)
    {
        printf("%d ",i+1);
        
        count++;
    }
    printf("\n");
    
    int ans=1;
    for(int i=2;i<=(n/2);i++)
    {
        if(i==(n/2) && count==n-1)
        printf("%d ",ans);
        else
        printf("%d ",ans+1);
        
        for(int j=0;j<2 && count<n;j++)
        {
           int ans1=2*i+j;
            printf("%d ",2*i+j);
           // scanf(" %d ",ans1);
            count++;
        }
        printf("\n");
    }
}

// printf("\n");
}
return 0;
}

can anyone tell why the error SIGXFXZ is coming in my code??

why code in c++ was showing tle and same code in c worked

My approach consisted of printing all primes including 1 on the first day and then printing co-primes pair from remaining non-primes. With this approach I was able to get AC for 1st subtask. Can someone help me optimize this further, to find the co-prime pairs in less than O(n^2) ?
Thanks!

My solution link : link

Yes, I have implemented the same approach printing all prime numbers on the first day and 2 pages & 1 single page on other days. I don’t know why it shows WA. I have wasted too much time to find the case where program gives wrong output. Please help me out.
https://www.codechef.com/viewsolution/31779859

See endl performs two operations

  1. Next line \n
  2. Flush the stream

However \n performs just 1 operation.

And when program terminates platform automatically flushes the stream thats why \n is faster than endl

For more tricks you can check this article

Try for n=15