Codeforces Beta Round #49 (Div. 2)

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

Странно, KirillB находится и в 100 комнате, и в 102. Но задачи сдаёт только в 100й.

→ Ответить

dlevshunov

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

Баг :( Забавный.. Во время раунда уже не поправить, но потом исправим.

→ Ответить

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

-7

почему на 1 тесте в задаче D нельзя получить ответ

3 2

2 1

3 2

Он так же приводит к правильной расстановке

→ Ответить

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

вопрос снимается, я дебил:)

→ Ответить

Fefer_Ivan

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

Вопросы через страницу соревнования, а не через топик.

→ Ответить

ballon

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

Что за странный вердикт :
Неправильный ответ на взлом 1
?

→ Ответить

Fefer_Ivan

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

Это значит, что твое решение прошло все претесты, но не прошло 1-й тест на котором взломали предыдущее твое решение.

→ Ответить

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

Ты должен пройти тест, которым тебя взломали.

Читаем правила до контеста.

→ Ответить

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

А почему я не вижу «вкладку» Взломы? Раньше вроде была.

Может конечно из-за того, что я вне конкурса, но всё равно странно.

→ Ответить

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

И вот в который раз.... Открываю код для взлома, вчитываюсь, закрываю и... понимаю, что не моню чей это код. :(

Реквестирую подпись автора сверху.

→ Ответить

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

да, тоже бесит..

→ Ответить

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

А если я перепослал решение, которое у меня взломали, то оно проверяется на этом взломе?

→ Ответить

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

да, читаем правила

→ Ответить

Hapuk

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

В задаче D на первом тесте может и быть такой ответ?

2 3

1 2

2 3

→ Ответить

RAD	13 лет назад, # ^ \| 0 Да → Ответить

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

+13

Неплохой контест получился)

→ Ответить

SyFy	13 лет назад, # \| +6 Великолепный раунд! Спасибо составителям и Всем, кто принял участие в создании и подготовке! → Ответить

v1m	13 лет назад, # \| ← Rev. 2 → 0 какой 4 претест в B? → Ответить

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

Можно смотреть тесты, на которых вы упали при клике на ид посылки в разделе "посылки"

→ Ответить

SyFy	13 лет назад, # ^ \| 0 Ничего... только исходник. → Ответить

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

Попозже появятся.

→ Ответить

_Vadim_

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

← Rev. 3 →

Вот 4 претест к B :

Ввод
9 10
Вывод
8 10

→ Ответить

Sereja

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

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

→ Ответить

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

Я не думаю, что это баг, возможно это сигнализировало о том что задача следующая в очереди, т.е. закончит теститься посылка другого участника-начнется твоя, или как-то так. Во всяком случае, если это и баг, смысла исправлять его не вижу.

→ Ответить

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

+12

И правда быстро. Может конечно сегодня тестов*посылок было меньше, но всё равно быстро. :)

→ Ответить

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

+15

Похоже, проклятье КФ на этот раунд меня покинуло:) Чтож, проверим дальше, тенденция ли это или случайность:)

→ Ответить

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

Тоже отпустило кажется, посмотрим, что будет на рейтинговом контесте

→ Ответить

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

это случайность

→ Ответить

abzaloid

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

а рейтинги когда поменяются?

→ Ответить

master_j

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

+13

Увеличение производительности сайта заметно - сегодня систесты завершились всего за 14 минут!=)

→ Ответить

marque

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

2nd one is a little bit confusing.. Especially "If those rules don't indicate the size of the cut are clearly, then the way with which the cut part possesses the largest area is chosen."

→ Ответить

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

it tried to mean, if the cuts were not unique...

→ Ответить

Tahlil

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

i used google translator to understand it :P

→ Ответить

rufferzool

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

Was the site running extremely slowly or was it just my connection as both have been having their ups and down recently :P

→ Ответить

mcsharma1990

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

Just your connection!

→ Ответить

Tahlil

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

To me codeforces was fast in last contest:)

→ Ответить

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

Интересно, а есть ли кроме меня умельцы, которые получили WA на D на финальных тестах?

→ Ответить

ostroumov

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

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

→ Ответить

free0u

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

Хотелось бы узнать, как решается последняя задача

→ Ответить

yeputons

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

+23

Первое, что надо было заметить - n <= 10. Это значит, что решение экспоненцеальное, и можно перебирать какие-нибудь подмножества. Так и сделаем.

