Page 7 of 9

bigInt... Large base = more speed? (10023)

Posted: Wed Apr 25, 2007 1:13 am
I recently solved 10023 (sqrt) using a method described in the forms, and my bigInt class used base 10 digits, in a time of about 5 seconds -- It's seems pretty obvious too me, that if I had used a higher base (i.e. base 10^9) -- it would have greatly increased the speed of addition and subtraction, although it would have also made multiplication by 10 or 100 slower.. Also conversion to/from base 10^9 would be more difficult.... Would anyone like to comment on this?

Posted: Wed Apr 25, 2007 2:02 am
I don't see a reason why it should make multiplication significantly slower.

Posted: Sat Feb 16, 2008 11:44 am
Thanks. It's works. I also improved some functions, making it more efficient.

memset is useful!

/*
# Problem Verdict Language Run Time Submission Date
6236651 Square root Accepted C++ 1.490 2008-02-16 08:33:31
*/

Posted: Tue Feb 19, 2008 7:47 pm
I'm sorry. I forgot to change this line:

Code: Select all

`` FILE* fp=fopen("Input.txt","r"); ``
To:

Code: Select all

`` FILE* fp=stdin; ``
Everytime I need to make this change before submission.

However, I'm now using this:

Code: Select all

``````#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
#endif``````

Re: 10023 - Square Root why WA?

Posted: Tue Sep 02, 2008 10:40 am
i cant figure out any reason of WA.
has judge changed the input limit?

Code: Select all

``````#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
int main(){
int n;
long double Num;
scanf("%ld",&n);
while(n--){
scanf("%Lf",&Num);
printf("%.0Lf\n",sqrtl(Num));
}
return 0;
}``````

10023 - RTE

Posted: Wed Sep 03, 2008 11:13 am
Hi,
I'm newbie in Java...
since the BigInteger class is needed for this problem I wanted to use JAVA, but I'm getting RTE.. and I don't know why...please, give mea hand.

I'm using jdk 1.6 on Fedora 9 and everything works fine here

Code: Select all

``````import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);

Integer t,i;
BigInteger x,xant,error,n;
t = in.nextInt();
for ( ;t>0;t--){
n=in.nextBigInteger();
x=n.divide(new BigInteger("2"));
do{
xant=x;
x=x.subtract((func(n,x)).divide(dfunc(x)));
//error=(x.subtract(xant)).divide(x);
}while (xant.compareTo(x)!=0);
while ((x.multiply(x)).compareTo(n)==1){
x=x.subtract(new BigInteger("1"));
}
System.out.println(x);
}

in.close();
}
public static BigInteger func(BigInteger n,BigInteger x){
return n.subtract(x.multiply(x));
}
public static BigInteger dfunc(BigInteger x){
return x.multiply(new BigInteger("-2"));
}
}``````

Re: 10023 - RTE

Posted: Wed Sep 03, 2008 4:20 pm
Try changing

Code: Select all

