Разбор Educational Codeforces Round 108

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Разбор

Решение (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")
    }
}

1519B - Торт - это ложь

Идея: adedalic

Разбор

Решение (adedalic)

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

1519C - Берляндский отбор

Идея: BledDest

Разбор

Решение (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 - Максимальная сумма произведений

Идея: vovuh

Разбор

Решение (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;
}

1519E - Сдвиг на один

Идея: BledDest

Разбор

Решение (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);
}

1519F - Сундуки и ключи

Идея: BledDest

Разбор

Решение (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;

}

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], }

Комментарии (51)

Показать архивные | Написать комментарий?

younes38

4 года назад, # |

Good contest, I really enjoyed it! Thanks.

→ Ответить

Ice_Cream

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

hazergaze

← Rev. 2 →

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

jimm89

4 года назад, # ^ |

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.

kashish_07

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

Edit: the issue is resolved thanks

Ritwin

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.

zarif_2002

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

CoderAnshu

+14

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

cobax

+27

Thanks for E, it was quite educational.

DL-POWER

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.

CaDe

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

abhishek945

Can anyone explain how the time complexity of C is nlogn

JPrime

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

precht

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

del1ke

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

k4droid3

← Rev. 3 →

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

upd: got it

Falcon__

Will the rating roll back QAQ

ethicalhacker365

can anyone show me simple readable solution for C?

ScarletS

Is this clean enough?

artish19

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.

arujbansal

-8

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

Dragon_in_Bed

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.

dumb_dot

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.

pajenegod

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

f(i,1,n+1) {
  vll pre(n+1);

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

vll pre(n+1);
f(i,1,n+1) {

Some other things I noticed about your code:

Remove cout.tie(NULL) from your code. Unlike cin.tie(NULL); the cout version does nothing and 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.

greentree888

6 месяцев назад, # ^ |

Hi. Could you please explain why just changing the order of the for loops is giving TLE here?

TLE: https://codeforces.net/problemset/submission/1519/263003944

AC: https://codeforces.net/problemset/submission/1519/263006010

Thanks a lot.

hypercoderg

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

godlike_011

← Rev. 6 →

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.net/contest/1519/submission/114635321

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

x_walker_x

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.

18o3

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.

C20200522

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

Anish_Bashyal

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

davidberard

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.

lameboredgenie

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

sujal10x

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$$$.

mohamedeltair

$$$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$$$.

KAMITO

16 месяцев назад, # ^ |

This is the only rigorous proof about B I've ever seen!!!

gravito69

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

_AnKahng

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

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

EDIEEee

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.

Here is my submission https://codeforces.net/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!

amireripmav786

3 года назад, # |

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.

Dzksh

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

kaihong

21 месяц назад, # |

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

snowball_ice_cream

5 месяцев назад, # |

can anyone tell why it's getting TLE https://codeforces.net/contest/1519/submission/268968581

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