Codeforces Round #181 (Div. 2)

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

Всем привет!

Очень скоро, 25 апреля в 19:30 MSK, состоится очередной Codeforces Round #181 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Игнатьев Александр (aiMR). Выражаем благодарность Геральду Агапову(Gerald) за помощь в подготовке задач, Михаилу Мирзаянову(MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой(Delinur) за перевод задач на английский язык.

Немного информации об авторах: я и Александр — студенты 3 курса Механико-Математического факультета Саратовского Государственного Университета. Для нас это первый раунд и, я думаю, что не последний.

Мы надеемся, что Вам понравятся наши задачи, и вы получите удовольствие от их решения.

Также настоятельно рекомендую Вам прочесть условия всех задач!

Всем удачи и высокого рейтинга!

UPD: Разбалловка задач будет динамической. Задачи расположены в порядке предполагаемой сложности.

UPD1: Разбор задач

UPD2: Соревнование закончено. Поздравляем победителей:

// ax + by = gcd(a,b) = d void eea(int a, int b, int& x, int& y, int& d) { if (!b) {x = 1; y = 0; d = a; return; } eea(b, a % b, x, y, d); int x1 = y, y1 = x - (a / b) * y; x = x1, y = y1; } int divide(int a, int b) { int d, x, y; eea(b, MOD, x, y, d); // if(a%d==0) return ((x+MOD)*(a/d)) % (MOD/d); // else "no quotient" }

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

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

gamezovladislav

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

+34

С дебютом авторов и ВСЕМ удачи! Надеюсь задачи будут как всегда интересные)

→ Ответить

dragan224

+41

Can't wait, hopefully it won't be too much maths :D

sparik

← Rev. 2 →

-7

Death_With_Live

I think it will be interesting.

toposort

-9

Good Luck ^_^

somag

-24

I hope the system testing starts soon after the contest not like the last contests.

dario-dsa

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

-20

System testing after contest starts when authors of task check all hacks.

egor-belikov

I think it's not true because all hacks are checked automatically by validator.

I suppose that main reason of our waitin' is that validator checks all the hacks.

irakli_p

-18

Welcome ! New authors always have interesting problems I think today it will be too :)

m17

One of the best announcements I ever read !!

abo

i hope today will be my day :))

nikalosaberidze

oh oh oh, abo's day its unbelievable :D :D

JuanMata

-11

gl & hf all! :)

halin.george

+24

Еще полгода назад я и не знал о таком сайте, как codeforces. Очень часто в контестах встречаются интересные задачи, способствующие развитию мышления. Я уже в нескольких контестах принимал участие, разумеется, с удовольствием приму участие и в этом контесте. Спасибо авторам за подготовленный контест. Всем успехов!

GonZaleZ

Он был бы ещё более замечательным, если б тут не минусовали любой попавшийся коммент, как твой)

-6

Абсолютно согласен. Я вчера вопрос задал и мне 65 лайков наставили:)

aitzhan.askar

-23

Сегодня состоится 181 раунд codeforces, я как участник этой олимпиады, готов участвовать в нем.

mbaros

+13

Саратовске ребята всегда готовят хорошие задачи. Удачного контеста всем...!!!

pakita

Главное чтобы не "первый блин комом" :)

newid

This is my first contest in codeforces, hope i can solve some problems in the contest

shakil_AUST

+10

best of luck, buddy.....:)

thanks , pray for me , best of luck to you also

CountZero

Hello, I'm Commander Sheppard and this is my first contest on Codeforces!

Igorjan94

+17

ой кого-то забанят...

17 	boy_boy10 	0
18 	boy_boy9 	0
19 	boy_boy8 	0
...

JKeeJ1e30

+25

Найти бы отца этих мальчиков.

newjakir

Hope to solve at least 3 problems :)

woot

what'er pity not joinning this contest= =..dynamic scoring could be really exciting and fun T____T...hope to reach 1700 T_T

← Rev. 3 →

+12

WTF???
UPD: he has already -179 hacks...

dalex

Codeforces was down. But how could lrb know about it? He was sure that the solution was incorrect. He pressed and pressed the button Hack! but nothing was happening. "Ok, I'm going to count how many times I pressed that damned button!", he thought: "66, 67, 68! Codeforces is available again! Let's see where my +100 points are..."

Ximera

Now he has 215 unsuccessful hacks

EG0R

Психанул!)

Suhaylee

When I saw that lrb wanted to hack my code my heart started boom boom boom:)I thought that my solution is wrong:)but when i saw that he has more than 100 unsuccessful hacks i understood that he want to break record and i calmed down:)

lrb

우리의 위대한 지도자 김 장군의 명예에, 나는 미국 제국주의를 정복 할 수있을만큼 우리 민족 강하게 만들기 위하여 열심히 컴퓨터 과학을 공부합니다!

Droom

