Codeforces Beta Round #40 (Div. 2)

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

Where do I add my friends?

→ Ответить

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

Go to their profile and click on the star next to their name.

Their profile is found at:

http://www.codeforces.com/profile/yourfriendsusername

→ Ответить

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

Thank you so much!

→ Ответить

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

Что там за 5 тест в таске С никак непойму врод же нет частных случаев.

→ Ответить

El_SiD

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

Что-то у меня ошибка компиляции, хотя на компе все нормально

→ Ответить

ant.ermilov

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

На странице с посылками есть ссылка на протокол компиляции.

→ Ответить

Remstam

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

А претест 2 к задаче B - тот, что в условии?

→ Ответить

MikeMirzayanov

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

Да

→ Ответить

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

Thanks for the really nice problems.

→ Ответить

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

Problems were nice. Even though the round was unrated for me, I would like to know what made me got a Presentation Error in Pretest 5 in problem D.

→ Ответить

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

And I want to know what was pretest 5 of problem C. I submitted my C# code and got WA. I wrote the same thing with C++ and got acc.

→ Ответить

SyFy	14 лет назад, # ^ \| ← Rev. 2 → +1 show me your code ( http://paste.ubuntu.com ) may be I can help you → Ответить

http://paste.ubuntu.com/528276/

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

← Rev. 3 →

THANKS

Here It is:

I'm an absolute beginner in C#

→ Ответить

SyFy	14 лет назад, # ^ \| 0 I think you have trouble in this part of your code: <pre> if(input.Substring(i,2)=="at") { input=input.Substring(0,i)+"@"+input.Substring(i+2); } </pre> reread the statement carrefully ;) → Ответить

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

What's wrong with it?

input.Substring(0,i) is from index 0 to i-1 and input.Substring(i+2) is from i+2 to end. "at" at indexes i & i+1 was replaced by "@"

→ Ответить

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

← Rev. 2 →

I just understood it.

You're right :D

I have a missing break

→ Ответить

SyFy	14 лет назад, # ^ \| +4 yep :) small mistake. → Ответить

SyFy	14 лет назад, # ^ \| 0 but what will be the answer for such test: dotdotatatatatatatatdotdot ? → Ответить

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

← Rev. 2 →

The ans: dot.@atatatatatat.dot
(Sorry! you did not ask the really ans. My mistake)

→ Ответить

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

dot.@atatatatatat.dot

вот ответ на этот тест

→ Ответить

SyFy	14 лет назад, # ^ \| +5 в вышеприведенной программе ответ не был бы таким :) → Ответить

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

Here's my code for problem D, in case someone can spot my mistake. Thx in advance.

→ Ответить

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

I can't see any code

→ Ответить

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

