Number of factors

Lets discuss another problem on codechef of medium difficulty NUMFACT

The problem says you are given n numbers and you have to return the total number of factors of the product of given n numbers.

So the problem consists of two problems:

  1. Given a number return all the prime factors. If prime factors are known other factors can be calculated.
  2. Given all prime factors of n numbers, return count of factors of the products of those n number.

Lets first solve 2nd problem

Lets assume we are given 2 numbers 6 and 10, so we need to return count of factors of 10*6 =>60.

6 => 2*3

10=> 2*5

60=> 22*31*51

factors of 60 are:

1(203050), 2(213050), 3(203150), 5(203051), 4(223050), 6(213150), 10(213051), 12(223150), 15(203151), 20(223051), 30(213151), 60(223151)

Now you might have guessed the result. To get the factors of a number we have to choose the coefficient of the prime factors. In case of 1, we chose to not choose any factor, in case of 12, we chose to choose 2 twice and 3 once and not choose 5.

So in how many ways we can do this choosing stuff is the total number of factors. We can do choosing in “product of all factors coefficient’s next number” ways. So for the above example (2+1)(1+1)(1+1)=>(3)(2)(2)=>12 ways

Now lets shift to the first problem. How to determine number of prime factors of a number along with its coefficients.

Since the number given can’t be more than 1000000, we know that it’s factor can be more that 10000001/2 => 1000. That means we just need to check whether numbers less than or equal to 1000 are factors of given number are not. In fact we should just check for prime factors less than or equal to 1000.

To compute prime numbers less than 1000.

  1. one simple approach would be that for each number(lets say x) less than 1000, start with 2 and check and go till x1/2 and see whether this number divides that number or not. If we get any number till x1/2 which divides x then x is not prime, if we don’t get any number then x is a prime.
  2. A better approach would be to create an array of 1000 elements(lets name isPrime) all element initialized to true, then start with i =2 and change all its multiple to false. Again start with i=3 and change all its multiple to false, again start with i=4 but since i=4 is already false don’t do any thing for this i and so on….

 

Mixtures

Today lets discuss about another problem named Mixtures.

The problem maps to the below problem:

You are given an array of n numbers and you are allowed to add any two adjacent numbers at a time, such that the result produced is sum of the two added elements mod 100, and the cost of doing the addition is product of the two added elements. You are required to give the combination such that cost is minimized.

Solution: If we think about the problem it looks like a math problem which says you are given a1a2….an-1an and you need to add them together such that addition result is ai+aj/100 and cost is ai*aj, and you are told to return the combination with minimum cost.

Can it be done in O(N)?

I don’t know. But lets first go naive. Lets first discuss in how many ways the mixing/addition can be done. After little bit of thinking the problem maps to permutation/combination problem.

You can choose your first element out of n elements in n ways, and after choosing first element the next element you want to mix it with can be chosen in 2 ways since the two added element should be adjacent. After the process you will be remained with n-1 elements, again going with similar logic the process can be done in 2*(n -1) steps and so on till the array remains with one element. So the entire process with take 2*n + 2*(n-1) + ….. + 2*1 steps => n*(n-1) steps.

Now if you see the limit of n in the problem, it says n can go till 100. That means any algorithm till O(N3) is okay for us.

The Next Palindrome

Lets look into another problem of codechef of Medium difficulty. The next palindrome

The problem is you are given a number and you need to return a palindrome just greater than that number. As you all know palindrome number is a number whose reversal(from end to start) is the same number. 121, 1331, 25452 are some examples of palindrome numbers.

So if you are given a number say 120 and you need to give a palindrome just bigger than that number, you now know the answer, it is 121.

But now the question is how to pro grammatically gets the answer. So lets try out.

lets say our given number k is a1a2a3a4a5…..an-1an, now since a1 is the most significant bit we would try to avoid changing it as much as possible but we can change an since it is least significant bit.

so for cases where a1a2a3..an..an-1an < a1a2a3…an/2..a2a1, a1a2a3..an/2..a2a1 is the palindrome. eg. 135 214 < 135 531 so for k = 135 214, 135 531 is the required palindrome.

But for cases where  a1a2a3..an..an-1an > a1a2a3…an/2..a2a1, a1a2a3..an/2..a2a1 is not the required palindrome because it is lesser. Lets divide the number in two halves..

135867 => 135    867

we can change 7 to 1 and 6 to 3 => 135 831 and change 5 and 8 to 6. => 136 631

but what if 5 was 9 and also 8 was 9 139967 => 139 967

we can change 7 to 1 and 6 to 3 => 139 931, now since 139931 < 139967 we need to change 9 to 10 reflecting the similar effect in other 9 of second half

13(10) 967  => 140 967 =do mirror imaging=>140 041

so for even digit numbers algo goes like this,

if an/2 < an/2+1

then increment an/2 to an/2+1 and forward the carry if there is any.

end if

do mirror imaging  of a1a2..an/2 to an/2+1…an-1an

Now for odd digit numbers algo goes like this,

if an-1/2 < an+1/2 +1

then increment an+1/2 by 1 and forward the carry if there is any.

end if

