Форум DL

Мой профиль

День 1: Прочитал задачу А, потратил на неё более 1 час и получилось только на 3 балла. пошёл дальше читать В, так же потратил час на 5 баллов, С и D не смог понять. Оставшийся 2 часа решал B. Переодически пытаясь перечитать A
День 2: Прочитал задачу А, придумал решение которое прошло на 39 баллов. Придумал как по другому проверять и сделал на 100. Прочитал задачу В, написал решение на 11 и пошёл дальше. Прочитал С, не придумал решение. Почти всё оставшиеся время решал 2 теста из D и набрал 7.8 балла, последние 60 минут пытался исправить и.
Какие ошибки совершил:
День 1: Решил не думать над А, а решать В.
День 2: Мог взять подтесты на В(чтобы набрать 35 баллов вместо 11) и не придумал фулл решение на 1 тест D.
Что и как нужно делать по другому на олимпиаде, чтобы лучше выступать:
Быть более собранным и прочитать все задачи, если есть идея написать, если не прошла подумать над другими способами получения ответа(как во втрой день с A), a не думать над одним решением(как в перый день с A и В) за исключением нескольких случаев.
Что нужно изменить в подготовке/тренировках, чтобы лучше выступать: Больше заниматься.

Мой профиль

Республика 2024

День 1
Прочитал А, вроде придумал жадос, минут 5 пробовал доказать, потом решил написать и отправить, так как писалось относительно быстро, но он зашел только на группу a<10.
Еще немного подумал, написал стрессы, нашел контртест, немного проанализировал и решил перейти на следующую задачу.
Прошло где-то 1,5 часа. На задачу B потратил минут 40, взял первые 2 подгруппы, думал над третьей, остальные казались сложными.
Начал читать задачу C, написал брут, остальные группы давались не очень. (минут 20 ушло).
Пошел на задачу D, сначала решил взять группу 5, потом думал минут 10 над 6 группой, минут 10 над первой, безуспешно. (в сумме 30 мин ушло).
Оставалось 2 часа, задачи C и D я решил больше не трогать. Вернулся к 3 группе задачи B, придумал только n * sqrt(n), что казалось недостаточным.
Вернулся к первой задаче. Все оставшееся время (1,5 часа) потратил на нее. Придумал пару жадников решающих контртесты, но WA. Решил набрать группы 2-4, но 4-я слетела по TL. Контест завершился. Мой жадос в A оказался почти правильным, добавив 1 модификацию я бы получил 100.

День 2
Прочитал A, через мин 30 решил перейти на B. По ней решил группы 1-3, 8, 9 (минут 30). Прочитал C, написал брут, проанализировал другие группы, решил для k=2 и пошел читать D. (30 мин)
На D тоже потратил около получаса, проанализировал тесты, придумал отжиг. Решил отложить, записав идею на листочке.
Вернулся к задаче B, по ней у меня было больше всего идей. Придумал полное решение, однако оно требовало большого количества времени на написание, решил реализовать сначала его упрощенную версию для маленьких m и/или n, однако даже оно словило WA. Был достаточно большой разбор случаев, видимо где-то опечатался, долго дебагать не стал. (~1 час)
За последние 2 часа я сначала вернулся к задаче A. Полчаса думал, написал бруты, полной идеи не было, решил перейти на D.
За час на D написал отжиг, взял 14 баллов, модифицировал, взял 22 балла.
Последние 30 мин потратил на A, безуспешно.

Что надо было делать по-другому на олимпиаде?
Да даже не знаю, я действовал по своей тактике : пробую задачи по порядку, трачу ~30 мин (если есть идеи, время может немного увеличиться), беру легкие группы,
в оставшиеся 3 часа смотрю где и что я могу улучшить. Всегда работало, по каждой задаче были баллы. Но тут видимо был другой случай.
За легкие группы по задачам давали мало баллов.
И в принципе раз диплом - 207 баллов, на этой респе лучшим было ничего вообще не читать кроме задач A. За 5 часов в каждом из дней точно придумаешь и сдашь первую задачу. Ну и еще время на пару брутов (чтобы до диплома добить) останется.

Но это конечно шутка, и следовать такому точно не стоит, однако на данном соревновании это работало гораздо лучше моей тактики)