Sorry, I forgot to paste the link :(

http://paste.ubuntu.com/528290/

→ Ответить

SyFy	14 лет назад, # ^ \| +1 really nice problems! thanks to authors and CodeForces! well done! → Ответить

xDDD	14 лет назад, # \| 0 почему я не могу взламывать чужие решения?(хотя я заблокировала свою) → Ответить

xDDD	14 лет назад, # ^ \| 0 Есть кто-нибудь??? скоро контест закончится((( → Ответить

taras.klaskovsky

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

+12

Так а в чем именно проблема? Они не открываются, не взламываются, выкидывают ошибку, или что-нибудь ещё?

→ Ответить

xDDD	14 лет назад, # ^ \| 0 Они не открывались... Спасибо за помощь, но я уже поняла в чем проблема, оказывается я могу взламывать участников только из моей комнаты, т.е. №101* )) → Ответить

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

Можно 4ый претест к задаче D?

→ Ответить

ballon

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

и 5-ий
спасибо
ну никак не мог его обойти :(

→ Ответить

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

задачи клёвые.

плохо что я такой невнимательный и читаю условие через слово.

→ Ответить

havi	14 лет назад, # \| +1 Всех с окончанием контеста, good luck in the future → Ответить

alexej

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

Можно третий претест к задаче E?

→ Ответить

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

I think there will be many pepele died in problem B.

→ Ответить

samshu

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

Well, i've still not understood the problem statement for problem B
!

→ Ответить

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

I missed "not more than once" .The problem mean you can buy and sell only one time or did not do it.Find the max value you can got.

→ Ответить

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

A simple greedy algorithm works :D

→ Ответить

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

Yeah, the problem is simple .Many people make a mistake on what the problem mean.

→ Ответить

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

I think i can only buy once and sell once before.
But finally i got WA...
Does the problem means, i can buy many times, but sell only once?

→ Ответить

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

Even if you can do so, the best possible thing to do is to buy once and sell once :D

→ Ответить

sygi	14 лет назад, # ^ \| 0 That's not true. In the test: 4 4 1 2 1 2 you could get more than 8 using 2 sells and buys. By the way, that's a test, which gave me 3 hacks :P → Ответить

checkmate

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

I don't get the point

So finally, can I sell many times ?

→ Ответить

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

No, You simply can't

→ Ответить

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

I did not got the point either.You can sell only "not more than once".

→ Ответить

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

that means, you can only sell once!!!

→ Ответить

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

we can not use 2 sells! the statement say only 1 sell....

when greedy, use:
    int cas = b / min[i];
    int t = b + cas * (data[i] - min[i]);
    if (t > max) max = t;

min[i] is the min number in the left side.

→ Ответить

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

i find my bug, thank you very much.

→ Ответить

nab	14 лет назад, # \| ← Rev. 4 → 0 Looks like a lot of people misread problem B and thought that you could sell as much as you wanted. (bug: commenting seems to not work (comment is blank) from chromium?) → Ответить

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

It's not a bug in codeforces. I'm writing these in Chromium.

→ Ответить

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

кто нибудь скажите плиз 3 претест в задаче Е там случайно не 5 было?

→ Ответить

anas17in

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

Can there be more than one word in problem A. I got my solution hacked but still cannot understand the reason

→ Ответить

SyFy	14 лет назад, # ^ \| 0 Can there be more than one word in problem A nope → Ответить

anas17in

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

ok then here is my solution
http://paste.ubuntu.com/528284/
Kindly explain the problem.

→ Ответить

sygi	14 лет назад, # ^ \| 0 a aa Is the contr-example. BTW - it's my first contest on Codeforces, so i think i should say 'hello' to everybody, and thank you for the exciting contest! → Ответить

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

the length of the string a and the string b can be different.

→ Ответить

nehalem

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

Пятая задача классная. Решение в несколько строчек)

→ Ответить

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

объясни плиз решение задачи Е

→ Ответить

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

← Rev. 2 →

Решение основано на факте, что в двудольном графе нет циклов нечётной длины.
Рассмотрим искомый граф: возможно он содержит циклы нечётной длины но длина больше трёх. Но тогда из каждого такого цикла можно сделать цикл чётный, заменив одно из рёбер например произвольное ребро цикла i<->i+1 на i<->i+2.
i<->i+2 - этого ребра раньше быть не могло, т.к. тогда бы был цикл длины 3.
Итого у нас получился двудольный граф, максимум рёбер которого достигается при делении на части величины N/2 и N-N/2 (можно доказать с помощью производной)
Ну а соединить можно просто все рёбра с 1 по N/2 с рёбрами с N/2+1 до N

→ Ответить

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

Не все так просто, при такой замене мог появиться треугольник.

→ Ответить

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

Нет, не мог, т.к. мы рассматриваем цикл нечётной длины в котором не менее 5 рёбер. Соответственно меньше четырёхугольника у нас получится не может. Тем более треугольник - это цикл нечётной длины, а мы получаем обязательно чётной

→ Ответить

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

Мы проводим новое ребро i<->i+2, откуда следует что нет вершины j (может, даже не из цикла), соединенной с этими обеими вершинами?

→ Ответить

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

Да, всё таки вы оказались правы. Прошу прощения за кривое доказательство.

→ Ответить

niyaznigmatul

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

В первой строчке у вас опечатка. В двудольном графе нет циклов нечетной длины.

→ Ответить

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

спасибо, поправил

→ Ответить

Yuliy

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

Скажите пожалуйста 11 тест к задаче B.

→ Ответить

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

How is the Rating calculated? what about the colors (sergeant,lieutenant,etc) ?

→ Ответить

PavelKunyavskiy

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

See this post about raiting and this about colors.

→ Ответить

kyo_key

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

← Rev. 3 →

what is D test 5?

→ Ответить

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

Please give test case number 8,too

→ Ответить

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

I got Presentation Erro in that one. I would really like to know what went wrong with it.

→ Ответить

kyo_key

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

i have solved my bug .
PE maybe you can get the right value, but the wrong path.

→ Ответить

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

It could be. Anyway, that would be a confussing judge response, in that case a wrong answer should be expected.

→ Ответить

SyFy	14 лет назад, # \| 0 толпа жаждит разборов задач, интересно, как же всё-таки проще всего решить последние две задачки :) → Ответить

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

Читай решения лидеров - там все довольно ясно.

D - стандартная динамика, E - задача-шутка, судя по ее стоимости и длине решения.

→ Ответить

SyFy	14 лет назад, # ^ \| 0 ага. уже просмотрел решения. действительно последняя задачка в пару строку или в одну(на руби ил питоне) :) → Ответить

Ksunya

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

Скажите, а можно смотреть решения других уже после контеста?

Не в статусе дорешки, а именно с контестов?)

