A Challenging High-Precision Bit Compression Problem#
Problem#
From the exam on 1.28
High-Precision Square Root Calculation [Easy]#
Description#
As the title suggests
Input#
An integer N.
Output#
The integer square root of N, rounded down.
Sample Input 1#
1
Sample Output 1#
1
Hint#
For 100% of the data, 0 < N <= 10^1000.
Analysis#
First of all, when I saw the word "Easy" in the title, I knew that this is an easy problem things are not that simple.
I initially wrote a normal high-precision algorithm.
Later, I found out that each test case has 1000 digits...
So bit compression is needed, of course, I didn't know how to do it at first. Two days later, I finally figured it out!
Code (Algorithm)#
#include<bits/stdc++.h>
#define LL long long
#define max(a,b) ((a)>(b))?(a):(b)
#define min(a,b) ((a)<(b))?(a):(b)
#define p 8//Number of bits to compress
using namespace std;
const LL MAXN=3005;
const string scarry="100000000";
struct bigNum{
private:
LL t[MAXN],siz;
public:
bigNum(string s){
memset(t,0,sizeof(t));
siz=0;
LL len=s.size();
string tmp;
tmp.resize(p);
while(len>=p){
for(LL i=0;i<p;++i){
tmp[i]=s[len-p+i];
}
++siz;
for(LL i=0;i<tmp.size();++i){
t[siz]+=tmp[i]-'0';
if(i<tmp.size()-1){
t[siz]*=10;
}
}
len-=p;
}
if(len){
tmp="";
tmp.resize(len);
for(LL i=0;i<len;++i){
tmp[i]=s[i];
}
++siz;
for(LL i=0;i<tmp.size();++i){
t[siz]+=tmp[i]-'0';
if(i<tmp.size()-1){
t[siz]*=10;
}
}
}
}
bigNum(void){
memset(t,0,sizeof(t));
siz=1;
return;
}
bigNum(LL x){
memset(t,0,sizeof(t));
char tmp[3005];
siz=0;
while(x){
tmp[++siz]=x%10+'0';
x/=10;
}
*this=(string)tmp;
return;
}
void print(void){
printf("%d",t[siz]);
for(LL i=siz-1;i>=1;--i){
char tmp[]="%00d";
tmp[2]=p+'0';
printf(tmp,t[i]);
}
putchar('\n');
}
LL size(void){
return siz;
}
friend bigNum operator -(bigNum a,bigNum b){
if(a==b)return (bigNum)0;
if(a<b)swap(a,b);
bigNum c;
LL jw=0;
LL len=max(a.size(),b.size());
for(LL i=1;i<=len;++i){
c.t[i]=a.t[i]-b.t[i]-jw;
if(c.t[i]<0){
jw=1;
c.t[i]+=carry;
}
else jw=0;
}
while(c.t[len]==0){
--len;
}
c.siz=len;
return c;
}
friend bigNum operator +(bigNum a,bigNum b){
bigNum c;
LL jw=0;
LL len=max(a.size(),b.size());
for(LL i=1;i<=len;++i){
c.t[i]=a.t[i]+b.t[i]+jw;
if(c.t[i]>=carry){
jw=1;
c.t[i]-=carry;
}
else jw=0;
}
if(jw){
c.t[++len]=1;
}
c.siz=len;
return c;
}
friend bigNum operator*(bigNum a,bigNum b){
bigNum c;
LL len=a.siz+b.siz;
for(LL i=1;i<=a.siz;i++){
for(LL j=1;j<=b.siz;j++){
c.t[i+j-1]+=a.t[i]*b.t[j];
c.t[i+j]+=c.t[i+j-1]/carry;
c.t[i+j-1]%=carry;
}
}
while(len>0 && c.t[len]==0)len--;
c.siz=len;
return c;
}
friend bigNum operator/(bigNum a,int b)
{
bigNum c;
LL g=0;
for(int i=a.siz;i>0;--i){
g=g*carry+a.t[i];
c.t[i]=g/b;
g%=b;
}
c.siz=a.siz;
while(c.siz>1&&c.t[c.siz]==0)c.siz--;
return c;
}
friend bool operator ==(bigNum a,bigNum b){
if(a.siz!=b.siz){
return 0;
}
for(LL i=1;i<=a.siz;++i){
if(a.t[i]!=b.t[i]){
return 0;
}
}
return 1;
}
friend bool operator <(bigNum a,bigNum b){
if(a.siz!=b.siz){
return a.siz<b.siz;
}
for(LL i=a.siz;i>=1;--i){
if(a.t[i]<b.t[i]){
return 1;
}
if(a.t[i]>b.t[i]){
return 0;
}
}
return 0;
}
friend bool operator <=(bigNum a,bigNum b){
return !(a>b);
}
friend bool operator >(bigNum a,bigNum b){
if(a.siz!=b.siz){
return a.size()>b.size();
}
for(LL i=a.size();i>=1;--i){
if(a.t[i]>b.t[i]){
return 1;
}
if(a.t[i]<b.t[i]){
return 0;
}
}
return 0;
}
friend bool operator >=(bigNum a,bigNum b){
return !(a<b);
}
};
int main(void){
string s;
cin>>s;
bigNum n(s);
bigNum l(1),r=n,mid,ans,yi("1");
while(l<=r){
mid=(l+r)/2;
if((mid*mid)>n){
r=mid-yi;
}
else{
ans=mid;
l=mid+yi;
}
}
ans.print();
return 0;
}
It turns out to be over 200 lines long.
It's comprehensive (not really), except for the lack of high-precision division...
After writing it, it kept giving wrong answers, and I couldn't find any issues even when testing it...
It turns out that it was a problem with the test cases (facepalm)
