Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main() {
repeat(readLine()!!.toInt()) {
val (r, b, d) = readLine()!!.split(' ').map { it.toInt() }
println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO")
}
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main() {
repeat(readLine()!!.toInt()) {
val (n, m, k) = readLine()!!.split(' ').map { it.toInt() }
println(if (n * m - 1 == k) "YES" else "NO")
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n;
scanf("%d", &n);
vector<int> s(n), u(n);
forn(i, n){
scanf("%d", &s[i]);
--s[i];
}
forn(i, n){
scanf("%d", &u[i]);
}
vector<vector<int>> bst(n);
forn(i, n) bst[s[i]].push_back(u[i]);
forn(i, n) sort(bst[i].begin(), bst[i].end(), greater<int>());
vector<vector<long long>> pr(n, vector<long long>(1, 0));
forn(i, n) for (int x : bst[i]) pr[i].push_back(pr[i].back() + x);
vector<long long> ans(n);
forn(i, n) for (int k = 1; k <= int(bst[i].size()); ++k)
ans[k - 1] += pr[i][bst[i].size() / k * k];
forn(i, n)
printf("%lld ", ans[i]);
puts("");
}
return 0;
}
```

1519D - Maximum Sum of Products

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
int n;
cin >> n;
vector<li> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<li> pr(n + 1, 0);
for (int i = 0; i < n; ++i)
pr[i + 1] = pr[i] + a[i] * b[i];
li ans = pr[n];
for (int c = 0; c < n; ++c) {
li cur = a[c] * b[c];
for (int l = c - 1, r = c + 1; l >= 0 && r < n; --l, ++r) {
cur += a[l] * b[r];
cur += a[r] * b[l];
ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
}
cur = 0;
for (int l = c, r = c + 1; l >= 0 && r < n; --l, ++r) {
cur += a[l] * b[r];
cur += a[r] * b[l];
ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
}
}
cout << ans << endl;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
struct point{
int a, b, c, d;
};
typedef pair<long long, long long> frac;
typedef pair<int, int> pt;
int n;
vector<point> a;
map<frac, int> sv;
frac norm(long long x, long long y){
long long g = __gcd(x, y);
return {x / g, y / g};
}
vector<vector<pt>> g;
vector<int> used;
vector<pt> ans;
int dfs(int v){
used[v] = 1;
int cur = -1;
for (auto it : g[v]){
int u = it.x;
int i = it.y;
if (used[u] == 1) continue;
int nw = i;
if (!used[u]){
int tmp = dfs(u);
if (tmp != -1){
ans.push_back({nw, tmp});
nw = -1;
}
}
if (nw != -1){
if (cur != -1){
ans.push_back({cur, nw});
cur = -1;
}
else{
cur = nw;
}
}
}
used[v] = 2;
return cur;
}
int main() {
scanf("%d", &n);
a.resize(n);
forn(i, n) scanf("%d%d%d%d", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
g.resize(2 * n);
forn(i, n){
frac f1 = norm((a[i].a + a[i].b) * 1ll * a[i].d, a[i].b * 1ll * a[i].c);
frac f2 = norm(a[i].a * 1ll * a[i].d, a[i].b * 1ll * (a[i].c + a[i].d));
if (!sv.count(f1)){
int k = sv.size();
sv[f1] = k;
}
if (!sv.count(f2)){
int k = sv.size();
sv[f2] = k;
}
g[sv[f1]].push_back({sv[f2], i});
g[sv[f2]].push_back({sv[f1], i});
}
used.resize(sv.size());
forn(i, sv.size()) if (!used[i])
dfs(i);
printf("%d\n", int(ans.size()));
for (auto it : ans) printf("%d %d\n", it.x + 1, it.y + 1);
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 6;
const int M = 400;
const int INF = int(1e9);
int a[N];
int b[N];
int c[N][N];
int n, m;
struct state
{
vector<int> need;
int v2;
int v1;
int rem;
state() {};
state(vector<int> need, int v1, int v2, int rem) : need(need), v1(v1), v2(v2), rem(rem) {};
};
int get_code(const vector<int>& v)
{
int ans = 0;
for(int i = 0; i < v.size(); i++)
ans = ans * 5 + v[i];
return ans;
}
int get_code(const state& s)
{
int code = get_code(s.need);
code = code * 6 + s.v2;
code = code * 6 + s.v1;
code = code * 5 + s.rem;
return code;
}
vector<int> get_vector(int code, int n)
{
vector<int> res(n);
for(int i = n - 1; i >= 0; i--)
{
res[i] = code % 5;
code /= 5;
}
return res;
}
state get_state(int code)
{
int rem = code % 5;
code /= 5;
int v1 = code % 6;
code /= 6;
int v2 = code % 6;
code /= 6;
vector<int> need = get_vector(code, n);
return state(need, v1, v2, rem);
}
const int Z = 40 * int(1e6);
int dp[Z];
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < m; i++)
cin >> b[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> c[i][j];
for(int i = 0; i < Z; i++)
dp[i] = INF;
state start(vector<int>(n, 0), 0, 0, 0);
int ans = INF;
dp[get_code(start)] = 0;
for(int i = 0; i < Z; i++)
{
if(dp[i] == INF) continue;
state s = get_state(i);
for(int f = 0; f <= 4; f++)
{
if(s.need[s.v1] + f > a[s.v1] || s.rem + f > b[s.v2])
continue;
int add = (f == 0 ? 0 : c[s.v1][s.v2]);
state nw = s;
nw.need[s.v1] += f;
nw.rem += f;
if(s.v1 == n - 1)
{
nw.v1 = 0;
nw.v2 = s.v2 + 1;
nw.rem = 0;
}
else
{
nw.v1 = s.v1 + 1;
}
if(nw.need == vector<int>(a, a + n))
ans = min(ans, dp[i] + add);
if(nw.v2 < m)
{
int code = get_code(nw);
dp[code] = min(dp[code], dp[i] + add);
}
}
}
if(ans == INF) ans = -1;
cout << ans << endl;
}
```

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

Are you a chinese person?

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

At least in my case the predictor was using my rating from 2 contests prior. I think it must have scraped the ratings at a time when ratings changes were rolled back.

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.com/contest/1519/submission/114709341

Edit: the issue is resolved thanks

Use

`vector<ll>`

for`a`

and`b`

, because the when you multiply two`int`

's, the compiler doesn't know to convert it to a`long long`

unless you explicitly tell it to do so, or have the types originally as`long long`

's.Yeah thanks a lot

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

Can't comment about F but problems like E are repeat or too obvious for Div1 contenders.

Thanks for E, it was quite educational.

i couldn't keeep upto editorial of E after dfs tree. Can you explain what they mean by dfs tree and what after that.

Thanks in advance.

This is a very nice dfs tree entry: https://codeforces.com/blog/entry/68138

Can anyone explain how the time complexity of C is nlogn

The time complexity is nlogn because you must to sort the elements of each university before the calculation of the prefixes.

But for each k from 1..n we calculate the result, which requires to go through all schools from 1..n. Doesn't it give n^2?

On each university we iterate between the values 1 and the number of students in that university, because for higher values the university can not make a team. This has a complexity of O(n).

thx, now I get it

Very interesting contest, I really enjoyed it! Thanks!

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?

Is this clean enough?

thanks. yeah!,white house clean

Can someone please give me a proof for B?

You can also use BFS

Sadly haven't got to covering this yet, trying to solve most of the A problems and B problems from Div2 90% before I go on to covering DP, DFS and BFS problems. If you could tell me a way to prove this without assuming the formula, that would be amazing.

No one directly "assumed" the formula in my opinion how I approached it was trying to convert my intuition to mathematical proof. Try reading this article. Have a good day!

Try to draw a 2d matrix and try to compute the value at random points from taking both ways left and right then u will come up with the same formula

Alright. Thank you

the round was amazing, can anyone help me identify the error in 114652844 to problem c, my approach is similar to the edi.

Link to solution as well as explanations.

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

They're actually the same

why did you take max(dp[i][j], dp[i — 1][j + 1] + A[i] * B[j] + A[j] * B[i]), what's the use of taking maximum here??

Yeah, you're right. There's no use of doing that here.

hi! can some one point out my mistake in D. I have used the same approach as in editorail, except i have used a 2-D dp. test case 27 is showing wrong answer. https://codeforces.com/contest/1519/submission/114798610

thanks

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.

when you are declaring:

vll pre(n+1),

i dont why but on my system it fills it with garbage value, and run time is really slow on my pc as you have stated

but,

when u use ll pre[n+1] ,

pre is filled with all 0s, and run time is fast on my pc

Your code is fundamentally O($$$n^2$$$) because of

As far as I can tell, the only reason why you didn't TLE on your 2nd submission is because the compiler was nice and effectively optimized your code to

Some other things I noticed about your code:

Remove

`cout.tie(NULL)`

from your code. Unlike`cin.tie(NULL);`

the cout version doesnothingand should never be used.Submit under C++17(64 bit) instead of C++11. You will see much better running times. You are basically handicapping yourself by using C++11.

Thanks, I'll take note of it.

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

Hey, I tried your approach as well, calculating answer for each value of k[1,n] , i got TLE as well, link similar to your solution(TLE): https://codeforces.com/contest/1519/submission/114824539

Nevertheless, I got ACC , finally. Here's some tips, i can give you:

1.) use vector<vector> instead of map<int,vector> db or use unordered_map

