TopCoder SRM 622 - Codeforces

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:26:03
Зарегистрироваться »

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

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

№	Пользователь	Рейтинг
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

Всё →

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

→ Прямой эфир

Детальнее →

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

TopCoder SRM 622

Автор chrome, 10 лет назад, По-русски

Всем привет!

Завтра рано утром, в 05.00 MSK состоится Topcoder SRM 622.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

srm, topcoder, утро, контест, рано, сон

chrome
10 лет назад
29

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

Написать комментарий?

Edvard

10 лет назад, # |

Я один до сих пор чищу кеш Java перед каждым запуском арены? Это можно как-нибудь вылечить?

→ Ответить

zholnin

10 лет назад, # ^ |

Может быть и один, ибо я с такой проблемой в принципе не сталкивался. А что бывает если не почистить?

→ Ответить

subscriber

10 лет назад, # ^ |

Вот, у меня та же проблема.

→ Ответить

naik

10 лет назад, # ^ |

Создаем батник под названием arena.bat Пишем в нем: javaws http://www.topcoder.com/contest/arena/ContestAppletProd.jnlp

Сохраняем и помещаем в папку Windows.

Чтобы запустить нажимаем Win+R, пишем "arena", жмем Enter. И все больше проблем с ареной нет!

→ Ответить

Edvard

10 лет назад, # ^ |

Спасибо помогло

→ Ответить

Rubanenko

10 лет назад, # |

← Rev. 2 →

UPD: Уже все норм.

→ Ответить

indy256

10 лет назад, # |

Интересно, увеличили ли стек для java.

→ Ответить

nic11

10 лет назад, # |

← Rev. 2 →

Что-то сегодня в div2 маловато хаков было =(

→ Ответить

zholnin

10 лет назад, # ^ |

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

→ Ответить

oversolver

10 лет назад, # |

кто как решал 500?

написал дп: минимальное количество компонент на которые можно разбить поддерево вершины v так, чтобы макс высота от v была h. O(n * n * maxDist).

→ Ответить

Egor

10 лет назад, # ^ |

Можно жадно взять минимум по компонентам, из всех таких — минимум по высоте, потому что в крайнем случае это все можно просто отрезать — ответ увеличится на 1 только

→ Ответить

nic11

10 лет назад, # |

← Rev. 2 →

Увидел в своей комнате чувака, который по div2 250 написал решение с переполнением — искал первые 1000 чисел Фибоначчи. Естественно, я подумал, что это можно использовать. Вывел с таким же переполнением сгенеренные числа от 1 до 10^6. Там оказались только числа Фибоначчи и я чет приуныл :(

a[0] = a[1] = 1;
for (int i = 2; i <= 1000; ++i) {
    a[i] = a[i - 1] + a[i - 2];
    if (a[i] > 0 && a[i] < 1000000) cout << a[i] << " ";
}

→ Ответить

Gassa

10 лет назад, # ^ |

+13

Логично: шанс того, что "случайное" 64-битное число окажется в диапазоне от нуля до миллиона, равен 10⁶ / 2⁶⁴, это мало.

→ Ответить

nic11

10 лет назад, # ^ |

+13

Но все-же 32-битное. Но я надеялся изо всех сил :)

→ Ответить

Gassa

10 лет назад, # ^ |

Да, тогда довольно точная оценка сверху на вероятность — 1000·10⁶ / 2³², это чуть меньше четверти. Действительно, тогда стоило проверить.

→ Ответить

Gerald

10 лет назад, # |

+13

Это правда, что я балда, и 900 так не решается, как я ее посубмитил? Если нет, почему все Java-кодеры не посубмитили это на 850? Вроде же BigInteger умеет делать xor, или я туплю?

P.S. Я бы и сам попробовал написать на Java. Но, к сожалению, когда я открыл задачу было 18 минут до конца. А Java-IDE у меня на ноуте не стоит, я подумал, что не успею поставить.

→ Ответить

Gerald

10 лет назад, # ^ |

Забыл приложить решение.

vector<li> fs;
map<li, number> d;
number get(li rg){
    if(rg <= 0)
        return number();
    if(d.count(rg))
        return d[rg];
    number& ans = d[rg];

    int idx = sz(fs) - 1;
    while(fs[idx] > rg){
        idx--;
    }

    li F = fs[idx];
    ans = get(F - 1);

    if(((rg - F + 1) & 1) == 1)
        ans.change(idx);
    ans.xored(get(rg - F));
    return ans;
}

Ответ — это (get(B).xored(get(A-1))).md(1e9 + 7).

→ Ответить