→ Ответить

SyFy	14 лет назад, # ^ \| 0 Можно, правда есть тут особенности кое-какие, если хочешь посмотреть отправку определенного участника. → Ответить

Ksunya

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

А посвятите девушку;)

→ Ответить

SyFy	14 лет назад, # ^ \| 0 Где-то подобный вопрос уже поднимался. Сейчас постараюсь откопать. Правда, есть вероятность, что код определенного участника всё-таки не удастся просмотреть. → Ответить

Ksunya

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

Спасибо огромное!)

→ Ответить

SyFy	14 лет назад, # ^ \| 0 :( не откопал... поиска по блогам нет, а листать в ручную - адская работа... → Ответить

glukin

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

Поиск по блогам достаточно успешно можно заменить волшебным воззванием к Google: "site:codeforces.ru <текст запроса>" :)

→ Ответить

ZumZoom

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

Гхм... Ввели девушку в заблуждение...
В меню контеста, справа от названия задачи есть число x123 - количество участников, решивших задачу. Кликнув на ссылочку, получаем неполный список решивших задачу во время контеста. Кликнув на номер решения, как и в дорешке, открывается код.
Мне неясно, почему нет таблицы со всеми результатами, а только 50 первых, в зависимости от сортировки, но думаю можно найти парочку подходящих решений)

→ Ответить

SyFy	14 лет назад, # ^ \| 0 я имел ввиду тот случай, когда необходимо найти отправку определенного человека, а это бывает сделать очень трудно, когда успешно отправленных посылок было много. стоило бы уже давненько ввести возможность поиска по пользователю его посылок. → Ответить

ZumZoom

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

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

→ Ответить

SyFy	14 лет назад, # ^ \| 0 ну я и ответил на её вопрос: "Можно, ... " :) → Ответить

ZumZoom

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

хД и посвятил)

→ Ответить

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

кто знает какой ответ в задаче Е на тестах 5,7,9.

→ Ответить

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

вот тебе ответы на 5 и 7

1 2

1 4

2 3

2 5

3 4

4 5

1 2

1 4

1 6

2 3

2 5

2 7

3 4

3 6

4 5

4 7

5 6

6 7

→ Ответить

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

спасибо. Я понял как решать эту задачу.Тут просто надо двудольный граф построить и всё

→ Ответить

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

хотя блин..

лень было на листочке разобрать?!