Что надо делать по-другому при подготовке к олимпиаде?
Да тоже точно не знаю. У нас была очень хорошая подготовка. Дома я тоже решал множество разных задач, писал виртуалки и официальные соревнования для отработки поведения на олимпиаде.
Лучшая подготовка к этому соревнованию была бы такой : решать только задачи cf на теги конструктив/математика/жадный. Никаких алгоритмов, ДПшек, структур, на диплом, как минимум, знать вообще не надо было. Однако конечно готовиться к соревнованию (не зная каким оно будет) решая только однотипные задачи - тоже не вариант. Но видимо раз такое происходит, то к респе надо больше времени уделять именно таким задачам.

Мои выводы :
Ну, во первых я убедился что идеальной тактики быть не может, и надо быть достаточно гибким : взять и полностью изменить тактику прямо на олимпиаде. Например я мог не писать частички, а только сначала все просмотреть и решить что зачем мне вообще время тратить на определенные задачи, если там и легкие группы пишутся не очень мало времени и берут мало баллов. Но конечно это до сих пор в голове не укладывается и из этого следует второй вывод - надо уметь рисковать. (но все же немного) Я понял, что результат на олимпиаде не всегда зависит от себя самого. Есть вероятность, что на контесте выработанная, хорошая тактика окажется нерабочей или попадется какая-нибудь конструктивная задача, решение которой просто не придёт в голову. Конечно с опытом вероятность такого исхода падает. Но она все равно есть

Потому что я не считаю что мало уделял времени подготовке или не решал что-то нужное. Я всегда был и остаюсь достаточно самокритичным и не хочу скидывать ответственность на авторов задач, но я считаю, что мне просто не повезло. Но повторюсь, безусловно с ростом времени работы вероятность невезения стремится к нулю.

Мой профиль

1 День
Сразу сел читать первую задачу и думать над ней. Поддался соблазну и начал писать первое нерабочее решение достаточно быстро после начала, не сильно обдумав. После того как понял что оно не рабочее начал решать остальные задачи. Троху подумав над всеми задачами я решил более глубоко думать А и Б более-менее параллельно. Долго не мог ничего придумать на высокие балы. После нескольких провальных попыток написать А я написал частички на все остальные задачи и начал упорно трудится только над А и Б. Потом как написал 43 бала на Б, понял что наглеть не надо и оаствил оставшиеся полтора часа только на А. Это оказалось хоршей идеей, потому что после написания множества казавшихся нормальными решений я нашёл в чём была загвоздка их всех и почему они брали только 5 балов, поменяв ее я досдал задачу на 78. Я пробовал подумать как ее сдать на фулл, но там сама идея была медленной и как соптимизтировать идей не было, поэтому я написал еще какие-то частички на С и Д. Эта тактика оказалась на удивление неплохой, я получил достточно много баллов относительно других, хотя в моменте я думал что делаю плохие решения.

2 День
Я решил сращу читать все задачи и потиху параллельно думать какие группы могу сходу решить. Эта идея кажется очень логичной на первый взгляд, но из-за того что все частички были очень неочевидными/сложными и давали мало баллов, это заставляло немного напрячься. По итогу моих раздумий я понял что смогу почти 100% взять 10 баллов на Д и еще какие-то баллы рандомом/отжигом. Я начал сидеть над А, Б, С. за 2 часа я смог сдать все эти 3 задачи только на 5 баллов. Спустя 15-20 минут попыток написания какого-то отжига, я понял что не смогу его сделать и написал просто брут, был уверен что написать что-то еще на большие баллы не смогу потому что это было как-то непрдесказуемо и тести после второго были ооочень большими. По итогу еще смог дописать подгруппу на С на еще 7 баллов и так и не смог додебажить сложное, но по идее правильное решение на 30-40 баллов А.

- что надо было делать по-другому на олимпиаде
В первый день итог выдался хорошим для таблицы хоть и досточно плохим если рассматривать конкретно мои возможности.
Во второй день возможно стоило посвятить всё время А, и пытаться ее решить как-то с других сторон, достаточно простое и банальное решение которое задумывалось авторами почему-то не приходило в голову.

- что надо будет делать по-другому при подготовке к олимпиаде
Явно имело смысл много решать CF раунды, там явно можно выработать стойкость к конструктивам и жадникам

Мой профиль

Задача с областной интернет-олимпиады 8-9 классов.
https://official.contest.yandex.ru/CYF/contest/61623/problems/G
Вердикт memory-limit на 2-ой (13-ый тест) и последней подгруппах.
Выяснили, что не слетает по памяти (а уже по runtime-error) на 2-ой подгруппе (тоже 13-ом тесте), если поставить ограничение на Q=11000. При Q=12000 и более слетает по памяти.

#include <bits/stdc++.h>
//mr.Chest's code

#define f first
#define s second
#define pb push_back
#define pf push_front
#define in insert
#define it iterator
#define nl '\n'

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC poison

typedef int64_t int64;
typedef uint64_t uint64;
typedef uint32_t uint;
typedef long double ld;

using namespace std;

const pair <int,int> h[4] = {{0,-1},{0,1},{-1,0},{1,0}};

#define N 800
#define M 800
#define Q 11000

vector <int> qu;
vector <bool> v;
bool was[N][M];
vector <pair <int,int>> w;
int n,m,q,x[N][M],sz[N*M],pr[N*M],nxt[N][M],lst[N][M],t[Q],r1[Q],r2[Q],c1[Q],c2[Q];

void dfs(int x,int y){
    was[x][y]=1;
    qu.pb(x*m+y);
    assert(qu.size()<=n*m);
    for (auto u : h)
        if (0<=x+u.f && x+u.f<n &&
            0<=y+u.s && y+u.s<m &&
            !was[x+u.f][y+u.s])
            dfs(x+u.f,y+u.s);
}

int get(int x){
    return ((pr[x]==x)?x:pr[x]=get(pr[x]));
}

void add(int x,int y){
    x=get(x);
    y=get(y);
    if (x==y)
        return;
    if (sz[x]<sz[y])
        swap(x,y);
    pr[y]=x;
    sz[x]=max(sz[x],sz[y]+1);
}

void del(int i,int j){
    if (lst[i][j]>-1)
        nxt[i][lst[i][j]]=nxt[i][j];
    if (nxt[i][j]<m)
        lst[i][nxt[i][j]]=lst[i][j];
    pr[i*m+j]=i*m+nxt[i][j];
}

main(){
    cin.tie(0); ios_base::sync_with_stdio(0); cout.tie(0);
                iostream::sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i=0;i<n*m;i++)
        pr[i]=i;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++){
            lst[i][j]=j-1;
            nxt[i][j]=j+1;
            x[i][j]=1e9;
        }
    for (int k=0;k<q;k++){
        cin >> t[k] >> r1[k] >> c1[k] >> r2[k] >> c2[k];
                       r1[k]--; c1[k]--; r2[k]--; c2[k]--;
        if (t[k]==2){
            for (int i=r1[k];i<=r2[k];i++){
                int j=get(i*m+c1[k]);
                if (j / m != i)
                    continue;
                j %= m;
                while (j<=c2[k]){
                    x[i][j]=k;
                    was[i][j]=1;
                    w.pb({i,j});
                    assert(w.size()<=n*m);
                    del(i,j);
                    j=nxt[i][j];
                }
            }
        }
    }
    for (int i=0;i<n*m;i++)
        pr[i]=i;
    int mx=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if (!was[i][j]){
                qu.clear();
                dfs(i,j);
                mx=max(mx,int(qu.size()));
                assert(qu.size()<=n*m);
                sz[qu[0]]=(qu.size()>1);
                for (int y=1;y<qu.size();y++)
                    pr[qu[y]]=qu[0];
            }
    for (int k=q-1;k>=0;k--){
        while (w.size()>0 && x[w.back().f][w.back().s]==k){
            int i=w.back().f,j=w.back().s;
            if (i>0 && x[i-1][j]>=k)
                add(i*m+j,(i-1)*m+j);
            if (i<n-1 && x[i+1][j]>=k)
                add(i*m+j,(i+1)*m+j);
            if (j>0 && x[i][j-1]>=k)
                add(i*m+j,i*m+j-1);
            if (j<m-1 && x[i][j+1]>=k)
                add(i*m+j,i*m+j+1);
            w.pop_back();
        }
        if (t[k]==1){
            if (x[r1[k]][c1[k]]<k || x[r2[k]][c2[k]]<k){
                v.pb(0);
                continue;
            }
            v.pb(get(r1[k]*m+c1[k])==get(r2[k]*m+c2[k]));
        }
    }
    for (int i=v.size()-1;i>=0;i--)
        cout << (v[i] ? "Yes" : "No") << nl;
}

