IZhO 2021 - Codeforces

→ Обратите внимание

До соревнования
Codeforces Round 941 (Div. 1)
4 дня
Зарегистрироваться »

*есть доп. регистрация

До соревнования
Codeforces Round 941 (Div. 2)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

CodeChef Starters 131 Solution Discussion

aryanc403

До начала 22:16:50

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

IZhO 2021

Автор 998kover, история, 3 года назад, По-английски

First: We apologize for any inconvenience caused. On the second day, we'll try to correct all today's mistakes.

We still hope that you enjoyed the contest.

You can upsolve here

Let's discuss the problems.

Upd: Day 1 unofficial results here

Upd: Day 1+2 unofficial results here

Upd: Day 2 now available to upsolving.

Upd: Editorials.

+155

998kover
3 года назад
63

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

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

Tekor

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

+41

Can you say how to solve A?

→ Ответить

nkamzabek

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

+63

Let's assume that we are at point $$$p$$$ now. We have two options.

1) Go to $$$t$$$ directly, paying extra $$$|p - t| * a_p$$$ money;

2) Go to another "optimal" point. There are two choices for that. Either it is minimum $$$r$$$ such that $$$a_r < a_p$$$ and $$$r > p$$$, or maximum $$$l$$$ such that $$$a_l < a_p$$$ and $$$l < p$$$.

So run Dijkstra, maintaining minimum distance. Update answer by the first option. Or go to the next optimal point paying $$$a_v * dist$$$ ($$$r - p$$$ or $$$p - l$$$) money. We are multiplying $$$a_v$$$ because each time we are going to the index with a lower value.

→ Ответить

enoone

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

+46

I also did djikstra, but there is no need for it. The graph you get is a DAG, so simple dp is enough.

→ Ответить

muzzaleeni

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

+13

If I'm not wrong, it can also be solved by the Convex hull trick. The naive solution will be using DP. Let's say $$$dp_i$$$ is the minimum time needed to reach the point $$$i$$$. Recurrent relation will look like $$$dp_i = dp_j + |i - j| \cdot a_j$$$. It is easy to notice that the next point's value will be always less than the current's (i.e $$$a_{cur} > a_{next}$$$). So the $$$a's$$$ will be decreasing.

→ Ответить

Ormlis

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

← Rev. 2 →

+22

I also solved it with a convex hull trick. I used two convex hulls. One for queries for the left (i < j) decreasing "ladder" from the start, the other for the right (i > j).

→ Ответить

__Davit__

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

-8

Could you share your code, please

→ Ответить

LastRonin

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

+25

Can you say how to solve B?

→ Ответить

Mansur

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

← Rev. 5 →

+10

To solve in n^2logn, we can notice that actually if we reassing our element from L to R, their id to from 1 to R — L + 1, it is easy to notice that actually after each separation their indexes goes left shift. So having M different groups, we can answer the sum with the formula. Then we can notice that 1 to R — L + 1, does not matter and we can just add their initial ID. So with that we can do MO in Nsqrt(N)log(N), but it will also be TL. Then we can notice that it is enough to keep the last Position where such division starts, so just by fixing R we can answer L easily with that information. My realization was with Trie and Fenwich. Nlog^2

→ Ответить

AlexArdelean

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

← Rev. 3 →

+29

I Don't understand what you mean by "such division starts". I had trie and Mo's algo but I still got wa-s(and also TLE :P). Here's what I did, it's probably the same thing. You are splitting the array into multiple subarrays based on prefixes in base 2. For 2 equal values you are trying to get to the point where the prefixes of the indexes differ. Another thing is that if A and B have a common prefix of some length, A — X and B — X will also have a common prefix of the same length. In my VALMAX trie I added indexes from the original array(thanks to the observation it still works) based on the value of respective index. I counted all the nodes that have at least 2 paths going through them, because that means you have to split up to that point(maybe even further down). I also had an unordered map which included all the points in which I have to split. From multiple values would've collided. It still got WA, so it's probably wrong.

→ Ответить

Lokeo

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

+45

Can you say how to solve C?

→ Ответить

kobor

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

+63

Can you say how to solve D?

→ Ответить

998kover

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

+52

not today

→ Ответить

enoone

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

← Rev. 2 →

+52

Is the second problem reference to this post?

→ Ответить

998kover

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

+54

Yes. To meme and author

→ Ответить

EmilConst

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

+22

Wowowowow, it's extremely cool, thanks :D :D :D

Is Aizhan a real person?

→ Ответить

Tima

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

+25

Is that meme a real life situation?

→ Ответить

EmilConst

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

+22

DavitMarg foresaw that he wasn't going to win a medal, so he decided to bring potatoes instead. He didn't bring potatoes either, though :D

→ Ответить

shejibri

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

← Rev. 2 →

+69

Will be official results published today?

→ Ответить

998kover

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

+42

