Sign in to follow this  
Concentrate

Frustrating problem.

Recommended Posts

So I am just practicing on my logic by trying to solve some code chef problems. The particular problem is this problem . I believe my solution should work, but however, it keeps telling me that its wrong. Maybe there is a special case or something that I forgot to cover. Any help should be greatly appreciated, because its really, really, and I mean really, frustrating me. Here is my attempt. I didn't comment because I think it should be straight forward.
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

typedef unsigned long long BigDataType;


bool isPalindrome(const string& value){
	int begin = 0;
	int end = value.size() - 1;

	while(begin < end){
		if( value[begin++] != value[end--] ) return false;
	}
	return true;
}
template<typename Type>
string convertToString(const Type& num){
	stringstream ss;
	(ss << num);
	return ss.str();
}

string getBase(BigDataType num, const unsigned int& toBase, const char * baseValue)
{	
	string baseNum = "";	
	while(num > 0){
		baseNum += baseValue[num % toBase];		
		num /= toBase;
	}
	std::reverse(baseNum.begin(), baseNum.end());
	return baseNum;
}


int main()
{		
	
	int numOfTestCases = 0;

	cin >> numOfTestCases;

	unsigned short *Answer = new unsigned short[numOfTestCases];
	unsigned short ansIndx = 0;

	const unsigned int MAX_BASE = 256;

	char baseValue[MAX_BASE];

	for(int i = 0; i < MAX_BASE; i++){
		baseValue[i] = char(i);
	}
	
	const BigDataType MAX = 10e10;

	while(numOfTestCases--)
	{
		BigDataType num;

		cin >> num;	
		if(num < 1 || num > MAX) 
			continue;

		for(unsigned int base = 2; base < MAX_BASE; ++base)
		{
			if(isPalindrome( getBase( num, base, baseValue ) ) ){
				Answer[ansIndx++] = base;
				break;
			}					
		}
	}
 
	for(int i = 0;i < ansIndx; i++){
		cout << Answer[i] << endl;
	}

	delete [] Answer;

	return 0; 
}


Feel like a noob.

Share this post


Link to post
Share on other sites
You are only checking bases up to 255. Did you try checking to see if there are any numbers that go over that?

Also, if you're only checking for palindromes, there's no need to reverse the string before checking it. (Not that this affects the correctness of the code.)

Share this post


Link to post
Share on other sites
You could use a vector of ints.

Here's a modification of your code. I didn't test it, but it should give you the right idea.


typedef unsigned long Uint32;

bool IsPalindromeInBase(BigDataType num, Uint32 base)
{
std::vector<Uint32> thestring;

while(num > 0)
{
thestring.push_back(num % toBase);
num /= toBase;
}

for( Uint32 i =0; i < (thestring.size() - i); ++i)
{
if ( thestring.at(i) != thestring.at(thestring.size() - i) )
{
return false;
}
}

return true;
}



Share this post


Link to post
Share on other sites
so you are suggesting that I should store a vector of ints instead of an array
of chars, and work with them the same way as I did with the chars?

What if the num % base return a 2 digits of greater number, then how will that
work?

Share this post


Link to post
Share on other sites
A quick search of Wikipedia didn't turn up anything particularly interesting, although it did confirm that some numbers do require bases larger then 255 to be palindromic. For example, 263 is not palindromic in any base below 262.

I doubt that there is any particular algorithm for this. Anyway, with small numbers like 10^10, it should be instantaneous on any modern processor.

It's only once you start using bignums that it becomes slow.

Share this post


Link to post
Share on other sites
I need a second opinion. Can you check if there is something I can do better?

Here is what I have so far :

#include <iostream>
#include <string>
#include <deque>

using namespace std;

typedef long long BigDataType;


#define DEBUG 1


#if (DEBUG )
#include<ctime > // for time
#endif

bool isPalindromeInBase(BigDataType num, const unsigned int& newBase)
{
std::deque<unsigned int> baseNum;

float inverseBase = 1.0f/newBase;

while(num > 0){
baseNum.push_back(num % newBase);
num *= inverseBase;
}

int begin = 0;
int end = baseNum.size() - 1;

while(begin < end){
if( baseNum[begin++] != baseNum[end--] )
return false;
}

return true;
}