2.) use a vector to store output of each value of k[1,n]

3.) after sorting the inner vector, use the same inner vector to store cumulative sum

3.) iterate this inner vector after sorting and increment the value of output-vector according to this inner vector

my Accepted solution(not the most efficient): https://codeforces.com/contest/1519/submission/114825135

thanks

Your code failed only because you used iterator as the second loop. The same reason my code failed and changing it will surely give AC. I also changed map to vector first and all the other optimizations and still it failed but this one small change gave AC. Reason why this happens is because when n >= 10^5, iterator being nested will be called in range of 10^5 times(depending on implementation). At this range it becomes really slow compared to normal for loop with [] operator. In my tests above 10^5 it was almost 1.2 — 2 times slower in this question(Can be more/less as I did these tests on my own PC but you can get the idea).

Check the running time in both these codes where the only difference is for loop instead of for-each(uses iterator)

Failed Code — https://codeforces.com/contest/1519/submission/114635321

Accepted Code — https://codeforces.com/contest/1519/submission/114687960

thanks

https://codeforces.com/contest/1519/submission/114986969

can you figure out why am i still getting TLE?

Can Any one help me in Problem D, i used BIT to calculate the prefix and suffix value and used Brute force for calculating the interval [i,j] , but still TLE at test case 9:

my solution: https://codeforces.com/contest/1519/submission/114828602

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.