Давайте посчитаем динамику по подмножествам: d[m][subm] - количество способов сделать связанное дерево из подграфа m с тупиковыми вершинами subm. Ответ будет суммой по d[2ⁿ-1][x], где кол-во единичных бит в x = k.
Как пересчитывать: для пустого множества и множества из двух вершин (либо 0, либо 1) - очевидно. Теперь для большего: переберём i из subm - какой-нибудь тупик. Отрежем его от дерева по некоторому ребру в b. Получаем дерево на меньшем множестве вершин и с либо уменьшенным на 1 множеством тупиков, либо с изменённым i на некоторое b. Добавляем к текущему ответу уже посчитанную динамику. В конце надо разделить на k.
В принципе, наверное, всё равно, какой тупик отрезать.

→ Ответить

it4.kp

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

То что решение экспоненциальное можно понять также из того факта, что при k=2 нас просят найти сколько гамильтоновых путей в графе, а это уже NP.

→ Ответить

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

это #P :)

→ Ответить

it4.kp

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

Я так и знал, что меня опять прижмут за фривольное использование буквосочетания NP :)

→ Ответить

TarifEzaz

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

I have a little question about a challenge case in problem A of today's contest. In my room one coder wrote a subroutine where he checked for every address whether it matches with the "input" string. In order to do that, he run a for loop which checked character by character whether the "input" string matches with any of the addresses. His for loop runs like this:

for ( int i = 0 ; i < input.size() ; i ++ ) {

if(input[i]!=current_address[i]) break;

}

Now my question, shouldn't there be a runtime error when the size of the input is bigger than the current_address, given all the other characters are equal?

I challenged it and it failed. Can anyone explain why?

→ Ответить

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

← Rev. 2 →

what data type of input && current_address?

As I know a[big_int] will return 0 if it is string

upd:

I tried this code in g++:

string a("abcde");

cout<<(int)a[17];

It prints 0

→ Ответить

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

Wouldn't there be an exception?

→ Ответить

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

No any exceptions,errors.

Just 0

→ Ответить

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

You are wrong, as far as my tests tell.

→ Ответить

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

Can you show me code you are tried?

And.. language?

→ Ответить

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

← Rev. 2 →

No problem. I used C++ and string. (as I suppose this is what is used in the solution shown above, though I am not sure).

So I tried the following:

int main()
{
    string str = "codeforces";
    cout << str[11] << endl;
    return 0;
}

It banged, crashed, exploded. Still, I agree that if current_address is char[], then the code will not crash and everything will go smoothly, exactly because of the '\0' character you spoke of.

→ Ответить

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

do you use MS Visual C++?

I tried this code:

#include <string>

#include <iostream>

using namespace std;

int main()

{

string str = "codeforces";

cout << str[12] << endl;

return 0;

}

it runs successful on my computer(g++) and in tab "Run" on codeforces (g++) but crashed in MS C++

→ Ответить

mcsharma1990

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

But '\0' is at str[10], not at str[11]. isnt it?

→ Ответить

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

You are correct, now as I changed the index it really runs smoothly. Cool I did not know that.

→ Ответить

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

Can you point to this solution?

→ Ответить

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

Hm, if it is char[],first symbol after End of String will 0 too

→ Ответить

pkhaustov

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

Вы наверное пошутили, когда так распределили задачи по сложности?!

В ACM системе это не играет роли. Но здесь! Задачи С и D в сумме легче, чем задача B. Задача A легче задач C и D. Как результат я сдал более сложные A, B и косячнул с размером массива в D. Да, ошибка уровня дебила, но как результат почти все, оказались выше меня! Потому что задачи C и D это вообще детсад какой-то. Это очень сильно напомнило Воронежскую олимпиаду прошлых лет, где за более сложные задачи дается меньше баллов, чем за простые.

→ Ответить

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

Плохо конечно, что за лучшие задачи дают больше, но уж от этого никак не зависят твои ошибки с размером массива..

Да и посмотреть какую задачу решать можно по монитору(т.е по кол-ву сдавших)

→ Ответить

pkhaustov

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

-6

Ты вообще понял мысль или нет?! Ты сначала прочитай внимательно, а потом отвечай. Какая разница в каком порядке решать? Баллов все равно будет в разы меньше. Задача D приносит НАСТОЛЬКО больше баллов, что в сумме A и B ничего не решают. А тут каждая из задач (A или B) по сложности превосходила D. Мне кажется, что надо делать все задачи равными по количеству баллов и убирать упорядоченность по сложности (это понятие субъективное, а оказывает существенное влияние на расположение участников в итоговой таблице).

