Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
Вернуться
Тема: Как нужно извратиться в 1391 задаче, чтобы уложиться в ML на яве?))
1
  1  Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 15:08:33
      Ограничение памяти в этой задаче подняли до 32 Мбайт, вариант с ArrayList<Integer> теперь проходит.
  2  Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 13:24:42
      С таким подходом к спискам смежности сдал с расходом памяти 6.4 Мбайт. Правда, в предыдущем сообщении баг в коде - первое ребро графа игнорируется. Правильно вот так (nV число вершин, nE число рёбер): инициализация int first[] = new int[1 + nV]; int vertex[] = new int[1 + nE]; int next[] = new int[1 + nE]; int size = 1; добавление ребра v1->v2: vertex[size] = v2; next[size] = first[v1]; first[v1] = size; size++; проход по рёбрам вершины v: for (int i = first[v]; i != 0; i = next[i]) { int child = vertex[i]; ... }
  3  Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 13:06:44
      Богдан, также Вы можете использовать подход классического Паскаля для реализации списков смежности (как я понимаю, основная загвоздка по памяти в них). Инициализация int first[] = new int[1 + nV]; int vertex[] = new int[nE]; int next[] = new int[nE]; int unused = 0; Добавление ребра v1->v2: vertex[unused] = v2; next[unused] = first[v1]; first[v1] = unused; unused++; Проход по рёбрам вершины v1: for (int v = first[v1]; v != 0; v = next[v]).
  4  Меньшиков Фёдор Владимирович, 05 ноября 2018 г. 12:53:50
      Сейчас написал свой IntArrayList - простейший на 22 строчки - с методами add, get, size - и прошло с памятью 9.9 Мбайт.
  5  Яндулов Богдан, 05 ноября 2018 г. 10:45:35
      Почему бы вообще не поднять ML для всех задач? На тимусе стандартный ML 64 Мб, на CF вообще 256.
  6  Яндулов Богдан, 05 ноября 2018 г. 10:43:44
      По идее, обычный Косарайю, где 2 массива списков, должен заходить без проблем. Но ML 8. С одним массивом списков - ML14.
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru