Блог пользователя swapnil07

Автор swapnil07, история, 22 месяца назад, По-английски

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

  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +105 Проголосовать: не нравится

+66, LET'S GO!!!

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve D?Proof?

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    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 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Is there any editorial available for the problems?

»
21 месяц назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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