→ Ответить

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

Не согласен, что A - сложная задача.

Особенно для любителей Java, обладающих методов startsWith(), определяющим, является ли строка префиксом данной или нет.

Согласен, что B сложнее, чем C, и чем D, так что распределение баллов действительно неадекватное.

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

→ Ответить

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

Абсолютно согласен. Решать надо было все четыре задачи.

→ Ответить

Urbanowicz

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

А как решать D?

→ Ответить

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

← Rev. 2 →

перебираем по очереди a-шки.

Ищем для нее ближайшую равную ей b и свопаем ее до нужно места, потом переходим к следующей a.

UPD: большинство решений что я смотрел были предельно понятны, так что имеет смысл посмотреть просто чье-нибудь прошедшее решение

→ Ответить

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

Кстати кто-нибудь чекер смотрел??? Авторы поугарали, отсвопали 300 равных чисел по 100500 раз:)

→ Ответить

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

← Rev. 2 →

Похоже на сортировку методом выбора.
http://ru.wikipedia.org/wiki/Сортировка_выбором
Только выбираем не минимальный элемент, а необходимый.

→ Ответить

Arkadiy

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

На Топ Кодере задачи имеют разные баллы и все довольны. Иногда 900 бывает проще, чем 500. В чем противоречие? Общий принцип один - решай больше задач, получишь больше очков. Не умеешь безбажно сдавать халявы - значит не спеши. Или тренируйся спешить без багов. Вероятность завалить халяву есть у всех, но чем кодер лучше, тем она меньше.

→ Ответить

pkhaustov

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

По идее раз задача - халява, то за нее должны давать меньше баллов, чем за не халяву. Тут же было наоборот.

→ Ответить

KirillB

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

ну ошиблись тут с баллами (видимо авторы разные - не согласовали) не отменять же из-за этого разбалловку

→ Ответить

Artishok

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

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

→ Ответить

KirillB

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

← Rev. 2 →

раз есть баллы значит должен быть критерий
на тк кстати тоже подставы с этим бывали, так как присутствует субъективность оценки

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

→ Ответить

Artishok

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

Я имел в виду, что оценка сложности (баллов по задаче) - это субьективное мнение авторов... Они вправе решать как считают верным...

→ Ответить

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

Не парься особо, я, например, аж 2 раза накосячил, как ребенок :)
Один раз - площадь в int-ах в B, второй раз - не поставил break из цикла после обмена в D.

На самом деле, конечно, порядок задач по сложности: A,C,D,B или даже C,A,D,B...

→ Ответить

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

Чтобы не ошибаться с размером везде пишу вектора, даже для деревьев. Тоже ошибся с распределением задач, все посдавали С на 8-20 минуте, я ее запинал на 32. Насчет А ты не прав, минуты за 3 набил и еще 4 минуты искал где еррор:). D сдал на 52, и хорошо еще что решения некоторых задач у моих соперников оказались палеными, потому что меня по баллам обгоняли. Но-это хороший урок. Не всегда надо читать те задачи которые "дешевле", в который раз на эти грабли наступаю:)

→ Ответить

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

> Чтобы не ошибаться с размером везде пишу вектора, даже для деревьев.

Извини, но по-моему это немножко быдлостиль.

Когда-нибудь по времени не успеешь с таким подходом. Владеть надо обоими.

→ Ответить

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

Неужели vector <vector <int> > v(n) намного длиннее написать, чем int v[1111][1111]???

Зато так гарантированно не ошибешься - все ошибки с выходом за границу массива/вектора ловятся сразу. Так что насчет быдлостиля я не согласен.

→ Ответить

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

Чо-то глупость какую-то ты сказал.

Я вообще-то про время выполнения, а не про написания.

Например на полуфинале 2009 не зашел vector < vector < string >> с TL, но зашел char[MAXN][MAXM][MAXLEN];

→ Ответить

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

Согласен, откатываю свой ответ.

→ Ответить

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

Я тут читал бложек и наткнулся на интересную фразу "Причём на второе место мы переместились только после того, как я вытребовал на форуме снятия у нас двух лишних попыток по задаче 11 из-за ещё одного из глюков. Суровый Паша Хаустов, лидер команды ТПУ, по поводу этого (вернее, не совсем этого) до сих пор рвёт и мечет – всем любителям троллесрача можно рекомендовать почитать."