Unofficial results already published.

→ Ответить

shejibri

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

+15

Are all the participants official in the standings?

→ Ответить

Tima

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

+15

yes

→ Ответить

AlexArdelean

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

+10

Lol who was responsible for the 6th subtask of 3rd problem? It genuinely costed me 20 minutes :P

→ Ответить

oknehcajd

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

+10

somehow, i had "ai = i; bi = i + 1" from the start of the contest, or i accidentally reloaded statements. im not sure

→ Ответить

nandonathaniel

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

← Rev. 3 →

+18

The broken statement is only at English statement, if im not mistaken.

→ Ответить

Olerinskiy

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

+19

How to solve day2 A for n <= 30 and n <= 2000?

→ Ответить

nandonathaniel

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

+66

Do you know the cutoff for the medalists?

→ Ответить

Tosic

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

+10

Or, at least, what it was (roughly) in the past years?

→ Ответить

Lokeo

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

18 is gold

43 is silver

80 is bronze

→ Ответить

Tosic

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

Okay but how many participants were there?

→ Ответить

Lokeo

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

Something around 290

→ Ответить

Tosic

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

There were 295 this year, yes. But how many were there in 2020, I heard somewhere that the no. of participants became quite bigger this year, right?

→ Ответить

LastRonin

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

161 participants

→ Ответить

FairyWinx

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

Dies from cringe(

→ Ответить

FairyWinx

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

← Rev. 2 →

-28

Why its not working in C on n <= 1e3?

Code

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int N = 1e5 + 228;
const int K = 17;

vector<int> G[N];
int up[N][K];
int d[N];
int timer = 0;
int tin[N], tout[N];

void dfs(int v, int p, int h = 0) {
    tin[v] = timer++;
    d[v] = h;
    up[v][0] = p;
    for (int i : G[v]) {
        if (i != p)
            dfs(i, v, h + 1);
    }
    tout[v] = timer;
}

int la(int v, int level) {
    for (int i = K - 1; i >= 0; --i) {
        if (level >= (1 << i))
            level -= (1 << i), v = up[v][i];
    }
    return v;
}

int lca(int a, int b) {
    if (d[b] < d[a])
        swap(a, b);
    b = la(b, d[b] - d[a]);
    if (a == b)
        return a;
    for (int i = K - 1; i >= 0; --i) {
        if (up[a][i] != up[b][i])
            a = up[a][i], b = up[b][i];
    }
    return up[a][0];
}

int get_lca(set<pair<int, int>> &q) {
    if (!q.size())
        return 0;
    int a = q.begin()->second, b = q.rbegin()->second;
    return lca(a, b);
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    for (int i = 0; i < n; ++i)
        cin >> p[i];
    for (int i = 0; i < n; ++i)
        --p[i];
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);
    }
    dfs(0, 0);
    for (int k = 1; k < K; ++k) {
        for (int i = 0; i < n; ++i)
            up[i][k] = up[up[i][k - 1]][k - 1];
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        set<pair<int, int>> q;
        int r = 0;
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            while (!q.size() || (r < n && !(d[get_lca(q)] <= d[i] && cnt))) {
                q.emplace(tin[p[r]], p[r]);
                if (tin[i] <= tin[p[r]] && tin[p[r]] < tout[i])
                    ++cnt;
                ++r;
            }
            if (d[get_lca(q)] <= d[i] && cnt)
                ans += (n - r + 1);
            q.erase({tin[p[j]], p[j]});
            if (tin[i] <= tin[p[j]] && tin[p[j]] < tout[i])
                --cnt;
        }
    }
    cout << ans << '\n';
}

→ Ответить

Olerinskiy

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

Put your code in a spoiler, please.

→ Ответить

FairyWinx

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

Как?

→ Ответить

Olerinskiy

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

Иконка кфа -> spoiler

test

→ Ответить

FairyWinx

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

Thx

→ Ответить

FairyWinx

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

Я не смог найти вкладочку

→ Ответить

AlexArdelean

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

Explain your idea

→ Ответить

FairyWinx

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

So. Let's for every vertex i and L border find max R, where in F(S[l, r]) no contains i. So clear, that with increasing L, the R monotonically increasing. So let's do this with 2 itterators, and check this. Condition is met, If there is a vertex in the subtree and depth LCA set <= d[i]. And i do this

→ Ответить

FairyWinx

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

Или более человечески по-русски. Для каждой вершины найдем все моменты времени, когда она находится в этом "обтянутом дереве". Для этого для каждой левой границы найдем минимальную правую границу, для которой это выполняется (понятно, что тогда выполняется на всем суффиксе). И что правая граница не убывает. Тогда будем это делать двумя указателями, а проверкой будет следующее условие: в поддереве этой вершины кто-то есть, и LCA этого множества выше, то бишь его глубина меньше, что, как мне кажется, у меня написано

→ Ответить