Your letters are so cute :)

-12

what is the 5th test in B problem??? "@

Nakilon

Как всегда, узнаю о контесте когда он уже идет или прошел...

А задача D мне нравится. Почему ее так плохо решают? ..(

krzys.minib00m

Hey, really enjoyed this competition, but i got a little problem with problem C. So im asking you for little help.

Here is what i came up with: We generate all possible sums ( highest possible sum has 6 digits ) and make equation

N = x*a + y*b, where N is our sum ( we do this with every generated sum ).

And we find number of solutions to this equation that: x>0, y>0 and a+b<=N ( it's pretty

clear ).

For most of my time i was trying to come up with some nice dp solution, but it turned

out to be impossible for me... If it's one right solution desribed above, then please explain to me how to calculate

those all solutions nicely?? Because for me it got too messy and i finished with only 2

first tasks :(

:) Thanks in advance

Elun

I think that answer is sum(C(n, x)) if N = x*a +y*b is good, but there is small problem for me, how fast and correct calc C) Sorry for my bad english.

demolishka

n!/(x!*y!) — number of different numbers of length n and containing x of "a" digits and y of "b" digits.

Reza_H

You can use this : C( n , k ) = n! * pow( (n-k)! * k! , mod-2 )

from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !

Sorry for my bad english

zulkan

i knew there is must be using some number theory, but, sadly after knowing a and b value, i cant compute C(n,a)

could you explain more with n = 14215 and k = 13517 ?

thx (taken from test 3 )

only pre-calculate every factorials module 1000000007 and store this numbers in an array .( for example fact array ) this step takes O(N) time and space .

then C( n , k ) = fact[n] * power( fact[k] , mod-2 ) * power( fact[n-k] , mod-2 ) . this step takes O( Log N ) .

farzad.shbfn

or calculating c(n,k) using c(n,k-1) c(n,k) = c(n,k-1)*(n-k+1)/(k)

but as Reza said, we have to pre-caculate them.

S.Ged

actually this wont work !

because there is no necessity that c(n,k-1)%MOD or (n-k+1) is divisible by k.

this will lead you to WA.

of course!

i didn't mention that for dividing u need to use modular division, i just said that this is another way tu calculate c(n,k)...

for dividing u can use pow(k, mod-2)(as Reza said) or use Extended Euclid algorithm :

both run in O(logn) time. however, pow(k,mod-2) is a lot easier... ;)

so that was my fault, I misunderstood you. :)

hiukim

"from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !"

Could you provide references to this proof?

from "fermet's little theorem" : a^(p-1) % p = 1

thus a * a^(p-2) % p = 1 and a % p == a^(p-2) % p from other view a * ( 1/a ) % p = 1 and a % p == (1/a) % p

finally : (1/a) % p == a^(p-2) % p

ptnk_1215_panaka_13

the same idea, but a little bit differences. x is the number of digits a still have sum=a*x+b*(n-x) (a,b from input), for each single value of x, i check whether sum is a good number. if yes, calculate number of numbers you can create with that.

the only problem that i had is the final step.

Egor.Lifar

Хорошо! Понравилось решать задачи) Спасибо очень хороший контест gridnevvvit :)

popoffka

Как решалась Е?

Очевидным решением было разложить произведение чисел из ввода на простые сомножители и потом бинарным поиском искать такое число, разложение факториала которого содержит каждое простое число, которое содержится в разложении силы Империи, как минимум столько же раз.

Но, естественно, разложение произведения чисел из ввода требует O(k * p * log a), что всё-таки слишком много.

Monyura

+15

Всё верно, основная задача посчитать степени простых в знаменатели, а сделать это можно с помощью решета, которое находит наименьший простой делитель числа. Когда мы все найдём, то для каждого числа от 1 до максимального а, посчитаем сколько раз оно войдёт в знаменатель, это просто кол-во чисел а, больше либо равных данного, а далее факторизируем его за О(кол-ва простых делителей). В сумме для всех чисел от 1 до 10 в 7 это работает быстро

I_love_Tanya_Romanova

Красиво)

Мой вариант, немного извращенный:

Посчитаем num[i] — сколько чисел i было в инпуте, на основании этого s[i] — сколько чисел в инпуте не больше i.

Теперь для каждого простого числа будем определять его степень в знаменателе. Как мы это делаем? Пусть наше число k. Рассмотрим все интервалы вида pk...pk+k-1, т.е. все интервалы чисел, которые при делении на k дают p, по всем p таким, чтоб интервал влезал в 10 миллионов. Для каждого такого интервала мы можем посчитать, сколько чисел из этого интервала было в инпуте, и для каждого такого числа мы знаем, что при вычислении его факториала мы p раз умножим на число, в разложении которого есть делитель k. Поэтому к степени числа k в знаменателе надо прибавить (s[pk+k-1]-s[pk-1])*p. Теперь нам надо обратить внимание на случаи, когда k входит в разложение в степени >1. Для этого решим аналогичную задачу для k^2, k^3, k^4 и так далее:)