Даже если считать, что vector занимает не N, а 2N памяти из-за доп. места и указателей, то мой код (по моим подсчётам) требует O(11NM+7Q) памяти (int'ов), или же 32 Mb (и то в крайнем случае)
(поясняю за цифры:
Есть 5 массивов (int'ов) размерности N*M: x, sz, pr, nxt, lst;
5 массивов (int'ов) размерности Q: t, r1, r2, c1, c2;
Вектор (int'ов) qu, размерность которого (в пике) N*M;
Вектор (int'ов) v, размерность которого (в пике) Q,
Вектор пар int'ов w, размерность которого (в пике) N*M.
Получаем, 5NM+5Q+(NM+Q+2NM)*2/*на 2, если считать, что вектор занимает 2N памяти от размерности N*/ = 11NM+7Q
). Но почему-то слетает по памяти при ограничении 512Mb.

Мой профиль

Я заменил vector'а на массивы, ничего не поменялось. Вот код:

#include <bits/stdc++.h>
//mr.Chest's code

#define f first
#define s second
#define pb push_back
#define pf push_front
#define in insert
#define it iterator
#define nl '\n'

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC poison

typedef int64_t int64;
typedef uint64_t uint64;
typedef uint32_t uint;
typedef long double ld;

using namespace std;

const pair <int,int> h[4] = {{0,-1},{0,1},{-1,0},{1,0}};

#define N 800
#define M 800
#define Q 11000

bool was[N][M],v[Q];
int n,m,q,x[N][M],sz[N*M],pr[N*M],nxt[N][M],lst[N][M],t[Q],r1[Q],r2[Q],c1[Q],c2[Q],qu[N*M],wSize,vSize,quSize;
pair <int,int> w[N*M];

void dfs(int x,int y){
    was[x][y]=1;
    qu[quSize]=x*m+y;
    quSize++;
    for (auto u : h)
        if (0<=x+u.f && x+u.f<n &&
            0<=y+u.s && y+u.s<m &&
            !was[x+u.f][y+u.s])
            dfs(x+u.f,y+u.s);
}

int get(int x){
    return ((pr[x]==x)?x:pr[x]=get(pr[x]));
}

void add(int x,int y){
    x=get(x);
    y=get(y);
    if (x==y)
        return;
    if (sz[x]<sz[y])
        swap(x,y);
    pr[y]=x;
    sz[x]=max(sz[x],sz[y]+1);
}

void del(int i,int j){
    if (lst[i][j]>-1)
        nxt[i][lst[i][j]]=nxt[i][j];
    if (nxt[i][j]<m)
        lst[i][nxt[i][j]]=lst[i][j];
    pr[i*m+j]=i*m+nxt[i][j];
}

main(){
    cin.tie(0); ios_base::sync_with_stdio(0); cout.tie(0);
                iostream::sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i=0;i<n*m;i++)
        pr[i]=i;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++){
            lst[i][j]=j-1;
            nxt[i][j]=j+1;
            x[i][j]=1e9;
        }
    for (int k=0;k<q;k++){
        cin >> t[k] >> r1[k] >> c1[k] >> r2[k] >> c2[k];
                       r1[k]--; c1[k]--; r2[k]--; c2[k]--;
        if (t[k]==2){
            for (int i=r1[k];i<=r2[k];i++){
                int j=get(i*m+c1[k]);
                if (j / m != i)
                    continue;
                j %= m;
                while (j<=c2[k]){
                    x[i][j]=k;
                    was[i][j]=1;
                    w[wSize]={i,j};
                    wSize++;
                    del(i,j);
                    j=nxt[i][j];
                }
            }
        }
    }
    for (int i=0;i<n*m;i++)
        pr[i]=i;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if (!was[i][j]){
                quSize=0;
                dfs(i,j);
                sz[qu[0]]=(quSize>1);
                for (int y=1;y<quSize;y++)
                    pr[qu[y]]=qu[0];
            }
    for (int k=q-1;k>=0;k--){
        while (wSize>0 && x[w[wSize-1].f][w[wSize-1].s]==k){
            int i=w[wSize-1].f,j=w[wSize-1].s;
            if (i>0 && x[i-1][j]>=k)
                add(i*m+j,(i-1)*m+j);
            if (i<n-1 && x[i+1][j]>=k)
                add(i*m+j,(i+1)*m+j);
            if (j>0 && x[i][j-1]>=k)
                add(i*m+j,i*m+j-1);
            if (j<m-1 && x[i][j+1]>=k)
                add(i*m+j,i*m+j+1);
            wSize--;
        }
        if (t[k]==1){
            if (x[r1[k]][c1[k]]<k || x[r2[k]][c2[k]]<k){
                v[vSize]=0;
                vSize++;
                continue;
            }
            v[vSize]=get(r1[k]*m+c1[k])==get(r2[k]*m+c2[k]);
            vSize++;
        }
    }
    for (int i=vSize-1;i>=0;i--)
        cout << (v[i] ? "Yes" : "No") << nl;
}

Мой профиль

Геннадий Марцинкевич:

Задача с областной интернет-олимпиады 8-9 классов.
https://official.contest.yandex.ru/CYF/contest/61623/problems/G
Вердикт memory-limit на 2-ой (13-ый тест) и последней подгруппах.
Выяснили, что не слетает по памяти (а уже по runtime-error) на 2-ой подгруппе (тоже 13-ом тесте), если поставить ограничение на Q=11000. При Q=12000 и более слетает по памяти.
[…]
Даже если считать, что vector занимает не N, а 2N памяти из-за доп. места и указателей, то мой код (по моим подсчётам) требует O(11NM+7Q) памяти (int'ов), или же 32 Mb (и то в крайнем случае)
(поясняю за цифры:
Есть 5 массивов (int'ов) размерности N*M: x, sz, pr, nxt, lst;
5 массивов (int'ов) размерности Q: t, r1, r2, c1, c2;
Вектор (int'ов) qu, размерность которого (в пике) N*M;
Вектор (int'ов) v, размерность которого (в пике) Q,
Вектор пар int'ов w, размерность которого (в пике) N*M.
Получаем, 5NM+5Q+(NM+Q+2NM)*2/*на 2, если считать, что вектор занимает 2N памяти от размерности N*/ = 11NM+7Q
). Но почему-то слетает по памяти при ограничении 512Mb.

Геннадий Марцинкевич:

Я заменил vector'а на массивы, ничего не поменялось.

Для начала, если по памяти слетает не на всех тестах, то виноваты скорее всего отнюдь не статические массивы (которые при каждом запуске создаются в одном и том же размере).

Вообще довольно сложно сказать сколько места займёт вся программа, но я тут в коде наблюдаю рекурсию с фактическим потолком в навскидку те же N*M (=640000 если я не разучился в умножение)… причём технически даже не одну (хотя вторая срезает повторное применение, предельный потолок это всё же не снижает). А в отличие от всяких Pascal'ей, со стеком у C всё очень сильно по-разному бывает (зависит от компилятора, параметров компиляции и от OS на которой запускается, включая настройки окружения). Понятия не имею как у них там сервер настроен, но вполне допускаю что полмиллиона копий процедуры в стек программы на C не влезет, вне зависимости от ограничения памяти в условии задачи.

Конечно, остаётся вопрос при чём здесь тогда Q… Но в этом коде включено две директивы агрессивной (и весьма сомнительной) оптимизации за счёт размера кода в том числе, так что вопрос объёма кода в памяти в принципе сложный выходит.

(…Ну и поскольку речь идёт о C, всегда есть шанс что где-то арифметика указателей привела к обращению куда не надо, с непредсказуемым результатом.

)
______________________
// LeX

Мой профиль

Опции компиляции на Яндекс.Контест
https://contest.yandex.ru/compilers/

GNU GCC 13.1 C++20 g++ -O2 -lm -fno-stack-limit -std=c++20 -x c++ source.cpp -o executable ./executable
GNU GCC 13.1 C17 gcc -lm -O2 -fno-stack-limit -std=c17 -x c source.c -oexecutable ./executable

Я так понимаю "-fno-stack-limit" означает, что нет ограничения на стек.

Как же всё-таки
1) Измерить использованную память?
2) Найти ошибку в коде если она есть?
На машине Гены ответ выдаётся правильный.
Диспетчер задач показывает, что использовалось 51Мбт ОП.