``public class Main {``
for

Code: Select all

``class Main {``

I'm not sure if that is your problem, though.

Re: 10023 - RTE

Posted: Thu Sep 04, 2008 12:05 am
I have changed as you say...but still RTE..with time 0.0000

Re: 10023 - RTE

Posted: Thu Sep 04, 2008 2:28 am
Try this input:

Code: Select all

``````1
1``````

Re: 10023 - RTE

Posted: Thu Sep 04, 2008 2:55 am
Thanks!! andmej, that was de error...

now it's time to face the TLE I got

Re: 10023 - Square Root

Posted: Tue Nov 11, 2008 12:01 am
what is the problem in this code ?
i got WA in this problem..

#include<stdio.h>
#include<math.h>

int main()
{
long int n,i;

scanf("%ld",&n);

for(i=0;i<n;i++)
{
printf("\n");

long double x,y;

scanf("%Lf",&y);

printf("\n");

x=sqrt(y);

printf("%.0Lf\n",x);
}

return 0;
}

Re: 10023 - Square Root

Posted: Tue Nov 11, 2008 3:32 pm
long double is not precise enough for this problem.
It has only 64 bits of precision, while you actually need log_2(10^1000) ~= 3321 bits for this problem!

Re: 10023 - Square Root

Posted: Tue Nov 11, 2008 7:28 pm
But some of my friends had got Acc
think judge has fixed it.

Re: 10023 - Square Root

Posted: Tue Nov 11, 2008 8:09 pm
A few years ago a solution like yours was indeed accepted by the judge, because it had a very weak input file.

But now that's finally fixed, and you have no easy way to avoid coding bignums here.

Posted: Thu Jan 15, 2009 1:33 pm
I submitted around 50 submissions for this problem .
I am not able to get AC.
( FRUSTRATED NOW )
Why im getting WA ?
I checked by Random generator inputs of length greater than 100 also.

Code: Select all

``````#include <time.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long int LL;
#define ALL(s) (s).begin(),(s).end()
#define R(i,m,n)	for(i=m;i>=n;i--)
#define FF(i,m,n)	for(i=m;i<n;i++)
#define F(i,n)	FF(i,0,n)
#define VI vector<int>
#define PB push_back
void _reverse(char s[]){
int i=0,l=strlen(s)-1;
char ch;
while(i<l){
ch=s[i];
s[i]=s[l];
s[l]=ch;
i++;l--;
}
}

char* to_str(int x){
char* s;
int i=0;
while(x){
s[i++]=(char)(x%10+'0');
x/=10;
}
_reverse(s);
return s;
}

int to_int(char *s){
int i,l=strlen(s);
int k=0;
F(i,l)
k=10*k+(s[i]-'0');
return k;
}

const int MAX = 1100;
class HugeInt {
public:

// vars
char number[MAX];
int length;

// constructors
HugeInt() {
memset(number,0,sizeof(number));
length = 1;
}

HugeInt(int n) {
*this = n;
}

// operators
// takes 'r' as right number and writes result to 'this'
// *veryfied*
HugeInt* operator= (const HugeInt* r) {
memset(number,0,sizeof(number));
strcpy(number,r->number);
length = r->length;
return this;
}

// *veryfied*
HugeInt* operator= (const int r) {
memset(number,0,sizeof(number));
sprintf(number,"%d",r);
length = strlen(number);
for (int i = 0; i < (length >> 1); i++) {
char c = number[i];
number[i] = number[length-i-1];
number[length-i-1] = c;
}
for (int j = 0; j < length; j++)
number[j] -= '0';
return this;
}

// *veryfied*
const HugeInt operator+ (const HugeInt& r) {
int n = max(length,r.length), carry = 0, k, i;
HugeInt theNew;
for (i = 0; i < n || carry; i++) {
k = number[i] + r.number[i] + carry;
theNew.number[i] = k % 10;
carry = k / 10;
}
theNew.length = i;
return theNew;
}

// slightly veryfied
void operator+= (const HugeInt& r) {
*this = *this + r;
}

const HugeInt operator- (const HugeInt& r) {
int n = length, b = 0, k, i;
HugeInt theNew;
for (i = 0; i < n ; i++) {
if(number[i]-r.number[i]-b<0){
theNew.number[i] = 10 + number[i] - r.number[i] -b;
b=1;
}
else{
theNew.number[i] = number[i] - r.number[i] -b;
b=0;
}
}
for (; i < n ||b; i++) {
if(number[i]-b<0)
theNew.number[i] = 10 + number[i] -b;
else{
theNew.number[i] = number[i] -b;
b=0;
}
}
theNew.length = i;
truncate(theNew);
return theNew;
}

// slightly veryfied
void operator-= (const HugeInt& r) {
*this = *this - r;
}

// *slightly veryfied*
const HugeInt operator* (const int r) {
int i, k, carry = 0;
HugeInt theNew;
for (i = 0; i < length || carry; i++) {
k = number[i] * r + carry;
theNew.number[i] = k % 10;
carry = k / 10;
}
theNew.length = i;
return theNew;
}

// *slightly veryfied*
void operator*= (const int r) {
*this = *this * r;
//return this;
}

// shifts number left by 'shift' positions
// useful when multiplying two HugeInt's
HugeInt operator<< (const int shift) {
int i;
HugeInt theNew;
// don't shift if number is 0 and there is no number
//if (length == 0 || length == 1 && number[0] == 0) return;
for (i = length - 1; i >= 0; i--)
theNew.number[i + shift] = number[i];
for (i = 0; i < shift; i++)
theNew.number[i] = 0;
theNew.length = length + shift;
return theNew;
}

HugeInt operator* (HugeInt& r) {
int i;
HugeInt theNew = 0;
for (i = 0; i < length; i++)
theNew += (r << i) * number[i];
truncate(theNew);
return theNew;
}

HugeInt operator*= (HugeInt& r) {
*this = *this * r;
return *this;
}

int operator % (int r) {
int n = 0;
for (int i = length - 1; i >= 0; i--)
n = (n * 10 + number[i]) % r;
return n;
}

int operator %= (int r) {
return (*this % r);
}

HugeInt operator/ (int r) {
HugeInt I = 0;
int n = 0;
int j = 0;
for (int i = length - 1; i >= 0 || n >= r; i--) {
n = (n * 10 + number[i]);
I.number[j++] = n / r;
n %= r;
}

// reverse string
for (int i = 0; i < j / 2; i++)
swap(I.number[i],I.number[j-i-1]);
I.length = j;
truncate(I);

return I;
}

HugeInt operator /= (int r) {
return (*this / r);
}

// functions
// *veryfied*
void print() {
for (int i = length - 1; i >= 0; i--)
putchar(number[i] + '0');
}

void truncate(HugeInt& n) {
for (int i = n.length - 1; i >= 0 && n.number[i] == 0; i--)
n.length--;
if (n.length == 0) {
n.number[0] = 0;
n.length = 1;
}
}

HugeInt power(int p) {
HugeInt theNew = 1;
for (int i = 0; i < p; i++)
theNew *= *this;
return theNew;
}

bool operator<(const HugeInt& rhs) {
if (this->length != rhs.length)
return this->length < rhs.length;
for (int i = this->length-1; i >=0; i--)
if (this->number[i] != rhs.number[i])
return this->number[i] < rhs.number[i];
return true;
}

bool isnull() {
if (length == 1 && number[0] == 0) {
return true;
}
return false;
}

};

int main() {
int t,i,j,l,k,n;
HugeInt sm,ml,tmp,tmp2;
char ans[1000],s[1100],f[2];
scanf("%d",&t);
gets(f);
gets(f);
while(t--){
gets(s);
l=strlen(s);
if(l<2){
if(s[0]=='1')	printf("1\n");
else if(s[0]=='4')	printf("2\n");
else if(s[0]=='9')	printf("3\n");
else{
k=s[0]-'0';
printf("%.0lf\n",sqrt(1.0*k));
}
continue;
}
j=0;
sm = 0;
if(l % 2){
k=s[0]-'0';
ml=k;
i=1;
}
else{
k=10*(s[0]-'0')+(s[1]-'0');
ml=k;
i=2;
}
while(i<l){
k=1;
sm*=10;
tmp=sm+k;
tmp2=tmp*k;
while( tmp2 < ml){
k++;
tmp=sm+k;
tmp2=tmp*k;
}
k--;
ans[j++]=(char)(k+'0');
tmp=sm+k;
tmp*=k;
ml -= tmp;
ml*=100;
n=10*(s[i]-'0')+(s[i+1]-'0');
ml += n;
i+=2;
sm+=2*k;
}
k=1;
tmp=k;
sm*=10;
while( tmp2 < ml){
k++;
tmp=k;
tmp2=sm+tmp;
tmp2*=k;
}
k--;
ans[j++]=(char)(k+'0');
ans[j]='\0';
puts(ans);
if(t)	printf("\n");
}
return 0;
}

``````