do mirror imaging  of a1a2..an-1/2 to an+1/2+1…an-1an

// thenextpalindrome.cpp : Defines the entry point for the console application.
//
#include <iostream>
using namespace std;

#include<stdio.h>
#include<string.h>
#define S(a,x) scanf("%"#a,&x) //#a expands to "a" we use this bcoz, arguments are not replaced within quoted strings
#define PS(a,x) printf("%"#a" ",x) //print with space
#define PN(a,x) printf("%"#a"\n",x) //print with newline
#define FOR(i,a,b) for( i=a;i<b;i++)
#define FORD(i,a,b) for( i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)
#define Max(a, b) ((a>b)?a:b)
#define Min(a, b) ((a>b)?b:a)
#define MAXSIZE 1000001

int main()
{
int n,i, flag;
bool flag9 = true; // true if all 9s
char s[MAXSIZE];
S(d, n);
while (n--)
{
flag = 0; flag9 = true;
S(s, s);
// case 999999..
int len = strlen(s);
FOR(i, 0, len)
{
if (s[i] != '9')
{
flag9 = false;
break;
}
}
if (flag9)
{
cout << "1";
FOR(i, 0, len-1) cout << "0";
cout <<"1"<< endl;
}
else
{
FOR(i, 0, len/2)
{
if (s[i] < s[len - 1 - i])
{
flag = -1;
}
else if (s[i]>s[len - 1 - i])
{
flag = 1;
}
s[len - 1 - i] = s[i];
}
if (flag == 0 || flag == -1)
{
int current = (len - 1) / 2;
while (s[current] == '9')
{
s[current] = '0';
s[len - 1 - current] = s[current];
current--;
}
s[current]++;
s[len - 1 - current] = s[current];
}
PN(s, s);
}
}
return 0;
}

It sometimes gets very irritating when you get so many wrong answers and you are committed to solving the problem without seeing other’s solutions. Even if you see other’s solution you sometimes are not able to figure out what mistake you have done because of which your solution is not getting accepted. Basically you are striving for the testcases which are not passing in your case. Next time we will try to see how to find out those test cases programmatically.

We will write an algo which uses two solution files (one written by you which is not getting accepted and the other written by someone else and is getting accepted) and it runs both the files to find the conflicting tests.

Closing the tweets

Lets begin by solving one moderate level programming question on codechef. Please go through the question once.

Now if you have gone through the question, it basically maps to a problem that says there is an array sort of thing which is of type bool (initialized with false) and the user has the option to toggle it on/off and also there is one button to set all to false. Now with each attempt of user doing his input job you have to say how many bools are on/true in the array.

HINT: since the array is just 1000 size long even any algo of time complexity N is also fine.

Read the size of array vs time complexity relation here

Copying here just for your reference.

  • when N <= 10, then both O(N!) and O(2N) are ok (for 2N probably N <= 20 is ok too)
  • when N <= 100, then O(N3) is ok (I guess that N4 is also ok, but never tried)
  • when N <= 1.000, then N2 is also ok
  • when N <= 1.000.000, then O(N) is fine (I guess that 10.000.000 is fine too, but I never tried in contest)
  • finally when N = 1.000.000.000 then O(N) is NOT ok, you have to find something better…

SOLUTION:

Since it is clear that any algo with O(N2) complexity with work here.

What we will do is on every entry we will update the array which in case of click x will take o(1) time since x index can be reached in constant time, where as operation close all will take o(n) since we need to go to every index of array to update the element. After each entry we will also update our currentActive variable which stores the number of true bools of array.

So in worst case it will take  O(N2) time where each entry is closeall.

CODE:

// closethetweets.cpp : Defines the entry point for the console application.
//

#include
#include
using namespace std;

#include
#include
#define S(a,x) scanf("%"#a,&x) //#a expands to "a" we use this bcoz, arguments are not replaced within quoted strings
#define PS(a,x) printf("%"#a" ",x) //print with space
#define PN(a,x) printf("%"#a"\n",x) //print with newline
#define FOR(i,a,b) for( i=a;i<b;i++) #define FORD(i,a,b) for( i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)
#define Max(a, b) ((a>b)?a:b)
#define Min(a, b) ((a>b)?b:a)
#define MAXSIZE 1010

int main()
{
int n, k, num;
int currentActive = 0;
bool arr[MAXSIZE] = { 0 };
S(d, n);
S(d, k);
char s[15];

while (k--)
{
S(s, s);
if (!strcmp(s, "CLICK"))
{
S(d, num);
num--; //0 based index
arr[num] = !arr[num]; //toggle
if (arr[num])
currentActive++;
else
currentActive--;
}
else
{
currentActive = 0;
memset(arr, 0, n + 1);
}
PN(d, currentActive);
}
return 0;
}

Lets begin problem solving

In this section and onwards I am going to explain and step by step solve some problems related to algorithms which will be very helpful if someone wants to sit in IT company interviews and/or want to compete in programming contest.

REQUIREMENT: you should have basic understanding of C/C++ as well as moderate understanding of data structures. Remembers this is not going to be a basic course. You should be decent in programming to go forward with this tutorial.