swapnil07's blog

By swapnil07, history, 22 months 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 27th May 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 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 the prize money through Paypal. All the other gift vouchers will be sent in INR.

We hope you like the contest! See you all at the leaderboard! :)

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

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I encounter a problem of "third-party library" when I am trying to confirm my phone number. What should I do?

»
22 months ago, # |
  Vote: I like it +105 Vote: I do not like it

+66, LET'S GO!!!

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

    Now, if you could please explain the problem statement for Q5.

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

      I think in statements it means that when visiting a sequence of houses, you need to enter and exit from same side, ie not visiting inside the house.

      I am not sure if the following is required condition:

      Spoiler
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D?Proof?

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

    DP I think not quite sure if some Greedy solution is there or not but DP solution did pass

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    Were test cases for D weak? I couldn't figure out the linear solution so decided to simply submit my $$$O(n^2)$$$ DP solution just for the sake of practice and it surpisingly didn't give me TLE (though there was a bug in my implementation which I couldn't fix in time ): ).

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    In D, Suppose there are 6 C's, then consider the path -> -> -> <- <- <- (-> means i will go forward and <- i will go backward). Calculate the answer for that path (call it rel), now I will calculate answer for a different path RELATIVE to this path. Call the difference delta. Then answer for arbitrary path = rel + delta. I want to maximize delta (rel is constant). Observe that if I flip -> arrow at the ith index It changes delta by +2*(suffsub (i) — suffadd(i) ) (Suffadd(i) is the no of '+' in string in the indexes from [ i to N ] , Suffsub(i) is the same for '-' ).

    Also observe that If I flip -> into <- then I also have to flip some other <- into ->. (To maintain the fact that I have to reach starrting pos at the end). So max value of delta is some j highest values of -> flip and <- flip.

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it +28 Vote: I do not like it

    Assume you have $$$2 \cdot x$$$ times $$$C$$$. Now you have to replace $$$x$$$ $$$C$$$ with $$$1$$$ and remaining $$$x$$$ $$$C$$$ with $$$-1$$$.

    Suppose you are at some $$$i$$$ such that $$$s[i]='+' $$$, what will you add to the answer for this $$$+$$$?

    The answer is number of times $$$1$$$ occured before position $$$i$$$ — number of times $$$-1$$$ occured before position $$$i$$$.

    Now think other way round.

    Suppose you at position $$$i$$$ such that $$$s[i]=C$$$, and you have $$$x$$$ $$$'+'$$$ to the right of $$$i$$$ and $$$y$$$ $$$'-' $$$ to the right of $$$i$$$. Now you add $$$x-y$$$ to the answer if you have $$$1$$$ at this position, otherwise you add $$$-(x-y)$$$ to the answer.

    Thus you take another array $$$b$$$ such that

    $$$\bullet$$$ $$$b[i]=0$$$ if $$$s[i]=C$$$

    $$$\bullet$$$ $$$b[i]=1$$$ if $$$s[i]=+$$$

    $$$\bullet$$$ $$$b[i]=-1$$$ if $$$s[i]=-$$$

    You find suffix sum of this array, and append $$$suff[i]$$$ in some vector(say track), if $$$b[i]=0$$$.

    Now sort track, and subtract first $$$x$$$ elements from the answer, and add last $$$x$$$ elements to the answer.

    My code
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you please open problems and allow to submit code now ....

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Is there any editorial available for the problems?

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

When is the rating update? Maybe tomorrow is the next rated event.