swapnil07's blog

By swapnil07, history, 2 months ago,

Warm greetings,

Newton School cordially invites you to be a part of our 3 year anniversary contest. The challenge will go live on 30th November 2022 at 9 PM IST.

You will be given 6 problems and 150 minutes to solve them. The contest will be rated for all!

The problems were written and tested by dnshgyl21, _deactivated_, Sawarnik, Xzirium, and _Enigma__. We would also like to thank pradumangoyal and gkapatia for co-ordinating the contest.

Highlights of contest:

1. The Prize Money for the top 5 performers are as follows:
• First Prize: ₹20,001
• Second Prize: ₹10,002
• Third Prize: ₹5,001
• Fourth Prize: ₹3,003
• Fifth Prize: ₹2,001
2. ₹333 gift vouchers to the top 50 participants.
3. ₹300 gift vouchers to participants with ranks 3, 6, 9, 12, ..., 333 (all multiples of 3 till 333).
4. Top 999 students get INR 20001 off on all Newton School courses!.
5. Placement opportunities with the top product companies for Indian participants.

See you all at the leaderboard! Happy coding :)

• +82

 » 2 months ago, # |   -34 The round would clash with CodeChef Starters 67. Can this round be shifted to 29th November?
 » 2 months ago, # |   +3 I'm definitely putting my name in the goblet
 » 2 months ago, # |   +16 "Did you put your name into the Goblet of Fire, Harry?" Dumbledore asked calmly
 » 2 months ago, # |   0 Waiting...
 » 2 months ago, # |   0 HOPE THIS TIME PROBLEMS ARE SIMPLIER
•  » » 2 months ago, # ^ |   0 Fingers crossed :P
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +1 Can you please post editorial link, or please make github repo which contains editorial of all the newton contest till now. Something like that, it will be helpful those for us those who try to upsolve the contest.Your problems are good, but some I don't get the editorials that's why aggregating them in one github repo would be good idea ig.
 » 2 months ago, # |   +2 That sudden increase in problem difficulty after problem 3 and the lack of editorial makes it very irritating for the participant. So these days I avoid this contest
•  » » 2 months ago, # ^ |   +11 The editorials will be released within a week. :)
•  » » » 2 months ago, # ^ |   +1 Can u please provide the link for editorial?
 » 2 months ago, # | ← Rev. 2 →   +22 Top 999 students get INR 20000 off on all Newton School courses!.Please make itTop 999 students get INR 20001 off on all Newton School courses!.
•  » » 2 months ago, # ^ |   +36 You asked it, we gave it! :P
•  » » » 2 months ago, # ^ |   +8 Ok brb upvoting your comment with my alleged 3 accounts.
 » 2 months ago, # |   +10 I have tried to register on the website for like 98054750943758034705 times but the OTP doesn't come. Is there something admins can do to help me out? On the other note, I don't really understand why you need my mobile number. This is annoying experience.
 » 2 months ago, # | ← Rev. 2 →   +6 Problem E has appeared before :)Edit: Not claiming the problem is copied, just stating a fact.
 » 2 months ago, # |   0 It appears that E has appeared before. However I solved it myself today and would like to share my solution.Map all numbers in the input to random numbers in a large range. The mapping should be done ensuring that the order of the numbers remains same after mapping. Now to compare two arrays, take their sum and product. If they are same then arrays are same. Other wise difference in sums will be the difference between the mismatched numbers and the divison of their products will be the divison of the mismatch numbers. Now solve for both numbers using these two equations. Both numbers must occur in their respsctive ranges and their positions should coincide. This last part can be performed offline after sorting the queries.
 » 2 months ago, # |   0 Any hint to solve B? I think this is the main idea (or I might be absolutely wrong), but could'nt implement. My approachIterate over 1 <= i <= M, and keep i in the first index. Now for the rest n-1 numbers, you can have numbers which have same bit set as i. So, I can use __builtin_popcount() to find number of set bits. But, here comes permutation and combination T-T and I got confused on how to keep m numbers in n elements(
•  » » 2 months ago, # ^ | ← Rev. 2 →   +7 so for every other positions there are Count_Submask(i)-1 options. So (Count_Submask(i)-1)^(n-1) will be the answer for a particular i. Just add answers for all i till m. How to find Count_submask?If a number i has j bits set then there can be 2^j submask. For this question do remember to exclude 0. That's why I have taken count_submask(i)-1.
•  » » » 2 months ago, # ^ |   0 Man TT_TT, seems so easy once you confirm/prove your approach. Still couldn't implement it, gotta be better. Also, how to solve these permutations problems, do you write down or have enough practice to just implement directly. Please suggest any resource where I can learn PnC important enough for CP. Thank youu!
 » 2 months ago, # |   +1 how to solve C?
•  » » 2 months ago, # ^ |   +5 I used dp. My dp had 3 states and dp[i][j][k]=number of subsequence such that the last index chosen from array is i , array b is j and array c is k. To do the transitions quickly I have used 2-d prefix sum. Sample code
•  » » » 2 months ago, # ^ |   0 Why we are getting TLE with 3d dp, with same states as yours. My code : Link
•  » » 2 months ago, # ^ |   +16 I used similar kind of dp but a more simplified form using inclusion exclusion. Code
 » 2 months ago, # |   +1 do i have to apply for gift voucher somewhere if i am eligible for it ?
•  » » 2 months ago, # ^ |   0 no you dont, it will be sent to your registered email.
 » 2 months ago, # |   0 Can anyone tell their approach for D problem, I am not getting any idea. Thanks for helping in advance.