→ Ответить

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

Есть пожелание к организаторам. Можно присылать уведомительное письмо об очередном раунде CodeForces пораньше? Например, за 36 часов. Потому что если оно приходит поздно вечером накануне, то, бывает, забываешь проверить почту вечером и пропускаешь в итоге раунд.

→ Ответить

SyFy

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

припишу сюда пожелание, т.к. не знаю куда еще его пихать: добавьте возможность при редактировании поста сменить и его язык.
сейчас вот с такой фигней столкнулся: написал коммент в английском блоге, а пост-то был в русском... а даубл постингом заниматься не хочется - захламляет думаю.

→ Ответить

forest

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

даубл ?

→ Ответить

slavik

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

Can somebody prove the solution of E?

→ Ответить

niyaznigmatul

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

← Rev. 2 →

Для доказательства корректности решения, нужно доказать теорему, что в любом графе из N вершин, не содержащем циклов длины три, не более N^2 / 4 ребер.

Будем доказывать по индукции, отдельно для четных и нечетных случаев N. Рассмотрим четный случай. Пусть мы доказали для всех N <= 2 * k. Докажем для 2 * k + 2. G - граф, из 2 * k + 2 вершин, не содержащий треугольников. Рассмотрим пару смежных вершин u и v, она существует. Удалим эти вершины из графа, останется граф из 2 * k вершин, не содержащий циклов длины три. По предположению индукции в нем максимальное количество ребер это k^2. Теперь нужно посчитать, сколько ребер могут соединять вершины нового графа с v и u, так чтобы не образовались циклы длины три. Вершины, к которой соединены и v, и u не существует, иначе в графе G был бы цикл длины три. Значит если v имеет t смежных вершин, то u не более чем 2 * k - t. Посчитаем количество ребер: k^2 + (2 * k - t) + t + 1 = (2 * k + 2) ^ 2 / 4. Точно так же можно доказать для нечетных. Ну а примером такого графа является полный двудольный из N / 2 и N - N / 2 вершин в каждой доле.

→ Ответить

Willionaire

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

Какой там 5 претест в задаче D?

→ Ответить

Arcady27

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

Напишите кто-нибудь пожалуйста тест 56 в задаче B

→ Ответить

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

пость код на pastebin.com

так посмотрим =)

→ Ответить

scientist1642

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

admins answer my questions fast during contest , thanks for that.

→ Ответить

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

Люди, а подскажите, что означает "успешный взлом"

→ Ответить

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

Читай правила http://mirror.codeforces.com/blog/entry/456

→ Ответить

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

И с чем его едят!?

→ Ответить

SyFy	14 лет назад, # ^ \| 0 его едят вроде с +50 очками дополнительными в соусе с основными баллами за задачи. → Ответить

ant.ermilov

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

за успешный взлом полагается 100 баллов, а за неудачный отнимут 50

→ Ответить

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

← Rev. 2 →

Проблема с задачей В. Не проходит по времени на 8 тесте
http://paste.ubuntu.com/528335/

→ Ответить

ivan.popelyshev

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

← Rev. 2 →

не по времени, а Runtime Error, ошибка времени исполнения.
Наверное делишь на ноль когда n = 1.
А ещё не факт что надо брать минимальную разность цен, надо попробовать все варианты и хранить максимум полученых бурлей.

→ Ответить

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

спасибо)
сейчас дальше дебажить бум)

→ Ответить

ivan.popelyshev

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

Я там коммент отредактировал, посмотри )

→ Ответить

kenny59

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

Расскажите как решалась задача D. Зараннее спасибо!

→ Ответить

ivan.popelyshev

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

Динамика по следующим параметрам: текущая клетка, текущий остаток от деления ответа на (k+1).

→ Ответить

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

← Rev. 4 →

Здравствуйте.

