Codeforces Round #140

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

+20

Abra какая-то получается.

→ Ответить

Androik

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

-18

Настроение у всех осеннее: вот у меня, например, уже три дня дождик накрапывает и тучи на все небо. Минусуя, все так прощаются с летом)

→ Ответить

Trytrytry

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

-22

Поэт что-ли?

→ Ответить

Androik

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

← Rev. 2 →

-15

Ага) Пушкин) - ...Дни поздней осени бранят обыкновенно, - Но мне она мила, читатель дорогой, - Красою тихою, блистающей смиренно. - Так нелюбимое дитя в семье родной - К себе меня влечет. Сказать вам откровенно, - Из годовых времен я рад лишь ей одной, - В ней много доброго; любовник не тщеславный, - Я нечто в ней нашел мечтою своенравной...

→ Ответить

RodionGork

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

+14

"Сегодня в 19:30 по Московскому времени" — по-возможности нельзя ли пожалуйста указывать к какому дню относится "сегодня". Я понимаю что в большинстве случаев это можно вычислить по дате поста... Которая выглядит как "столько-то часов назад"... Но всё же. ;-)

→ Ответить

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

+27

Если навести курсор на "столько-то часов назад" — всё станет понятно.

→ Ответить

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

+79

Всем желаю слить и опуститься в рейтинге!
Ну а если серьёзно, то чтобы задачи порадовали и, возможно, научили чему-то новому.

→ Ответить

TheWishmaster

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

← Rev. 2 →

Спасибо, тебе того же!

→ Ответить

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

Отличная шутка.

→ Ответить

TheWishmaster

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

// Информация о разбалловке появится незадолго до начала раунда.

А почему так?

→ Ответить

danpol

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

Готовят сюрприз))

→ Ответить

TheWishmaster

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

← Rev. 2 →

-11

Стандартная — зря

→ Ответить

BekzhanKassenov

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

Осенний пессимизм на КФ — положительный пост с пожеланиями успехов заминусовали, а пожелания слить рейтинг — +25

→ Ответить

qwerq

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

+22

я может быть понял

Здесь сливаются любые посты, кроме: 1) нормально-средних шуточек-прибауточек 2) постов красных (не видел ни разу, чтобы красных именно слили; может, так бывает, но это скорее исключение) 3) нормально-средних вопросов/ответов участников

А вот посты с пожеланиями удачи минусуются вне зависимости от того, какое количество няшности автор в него вложил)

→ Ответить

Petruchcho

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

+32

4) Шутки про JKeeJ1e30

→ Ответить

Fefer_Ivan

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

+44

Просто если каждый из 2000+ зарегистрировавшихся участников напишет один коммент "Good Luck & Have Fun", то ленту будет невозможно читать. На TopCoder'е пишут такие сообщение, потому что каждое из них содержится в своей комнате.

→ Ответить

DmitriyH

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

Вопрос по системе в целом: доступна ли эта фича сайта во время соревнования?

P.S. Да, абсолютно верное решение всегда проходит по времени с запасом и эта фича не нужна. :)

→ Ответить

andreyv

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

+14

Да, доступна.

→ Ответить

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

I have a question. In round #138 they explicitly said that "D language will not be available on this contest.". In the emails I get I don't ever see it mentioned in the list of available languages. What's up with that? :)

→ Ответить

MikeMirzayanov

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

You may use it on your own risk. We will announce official support after we will be sure that everything is OK.

→ Ответить

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

Attention CHelper users. Codeforces for whatever reason slightly changed task pages format (capitalizing some tags) rendering CHelper not possible to parse tasks. Please update your plugins through File->Settings...->Plugins, right click on CHelper->Update plugin

Пользователи CHelper, Codeforces по какой-то причине слегка изменил формат страниц с задачами (некоторые теги стали большими буквами). Старая версия CHelper не может их распарсить. Обновите плагин через File->Settings...->Plugins, правый клик по CHelper->Update plugin