Yes it would TLE as (5000)^3 = 125*10^9=1.25*10^11 As this is much greater than the recommended 10^9 it would not fit within the time limit and give a TLE error.

Thanks a lot

Can anyone Explain D a little bit in detail

I am sure this will help Video

Love the explanation. Thanks. Cleared all the doubts

What does

`if(nw.need == vector<int>(a, a + n))`

in F's solution mean?I believe I tried to solve with the same approach as explained in the editorial for C . i.e grouping the students according to university_id and then taking the prefix sum for individual university . however I kept getting TLE on test 4 . can anyone tell why ? 114624170

I have got the same issue .. try to sort the vector of vector in terms of size of v[i].size in greater(). Uh can check out my code too .. i can explain that

why does erasing gives TLE ?

Erasing what ?

Erasing an arbitary element from a vector takes $$$O(n)$$$, since all elements after the deleted element need to be shifted.

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

Consider the two paths shown in the picture below: one which takes the blue route and one which takes the red route. The black parts of the two paths are the same in both paths.

Either way, the contribution from the red section or the blue section is $$$+(i+j)$$$, so both paths have equal cost.

You can change from any path to any other path via a sequence of paths which each differ only by one square, like in the picture above.

Thank you very much. I get it now!

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

You must be missing tricky point. Check this explanation

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 anyone tell me why this code is giving me tle :( but after reversing the conditions of last for loop it got accepted......Thanks in Advance :)

#include<bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; vector uni(n); vector score(n); vector<vector> combine(n,vector()); for(int i=0;i<n;i++){ cin >> uni[i]; } for(int i=0;i<n;i++){ cin >> score[i]; }

115108145 Please help! Why am I getting TLE ?

115150110 Any of you guys have any idea why is this code failing for Test case 11 in Question D. Thanks in advance!

In problem D (Maximum Sum of Products) , Is there an algorithm with Time Complexity less than O(n^2) ? Like O(n) or O(nlogn) ?? Further thanks..

I can't find the problem in my solution for problem D (wrong answer test 9) 115467785, help please

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))?