Bitwise 2011 - Codeforces

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

У них лежит сайт или он только у меня не открывается?

→ Ответить

Sereja

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

У меня тоже еле-еле работает. Страницу 5 минут грузит.

→ Ответить

al13n

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

← Rev. 2 →

Почти лежит, но у меня одна задача открылась. И ссылки на задачи неправильные. Видимо, они пригласили специалистов из фейсбука для проведения контеста :)

→ Ответить

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

← Rev. 2 →

У них уже нельзя зарегистрироваться что-ли?
Ни у кого нет свободного места в команде?)

UPD: не заметил кнопку на самом видном месте. Тем не менее, кто-нибудь хочет ко мне присоединиться?

→ Ответить

niyaznigmatul

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

← Rev. 2 →

cerealguy тут промахнулся:)

→ Ответить

cerealguy

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

Мы с niyaznigmatul с удовольствием присоединимся

→ Ответить

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

Там команды по 2 человека

→ Ответить

cerealguy

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

А оно давно началось?
И сколько времени идет?

→ Ответить

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

Уже почти час

→ Ответить

brainail

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

I am alone :))

→ Ответить

sdryapko

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

А как там отправлять?

→ Ответить

Alex_KPR

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

вот странные вы =/

человек выложил информацию о соревновании, но ошибся со временем проведения; и всё равно все успели

сейчас у него -4 - такое впечатление, что лучше писать о контестах, которые уже закончились

→ Ответить

dyussenaliyev

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

← Rev. 3 →

Приношу всем свои извинения.

А во сколько началось?

Я только зашёл в блог.

Письма о комментах на почту не прихдят.

Ещё раз извеняюсь.

→ Ответить

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

Хороший проблем сет. Интересно как решать 7 и 9

→ Ответить

Philip_PV

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

← Rev. 2 →

7-ая задача: это проверка существования perfect vertex elimination scheme (эквивалентно тому, что граф хордален). Сам pves можно пытаться построить за O(n + m) (keywords: lexicographic BFS), потом за O(n + m) проверить, действительно ли это pves.

Кодиться честное O(n + m) может быть немного лень (мне было:)), но ограничения были такие, что что-то нелинейное было очень сложно пропихнуть (у меня было так: O((n + m) log n) = 20 pnts, O(n^2 + m) = 80 pnts, однако в итоге прошло O(n^2 + m) с эвристическими попытками от этого самого квадрата (n^2) избавиться)

→ Ответить

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

Точняк! я смутно помню что чего-то похожее давно читал, но пытался загуглить
lexicographic DFS ниче не нашел и забил))

→ Ответить

Philip_PV

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

Да, а кроме lexBFS можно построить pves совсем просто по-другому:

построение идёт с конца, берём в качестве следующей вершины ту, которая смежна с наибольшим числом уже выбранных (случаи равенства разрешаем любым образом)

→ Ответить

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

может мне кто-нибудь объяснить условие пятой задачи?)

→ Ответить

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

нужно максимизировать ф-ию x*y*b + x*x+a + y*y*c + x*d + y*e -> max при ограничении x*g + y*h <= j

→ Ответить

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

спасибо :)

→ Ответить

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

← Rev. 3 →

как я понимаю x и y целые неотрицательные?)
и еще x * x * a, а не x * x + a :)

→ Ответить

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

да

→ Ответить

Kenny_HORROR

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

Подстава. Не успел где-то на минуту в кодинге 8ой (правда возможно она бы упала).

→ Ответить

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

В восьмой творилось что-то непонятное с тестами. Во всяком случае, не все утверждения админов о них верны.

→ Ответить

Kenny_HORROR

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

Ну как и в 4-ой =). (там вообще подлые тесты были). А вообще жаль, что не получилось даже попробовать заслать.

→ Ответить

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

Более жаль, когда пишешь и тупое, и умное решение, а потом за пару часов и 20 посылок так и не проходишь даже первый тест.

С другой стороны, участвуя в этом контесте, мы знали, на что шли.

→ Ответить

hydrastuff

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

а где standings?

→ Ответить

http://www.bitwise.iitkgp.ernet.in/rankings2011

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

→ Ответить

daftcoder

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

«Error! You are not logged in.»

Аргх!

→ Ответить

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

← Rev. 4 →

Топ 25 скопировал сюда.

Вообще, Bitwise в последние несколько лет — типичный “индусский контест”. Отсутствуют реальные ограничения на входные данные, правила меняются по ходу соревнования, загадочные сообщения при тестировании, в наличии кривизна условий и тестов в нескольких задачах, а также нежелание админов верить в эту кривизну.

Тот же CodeCraft (пару лет назад довелось участвовать, тогда crazyb0y был автором половины задач) был проведён гораздо лучше. Пишут, что и в этом году тоже.

→ Ответить

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

← Rev. 2 →

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

→ Ответить

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

Это как раз следует из условия (косвенно) и подтверждается сэмплом (прямо: иначе бы не было как минимум одной из -1).

→ Ответить