→ Ответить

ymondelo20

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

-7

I have the impression that today... tourist, again surpass the 3000 points ... A new range? Something like Intergalactic Grandmaster? LOL

→ Ответить

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

tourist was here 5 days ago.

→ Ответить

GaryYe

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

+21

He is in Italy probably(IOI), so I don't think so :)

→ Ответить

tunyash

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

i have a dream

→ Ответить

scorpion

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

← Rev. 2 →

-45

Читайте спойлер!!!!!

→ Ответить

Petru

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

-16

Can somebody explain C. I can't understand it :(

→ Ответить

nurhidayat

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

-19

why my C got wrong answer at pretest 1? I already same as the sample IO

→ Ответить

KirillTim

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

Первый раз участвую, поясните , почему может постоянно быть ошибка на претесте 1.(задача В) Хотя код гонял на куче тестов и он работал?

p.s писать ответ надо в standard.output или в standard output?

→ Ответить

Miras321

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

Без файлов надо сдавать)

→ Ответить

KirillTim

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

← Rev. 2 →

О_о спасибо, просветил)

всёравно падает(

→ Ответить

aram_gyumri

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

у тебя проблема в том что решение А отправил за В

→ Ответить

KirillTim

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

Программа называется A)) а на самом деле это В) Но возможно , что моя программа просто плоха

→ Ответить

Fefer_Ivan

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

+12

Все вопросы надо задавать авторам через кнопку "задать вопрос" на странице со списком задач внизу.

→ Ответить

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

Anyone search ideas from Google for E(Div 2)/C(Div 1) like me?

→ Ответить

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

← Rev. 2 →

We can use fact, that gcd(Fib_x, Fib_y) = Fib_gcd(x, y). But I have still no correct idea how to get subset with maximal gcd(since binary search is wrong).

→ Ответить

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

← Rev. 2 →

def d_down( r,l,k ):
  d = (r-l)/(k-1)                                    ### 1 below
  while d > 1:                                       ### 4 below
    if (1+(r/d)-((l+d-1)/d))>=k: return d            ### 2 below
    N = 1 + (r/d)                                    ### 3.2 below
    d -= ( ((N*d)-r) + (N-1) ) / N                   ### 3.4 below
  return 1

