Good contest, I really enjoyed it! Thanks.

Here is a problem which has the same idea with D. http://acm.hdu.edu.cn/showproblem.php?pid=6103

Anyone knows why there's a major difference between predicted and actual rating changes?

Can anyone help me in identifying the mistake in Problem D, the approach is similar to the longest palindromic substring. It is failing in the 11th test case.

Link to the submission: https://codeforces.me/contest/1519/submission/114709341

Edit: the issue is resolved thanks

Aren't problems like E and F suitable better for div1? Why not use them in div1 then as creating div1 problems is harder.

Thanks for E, it was quite educational.

Can anyone explain how the time complexity of C is nlogn

Спасибо за очередной интересный контест! С нетерпением жду ещё!

can anyone explain how forward edges are handled in last paragraph of editorial of E?

upd: got it

Will the rating roll back QAQ

can anyone show me simple readable solution for C?

I was learning FFT recently (only out of curiosity) and been wondering if D can be solved by it? I don't need the solution, I just want to know if it's possible.

Short Video Editorial For Problems A — D

I have a different solution for problem D.
We can just calculate the sum if we flip a subarray $$$[j, i]$$$ for all subarrays.

$$$dp[i][j] = dp[i - 1][j + 1] + A[i] * B[j] + A[j] * B[i]$$$

We are basically swapping $$$A[i]$$$ and $$$A[j]$$$ assuming that the subarray to be reversed is $$$[j, i]$$$.

After this we can loop over all subarrays and add the prefix and suffix profit using prefix sums. We take the max value.

See my code for clarity: 114583311

Short Video Editorial For Problems A — D

I have a different solution for problem D (Maximum Sum of Products):

$$$sum[i][j]$$$ stores the new sum on reversing the subarray $$$[j, i]$$$
$$$sum[i][j] = sum[i - 1][j + 1] + A[i] * B[j] + A[j] * B[i]$$$

We calculate the sum of elements we get on reversing every subarray $$$[j, i]$$$.

To account for the rest of the array, loop over all subarrays and use prefix sums to add the remaining part. Take the best value over all subarrays.

Time complexity: $$$O(N^2)$$$

See my code for clarity: 114583311

Hi, for problem C, can somebody explain why 114796728 gives TLE and 114799663 doesn't. The only difference is the usage of an array instead of a vector.

