Приветствуем всех на первом летнем раунде - Codeforces Beta Round #73
Авторами этого соревнования являемся мы: kuniavski (Павел Кунявский) и Zlobober (Макс Ахмедов). Соревнование проходит одновременно в двух дивизионах. Суммарно вам будет предложено 7 различных задач с вариациями в разных дивизионах, по 5 в каждом дивизионе. Мы надеемся что все смогут показать свой результат и решить как можно больше задач.
Мы хотим поблагодарить RAD (Артем Рахов) за помощь и множество полезных советов во время подготовки контеста, а также Delinur (Мария Белова) за перевод задач и MikeMirzayanov (Михаил Мирзаянов) за Codeforces в целом.
Мы хотим поблагодарить RAD (Артем Рахов) за помощь и множество полезных советов во время подготовки контеста, а также Delinur (Мария Белова) за перевод задач и MikeMirzayanov (Михаил Мирзаянов) за Codeforces в целом.
Поздравляем победителей!
Div1 - ilyakor
Div2 - peter50216
И еще немного статистики. Первые успешные посылки и хаки по дивизионам:
Div1-A Dmitry_Egorov 4:09
Div1-B ilyakor 13:05
Div1-C A_A_Lunyov 8:05
Div1-D hos.lyric 30:57
Div1-E rng_58 75:20
hack VArtem 26:15
Div2-A epizend 5:27
Div2-B random.johnnyh 19:15:29
Div2-C RomaFurko 11:31
Div2-D peter50216 41:18
Div2-E peter50216 54:00
hack diogen 55:33
Each division has, as usual, 5 problems.
It means that 3 problems will be common for each division.
мб такое?
2
typedef a b
typeof b
"Попытка использовать не объявленный ранее тип данных так же приведет к типу errtype."
видимо да)))
не runtime,и не только возвращается,а создается новый и заносится в map:
map<int,int>x;
int main()
{
int y=x[0];
printf("%d\n",x.size());
}
проверьте так.
И вот как такие ошибки ловить в тестах - непонятно :)
И так, кстати, ИМХО, лучше. Сразу видно, в TL всё-таки влазит или нет. А если с ленивой - непонятно.
При взломе, стала читать решения других. Оказалось что многие решали проще и хитрее. Может кто-нибудь напишет отличную идею решения.
UPD. И она все равно упала, так что даже и не обидно :D
UPD. Минус 3 символа и оно зашло.
Там же кроме for i in range(29) еще дополнительно одна строка выводится print "b" * 29 + "S".
I think, it was at bit disbalanced: first two problems was simple, C was classical, D and E required a lots of code.
Fill the grundy table g[0...N] and each g[X] means you have a game of X piles. Try all possible moves, i.e., all possible K such that X = a * K + (K*(K-1))/2 , which results in subgames {a,a+1,a+2,....,a+K-1}. The grundy of the collection of these subgames is ( g[a] ^ g[a+1] ^ ... ^ g[a+K-1] ). Some coders just iterated and found this value, but you can simply maintain a prefix xor on g[ ] , say pg[ ] and get it using pg[a+K-1] ^ pg[a-1] in O(1). g[X] = the mex among all grundy values reachable from X. Complexity is O( n . sqrt(n) )
This round may be easier than past round (Div2). Normally, I solve only one problem during contest, but today i solve 3 problems
Сначала написал "почти верное" решение с желаем дооптимизить позже :) Забыл и радостно получил TL
1000000 999999
a*b идет переполнение.
Печаль :(
Codeforces имеет в целях в том чисел и подготовку к более продолжительным и серьезным олимпиадам, и если например на Всеросе ты теряешь 20-30 баллов потому, что не написал рандом в qsort, то становится обидно
Но это, конечно, моё мнение.
Даже с рандомизированными алгоритмами ведь вообще такая фигня, что если решить их позволять, то у какого-нибудь эпичного неудачника может не пройти, а если решить их не позволять, то жюри навряд ли сумеет сделать тесты, кототые валят по всем возможным рандсидам, однако это будет несколько проще сделать тем, кто будет взламывать, - ведь они будут видеть код (ну, это озвучил уже и предыдущий оратор). Да и неравноправие языков усиливается, ведь где-то есть встроенные рандомизированные алгоритмы, в которых этот самый сид зависит от погоды, а где-то нет (Java & C++ vs Pascal). Поэтому минусуйте меня семеро, но я скажу, что в идеале во избежание Q-срача надо не давать задачи, в которых требуется сортировка за O(N * logN), а во избежание хешесрача - соответственно, задачи, где вообще можно решать с ними, с хешами.
Ну и ещё, кстати, такой момент. На ACM можно увидеть, что не прошло, и переделать. На школьной олимпиаде можно потерять только часть баллов. На TopCoder ограничения маленькие, там даже всякие лишние линии вместо логарифмов не повредят. А вот здесь, на Codeforces...
Насчет хешей и сортировок: у авторов же всегда есть решение, которое работает(!), значит видимо у участника ручки кривые, если не зашло то, что должно было
Т.е. пофигу, какое p брать в выражении a0 + a1· p + a2· p2 + a3· p3 + ...?
Серёжа Копеилиович на этих зимних сборах о ней говорил, помнишь?
А с недетеримнированными хуже - всё-таки анализировать рандомные значения как-то сложно.
Просто я хочу донести мысль, что детерминированный алгоритм за O(n^2) в худшем случае ну ничем не отличается от неоптимального решения.
Смотрю задачи. Авторы молодцы, победителю слава!
Main idea is that we sort edges and add by groups in the graph, counting for each new edge all the paths that include it using DSU.
b=999999
gcd(a,b)=1;
a*gcd(a,b)=1000000;
a*b>2^31-1
Немного не в тему, но когда будет дата следующего матча?
У меня сейчас 2 варианта: либо он будет очень нескоро, либо нам сообщат о нем очень незадолго до самого матча)
By the way, the link to the tutorials is wrong.
greetings
When I used scanf("%lld%lld",&a,&b); --- it gave me wrong answer.
But when I used cin>>a>>b; --- the solution was accepted!!
What was the problem? Anyone please reply.
That wasted my 25 minutes :sob:
Concerning problem D,
I wonder if if final tests contained this type of a test:
We have a large tree with this structure -
4
1 2 1
2 3 2
3 4 3
It is a straight line tree with the largest weight edge at the bottom.
I m guessing final tests, skipped such a case. I could notice solutions without the use of DSU pass the system tests but fail this one.
Appreciate a reply.