SRM 440 div-1 Hard (SquareFreeSets)

Problem Link

The problem in short:

A square-free number is an integer that is not divisible by the square of any integer except 1. A set containing only square-free numbers is called a square-free set. The product of such a set is the product of all its elements. If the product of a square-free set is a square-free number itself, that set is called a perfect set.

You are given two ints N and K. Determine the number of perfect square-free sets that contain between 1 and K elements, inclusive, where each element is between 2 and N, inclusive. Return this number modulo 1,000,000,007.

Some observations:

1. In the prime factorization of a square-free number, each of it's prime factors occurs exactly once.
2. There are 95 prime numbers smaller than 500. So, the size of a perfect square-free set can't exceed 95.
3. There are only 8 primes {2,3,5,...,19} smaller than the square-root of 500.
4. In the prime factorization of any integer x, there can be at most 1 prime, which is greater than sqrt(x).
5. So, in the prime factorization of a square free number x <= 500, at most one prime p > 19, can exist.

The Dynamic Programming Solution:

Divide the numbers (1 to N) into buckets. Let, LP(x) be the largest prime factor of x. Two numbers x and y will be kept in the same bucket if and only if LP(x) = LP(y). Note that, in a perfect square-free set, no 2 elements will be from the same bucket.

Lets define dp[i][len][mask] to be the the number of perfect square-free sets of size 'len' and the elements are taken from the buckets 0,1,...i. 'mask' is a bit-mask that represents which of the 8 primes are already used. The rest is easy!

Here is the code that I submitted in the practice room:

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))

const LL mod = 1000000007;
             
vector<pii> buck[505];
vector<int> primes;

bool is[505];
int smallPrimes[] = {2,3,5,7,11,13,17,19};
int pos[25];

void precalc(int n)
{
for(int i = 0; i < 8; ++i)
pos[smallPrimes[i]] = i;

for(int i = 2; i <= n; ++i)
{
 bool isSqFree = true;
 int temp = i, mask = 0;

 for(int j = 2; j*j <= temp; ++j)
 {
  int cnt = 0;
 
  while(temp%j==0)
  {
   temp /= j;
   ++cnt;
  }
 
  if(cnt)
  {
   mask|=(1<<pos[j]);
  }
 
  if(cnt>1)
  {
   isSqFree = false;
  }
 }

 if(temp > 1 && temp*temp<=n)
 {
  mask |= (1<<pos[temp]);
 }

 if(isSqFree)
 {
  buck[temp].push_back(pii(i,mask));
 }

 if(temp==i)
 {
  primes.push_back(i);
 }
}
}

LL dp[100][100][1<<8];

LL F(int i, int len, int mask)
{
if(len == 0) return 1;

if(i < 0) return 0;

LL& ret = dp[i][len][mask];
int p = primes[i];
if(ret>-1) return ret;

ret = F(i-1,len,mask);

FOR(j,buck[p].size())
{
 if((buck[p][j].second&mask)==0)
 {
  ret = (ret + F(i-1,len-1,mask|buck[p][j].second))%mod;
 }
}

return ret;
}

int calc(int k)
{
if(k > primes.size())
k = primes.size();

CLR(dp,-1);
LL ret = 0;

for(int len = 1; len <= k; ++len)
{
 ret = (ret + F(primes.size()-1,len,0))%mod;
}

return (int)ret;
}

class SquareFreeSets {
public:
int countPerfect(int N, int K) {
 precalc(N);
 return calc(K);
}
};

On MMOD29 (SPOJ)

Yesterday I solved this problem.
You can find a nice analysis of the solution here.

A Modified Version:

Find the multiplication of all the divisors of (2004)^x modulo 29

is it possible ?

This question arose in my mind recently, while working on a similar problem:

Given an integer array A with n integers. R is an array of size n where R[i] denotes the number of distinct j, such that i < j and A[i] ≥ A[j]. Is it possible to calculate R in O(n) time?

The Answer:

This is not possible in the general case. Because, if it was possible, then we could have designed an O(n) sorting algorithm for arbitrary integer arrays in the following way:

Lets assume that it is possible to compute the array R in O(n) time. Note that, in that case, it would also be possible to compute another similar array L of size n, where L[i] denotes the number of distinct j, such that i > j and A[i] ≥ A[j].

Now, L[i]+R[i] is the number of distinct j such that, i ≠ j, and A[j] ≤ A[i]. This tells us, for each i, where to place the number A[i] in the sorted array and sort A in O(n).

Question:

Is it possible to solve the task in O(n) time, if the numbers in A are small positive integers (say ≤ 1000).

A Problem From The Sixth IMO (1964)

I am passing a very busy time because of my undergraduate thesis!

But still I managed to solve this really entertaining problem from the sixth IMO:

Problem Description:

Each of 17 students talked with every other student. They all talked about three different topics. Each pair of students talked about one topic. Prove that, there are three students that talked about the same topic among themselves.

