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. 