Can anyone help me figure out why I am getting TLE (https://codeforces.me/contest/1519/submission/114826178)

for problem D, if I try to implement the brute force approach which would take O(n^3) time then will it be TLE ? As the constraint is n <= 5000.

What does if(nw.need == vector<int>(a, a + n)) in F's solution mean?

Please explain the proof for problem B little more briefly.. Why doesn't the cost depend on path taken?

Can anyone help me out in c question i had also used prefix sum but getting tle on 4 th case but it should not come 115057482

I believe there is a typo in the editorial for F: instead of $$$\sum_{i=1}^{a_i} - mincut$$$ it should be $$$\big(\sum_{i=1}^n a_i\big) -mincut$$$.

$$$2$$$ more proofs for problem $$$B$$$:

Mathematical proof:

Assume that the sequence of movement is as follows: $$$x_1$$$ units down, then $$$y_1$$$ units right, then $$$x_2$$$ units down, then $$$y_2$$$ units right, ..., then $$$x_c$$$ units down, then finally $$$y_c$$$ units right, where $$$x_i, y_i \geq 0$$$, $$$1+\sum_{i=1}^{c}x_i=n$$$, and $$$1+\sum_{i=1}^{c}y_i=m$$$. The total cost will be:

$$$x_1*1+y_1*(1+x_1)+x_2*(1+y_1)+y_2*(1+x_1+x_2)+...+(1+\sum_{i=1}^{c-1}y_i)*x_c+(1+\sum_{i=1}^{c}x_i)*y_c=$$$

$$$\sum_{i=1}^{c}y_i+\sum_{i=1}^{c}x_i*(1+\sum_{i=1}^{c}y_i)=m-1+(n-1)*m=n*m-1$$$

Ad hoc proof:

A step from $$$(i,j)$$$ to $$$(i+1,j)$$$ spans all the cells from $$$(i+1,1)$$$ to $$$(i+1,j)$$$, and a step from $$$(i,j)$$$ to $$$(i,j+1)$$$ spans all the cells from $$$(1,j+1)$$$ to $$$(i,j+1)$$$. Which means that for every step down to a cell $$$x$$$, all the cells from $$$x$$$ to the left will be counted, and for every step right to a cell $$$y$$$, all the cells from $$$y$$$ to the top will be counted. At the end, all the cells in the grid will be counted except the first cell $$$(1,1)$$$, that is $$$n*m-1$$$.

Can we do D with two segment trees s1 and s2, where s1 stores the sum of a[i]*b[i] over [l,r) and the s2 stores the similar sum but for the reversed array a over ranges [l,r), Afterward the ans can be brute forced by taking each possible segment that can be reversed and taking the maximum. The runtime will be O(n*n*log(n))?

Can anynone help me with my A.cpp code ? Why is it wrong :(( ?? https://codeforces.me/contest/1519/submission/115942467

can anyone help me with my A.cpp code ? Why is it wrong :(( https://codeforces.me/contest/1519/submission/115942467

Hi awoo

For problem F, using the idea of saturating all out going edges from source to chests, I used this dynamic programming state : dp[i][j][a][b][c][d][e][f] = the minimal cost to saturate the first i out going flow edges from source, where the i-th out going edge currently has j units of residual remaining, and the 1st incoming edge to sink has a units of residual left , second incoming edge to sink has b units left , 3rd has c units left, 4th, 5th, 6th have d , e , f units left respectively.

base case: dp[0][0][a][b][c][d][e][f] = 0 , for all a,b,c,d,e,f <= 6
transition: dp[i][j][a][b][c][d][e][f] = min{
dp[i][j - min(j , a)][a - min(j , a)][b][c][d][e][f] + C[i][1],

dp[i][j - min(j , b)][a][b - min(j , b)][c][d][e][f] + C[i][2],

dp[i][j - min(j , c)][a][b][c - min(j , c)][d][e][f] + C[i][3],

dp[i][j - min(j , d)][a][b][c][d - min(j , d)][e][f] + C[i][4],

dp[i][j - min(j , e)][a][b][c][d][e - min(j , e)][f] + C[i][5],

dp[i][j - min(j , f)][a][b][c][d][e][f - min(j , f)] + C[i][6],

}

Here is my submission https://codeforces.me/contest/1519/submission/116235067 I got wrong answer on test case 93, I have been trying to find the bug for a day and could not resolve it.

You will be my life saver if you hint me on why my solution did not get AC!

This is my solution.

This is an accepted solution.

Can someone, please tell me why my solution is not being accepted? The time complexity of both the solutions seems same to me.

Help me out ;( here.

Even though I have used the exact same approach as given in editorial my solution is showing TLE for some cases. Pls can anyone help me out. I have used std :: unordered_map for the universities. My solution is 131142379

Even though I have used the exact same approach as given in editorial for Problem : 1519C — Berland Regional, my solution is giving TLE for some cases. I have used unordered_map for the universities. Pls can anyone help me out. My solution is 131142379

Can anyone tell me why this java implementation code with hashmap will get TLE for Problem C?

code In Problem D why it is Accepted i thought i will get TLE

366086518 For people getting TLE, the approach over looping first over all $$$k$$$ 's and then the prefix array inside does not work, due to caching(from AI and other sources), this has to do with accessing the entire prefix array in each iteration v/s the given approach where you loop over array in the prefix array only once, which results in much faster code. Adding as this problem is in TLE Eliminators sheet.