swapnil07's blog

Newton's Coding Challenge December 2021 Invite
By swapnil07, history, 3 years ago, In English

Warm greetings,

Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 28th December 2021 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, and Xzirium.

We would also like to thank gkapatia for co-ordinating the contest.

Highlights of contest:

  1. The Prize Money for the top 5 performers are as follows:
    • First Prize: ₹10,000
    • Second Prize: ₹5,000
    • Third Prize: ₹2,500
    • Fourth Prize: ₹1,500
    • Fifth Prize: ₹1,000
  2. ₹100 Amazon gift vouchers to the top 50 participants.
  3. ₹100 Amazon gift vouchers to 50 randomly selected participants ranked between 51-500.

Note: Top 5 participants from other countries can opt to receive an Amazon Gift voucher in their respective currencies or through a Paypal transaction. All the other gift vouchers will be sent in INR.

We hope you like the contest! Hope to see you all at the leaderboard! :)

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

»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

what is the meaning of sequence in question C ? is this a sequence [ 1,3,5] or its need to be contigeous ?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is basically an array of numbers or a series of numbers like {1,2,3}. It is not a segment.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      they should have mentioned it properly, got 2 penalties and a lot of time wasted

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can't i register for the contest and enter the contest once the contest has started? i was giving round here on codeforces thats why didnt register and now i cant enter the contest :<

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Anybody has an edge case for D getting 14 out of 15 AC and 1 WA :(

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Check the following test case

    2
4060361101701000 10000000000000000
8788101400260000 10000000000000000

    Answer should be, 1 1.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

How to solve problem D? (Find the number of pairs $$$A$$$, $$$B$$$ ($$$A < B$$$) such that $$$lcm(a, a + 1, .. b - 1, b) = x$$$

I tried to handle cases up to length 5 $$$(B - A <= 4)$$$ and then brute force for bigger lengths.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Brute for all length > 2, then for 2 find by solving quadratic. Store for all lcm in map of vectors and then find using binary search.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E anything to do with solving XOR equation using Gaussian elimination or something?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended complexity for F?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I was able to solve it in $$$O(2^r r^2 \log mr)$$$

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When can we expect the editorial, and what is the approach to solve question C (Anya's triplets)?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Sort the segments in the increasing order of endpoints. Then greedily pick c points from R to L for each segment. This works because, let Sj and Si be the segments such that j > i. As the segments are sorted in increasing order of end points, Rj >= Ri. Hence, if Sj and Si share the common points these points will lie close to Ri. Hence picking points from R to L is optimal.

    Code
    → Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

With great international coders also coming in, looking forward for an extended and revised Prize Distribution Criteria!

→ Reply