int main()
{

int numOfTestCases = 0;

if(DEBUG)
numOfTestCases = 10;
else
scanf("%d", &numOfTestCases );

unsigned short Answer[1100];

unsigned short ansIndx = 0;

const BigDataType MAX = 10e10;

unsigned long base = 2;

while(numOfTestCases--)
{
BigDataType num;

if( DEBUG )
num = rand()*(MAX - 1) + 1;
else
scanf("%lld", &num );

while(!isPalindromeInBase(num,base) ){
base++;
}
Answer[ansIndx++] = base;

if( DEBUG ){
cout <<num << " is palindrome at base : " << Answer[ansIndx - 1] << endl;
}

base = 2; //reset
}

if(! DEBUG )
for(int i = 0; i < ansIndx; i++){
printf("%lu\n", Answer[i]);
}


return 0;
}




I was using scanf and printf for faster speed. Plus, I never used the #define DEBUG method before, hope I am using it correctly.

Share this post


Link to post
Share on other sites
This can be solved without external storage (queue, vector, etc...).

Given number N in base B, how many digits are needed to represent it (it has to do with logarithms)? How does this help you determine what the individual digits are?

What is palindrome? Consider B=10 and N=2112

There are 4 digits, so multipliers will be 1, 10, 100 and 1000. To test for palindrome, test
- (2)112 (digit 4, mutliplier 1000) == 211(2) (digit 1, multiplier 1
and
- 2(1)12 (digit 3, multiplier 100) == 21(1)2 (digit 2, multiplier 10).

Same thing for other bases.

Think about how you would implement this generically. You need a way to find out how many digits are needed to represent number N in base B, and how to calculate any given digit in base B.

Share this post


Link to post
Share on other sites
I think a puzzle of these types of sites are meant to be solved by the person, who tries to solve it, so what's the point of having it solved by others? Where's the fun? Or is it for money? Then where's the helpers' percentage?


Shit, I just cannot make the first sentence to make sense.

Share this post


Link to post
Share on other sites
>>This can be solved without external storage (queue, vector, etc...).

Through some trial, I find that the number of digits needed to represent a number
from base A, to number in base B is calculate by :

int maxDigNeeded = ceil(log( double(num) ) / log ( double(newBase) ));



>>Given number N in base B, how many digits are needed to represent it (it has to do with logarithms)? How does this help you determine what the individual digits are?

What is palindrome? Consider B=10 and N=2112

There are 4 digits, so multipliers will be 1, 10, 100 and 1000. To test for palindrome, test
- (2)112 (digit 4, mutliplier 1000) == 211(2) (digit 1, multiplier 1
and
- 2(1)12 (digit 3, multiplier 100) == 21(1)2 (digit 2, multiplier 10).

Same thing for other bases.

Think about how you would implement this generically. You need a way to find out how many digits are needed to represent number N in base B, and how to calculate
any given digit in base B.

I see what you did. But how I am not sure this palindrome checker will help
enough.

>>I think the problems of these types of sites are meant to be solved by the person, who tries to solve it, so what's the point of having it solved by others? Where's the fun? Or is it for money? Then where's the helpers' percentage?

True,but I asked for helpful hints, and some theories that I may not know of
for this particular subject. I did not ask for the blatant solution. In fact
they show the solution of other already, so if I just wanted the points from
them, I would just hand in their solution. Its not for money. There is no
helpers' percentage.

Share this post


Link to post
Share on other sites
Quote:
Original post by Concentrate
In this code :


while(num > 0){
baseNum.push_back(num % newBase);
num *= inverseBase;
}


You think we can check( if palindrome) while converting( to radix r )?



Why on earth are you storing the reciprocal of the base as a floating point and multiplying by that?

With floating points, you'll get rounding errors and loss of significance. It will make your program give incorrect results!
Plus it doesn't actually make it any faster. In fact, switching to floating points probably makes it slightly slower.

Share this post


Link to post
Share on other sites
Thanks. Do you think this brute force can be improved :

while(!(isPalindromeInBase(num,base)) ){
base++;
}


Checking from base 2 to base n, is really not good. I am trying some stuff,
but can't think of anything.

Share this post


Link to post
Share on other sites
Quote:
Original post by Concentrate

I see what you did. But how I am not sure this palindrome checker will help
enough.


This is not a hard problem per-se, it's more about exploring different ways of implementing same algorithm.

Here is a solution without storage.
#include <cmath>
#include <cstdio>

typedef int num_t;

// test pairs of digits for equality
// 5115, test outer 5 and 5, then inner 1 and 1
void test(num_t val) {
// check bases from 2 to val-1 inclusively
// val is biggest base in which val can be represented
for (num_t base = 2; base < val; base++) {
// right cursor is always right-most digit
num_t right = 1;
// left cursor is left-most digit
num_t left = (num_t)pow((double)base, floor(log((double)val) / log((double)base)));

// check if current left and right digits are same
while ((val / left) % base == (val / right) % base) {
// move cursors inward
left /= base;
right *= base;

if (left <= right) {
// if cursors met, all pairs were equal, it's a palindrome
// if cursors point to same digit, number of digits is odd (919), and it's a palindrome
printf("%d\n", base);
return;
}
}
// not a palindrome, try next base
}
}

int main ()
{
num_t val;
while (scanf("%ld", &val) == 1) test(val);
}

Comments make it look larger than it really is.

The basic idea is:
- convert number into specific base (implicitly done in calculations)
- set cursors to left and right most digit
- while digits at cursors are equal
-- move cursors inward
-- if cursors meet, it's a palindrome


There might be other rules that could be exploited, for example, if a number in some base is not palindrome, then it cannot be in other, larger bases either.

Implementing that is annoying though, since one would need some library that deals with large ints. There is some literature on doing base conversions between arbitrary numbers.

Share this post


Link to post
Share on other sites
Believe or not, my algo before this was similar to that( maybe not as good), but
it still ran over the time limit. There is about 1000 test cases of number ranging from 1 to 10^10 so I am guessing that its the checking from base 2 to base n, is
where they expect us to improve, I think.

Do you think, certain types of numbers, like primes and so might have a higher
palindromic base?

Share this post


Link to post
Share on other sites
Quote:
Original post by Storyyeller
I just registered at CodeChef for fun and got 1.69 seconds.

Here's a hint. Think about what possible values the base can be in order for n to be a palindrome.


Thanks for rubbing it in, lol.

I'll think about it tomorrow.

Share this post


Link to post
Share on other sites
>>Here's a hint. Think about what possible values the base can be in order for n to be a palindrome.

Is this true :

Let testNumber = random( 1 , 10e10 );

Then if sqrt( testNumber ) does not have the smallest base, then 2*sqrt(test)
number also does not the smallest base?

Share this post


Link to post
Share on other sites
The algorithm I came up with is based on the observation that if
b>=sqrt(n), then b=n/a - 1 for some integer a.


#include <iostream>
#include <vector>

typedef unsigned long Uint32;
typedef unsigned long long Uint64;

const Uint32 MAXVECTORSIZE = 35; //Enough to hold 10^10 in binary

std::vector<Uint32> digits;

bool IsPalindromeInBase(Uint64 n, Uint32 base)
{
digits.clear();

if (n % base == 0) {return false;}

while (n>0)
{
digits.push_back( n % base );
n /= base;
}

for (int i=0; i < (digits.size() - i - 1); ++i)
{
if (digits[i] != digits[digits.size() - i - 1])
{
return false;
}
}

return true;
}

Uint64 GetSmallestBase (Uint64 n)
{
Uint32 base;

//Edge cases
if (n==1) {return 2;}
if (n==2) {return 3;}

for (base = 2; ((Uint64) base) * base < n; ++base)
{
if (IsPalindromeInBase(n,base))
{
return base;
}
}

--base;
if ( ((Uint64) base) * (base + 1) >= n)
{
--base;
}


for (Uint32 a = base; a>= 2; --a)
{
if (n % a == 0)
{
return n/a - 1;
}
}

return n - 1;
}

int main()
{
int numtests;

digits.reserve(MAXVECTORSIZE);

std::cin >> numtests;

for (int i=0;i<numtests;++i)
{
Uint64 nexttest;
std::cin >> nexttest;
std::cout << GetSmallestBase(nexttest) << '\n';
}
}


Share this post


Link to post
Share on other sites
>>The algorithm I came up with is based on the observation that if
b>=sqrt(n), then b=n/a - 1 for some integer a.

how did you observe that? It doesn't seem like its a common thing to observe.

Can you explain please?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this