У меня вопрос к создателям задачи В. Что означает строчка "Он может не более одного раза за n дней купить сколько-то долларов, а потом их продать."? В моей программе до этого не допускалось, чтобы Вася купил несколько раз 5 долларов или продал несколько раз 4 доллара (не подумайте, что я обрабатывала только 4 и 5, это пример). Меня взломали тестом

Input:

4 100
2 100 2 100

Так что же означает эта строчка в условии?

Я переписала задачу, теперь же меня валит тест (взят из списка успешных взломов)

5 10
10 5 7 1 3

мой ответ 42, верный же ответ 30. В условии написано

"Выведите одно число — какую наибольшую сумму денег в бурлях Вася может получить к концу n-го дня."

Так чем же 42 хуже 30?

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

а) значение вышеупомянутой строчки

б) как же получается 30 во втором примере.

Я получаю 42 по алгоритму:

Продадим 10 бурлей по цене 5.

Теперь у нас 0 бурлей, 2 доллара.

Купим 14 бурлей (2 доллара по цене 7).

Теперь у нас 14 бурлей, 0 долларов.

Далее продаем 14 бурлей по цене 1.

Теперь у нас 0 бурлей, 14 долларов.

Продаем 14 бурлей по цене 3

Ответ - 42.

Помогите мне, пожалуйста, довести задачу до ума.

→ Ответить

SyFy	14 лет назад, # ^ \| ← Rev. 2 → 0 мы можем только один раз купить k бурлей и один раз продать j долларов. причем день продажи j долларов должен быть больше либо равен дню купли долларов. → Ответить

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

Спасибо

→ Ответить

SyFy	14 лет назад, # ^ \| 0 пожалуйста :) → Ответить

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

Извините, а почему тогда

тест

4 100
2 100 2 100

Дает ответ 5000, а не 250000?

Ведь мы покупаем 50 долларов по цене 2, продаем 50 долларов по цене 100, продаем 5000 бурлей , получаем 2500 долларов и продаем доллары по цене 100, получаем ответ 250000.

Как можно заметить мы ни разу не продали k бурлей больше одного раза(мы продали 100 и 5000), да и доллары не всегда были в разном количестве (50 и 2500). Только цены совпадали. Почему так?

→ Ответить

sas4eka

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

← Rev. 2 →

"Он может не более одного раза за n дней купить сколько-то долларов, а потом их продать."
То есть можно совершить не более 1 акта покупки и 1 акта продажи за все n дней.

→ Ответить

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

УРА!!!

Полное решение

БОЛЬШОЕ СПАСИБО!!!

→ Ответить

asif_iut

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

what is the idea for solving problem E??

→ Ответить

http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem

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

Problem E is solved by Turan's theorem:

http://en.wikipedia.org/wiki/Triangle-free_graph

As said in Wikipedia:

the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.

so something like this works:

http://snipt.net/Amirkg/codeforces-40-e-c/

→ Ответить

Ever1989

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

Can you give the test 3 of the problem D? I get PE,I'm confused!

→ Ответить

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

Test 3 is from the problem statement.

→ Ответить

ciprianfarcasanu

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

← Rev. 2 →

Hello. Does anyone know a good article(in english) about using envelopes in dynamic programming? I would really need one.
Thx

→ Ответить

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

I'm not sure what envelope means in this case but maybe this will be interesting for you: http://mirror.codeforces.com/blog/entry/325

→ Ответить

galiver

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

hi
please help me.
in B,What is mean bourles?
and
in C,what is pretest 5?
thanks

→ Ответить

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

It's a new Russian currency. One bourle = 100 pokeikas ≈ 0.032 laddors.

→ Ответить

NiceDay

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

← Rev. 2 →

Не знаю оговаривалось ли - это где-то раньше или это у меня одного(но врятли).
Так вот почти у многих юзеров(а может и у всех, я всех не пересматривал:)), кто участвовал на Codeforces BR#40 в табличке контестов показано что они участвовал в 41 раунде хотя его даже судя по расписанию не было, это что баг или что?) у кого еще такое?
А у не которых написано, что они и в 40 участвовали и в 41.

→ Ответить