### Nightmare05's blog

By Nightmare05, history, 4 weeks ago, 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

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

Cheers!!! Comments (23)
 » 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 !
•  » » 4 weeks ago, # ^ | ← 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 :)
 » 4 weeks ago, # | ← 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 ? CODE#include #define int long long using namespace std ; const long mxN =1e16+2 ; int c=1,idx=1,n ; vectora,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> 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//Nightmare05 #include 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 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; buf = '\n'; int i = 18; while (n) { buf[i--] = n % 10 + '0'; n /= 10; } while (buf[i] != '\n') putchar(buf[++i]); } } int n; vector> mat_mul(vector> a,vector> b) { int n=5; vector> ans2(n,vector(n,0)); for(int i=0;i> pow_mat(vector> mat_a,int p) { if(p==1) return mat_a; vector> temp=pow_mat(mat_a,p/2); vector> 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> dp; vector 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 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; } Hope it helps :)
•  » » » I'll study the code, thanks!
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   Codeint 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 val(10000); val=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 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
•  » » » 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...
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   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).
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   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 :)
 » 4 weeks ago, # | ← Rev. 3 →   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_TI 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