### swapnil07's blog

By swapnil07, history, 6 weeks ago, 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.

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! :) Comments (16)
 » I encounter a problem of "third-party library" when I am trying to confirm my phone number. What should I do?
•  » » Thanks for your help!
•  » » » how to fix it?
•  » » » » No answer as you see.
 » +66, LET'S GO!!! •  » » Now, if you could please explain the problem statement for Q5.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   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: SpoilerI think it means that there needs to be non-house non-tree block which can reach any house directly (without visiting any house in between). Using this any sequence of houses may be visited.
 » How to solve D?Proof?
•  » » DP I think not quite sure if some Greedy solution is there or not but DP solution did pass
•  » » » greedy works too!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   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 ): ).
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   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.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   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 codevoid solve(){ ll n,ans=0,now=0; cin>>n; vector track; string s; cin>>s; reverse(all(s)); for(auto it:s){ if(it=='+'){ now++; } else if(it=='-'){ now--; } else{ track.pb(now); } } sort(all(track)); n=track.size(); for(ll i=0;i
 » Can you please open problems and allow to submit code now ....
 » Is there any editorial available for the problems?
 » When is the rating update? Maybe tomorrow is the next rated event.