Discussion @ 1001. Reverse Root @ Timus Online Judge

Newton Raphson instead of sqrt() but getting WA on test case 2 thanos 5 Aug 2017 18:22

#include<iostream>
#include <iomanip>
#include<vector>

int main(){
    long long num;
    std::vector<double> v;
    int count=0;
    while(std::cin>>num){
        if(num==0){
            v.push_back(num);
            }
    else{
    int i=0;
    double n=num/10;
    while(i<10000){
        n=n-(n*n-num)/(2*n);
        i++;
    }
    v.push_back(n);
    }

    }
    for(int i=v.size()-1;i>=0;i--)
        std::cout<<std::fixed<<std::setprecision(4)<<v[i]<<std::endl;
    return 0;
}

Re: Newton Raphson instead of sqrt() but getting WA on test case 2 Mahilewets 5 Aug 2017 19:56

Suppose you have no WA.

Then you might have 15000+ square roots by 10000 iterations each

(If pay attention there are maximum 256KB of numbers)

TLE for sure

Re: Newton Raphson instead of sqrt() but getting WA on test case 2 thanos 6 Aug 2017 10:30

Yup. I just realized it. But I think it converges to 4 decimal places much, much before 10000 iterations (say, like 300-400). Thanks for the help :)

Discussion of Problem 1001. Reverse Root