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!!!
Dude, please format your code, it's totally screwed up as of now
Oh oops, sorry, my bad, wait a second, I will format it, using the spoiler feature for the first time
Done bro, I hope it's readable now :)
Thanks, that was quick !
Agreed, use the "Block" option.
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 :)
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 ?
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!
Hope it helps :)
I'll study the code, thanks!
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 :)
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