"""
basically` 
1) (r-l)/(k-1) is the maximum possible d, given r, l and k
2) the if...return tests if k d's fit between l and r
3) if not, then d must decrease; can't loop decrement (d-=1) with 1E12 ranges, so
3.1) R = d * (1 + r/d) is a multiple of d greater than r, and
3.2) N = (1 + r/d) is the multiplier of d that gets to that R = N*d, so
3.3) (N*d - r) is how far R has to drop to be <= r, so
3.4) ((N*d-r) + (N-1)) / N is the minimum decrease in d which will drop R to <= r
4) go back to 2) above, with decreased, new d

e.g. input m,101,200,2  (answer is 66: *2=132; *3=198)

Initial d = 200 - 101 = 99
but only one multiple of 99 between 101 and 200 inclusive, i.e. 198

       101                       200                    ## boundaries r and l
     99                       198              297      ## multiples of max possible d; R=297; N=3

and if you start decreasing d from 99, then

  98                      196              294           ## multiples of d-1
97                    194               291              ## multiples of d-2
...

so, as d decrements, the numbers on the right (3*d) move faster (3x decrease in d) to get inside 200 than the numbers in the middle (2*d) move to go past 101 (2x decrease in d). the number on the right reaches (or passes) r when 3*d <= 200 i.e. the decrease in d will be the formula in 3.4 above i.e. ( (3*99 — 200) + (3-1) ) / 3 = 33.

the only question is whether 2*d has by that time dropped below l (101), but if it has then repeat the loop.

→ Ответить

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

If you want ugly, it's only 11 lines of python:

import sys
def recfib(n,m):
  if n==0: return (0,1,)
  a, b = recfib(n / 2,m)
  return ( [ a*(((2*b)-a)%m), ((b*b)%m)+((a*a)%m)][n%2], [ ((b*b)%m)+((a*a)%m), b*((2*a+b)%m)][n%2], )
m,l,r,k = map( int, sys.stdin.readline().strip().split()[:4] )
D = (r-l)/(k-1)
while D > 1 and (1+(r/D)-((l+D-1)/D))<k:
  N = 1 + (r/D)
  D -= ( ((N*D)-r) + (N-1) ) / N
print( recfib( D, m)[0] )

only four lines implement the algorithm for the fib. index, the rest is i/o (3 lines) and the index-to-fib# function.

→ Ответить

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

Nice solution! Can you explain that the meaning of (a, b) in a, b = recfib(n, m)

I guess a is the n(th) fib number. But what's b?

→ Ответить

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

Your code cannot pass the tests. You put the '%m' in wrong places. After my modification it passed.

And, spliting the long long return statement in recfib using the V1 if C else V2 expression would make the code faster, since that can supress the useless evaluation.

    return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)

See, it's only 80 chars. You don't even need to break the line.

→ Ответить

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

Thanks, you are right, I forgot about the ternary operator added in 2.5 that will short-circuit to evaluate just one of the paths. I just read about it the other day, too.

And yes, the version I posted is not the one that worked: I added %m's after the [n%2] selectors in the return statement and it passed. Actually, your version may not pass if, for example, (b*b+a*a) overflows. Ihat's why I put so many %m ops in there. And I still think either mine or yours could fail if given the right parameters; using this construct ((VALUE%m)+m)%m) a few times should fix it though. Python may be hiding some of our problems and be more robust here because of automatic type promotion on overflow.

Btw, I got it down to 10 lines (raw_input() instead of "import sys" & sys.stdin.readline()). That uses the ugly return construct, but the important thing to note is that the guts of the program, the GCD loop, only takes four lines.

→ Ответить

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

Actually, you don't need so many '%m' in python. For example, it will convert to long for you automatically if a*a+b*b run out of the range of int. And -1 % 5 == 4 in python.

Btw, after I copy your code to my editor, the first thing I do is to remove the import line and replace sys.stdin... by raw_input().split().

→ Ответить

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

← Rev. 2 →

thanks.

i know python promotes the type on overflow, i'm just cautious and then i don't have to think about the range of m.

and thanks for the raw_input() thing; i know it's there but i think that changes or breaks in V3 so i tend to not use it a lot; again, i'm cautious.

i didn't know % alway goes to a positive number; i started doing the extra +m)%m in C++. but since that's the case then even overflows are not a problem.

hey, could the %m generate a premature n==0 in the recursive fib routine? would it matter?

→ Ответить

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

The first argument of recfib, namely n, will not affected by m.

→ Ответить

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

2251104 Even shorter(7 lines) with functional style. Accepted.

def recfib(n,m):
    if n == 0: return (0, 1)
    a, b = recfib(n / 2,m)
    return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)
def next_d(D): return D if 1+r/D-(l+D-1)/D>=k else next_d(D-(D-r%D+r/D)/(1+r/D))
m, l, r, k = map(long, raw_input().split())
print recfib(next_d((r-l)/(k-1)), m)[0]

# Trick to remove N from the code: N = 1 + r / D
# D -= (N*D-r + N - 1)/N
#   N*D - r = (D + r - r % D - r) = (D - r % D)
#   N*D - r + N - 1 = D - r % D + r / D

→ Ответить

tsenmu

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

A really nice solution Thank you !

→ Ответить

bogdan.sumy.ua

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

Как решать div2 D?

→ Ответить

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

← Rev. 2 →

+30

Задача C великолепна) Давно уже стольких эмоций от взломов не получал. Для всех интересующихся что же не так — бинпоиск не работает ни в каком виде. Тест — 123456789 100000000000 300000000000 3

P.s. В целом задачи очень интересные, один из немногих раундов, где действительно надо думать, а не просто тупо писать километры кода.

→ Ответить

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

А как делать без бинпоиска-то?

→ Ответить

Malinovsky239

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

← Rev. 2 →

Дождитесь разбора: сегодня-завтра он появится.

На "подумать": асимптотика авторского решения — $\text{[math]}$

→ Ответить

tunyash

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

А как тогда делать?

→ Ответить

RomaWhite

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

Можна приблизительно оценить g = gcd(i1,i2,..,ik). Если g < 1000000 ,то перебрать его. Если g > 1000000, то оно в виде r/i (целая часть).

→ Ответить

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

не очень понял, можете конкретнее?

→ Ответить

RomaWhite

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

← Rev. 2 →

g — такое число, что F(g) — ответ.

Тогда приблизительно считаем g. Например g = (r — l) / k;

Если ето число меньше 1000000, то перебираем все числа от 1 до 10^7(c запасом) и выбираем наибольшее для которого выполняеться условие.

Если ето число больше 1000000, то g должно быть у виде r / i , потому что r / (i + 1) должно быть меньше r/i. Перебираем i от 1 до 10^7.

Но я сам еще не уверен:)

→ Ответить

RomaWhite

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

На контесте упало, потому что я баран. А вообще прошло. код

→ Ответить

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

Я делал так — будем постепенно уменьшать это число (пусть x). Изначально оцениваем, что оно не более r / k. b = (l — 1) / x. Теперь оцениваем x как не более r / (k + b). Снова b = (l — 1) / x и так, пока не сойдется. Не уверен, что это проходит, но у меня решение упадет независимо от

→ Ответить

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

^^^ Это решение проходит за 140 мс

→ Ответить

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

+21

Это неэкономно. Я вот сначала клиентов обрабатывал тестом 66 99 2, а когда они добавляли "поискать рядом с ответом из бинпоиска" — уже добивал 666666666666 999999999999 2. У меня, правда, у самого упадет из-за того, что забыл сделать 1 % mod

→ Ответить

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

Это уже совсем манчкинство) Но тут тогда надо внимательно действовать — люди, почему-то, по большей части писать бинпоиск не умеют, у них очень часто вылезают какие-то +-единички, крайние случаи и т.д. и т.п., можно случайно нарваться на это. Не хотел тратить время, думал, может оно еще пригодиться в E, но ничего лучше хэви-лайта не пришло в голову.

→ Ответить

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

← Rev. 2 →

ответ то какой? еще лучше нод

→ Ответить

Gassa

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

А что же всё-таки нужно делать в том месте, где половина участников сделала двоичный поиск?

→ Ответить

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

Ответ имеет вид [r/z], где z — какое-то целое число. Либо z<=2e6, либо [r/z]<=2e6. Перебрали, выбрали наибольшее.

→ Ответить

Gassa

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

Спасибо, понял. У меня в комнате как раз только это и выжило. А сам стал это писать, запутался и подумал, что неправильно.

→ Ответить

bogdan.sumy.ua

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

В этом тесте ответ 57272247?

→ Ответить

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

Нет. 33025443.

→ Ответить

OSt

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

-10

С(Div 2) прям на второй странице гугла. Пичаль :-(

→ Ответить

ONU_1785

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

-7

Как сложно определить тех, кто вместо решения ищет все в гугле...

→ Ответить

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

классный контест. как решать Б, и на чем ломали С?

→ Ответить

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

← Rev. 4 →

В Б прошла следующая штука:
Для k = 1 ответ очевиден, сразу посчитаем его за линию.
Для k > 1 посмотрим, что нам будет нужно как максимум 1 кучку ни к кому не подцеплять, как максимум k кучек подцеплять один раз, и как максимум k^x кучек подцеплять x раз(из них все кроме одного непосредственно). Каждое подцепление добавляет ровно массу кучки к ответу.
Отсортируем массив по невозрастанию и первый элемент добавим с множителем 0, следующие k с множителем 1, следующие k^2 с множителем 2 и т.д. Если будем считать ответ на подотрезке за O(1) суммами на префиксах, то итого выйдет что-то вроде log_kn.

→ Ответить

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

мне кажется, или Д уже бывала на контестах?

→ Ответить

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

Д баян. Была на ИОИП

→ Ответить

naagi

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

+11

http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=2528&chapterid=3021#1 - это в чистом виде задача D div 1. А тут ее обсуждение: http://codeforces.net/blog/entry/1550

→ Ответить

---Grigor---

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

Расскажите пожалуйста решение Div 1 D

→ Ответить

pavel.savchenkov

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

Кстати, вот она.
Ищем отрицательную строку/столбец, меняем, пока всё плохо. Это работает, так как сумма всех чисел в матрице от этого каждый раз растёт. Надеюсь работает..

→ Ответить

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

Во время решения задачи С из этого контеста у меня возникла следующая подзадача: Найти наибольшее x такое что на отрезке с l по r есть не менее k чисел кратных x. Я умею решать такую подзадачу за O( sqrt(r) ). Можно ли быстрее?

→ Ответить

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

← Rev. 2 →

бред

→ Ответить

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

Это boolen значение, мне надо f(l, r, k) - > x т.е. функцию в целые числа.

→ Ответить

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

забей, я вопроса не понял

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

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

→ Ответить

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

In my opinion, these OEIS problems don't add anything to the contest.

→ Ответить

eipie

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

Well I did it figuring out on paper and still made a noobie mistake.

((3^n — 1)+MOD)%MOD is the answer. I guess you never forget to do this once you lose 900points. >_<

(I did the 3^n part efficiently and correctly)

→ Ответить

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

Same method but WAed!

→ Ответить

eipie

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

Is that not the answer? Ruh ruh.

→ Ответить

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

← Rev. 2 →

-9

Edit:How come the font become enlarged? --> WA with 6th pretest case

→ Ответить

Filins

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

← Rev. 2 →

Use long long instead int .

→ Ответить

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

Maybe you CAN figure it out on paper but it's so much faster this way... so you have to take the easy way to stay ahead of competition.

→ Ответить

eipie

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

← Rev. 3 →

F(N) = 3*F(N-1) + 2

F(1) = 2
F(2) = 3*F(1) + 2
F(2) = 3*2 + 2
F(2) = 3*2 + 3 - 1
F(2) = 3 (2+1) - 1
F(2) = 3^2 - 1
...
F(N) = 3^N - 1

Took me a bit to turn the 2 into a 3-1 though :( I'm out of practice.

→ Ответить

bcurcio

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

+13

I disagree, realizing the solution required a little thinking, and it wasn't some obscure formula or some numbers that are hard to compute. I even think that for some it was even faster thinking about the solution. If you don't try to think the easy problems, how do you expect being able to think the hard ones? That's the way you'll stay ahead, thinking

→ Ответить

tsenmu

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

Indeed, I forgot to write +MOD thing and lock my problem like a fool... 900 points lost will be a real tragedy.

→ Ответить

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

same with me :( lost 1344 points

→ Ответить

bcurcio

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

The fun part is not using OEIS. I think it was a nice problem

→ Ответить

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

[PlayLikeNeverB4: In my opinion]

See my comment below re normative. I'm not sure if you are referring to Div-2/C or /E, but I thought they were great problems. A bit of knowledge, or maybe a chat with the Google, a little insight, and then coding it right, which was the real challenge in both cases to avoid the TLE, and WA if the modulo operation is not done right.

The OEIS is just the turf on which the game i played. Think of yourself as TRON.

→ Ответить

Kostyazz

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

← Rev. 2 →

Повёлся на то, что C(Div1) сдают больше чем B. Своими руками нашёл способ вычисления номера числа Фибоначчи, которое окажется ответом на задачу (если я не ошибся нигде, конечно). Вот только вычисление Fn быстрее чем за О(n) мне оказалось не под силу, а копипастить нагугленный чужой малопонятный код счёл нечестным.

Вопрос: есть ли решение задачи без вычисления Fn с помощью матриц?

→ Ответить

AlexanderBolshakov

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

Ответ на вопрос: есть формула Бине, она задает i-ое число Фибоначчи в явном виде, но для ее использования нужна высокоточная дробная длинка, да и по модулю ее вычислить нельзя.

→ Ответить

Kostyazz

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

Такой способ мне известен. Но вы сами только что объяснили, почему он не подходит ^_^

→ Ответить

lth

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

I can't understand, why my O(8log(10^12)) got TL. Submission #2245668 ?

→ Ответить

TankEngineer

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

← Rev. 2 →

Well, for Problem B(div1)/D(div2), you will get TLE if you don’t use some technique to remember the answer you printed each time. This is because there exists cases that all k equal to 1. That's how I got TLE for the first time.

→ Ответить

bcurcio

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

I just remembered the case k=1. I hope it doesn't get time out

→ Ответить

lth

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

But I meant problem E div2

→ Ответить

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

Problem E in div2 is quite tricky...when I realized what i had done wrong it's all too late. congrats to those who solved this problem successfully.

→ Ответить

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

Congratulations to Velicue for the only contestant to solve E.

→ Ответить

Metamorphus

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

Долго ещё ждать системное тестирование?

→ Ответить

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

Е скучная — напишите HL декомпозицию с бинарным поиском за n log^2 n вместо n log^(3+) n. Остальные задачи зачотные, но С, конечно, не на своем месте с такими претестами

→ Ответить

Gerald

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

Можно без декомпозиции, с персистентным деревом отрезков. Это заметно короче, и с большим запасом укладывается в TL.

→ Ответить

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

+12

Тогда тоже клевая задачка. Жаль, что я не придумал. А кстати, так ведь можно любую HL декомпозицию, где нету изменений. Клево

→ Ответить

Romchela

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

Расскажите решение задачи C div 2

→ Ответить

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

-7

Ответ: (3^N — 1) % M. 3^N считаем бинарным возведением в степень

→ Ответить

egor-belikov

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

Если почертить, то становится понятно, что состояний всего 3^N, следовательно, переходов будет сделано 3^N - 1. Осталось только прикрутить к этому быстрое возведение в степень, взятие по модулю и грамотное по модулю вычитание. Как сделать первое, описано, например, здесь, взятие по модулю вставляется после каждой операции умножения, а грамотное вычитание описывается так: res = (pow(n) + m - 1)modm.

→ Ответить

Vladyslav

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

-6

Никто не знает, что будет, если был зарегистрированный, но не получилось прийти и не сделал ни одной отправки?

→ Ответить

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

Ничего

→ Ответить

Vladyslav

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

-6

Спасибо)

→ Ответить

dumbhead

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

How can we solve DIV 2 E ? How can we get the maximum gcd of all the k element subsets between L and R ?

→ Ответить

kostya_by

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

+14

Блин, делать модуль равный единице в задачах на ответ по модулю вообще не клево. =(

→ Ответить

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

Anyone thinks that A in Div2 is more difficult than B?

→ Ответить

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

Solution in one phrase : cross product. Without that it'll be a bit troublesome.

→ Ответить

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

I did take out cross products but got WA on test 31 .[code] .. Can anyone tell me what did I do wrong because I cannot see the test case until the system test is over ... And the system test is playing with my patience by being slow

→ Ответить

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

Floating point number is not accurate enough. use integers instead.

→ Ответить

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

Correction — > long because int will overflow :P

→ Ответить

GaryYe

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

I do, but only because I suck in geomtry.

→ Ответить

rais.fathin38

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

Well, I don't know cross product but managed to get AC by writing several ifs. It's easier since it's guaranteed that ABC makes up either right angle or straight line

→ Ответить

hacker007

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

← Rev. 4 →

The problemsets are good, thanks, Malinovsky239. However, some statement clarifications are wanted. Thanks for any reply.

div2(D)/div1(B):

"each pile will let you add to it not more than k times (after that it can only be added to another pile)". Assuming adding pile i to pile j, we name i as addend, j as summand, then is the constraint saying which role(addend or summand) can be used at most k times?

div2(E)/div1(C):

"for each such subset let's find the largest common divisor of Fibonacci numbers with indexes", does this refers to the elements of subsets indexing at 1,2,3,5,8...?

→ Ответить

nurzhands

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

Binary search in Div1.C is incorrect :(
l=7, r=14, k=2:
7 — ok
6 — not

→ Ответить

I_dont_have_girlfriend

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

← Rev. 10 →

I think You can try to use dp: Let dp[i] is the minimum step to move n-i+1 alien (i..n) from section 3 to 1 (or section 1 to 3)

So dp[i] = dp[i+1] + dp[i+1]*2 + 2 ( because we have to

move i th alien from section 3 to 2
move n-i+2 alien (i+1..n) from section 1 to 3
move i th alien from section 3 to 1
move n-i+2 alien (i+1..n) from section 3 to 1 )

**Upd: Sorry, I think you say Problem C div 2.

Probielm C div 1, you can use gcd(fibonacci(a), fibonacci(b)) = fibonacci(gcd(a, b)) Then you can try to understand dp[i] = 3^(n-i+1) — 1

→ Ответить

aram_gyumri

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

sorry, but it's not C(Div.2)?

→ Ответить

I_dont_have_girlfriend

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

Sorry, I think iTwin say problem C div 2 :D

→ Ответить

rdivyanshu

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

what is special about test case number 106. why binary search does not work ?

→ Ответить

caustique

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

Check test 12345678 7 14 2

→ Ответить

rdivyanshu

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

mine code is outputting 13 which is right i guess. http://codeforces.net/contest/226/submission/2246243

→ Ответить

caustique

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

What about this test 123456789 100000000000 300000000000 3 какой ответ? Right answer is 33025443

→ Ответить

rdivyanshu

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

Thanks.

→ Ответить

tunyash

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

А как получилось, что задача из сета вплоть до ограничений совпала с задачей, бывшей на относительно недавней олимпиаде?

→ Ответить

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

Неожиданное совпадение!

→ Ответить

Gerald

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

+44

На самом деле случайно. Я не ожидал, что так получится. Задачу я раньше не видел. Перед тем как её утвердить я погуглил, но этой задачи не нашел. Мои извинения за недоработку.

→ Ответить

SyFy

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

Да и первая задача с А дива2.

Линк.

→ Ответить

Ghella

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

Некоторые неудачники, не будем показывать пальцем, хотя я, конечно, имею в виду себя, умудрились и это решение зафэйлить. Никак не могу понять, что не так. Всё в long делалось, естественно.

→ Ответить

pavel.savchenkov

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

← Rev. 2 →

Тыц
Задачу не читал; первое, что пришло в голову.

→ Ответить

andreyv

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

+11

На данной платформе long тоже имеет длину 32 бита, а вот long long — 64.

→ Ответить

Ghella

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

Печаль. Большой печаль. Спасибо ответившим.

→ Ответить

aropan

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

Конечно случайно, никогда бы не подумал, что на кф дают специально свеченные задачи)))

→ Ответить

NTaveras

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

Message received from user "messsi" during todays contest:

send me you code of A please man and i send me code of B ok???? this is my code of B now you send me your code please

/* His problem b code here.. */

→ Ответить

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

Did his B pass? :D

→ Ответить

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

Всё-таки по-моему давать задачей A во втором дивизионе геометрию, это как-то жестоко.

→ Ответить

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

Это не геометрия.

→ Ответить

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

А что?

→ Ответить

dalex

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

Еще какая геометрия. Косое произведение. В OVER 9000 школ не проходят.

→ Ответить

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

планиметрия

→ Ответить

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

геометрия геометрии рознь.

→ Ответить

it4.kp

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

Вот это жесть... в D у меня прошел тупой рандом. Пока есть плохие линии (ряды или колонки) берем из них случайную и ее минусуем. Это самая простая задача сета :)

→ Ответить

nk.karpov

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

Ну это почти авторское решение ;)

→ Ответить

gen

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

Это правильно.

→ Ответить

SkyHawk

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

"в D у меня прошел тупой рандом" ... "Это правильно." — вот она, вся суть некоторых задач.

→ Ответить

I_love_natalia

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

← Rev. 2 →

1. Утверждение: этот процесс сходится.

Рассмотрим общую сумму элементов матрицы. Она может быть вычислена как сумма сумм всех строк (столбцов). Очевидно, что изменение знака с отрицательного на положительный увеличивает сумму всех строк (столбцов).

2. Этот процесс сходится быстро.

Всего существует не более 10^6 + 1 различных возможных сумм (максимальная сумма 10^6 по модулю, четность сохраняется). Итого это точно работает не дольше, чем за 10^6 операций. Если каждая операция реализована за O(max(N,M)) (это легко), получаем сложность 10^8 -- OK.

→ Ответить

it4.kp

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

← Rev. 2 →

+15

3) Этот процесс сходится очень быстро, либо тесты слабые

У меня каждая операция реализована за O(N*M) и все равно — ОК

4) Задача не стоит 2000 баллов

Прямое следствие 1.-3.

→ Ответить

I_love_natalia

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

3) Даже чтобы получить 10^5/2 (оценочная граница захода N*M) итераций, нужно непонятно какую матрицу сделать. Ограничение 10^6 исходит из плохо совместимых утверждений: все числа порядка 100 и при этом отрицательные суммы порядка -1.

4) Оценка субъективна. В целом — не очень понятно, как оценивать сложность решения задачи, когда доказательство того, что решение правильно, сложнее идеи решения. ИМХО — да, эта задача не стоит 2000.

Кстати, в решении жуткие мотивы холодильника из братьев пилотов, правда, я не умею там доказывать аналогичную эвристику "срисовать и протыкать все неправильные; повторять до посинения", а правильное решение вообще строится из специфического инварианта.

→ Ответить

danpol

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

-7

Классно то, что впервые за последние N контестов не было задержки на 15 минут)

→ Ответить

sinansahin

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

Using "int" instead of long long caused system test fail (A. div 2) :(

→ Ответить

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

Thats obvoious becuase range was 10^9 .. So int * int will overflow

→ Ответить

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

+41

Screencast

→ Ответить

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

Nice idea to stream video. Streamers usually use 3-minuts delay and stream online.

→ Ответить

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

It is not viable even with delay

→ Ответить

bolivar1997

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

ждем обновления рейтинга

→ Ответить

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

обновили же

→ Ответить

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

Просто у него после этого контеста изменение рейтинга нулевое. =))

→ Ответить

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

u don't say?

→ Ответить

khuongnd

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

Based on the number of people solving, C and D should be exchanged their order in Div 1.

→ Ответить

priyank20011

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

also in Div. 2 , A and B should change their order based on difficulty level or no. of people solved.

→ Ответить

herr_bilbo

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

No, binary search and sorting are more difficult than school geometry.

→ Ответить

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

I suck at geometry and honestly I don't really like it either. And like me are a lot of Div2 participants.

→ Ответить