DIVCOL - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: everule1
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Color the integers from 1 to N in such a way that if x divides y, they have different colors.
Minimize the number of colors used.

EXPLANATION:

First, we find a lower bound on the answer.
Note that if we have a ‘chain’ of values x_1 \lt x_2 \lt \ldots \lt x_k such that x_i divides x_{i+1} for every 1 \leq i \lt k, then all these x_i must receive different colors, since for each pair of them, one of them will divide another.

The longest such chain is obtained via the powers of two, i.e, 1, 2, 4, 8, 16, \ldots
So, let k be the largest integer such that 2^k \leq N (specifically, k = \left \lfloor \log_2 N \right\rfloor ).
As per our initial observation, we definitely need at least k+1 colors to color all these powers of 2.

It turns out that this k+1 is also tight: it’s always possible to use exactly this many colors.
There are several different constructions possible, but here’s a rather simple one:

  • Color 1 with the color 1.
  • Color 2 and 3 with the color 2.
  • Color 4, 5, 6, 7 with the color 3.
    \vdots

More generally, color all the values from 2^i to 2^{i+1}-1 with the color i+1.

This clearly uses \left \lfloor \log_2 N \right\rfloor + 1 colors, which as we noted above is optimal.
Further, it’s also not hard to see that no two elements with the same color divide each other - after all, if x divides y and x\lt y, then y\geq 2x so x and y will definitely have different colors.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> ans(n + 1, 1);
    for (int i = 2; i <= n; i++){
        if (ans[i] == 1){
            for (int j = i; j <= n; j += i){
                int copy = j;
                while (copy % i == 0){
                    copy /= i;
                    ans[j]++;
                }
            }
        }
    }
    
    int mx = *max_element(ans.begin(), ans.end());
    cout << mx << "\n";
    
    for (int i = 1; i <= n; i++){
        cout << ans[i] << " \n"[i == n];
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Tester's code (C++) 
#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...)
#endif

namespace mint_ns {
template<auto P>
struct Modular {
    using value_type = decltype(P);
    value_type value;
 
    Modular(long long k = 0) : value(norm(k)) {}
 
    friend Modular<P>& operator += (      Modular<P>& n, const Modular<P>& m) { n.value += m.value; if (n.value >= P) n.value -= P; return n; }
    friend Modular<P>  operator +  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r += m; }
 
    friend Modular<P>& operator -= (      Modular<P>& n, const Modular<P>& m) { n.value -= m.value; if (n.value < 0)  n.value += P; return n; }
    friend Modular<P>  operator -  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r -= m; }
    friend Modular<P>  operator -  (const Modular<P>& n)                      { return Modular<P>(-n.value); }
 
    friend Modular<P>& operator *= (      Modular<P>& n, const Modular<P>& m) { n.value = n.value * 1ll * m.value % P; return n; }
    friend Modular<P>  operator *  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r *= m; }
 
    friend Modular<P>& operator /= (      Modular<P>& n, const Modular<P>& m) { return n *= m.inv(); }
    friend Modular<P>  operator /  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r /= m; }
 
    Modular<P>& operator ++ (   ) { return *this += 1; }
    Modular<P>& operator -- (   ) { return *this -= 1; }
    Modular<P>  operator ++ (int) { Modular<P> r = *this; *this += 1; return r; }
    Modular<P>  operator -- (int) { Modular<P> r = *this; *this -= 1; return r; }
 
    friend bool operator == (const Modular<P>& n, const Modular<P>& m) { return n.value == m.value; }
    friend bool operator != (const Modular<P>& n, const Modular<P>& m) { return n.value != m.value; }
 
    explicit    operator       int() const { return value; }
    explicit    operator      bool() const { return value; }
    explicit    operator long long() const { return value; }
 
    constexpr static value_type mod()      { return     P; }
 
    value_type norm(long long k) {
        if (!(-P <= k && k < P)) k %= P;
        if (k < 0) k += P;
        return k;
    }
 
    Modular<P> inv() const {
        value_type a = value, b = P, x = 0, y = 1;
        while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
        return Modular<P>(x);
    }
 
    friend void __print(Modular<P> v) {
        cerr << v.value;
    }
};
template<auto P> Modular<P> pow(Modular<P> m, long long p) {
    Modular<P> r(1);
    while (p) {
        if (p & 1) r *= m;
        m *= m;
        p >>= 1;
    }
    return r;
}
 
