Wow! such big brain! and after every hack, rating changes of all 25,000 participants will be recalculated! No problem sir! I will put the word through to Mike

Lunchtime is Tomorrow. And Amazon is hiring via Lunchtime.

your spirit deserves me to learn

yes

waoooo~

then day after global

It'll be alright, Ron!

me too,good luck bro

You say this in every contest.

wish to have a good vacation

B and D is almost same difficulty level though

Can you wait till the end and not spoil solutions?

Its not "unexpected" since its not hard to figure out why it doesn't tle

i too did bruteforce in C. Got TLE. can you tell me where I went wrong? I can't think of any more optimisation. :/

https://codeforces.net/contest/1519/submission/114607388

link to my submission.

true lol

You will get MLE because final answer can be equal to 5*10^17 which needs to be stored in long long int. 2*5000*5000*8 contiguous allocation is not possible (In case you used DP).

Pretty crazy variance. Solving A through D could either get you 60th place (with an implied rating of about 2250 according to cf-rating-predictor, which is orange), or as low as 2400th place (with an implied rating of about 1640, which is blue).

Interesting. I just used a known algorithm, which is given a graph cover it with paths of length 2 using a DFS. Seems most other people did it this way as well.

Two almost same problems :

https://www.codechef.com/APRIL21A/problems/PAIRFLIP/

https://codeforces.net/problemset/gymProblem/102001/K

Numbers were very large, how will you apply FFT?

FFT has a large constant factor. But also, for $$$n=5000$$$ I think it should be quite difficult to get any $$$n^2 \log{n}$$$ solution to pass, much less FFT.

my solution didn't pass also. 114602456 . looking for a AC solution with FFT. or its impossible with such time limit !!

I solved this problem using DP.Here is the link of my submission: https://codeforces.net/contest/1519/submission/114578483

I have solved in O(n^2) time using DP. Video Explanation and Solutions

D is similar to finding the longest palindromic substring, suppose you want to find ans why reversing index i to j, so instead of calculating whole i to j we can make use of ans of i+1,j-1 and add it to ans of end points(i,j).

for mode detail here: my soln :https://codeforces.net/contest/1519/submission/114607034 here's the link of classic problem which I think my soln is based upon:https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

I'm not sure what intended is, but we can do tree DP: think of each point as connecting two slopes. Then, create the DFS tree from this graph. Now, the question is what's the maximum number of 2-length paths we can partition this graph into. Then, for each subtree, let's greedily partition it. Let dp[x]=whether we need to reserve the edge going to x's parent. Then we can greedily match x's immediate children with DP value 1, and back edges leading up to x. dp[x]=[whether the count of such nodes is odd].

Now, we can easily obtain our answer by keeping track of which edges refer to which original points. This is optimal because the number of extra/unused edges at the end is 0 or 1.

can you please explain your approach

Pls don't make me feel stupid :(

D is simple implementation once you see how the dp works. But getting that idea is not so simple.

C on the other hand is the opposite. The idea is simple to see, but the implementation has some pitfalls.

Am I the only one who did it in O(n) space?

No additional memory other than the original array was needed actually.

try to replace the vector with an array

In D, any n^2 memory takes 200 MB in worst case. So even if you had 2 such types of memory, it will MLE.

My O(n^2) Space and time dp passes all TC. Video explanation

This Video Explanation might help you.

Link to Explanation

Maybe post this as a different blog, that will get it noticed faster.

For Python, others did something like ans+=(a[left]-a[right])*(b[right]-b[left]) to get accepted

https://codeforces.net/contest/1519/submission/114576707

Why not? They never said each university had a competetive programmer. It is possible for a university to have no competetive programmers.

Keep giving contests

That's once you guess what the answer is. And then you can defer the proof until after the contest.

store indices where ans[j].size()>0 and then run loop on those indices only

We can prove by induction that regardless of the path you chose, the cost at any point (x,y) along that path will be x*y-1.

The path can be described by a sequence of R (right) and D (down).
It's easy to prove that swapping a R and a D doesn't change the answer.
You can reach any sequence, starting from a fixed sequence (e. g. RR...RRDD...DD), with a finite number of swaps.

You can visualize it by realizing that at each point $$$(x,y)$$$ of the path the cost is equal to the area of the rectangle with a diagonal $$$(1,1) -(x,y)$$$ with cell $$$(1,1)$$$ removed. When you move right you add a column to the rectangle, and when you move down you add a row.

You can also prove it like this:

Consider the conservative field $$$\vec{E}=y\hat{i} + x\hat{j}$$$. Observe that the value required is just the work function. As potential function is $$$U = xy$$$, work done will always be $$$nm - 1$$$.