Я думал над таким вариантом, но мне показалось что там просто гигантское кол-во операций получится, а сейчас прикинул, что там сумма ряда даже меньше гармонического) Если только первые степени рассмотреть, то получается n * (1 / 2 + 1 / 3 + 1 / 5 + ...), кстати кто-то в курсе оценок для его суммы, не O(log(log(n))) ли?

BekzhanKassenov

Я был очень близок... Как надо осуществлять проверку в бин. поиске?

Temirulan

Скорее одним пробегом, за O(k * log x).

accidentallygivenfuck

I can't believe that my B is going to fail because I forgot to check if the "connected-team" size is less than or equal to 3, submitted and locked it. Just after I locked it I remembered that. :(

Понравилась задача Е Звездные войны еще в моде)

-21

не савсем понятна задача D А как она решалась?

-28

задачу А не все сдали Просто реализация нечего сложного )

Смешно просто что задачу E не все сдали Просто реализация нечего сложного )

Andrew_Merkulov

Может мне кто-нибудь объяснить 2 вещи. Во-первых, почему в задаче С имеется вот такой вот тест: входные данные 2 3 10 выходные данные 165 Если я правильно понял условие, нужно найти количество "замечательных" чисел длины 10, то есть 10-значных чисел, состоящих из 2 и 3 и имеющих сумму, которая является "хорошим" числом. Ясно, что хорошие числа длины 10 могут иметь сумму от 20 (все двойки) до 30 (все тройки). В диапазоне от 20 до 30 есть только одно хорошее число — 23. Такую сумму имеют числа из 3 троек и 7 двоек. То есть, их количество 10!/(7!*3!)=120. Откуда 165?! Второе: почему в задаче D, в тесте 7 2 нельзя первым шагом выбрать 2-ю строку и 2-й столбец, получит 2 квадрата 1*1 и 5*5 и вторым шагом разбить на квадраты квадрат 5*5. Если можно, то почему ответ на тест 4?! Ответьте кто-нибудь, пожалуйста.

Не учёл вариант 8 2. Тогда получается хорошее число 22

Точно. А что с квадратами?

Ну если сделать, как вы говорите, получится еще два прямоугольника 1x5, что запрещено по условию

Ясно.

_malioboro

I think the problem more difficult than before.. a lot of counter testcase..

logic_max

I loved the contest, especially C, got it accepted at the last minute (stupid overflow mistake :(). This is when you have to love the dynamic scoring :)

Thanks!

gagaga5-gagaga

When is the rating come out??

SayWhatAgain

Nice contest, keep up the good work.

gaurarpit

-26

The problem A — Array in the description it guarantees a correct solution: 1st list -product should be negative 2nd list — product should be positive 3rd list — product should be zero

where as your pretext 3 test case is : Input 5 -1 -2 1 2 0 Output 1 -2 3 -1 1 2 1 0

This is incorrect. List 2 doesn't have a positive product. -1 * 1 * 2 = -2 is NEGATIVE. WRONG TEST CASE.

It's your output, not jury's.

ohh.. sorry.. got it now. i read it in the incorrect order... thanks.

problem-solved

what's the idea of problem D

UPD :

Fcdkbear

Расскажите что-то про 3-ий тест в задаче D. Я вижу, у многих ответы как у меня.

Делал так: 1) Для четных — ответ или 1 если k==0, или 0

2) Для нечетных — посчитаем глубину числа — сколько раз его можно делить на квадраты (пока делим на 2 и получаем нечетное число — наращиваем глубину). Далее динамика. В динамкие делим на 4 сына и пробуем перераспределеить действия между 4-мя сыновьями.

У тебя хотя бы 3, а у меня 2) И я толком не могу понять в чем не прав, но смысл такой же: максимальная "глубина" — это кол-во единичек подряд в двоичном представлении начиная с младшего разряда, кроме случая степени двойки минус 1, тогда глубину надо уменьшить на 1. Далее динамика D[k][deep] — кол-во способов разбить квадрат k разрезами с макcимальной глубиной разреза deep, пересчитывается D[k][deep]=D[a][deep-1] * D[b][deep-1]*D[c][deep-1]*D[d][deep-1] | a+b+c+d -1 = k; Чтоб за 3 степень не пересчитывать ещё во второй динамике храним Pr[k][deep] = D[a][deep]*D[k-a][deep];

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

Звучит вроде бы правдоподобно, пока баг не вижу.

Я тут немного подебажил — вроде что-то не так. Смотри, у тебя D[1][2]=2. То есть выходит, что квадрат глубины 2 можно разбить одним разрезом двумя способами.

Я переделал чуть твое решение — АС.

3630529