Can Someone Help Me With Newton's Coding Challenge Solutions?

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Hi guys,

I gave the Newton's coding challenge held today and could solve only 4, I got 15+ WAs on 5th and couldn't solve the 6th problem. Can anyone please tell me the solution for the last problem and if possible tell me the error in my code for 5th problem?

Also feel free to use the comment section to discuss other solutions as well.

Please visit this link to see a screenshot of the problem statement of P5

My Code For P5

//Nightmare05
#include<bits/stdc++.h>

using namespace std;

#define sp << " " <<
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define int long long
#define double long double
#define INF (1e18+13)
#define PI 3.1415926535898

int power(int p,int j)
{
    int res=1;
    p=p%mod;
    while(j>0)
    {
        if(j&1)
            res=(res*p)%mod;
        j=j>>1;
        p=(p*p)%mod;
    }
    return res;
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dice(int d,int p)
{
    uniform_int_distribution<int> uid(d,p);//specify l and s.
    return uid(rng) ;
}

double s(double m1,double m2,double c1,double c2,double c3,double c4)
{
    double x1,x2,x3,x4,y1,y2,y3,y4;
    x1=(c2-c1)/(m1-m2);
    x2=(c3-c2)/(m2-m1);
    x3=(c4-c3)/(m1-m2);
    x4=(c1-c4)/(m2-m1);
    y1=m1*x1+c1;
    y2=m2*x2+c2;
    y3=m1*x3+c3;
    y4=m2*x4+c4;
    double d[4];
    d[0]=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
    d[1]=(y3-y2)*(y3-y2)+(x3-x2)*(x3-x2);
    d[2]=(y4-y3)*(y4-y3)+(x4-x3)*(x4-x3);
    d[3]=(y1-y4)*(y1-y4)+(x1-x4)*(x1-x4);
    sort(d,d+4);
    if(abs(d[3]-d[0])<0.01)
        return sqrt((d[0]+d[3])/2)+26.0;
    else
        return -1;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("elimination_validation_input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t;
    cin >> t;
    while(t--)
    {
        double dp=-1;
        double x1,x2,x3,x4,y1,y2,y3,y4;
        pair<double,double> a[4];
        cin >> a[0].first >> a[0].second >> a[1].first >> a[1].second >> a[2].first >> a[2].second >> a[3].first >> a[3].second;
        for(int j=0;j<6;j++)
        {
            if(j==1||j==3||j==5)
                swap(a[2],a[3]);
            if(j==2||j==4)
                swap(a[1],a[3]);
            x1=a[0].first;
            y1=a[0].second;
            x2=a[1].first;
            y2=a[1].second;
            x3=a[2].first;
            y3=a[2].second;
            x4=a[3].first;
            y4=a[3].second;
            for(double i=0.0;i<=1.0;i+=0.0001)
            {
                double m1=i*PI;
                m1=tan(m1);
                double c1=y1-m1*x1,c3=y3-m1*x3;
                double m2=-1/m1;
                if(m1==0.00000)
                    m2=tan(PI/2);
                double c2=y2-m2*x2,c4=y4-m2*x4;
                int h=1;
                double p[3];
                p[0]=y2-m1*x2-c1;
                p[1]=y3-m1*x3-c1;
                p[2]=y4-m1*x4-c1;
                if(abs(p[0])>abs(p[1])||abs(p[2])>abs(p[1]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                p[0]=y1-m2*x1-c2;
                p[1]=y3-m2*x3-c2;
                p[2]=y4-m2*x4-c2;
                if(abs(p[0])>abs(p[2])||abs(p[1])>abs(p[2]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                p[0]=y2-m1*x2-c3;
                p[1]=y1-m1*x1-c3;
                p[2]=y4-m1*x4-c3;
                if(abs(p[0])>abs(p[1])||abs(p[2])>abs(p[1]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                p[0]=y2-m2*x2-c4;
                p[1]=y3-m2*x3-c4;
                p[2]=y1-m2*x1-c4;
                if(abs(p[1])>abs(p[0])||abs(p[2])>abs(p[0]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                if(h)
                    dp=max(dp,s(m1,m2,c1,c2,c3,c4));
            }
        }
        if(dp<26)
            cout << -1 << endl;
        else
            cout << fixed << setprecision(2) << dp << endl;
    }
    return 0;
}

I would be really thankful if someone can point out, exactly what edge cases did I miss!

Cheers!!!

//Nightmare05 #include<bits/stdc++.h> using namespace std; #define sp << " " << #define mod 1000000007 #define mp make_pair #define pb push_back #define int long long #define double long double #define INF (1e18+13) #define PI 3.1415926535898 int power(int p,int j) { int res=1; p=p%mod; while(j>0) { if(j&1) res=(res*p)%mod; j=j>>1; p=(p*p)%mod; } return res; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int dice(int d,int p) { uniform_int_distribution<int> uid(d,p);//specify l and s. return uid(rng) ; } /* int read() { int cc = getc(stdin); for (;cc < '0' || cc > '9';) cc = getc(stdin); int ans = 0; for (;cc >= '0' && cc <= '9';) { ans = ans * 10 + cc - '0'; cc = getc(stdin); } return ans; } inline void print(int n) { if (n == 0) { putchar('0'); putchar('\n'); } else if (n == -1) { putchar('-'); putchar('1'); putchar('\n'); } else { char buf[20]; buf[19] = '\n'; int i = 18; while (n) { buf[i--] = n % 10 + '0'; n /= 10; } while (buf[i] != '\n') putchar(buf[++i]); } } int n; vector<vector<int>> mat_mul(vector<vector<int>> a,vector<vector<int>> b) { int n=5; vector<vector<int>> ans2(n,vector<int>(n,0)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int ans2=0;ans2<n;ans2++) { ans2[i][j]+=((a[i][ans2]*b[ans2][j])%mod); ans2[i][j]%=mod; } } } return ans2; } vector<vector<int>> pow_mat(vector<vector<int>> mat_a,int p) { if(p==1) return mat_a; vector<vector<int>> temp=pow_mat(mat_a,p/2); vector<vector<int>> res=mat_mul(temp,temp); if(p&1) res=mat_mul(res,mat_a); return res; } */ int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("elimination_validation_input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n; cin >> n; vector<pair<int,int>> dp; vector<int> k; k.pb(1); dp.pb(mp(1,1)); int y=1; for(int i=0;i>-1;i++) { if(i%2==0) y*=2; else y*=4; dp.pb(mp(dp.back().second+1,dp.back().second+y)); k.pb(y); if(y>n) break; } while(dp.back().first>n) { dp.pop_back(); k.pop_back(); } int m=dp.size(); vector<int> h; for(int i=m-1;i>=0;i--) { h.pb(n); if(i==0) continue; int y=n-dp[i-1].second; int z=k[i]/k[i-1]; int f=(y-1)/z; n=dp[i-1].first+f; } for(int i=h.size()-1;i>=0;i--) { cout << h[i] << " "; } return 0; }

Comments (23)

Write comment?

Makise_Kurisu

4 years ago, # |

+13

Dude, please format your code, it's totally screwed up as of now

→ Reply

Nightmare05

4 years ago, # ^ |

Oh oops, sorry, my bad, wait a second, I will format it, using the spoiler feature for the first time

+12

Done bro, I hope it's readable now :)

Thanks, that was quick !

gupta_samarth

← Rev. 3 →

Agreed, use the "Block" option.

~~~~~
// your code here
~~~~~

Oh, you already updated.

Can you describe the problem? I can't seem to open the problems

Yeah bro, already did that, please refresh it once :)

← Rev. 2 →

How did you guys do 3rd one? I did it by tracing back the parent in each step by binary search. Is there an easy to implement solution or observation that simplifies the problem ?

PROBLEM STATEMENT

CODE

#include<bits/stdc++.h>
#define int long long 
using namespace std ;
const long mxN =1e16+2 ;
int c=1,idx=1,n ;
vector<int>a,ans;
int fp(int n){
  int l,r,p,idx,del,d;
  idx=lower_bound(a.begin(),a.end(),n)-a.begin() ;
  l = a[idx-1]+1 ,p= a[idx-2]+1;
  del = (idx&1LL?4LL:2LL) ;
  d = (n-l)/del ;
  return d+p ;
}
signed main(){
  a={0} ;
  for(;c<mxN;c*=(idx&1LL?2LL:4LL),++idx)
    a.push_back(c) ;
  for(int i=1;i<a.size();i++)
    a[i]+=a[i-1] ;  
  cin >> n ;  c = n  ;
  ans.push_back(c) ;
  while(c!=1)
    c=fp(c),ans.push_back(c) ;
  reverse(ans.begin(),ans.end()) ;
  for(int x:ans)
    cout << x << " " ;
}

Yes, bro I have a faster solution without binary search, since the number of children follows a nice ratio, binary search wasn't really needed!

My Solution for P3

Hope it helps :)

I'll study the code, thanks!

sharath101

Code

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll T=clock();

    ll n;
    cin>>n;
    if(n==1){
        cout<<1;
        return 0;
    }
    vector<ll> val(10000);
    val[1]=1;
    ll i=2, r=1;
    while(1){
        if(i%2==0) r*=2;
        else r*=4;
        val[i]=val[i-1]+r;
        if(val[i]>=n)
            break;
        i++;
    }
    vector<ll> ans;
    ans.pb(n);
    while(i>1){
        ll div;
        if(i%2==0) div=2;
        else div=4;
        ll ex=(n-val[i-1]+div-1)/div;
        n=val[i-2]+ex;
        ans.pb(n);
        i--;
    }
    reverse(ans.begin(),ans.end());
    for(ll i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";



    cerr<<"\n\nTIME: "<<(double)(clock()-T)/CLOCKS_PER_SEC<<" sec\n";
    T = clock();
    return 0;
}

Here's mine, I stored the number of nodes in each level and traced back the parent using that information.

That was neat and smart, Thanks a lot!

Can you share the SS of the problem statement? You can get it in my submissions section.

Bro, what site do you use to host the image?

I uploaded it on imgbb, but it's not loading as an image as it should be...

Did you check this ?Upload the pic on this site and then once upload is complete scroll down to find the HTML embed code

I just have to copy the url of the hosted image right?

Anyways, I have already posted the link to the screenshot, I hope for now that would suffice

Auto comment: topic has been updated by Nightmare05 (previous revision, new revision, compare).

I think you mistakenly uploaded same image in both the links

Oh yea sorry, just noticed, I am sorry, didn't have any submission on P6, so can't view it... Anyways updated :)

AreluF

Last Problem

For (k < n), add (k+1)th smallest element to all the elements to its left(in sorted array), so now all the elements have value greater than the (k+1)th element, so (k+1)th element will be our final answer.
Otherwise choose two index i and i+1 such value of (A[i] + A[i+1]) is maximum, then perform (k-(n-1)) operations on this pair, let say this pair is (x, y). After performing k-(n-1) operations on it, add the maximum among them(after operations) to the rest of the (n-1) elements, let suppose (x > y) after (k-(n-1)) operations, then add x to rest of the (n-1) elements, so now x is smallest element after all the k operations, which is the maximum possible.

Can you please share the screenshot of the problem statement ?

Wait oops, were we allowed to reorder the array? T_T

I think I missed this, thanks a lot for the solution bro

No, we aren't allowed to reorder the array, i have sorted the array only in the case where k < n.

Oh okk I finally got the idea,thanks a lot bro

Nightmare05's blog