An obvious way to restate the problem is:

Given a complete graph with 17 nodes. Each edge is colored with one of three colors. Prove that, there exists a triangle (i.e. cycle of length 3) such that, all three edges are colored with the same color.

Initially I had no idea how to attack the problem. I started drawing a complete graph with 17 nodes which turned out to be a jungle of edges! So, I had to simplify the problem somehow to make it more accessible. Now, what makes the problem hard ? Clearly, the size 17 is a bit too high to draw some graphs and try to understand what happens when we color the edges.

So, I came up with the following simpler problem, by solving which, I got the required insight to solve the original problem.

The Simpler Problem:

Given a complete graph with 6 nodes. Each edge is colored either red or blue. Prove that, there exists a triangle with all three edges colored with the same color.

Now, this problem is more accessible in a sense, because it is easier to draw a complete graph with 6 nodes and color the edges with 2 colors and try to understand what happens.

How did I come up with these numbers, 6 nodes, 2 colors ? Well, I drew a few complete graphs with 4 nodes, 5 nodes and then 6 nodes and found that, I could not color the 6-node-graph with 2 colors without creating a critical triangle (lets denote those single-colored-triangle by this name)

A Journey to the solution of "the simpler problem":

I kept experimenting with this smaller problem and the following observations emerged one by one:

1. If edge (a,b) and (a,c) are colored red then, edge (b,c) must be colored blue (if we want to avoid creating critical triangles)
2. if edge (a,b) and (a,c) are colored red and edge (c,d) and (b,d) are colored blue then, we are in a situation where critical triangle is unavoidable, whether we color the edge (b,c) red or blue.
3. if all of the edges (a,d), (b,d) and (c,d) are colored red, we cannot avoid a critical triangle, because, coloring any one of the edges (a,b), (b,c) or (c,a) with color red will create a red triangle and coloring all of them with color blue will create a blue triangle.

The last observation is the most important one! Because, it is easy to show that, this circumstance is unavoidable in case of 6 nodes and 2 colors. Why?

As the graph is a complete graph of 6 nodes, every node will have 5 edges adjacent to it. If we color those 5 edges with 2 colors, then by the pigeonhole principle, at least 3 edges will have the same color. And we are done, because this is the situation of the above image! The simpler problem is solved! And, this has provided us with an insight and a technique that will be directly useful in the solution of the actual problem.

So, here is the solution to the main problem:

Here, the complete graph has 17 nodes and we have 3 colors to color the edges. Any node u has 16 edges adjacent to it. By the pigeonhole principle, at least 6 of those edges will have the same color (say, red). denote the nodes on the other side of those edges to be v₁, v₂ ... v₆. Note that, we cannot color any of the edges-among-them red because, this will create a red triangle. So, the edges among v₁, v₂ ... v₆ must be colored with the other 2 colors! And Here We Are! This is exactly the smaller version of the problem (6 nodes, 2 colors) that we have solved earlier.
Note that, instead of describing the final solution formally in mathematical language, I have tried to describe the way I have attacked the problem. This is because, that is the real-fun-part of problem-solving!

An Easy Exercise:
Find the minimum number of nodes of a complete graph, for which there always exists a critical-triangle (defined earlier) if we color the edges with four colors.

Answer to the Tilling-Puzzle Question

Today I am going to post the stunningly simple answer to the unanswered question from my last post. I couldn't solve it myself. So, I just saw the solution.

The Question was,
If you are given an 8x8 chessboard and infinite supply of (1 x 3) and (3 x 1) tiles, is it always possible to tile the chessboard using some of these tiles, if the position of the single uncovered cell is specified?

The Beautiful Answer:


Let's number the (8 x 8) board like the figure above. Here, we have 21 cells numbered 2, 21 numbered 3 and 22 numbered 1. A single tile covers three different numbers. So, the board cannot be covered if the uncovered cell is specified to be a cell with a 2 or 3 on it.

This beautiful technique of proof is known as Coloring Proof (here, 1, 2 and 3 represents three different 'colors')

The answer doesn't imply that, we are always safe with an uncovered-cell with an 1 on it. So, here is another question:
Which of these cells-containing-an-1 are safe to be kept uncovered ? (here, 'safe' means, it is still tillable).

Let's try to answer to the opposite question, "Which of these cells-containing-an-1 are not safe to be kept uncovered?"

Note that, the top-left cell contains an 1 but it is still an unsafe cell because, it is equivalent to the top-right cell containing a 2 ( the mirror reflection of this board has a 2 on the top-left cell ).

So, we might claim that, those cells that contain 1, both before and after the reflection of the board along the x-axis or y-axis, are safe to be kept uncovered.

There are four such cells. If we number rows and columns with numbers 1 to 8 then those safe cells are (3,3), (3,6), (6,3) and (6,6). Because of the symmetry of the board, proving the safety for one of these cells would prove for all four. And, we have already proved it for cell (3,6) in the previous post ( the solution image ).