swapnil07's blog

By swapnil07, history, 2 months ago, In English

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.

Registration Link: Newton's Coding Challenge

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 :)

 
 
 
 
  • Vote: I like it
  • +82
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -34 Vote: I do not like it

The round would clash with CodeChef Starters 67. Can this round be shifted to 29th November?

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm definitely putting my name in the goblet

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

"Did you put your name into the Goblet of Fire, Harry?" Dumbledore asked calmly

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

HOPE THIS TIME PROBLEMS ARE SIMPLIER

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fingers crossed :P

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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, # |
  Vote: I like it +2 Vote: I do not like it

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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The editorials will be released within a week. :)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can u please provide the link for editorial?

»
2 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

Top 999 students get INR 20000 off on all Newton School courses!.

Please make it

Top 999 students get INR 20001 off on all Newton School courses!.

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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   Vote: I like it +6 Vote: I do not like it

Problem E has appeared before :)

Edit: Not claiming the problem is copied, just stating a fact.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Any hint to solve B? I think this is the main idea (or I might be absolutely wrong), but could'nt implement.

My approach
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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?
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +1 Vote: I do not like it

how to solve C?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why we are getting TLE with 3d dp, with same states as yours. My code : Link

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I used similar kind of dp but a more simplified form using inclusion exclusion. Code

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

do i have to apply for gift voucher somewhere if i am eligible for it ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell their approach for D problem, I am not getting any idea. Thanks for helping in advance.