Пруфлинк: http://ferlon.livejournal.com/27235.html

Кажись, ничего с тех пор не изменилось.

P. S. Никого не хотел обидеть, просто фраза объясняет ситуацию :)

→ Ответить

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

so, those who are not in div2, were not allowed to open any solution? or it was a problem here? I just wanted to see some people's code (no intention was for hacking :P) but it didn't allow me to do so...

→ Ответить

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

← Rev. 2 →

you can see and hack solution in your own room( This room consist of users from your division only)

→ Ответить

mkagenius

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

+12

+83 and blue :D , All effect of "rng" thanx rng_58.

→ Ответить

AlexErofeev

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

← Rev. 2 →

Be careful. It is possible, that due to Pauli exclusion principle there can be only one red rng at single moment. :)

→ Ответить

mkagenius

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

hehe...

I will happier even to float at "yellow-red" border.. :)

→ Ответить

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

man, trust me, blue is the most beautiful color out there .... :D

→ Ответить

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

red attracts me more:)

→ Ответить

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

red is the color of error :)

→ Ответить

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

red is the color 2000+:)

→ Ответить

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

← Rev. 2 →

Ребят, кто задачу Е решил? Как вообще она решается? Была идея на meetinthemiddle для путей, но понял что идея палевная:)

→ Ответить

Rubanenko

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

Перебором,наверное. Мой дошёл до 11 теста,но его можно было оптимизировать и оптимизировать :)

→ Ответить

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

поподробнее идею перебора расскажи.

→ Ответить

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

← Rev. 2 →

За что минусанули человека?:)

Я решал перебором за O(числа деревьев). Деревьев <= n^(n-2) так что по времени проходит да и память сэкномлена по сравнению с динамикой:). Идея перебора хранить маску посещенных вершин и маску тупиковых, а при переходе пытаться увеличить дерево из первой (по номеру) тупиковой вершины после чего эта вершина перестает быть тупиковой (для алгоритма т.е. она удаляется из подмн-ва тупиковых). Ясно что при такой рекурсии ни одно дерево соответствующее пути(стэку) рекурсии не встретится дважды.

→ Ответить

pank.dm

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

← Rev. 2 →

Я не решил, но в конце появилась такая идея.

Перебираем все возможные подмножества тупиковых вершин.
Для оставшихся вершин считаем количество остовных деревьев на них. (например по теореме Кирхгофа http://e-maxx.ru/algo/kirchhoff_theorem)
А также динамикой считаем количество способов выбрать из каждой тупиковой вершины по одному ребру, так чтобы в каждую нетупиковую входило хотябы одно ребро.
Перемножаем эти два числа и прибавляем к конечному ответу.

Наверняка есть способ проще ;)

Неправильное решение.

→ Ответить

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

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

→ Ответить

pank.dm

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

Да теперь понял, что так решать нельзя.
Вот и хорошо, что не стал такую фигню под конец контеста кодить))

→ Ответить

yeputons

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

+12

Чуть выше я рассказал своё решение.

→ Ответить

Rubanenko

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

Я за (n-1)!(в худшем случае) перебирал все возможные остовные деревья данного графа.А именно: для каждой вершины кроме корня выбираем предка в текущем дереве.Потом ,зная предков, строим граф и проверяем - является ли он деревом.

→ Ответить

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

зачем писать идею которая в ТЛ упала???

→ Ответить

Sereja

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

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

→ Ответить

Ripatti

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

← Rev. 2 →

я, возможно, что то не так понимаю... но почему тут тл?

UPD
а, прошу прощения, дошло))

→ Ответить

mexmans

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

В чем может быть ошибка алгоритма для задачи E

Перебираем всевозможные комбинации n-1 ребер из всех m ребер, проверяем полученные графы на связность, считаем количество тупиков и если кол-во совпало с k прибавляем к ответу?

→ Ответить

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

→ Ответить

mexmans

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

Если отбросить ограничение на время?

→ Ответить

Rubanenko

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

У меня ТЛ было,значит всё верно

→ Ответить

mexmans

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

Значит я криво написал, раз у меня ВА =)

→ Ответить

Kostroma

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

← Rev. 2 →

скорее на маленьких тестах проходило хорошо.

в принципе, неправильное решение при каких-то условиях тоже может получить ТЛ

→ Ответить