template<auto P> ostream& operator << (ostream& o, const Modular<P>& m) { return o << m.value; }
template<auto P> istream& operator >> (istream& i,       Modular<P>& m) { long long k; i >> k; m.value = m.norm(k); return i; }
template<auto P> string   to_string(const Modular<P>& m) { return to_string(m.value); }
 
}
constexpr int mod = (int)1e9 + 7;
using mod_int = mint_ns::Modular<mod>;


 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  const int NN = 2e5 + 2;
  vector<int> prime, P(NN, 1);
  for(int i = 2 ; i < NN ; ++i) if(P[i]) {
    prime.push_back(i);
    for(int j = 2 * i ; j < NN ; j += i)
      P[j] = 0;
  }
  auto __solve_testcase = [&](int test) {
    int N;  cin >> N;
    vector<int> color(N + 1); color[1] = 1;
    for(int k = 1 ; k <= N ; ++k) {
      for(int &j: prime) {
        if(j * k > N) break;
        color[j * k] = color[k] + 1;
      }
    }
    cout << *max_element(color.begin(), color.end()) << '\n';
    for(int i = 1 ; i <= N ; ++i)
      cout << color[i] << " \n"[i == N];
  };
  
  int NumTest = 1;
  cin >> NumTest;
  for(int testno = 1; testno <= NumTest ; ++testno) {
    __solve_testcase(testno);
  }
  
  return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    print(len(bin(n)) - 2)
    for i in range(1, n+1): print(len(bin(i))-2)
2 Likes
2

I find this construction more intuitive.
We can start by filling all the primes <= n with ‘1’. This works because prime numbers have no other factor than ‘1’ and themselves. Hence giving them a value ‘1’ is appropriate.

So how we fill composite numbers? The answer is simple we fill them based on their largest factor. Why? This is because since we have already filled all the numbers <= current number, hence the only factor that makes sense is the largest factor of the current number. What value to we assign to this number? We assign val[largest factor]+1, since we can’t repeat. Now we can do this for every number from [2, N], and finally assign the value val[1] = max(2, N) + 1.

A quick way to find largest factor is to find the lowest prime factor and divide the number by it, for example lpf[46] = 2 and it’s largest factor is 23 [46 / 2].

This construction always works and is very intuitive.

2 Likes
3

Problem statement from contest: You are given an integer NN.
Your task is to find the minimum integer CC such that there exists an array AA of size NN satisfying:

  • 1≤Ai≤C1≤Ai​≤C;
  • For distinct indices xx and yy where xx divides y; Ax≠Ayy; Ax​=Ay​.

You need to print the minimum value of CC as well as the array AA. In case multiple arrays exist, you may print any one.

problem statement from solution:Color the integers from 1 to N in such a way that if x divides y, they have different colors.
Minimize the number of colors used.

i simply cant understand
anyone explain please

4

The construction is correct, but intuition aside I hope you know why it always works (greedy coloring doesn’t work in a more general setup).

What don’t you understand?
The value A_i can be thought of as the color given to the index i, the rest of the statement is the same. (The colors being used are 1, 2, \ldots, C so minimizing C is of course the same thing as minimizing the number of colors.)

5

I did a solution which is inspired by the sieve of erasthothenes,
initialize everything to 1, then just loop from one 1 to n, with an inner loop looping from 2 * i with increments of i and then if the current value is equal to the i’th value (i.e a multiple of i has the same array value), just increment that.
it is O(nlogn), not just O(n^2) despite 2 loops because if you count the total number of iterations, you will get an expression involving the harmonic series (n/1 + n/2 + n/3…) = n(1+1/2+1/3…) = O(nlogn)
https://www.codechef.com/viewsolution/1072375101

6 
class Codechef {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t --> 0) {
		    int n = sc.nextInt();
		    solve(n);
		}
		sc.close();
	}
	private static void solve(int n) {
	    System.out.println(Integer.toBinaryString(n).length());
	    for (int i = 1; i <= n; i++) System.out.print(Integer.toBinaryString(i).length());
	    System.out.println();
	}
}

Can someone please help me understand where did I go wrong with my approach in this code?

7

Can someone tell what is the flaw in this submission: https://www.codechef.com/viewsolution/1072455989

8

Solution

Consider A is the output array (1-indexed).

Algorithm

  • A[1] = 1
  • A[i] = 2, if i is prime
  • A[i] = 3, if i is odd
  • A[i] = A[i/2] + 1, otherwise
9

If there are no other checks, this is obviously a problem: for example you’ll set A_9 = 3 and A_{27} = 3 which isn’t allowed.