Codeforces Beta Round #82 (Div. 2)

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
27:23:13
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

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

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Ripatti

Codeforces Beta Round #82 (Div. 2)

Автор Ripatti, 13 лет назад, По-русски

Добрый вечер.

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

Раунд мне помогали готовить RAD, Connector, it4.kp, а также MikeMirzayanov. На английский язык условия перевела Delinur.

На этот раз контест будет проходить в старых добрых традициях Codeforces. Никаких нововведений, в меру короткие и понятные условия.

Разбалловка задач стандартная: 500-1000-1500-2000-2500.

Всем удачи!

UPD. Раунд завершен, рейтинги обновлены.

Победители:

1. tsundere

2. jte

3. abacadaea

4. ltaravilse

5. Billy_Herrington

Разбор задач.

Анонс Codeforces Beta Round 82 (Div. 2)

beta round 82, codeforces

Ripatti
13 лет назад
140

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

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

Zlobober

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

Давно просто div. 2 не было. Написать что ли по фану...

→ Ответить

Killever

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

there are any precision issues like last contest :)

→ Ответить

DULGUUNBATMUNKH

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

By the way who is Delinur? Isn't he a coder or someone who belongs to CODEFORCES? Moreover i appreciate his/her translations. Thanks for all your great works. :)

→ Ответить

Zlobober

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

Delinur isn't 'he'. Delinur is 'she' :-)
She isn't a coder (as far as I know), but she is great translator for texts such as statements on CF, so she usually translates contests into English.

→ Ответить

wil93

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

Look here: http://codeforces.net/blog/entry/1984

→ Ответить

Shuaib

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

Is rating affected by reading the problem statements? Or only if you try to submit a problem?

→ Ответить

Zlobober

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

Only if you submit smth.

→ Ответить

InvincibleUZ

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

Good luck and good ratings to everyone

→ Ответить

DULGUUNBATMUNKH

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

I wonder why people gave negative votes to Mehran-r but gives positive votes to schirevko? I think that there is no difference between those comments at all.

→ Ответить

Logvinov_Leon

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

Короткие и понятные условия. Ура. Они услышали глас народа. Спасибо. Удачи всем

→ Ответить

maksay

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

← Rev. 2 →

(70 * 2)³ * 100 операций с даблами - в запуске 1.3 сек. Это кодфорсес, детка:)

P.S. - увидел прекрасное и спешу поделиться. Пропих wrong на задачу Е великолепен! Получил от него чисто эстетическое удовольствие!

→ Ответить

Egor	13 лет назад, # \| 0 Я явно чего-то не понимаю в этой жизни. Ведь задача Е, очевидно, включает в себя центр сферы по 4 точкам, так? → Ответить

maksay

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

Или по 2 в конце диаметра или по 3 на центральной окружности. Но в общем вроде да.

→ Ответить

Egor	13 лет назад, # ^ \| 0 66 человек ее сдало... Пора мне на пенсию... → Ответить

unprost

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

tourist тоже не сдал, ему тоже пора, сразу после школы :)

→ Ответить

Zlobober

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

← Rev. 2 →

Я же прав, что ещё можно её вогнать тремя вложенными тернарниками по каждой из координат? Потому что функция len(v) - расстояние от точки v до наиудалённейшей планеты из точки = min_i{|v - v_i|} где v_i - положение i-ой планеты - функция выпуклая.

→ Ответить

_jte_

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

Можно, но нужно грамотно для новых границ трихотомии определять, принадлежит ли новая точка текущему многограннику.

→ Ответить

Ruslan

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

Не нужно. Если она не принадлежит, то расстояние не улучшится.

→ Ответить

_jte_

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

но функция же себя вроде бы не так хорошо ведет, или я неправ?

→ Ответить

Zlobober

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

Ещё раз. Функция f(v) = |v - v_i|, где v_i - какая-то фиксированная точка, точнее, одна из планет - выпуклая вниз очевидно.
А максимум из набора выпуклых вних функций - тоже выпуклая функция. Тернарники летают, как показывает практика.

→ Ответить

_jte_

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

действительно туплю, спасибо.

→ Ответить

knock-knock

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

Не хватило 20ти секунд чтобы заметить тупой баг в D Т_Т
Глубокий 2 дивизион, привет.

→ Ответить

vlyubin

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

И не говори...

Я North и South местами перепутал и вместо + был - и наоборот в D. Заметил за 20 секунд до окончания но ничего уже не мог поделать...

→ Ответить

_jte_

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

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

→ Ответить

vlyubin

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

Я видел что у меня не тот результат но не мог понять почему ...

→ Ответить

_jte_

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

Я писал на жабе, и она мне выкинула экпшен за границы, поэтому и отловил быстро.

→ Ответить

BaJIuK

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

+ авторам контеста! условия очень порадовали! спасибо! ждем разбора :)

→ Ответить

Zlobober

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

← Rev. 2 →

У меня вопрос к составителю контеста:
Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10^- 6 по абсолютному или относительному значению.

Давайте прикинем. Посчитать расстояние, кроме как корень из суммы квадратов длин проекций вектора на оси мы, вроде, не можем.
Если d имеет погрешность 10^- 6, то d² должно иметь погрешность 2d, то есть 2 * 10^- 6. Значит, каждый из трёх квадратов чисел, стоящих под корнем в d должно иметь погрешность 2 / 3 * 10^- 6 < 7 * 10^- 7. Каждый из этих трёх квадратов имеет порядок 10⁸, значит нам нужен тип данных, держащий $\text{[math]}$ значимых цифр.
Стандартный дабл (кроме которого, например, в VC++ ничего нет) гарантированно держит 15 цифр. Не знаю как вы, а я бы побоялся давать задачу с такими узкими рамками.

UPD:
0_o зашла...

→ Ответить

Egor	13 лет назад, # ^ \| 0 "или относительному" → Ответить

Zlobober

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

← Rev. 3 →

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

UPD:
Так может и пройти, будем ждать систесты.

→ Ответить

maksay

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

Ого, по всем нашим постам пробежали злобные минусеры. Кто ж так не взлюбил задачу Е?:)

→ Ответить

maksay

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

Погодите. пусть верный ответ - (x, y, z), а мы дали (x+e, y+e, z+e). Погрешность 2*e*(x+y+z)+3*e² не должна превышать 2*10 - 6. Максимальное х -10⁴, значит порядок е должен быть 10 - 10, как-то так, нет?

ПС. Впрочем, теперь и мне стало стрёмно за мои 70 итераций тернарника..:)

→ Ответить

Zlobober

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

Во-во :-) Сейчас я всех перепугаю, как сам напугался к концу контеста))
У нас получилось в результате x² + y² + z² + 2 * e * (x + y + z) + 3 * e², а вся эта величина - порядка 3 * 10⁸ из-за первых трёх членов. И уже она должна иметь маленькую погрешность порядка 10( - 6).

→ Ответить

Sereja

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

То что у меня зашло претесты, дает неверный знак уже на 3й позиции числа на входном тесте...

→ Ответить

Zlobober

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

У меня на тесте:
1
10000 10000 10000
тоже ошибается уже на третьем-четвёртом знаке, походу :-(

→ Ответить

maksay

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

Ну, логично. Выскакивает квадрат, получается 10 - 6 и оно по краю заходит. А вот когда ответ близко к 10⁴ по координатам, Ваше решение должно начать чудить. Как, впрочем, и все остальные, вероятно.

→ Ответить

Rubanenko

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

Горе от ума:)

→ Ответить

Billy_Herrington6

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

I love this contest!

→ Ответить

omse1998

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

← Rev. 2 →

You have broken my solution! I hate you!

→ Ответить

ant.ermilov

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

I think you should love him because your solution anyway failed during systest phase, but he allowed you to fix bug and get points!

→ Ответить

omse1998

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

Oh yes, you are right. Sorry, Billy, it's my oversight

→ Ответить

Billy_Herrington6

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

Sorry...Be careful next time,boy.

→ Ответить

phantom11

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

great contest..good questions (and this time shorter too).Although my ratings wont increase much but i enjoyed the contest.It was fun and a lot of learning.Thanks Ripatti:)

→ Ответить

CroDoc

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

testing not started yet?

→ Ответить

sgaflv

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

Usually, when you submit a task, and it fails, it does say whether your solution had WA or TL. My submission was hacked, so I tried to find an error in it. Finally, when I resubmitted it, it said TL on hack 1.

It seems inconsistent. If it told be TL with the initial hack message, I would know what to fix straight away... :(

→ Ответить

Egor	13 лет назад, # ^ \| ← Rev. 2 → 0 You need to click on "Successful hacking attempt" at your status page to find out what's up → Ответить

sgaflv

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

Thank you! Does it also tell you what test case broke it? or just WA?

→ Ответить

Egor	13 лет назад, # ^ \| 0 Only verdict I believe → Ответить

wil93

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

It shows the verdict and the test case

→ Ответить

riadwaw

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

AFAIK test case added after contest only

→ Ответить

wil93

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

When I click on "Successful hacking attempt" from my own "Hack" tab I see the verdict and the full test case written by who hacked me.

→ Ответить

riadwaw

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

Did you click before end of contest?

→ Ответить

wil93

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

Ok now I understand what you're talking about :)

Sorry

→ Ответить

Lewin

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

Great contest! This was my first official contest (since the other one was unrated due to an unusually difficult problem), and I really enjoyed it. It was a good balance of difficulty and coding and thinking.

Can anyone help me with problem E? I know you have to find the minimum enclosing sphere, and that's what I was trying to do, but a lot of other people just seem to be starting at a arbitrary point and stepping towards the correct solution. I was considering this approach, but thought it was too risky, so I'm curious as to what the intended solution is. Since a sphere is uniquely determined by 4 points, the obvious algorithm is O(N^4), but I was wondering if anyone had a faster algorithm. If so, can you please refer it to me? Thanks in advance. (Sorry if this isn't the right place to post this, move this if necessary)

→ Ответить

CroDoc

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

Why isn't it possible to see the hacked test case after the contest?

→ Ответить

AVoz	13 лет назад, # ^ \| 0 It is possible.... → Ответить

CroDoc

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

that helped :) thx

→ Ответить

Sarkin

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

Anyone can explain how to solve problem E?
I had an idea, but I'm not quite sure if it works.
Let C be the optimal point, R be the maximum distance from C to any other point in the input and S be the sphere with center at C and radius R. We have 3 cases:
1 - S has 2 points from the input on its surface in which case C is the center of the line connecting these 2 points.
2 - S has 3 points from the input on its surface in which case C is the center of the circle connecting these 3 points.
3 - S has 4 or more points from the input on its surface and we can determine the center easily given 4 points.
Nice contest BTW, but problems A to D are a bit easier than usual I think.

→ Ответить

Lewin

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

That was what I was thinking as well too, but O(N^4) is a little big especially for N=100.

The smallest enclosing circle can be found in O(N) time: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm, but I'm not sure how to extend that to 3-d, and what the time complexity would be then too.

→ Ответить

rng_58

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

Straightforward implementation will be O(N^5). It can be improved to O(N^4), but it's too hard for Div 2 contest.

I think the intended solution is Hill climbing

→ Ответить

Billy_Herrington6

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

more details?

→ Ответить

rng_58

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

Read accepted solutions. They are very short.

→ Ответить

havaliza

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

I loved this solution. BTW do you know other problems that can be solved using Hill climbing? Are these solutions very common?

→ Ответить

maksay

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

Many marathon matches in TopCoder require some kind of Hill climbing or Simulated Annealing.

However, I have never seen it used in any kind of algorithm competition before. I would also be grateful if somebody could give me some more examples of problems with solutions like these.

→ Ответить

Lewin

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

How do you choose the numbers though? They seem pretty arbitrary. I looked through some of the div2 submissions that failed, that either timed out because their stepsize was too small, or wrong answer when their stepsize was too big. Thanks.

→ Ответить

yangzhe1991

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

I have the same question with you. My solution is wrong answer at case 10 because of the stepsize is only 100. but when i set it to 500, 700 or even 1000, it is wrong answer just at case 7.

→ Ответить

xeronix

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

Considering x and y coordinates only, can't we find minimum enclosing circle's centre and then search for required z coordinate because min_z <= z <= max_z,
min_z = min. z coordinate in given set of points
max_z = max. z_coordinate in given set of points

Though, it might be inefficient as answer can be real number instead of integer value.

→ Ответить

Gassa

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

← Rev. 2 →

I got O(N^5) accepted by loop unrolling (Upd: actually, the final version works faster without it =) ).

There are quite a few solutions with nested ternary searches accepted, too.

→ Ответить

TLN

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

Actually it seems that problem E can be solved in linear time according to the original paper by Mediggo in 1983 (see here for reference and code library).

But I doubt this was the expected solution to implement, as it took like more than a century since the smallest enclosing circle problem was posed by Sylvester in 1857 for a linear algorithm to be found ...

→ Ответить

Martial

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

← Rev. 3 →

Has anyone thought about using inversion?
edit: never mind. I guess I wanted apply a trick in practice like in here, but it doesn't seem to help.

→ Ответить

Martial

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

← Rev. 2 →

Here is an approach:

- Isolate a center point. Call it C. Separate it from the others. We search for a minimum sphere that contains C.

- Invert with respect to C. A sphere that contains C is inverted to a plane that does not contain C. A point inside the sphere is inverted to a point on the other side of the plane.
In particular, the minimal enclosing sphere is inverted to a plane that is as far as possible from C, and such that all points are on the other side from C.

- Find the 3d convex hull, in O(N lg(N)), deduce the farthest plane in O(N).

- Invert again, to get the minimum sphere.

→ Ответить

Rubanenko

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

Посмотрите статус - там люди сейчас сдают задачи с этого контеста... Как?!

→ Ответить

Zlobober

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

Дорешивание.

→ Ответить

Rubanenko

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

Дорешивать, когда идёт ожидание системного тестирования? Я проверял - кнопки такой нету, ты уверен, что это дорешивание?

→ Ответить

Zlobober

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

Во время ожидания можно, а во время тестирования - нет, насколько я понимаю.

→ Ответить

wil93

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

← Rev. 2 →

I didn't perform very well on this contest, but I really liked the problems. Thanks Ripatti :)

From A to D it's quite easy to find a solution, but I wasted the first hour on E (because it seemed to me very similar to this).

→ Ответить

shtorm941

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

Буду внимательно читать условия!!!

→ Ответить

Zlobober

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

Ололо, вот это я мастер... Я умудрился завалить A и C, но вогнать в E тернарник.
Мне понравился этот контест, только надо было его с конца писать))

→ Ответить

Fcdkbear

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

Нда. Лично у меня в E проходят 79 итераций тернарника и не проходят 80.

→ Ответить

Fcdkbear

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

А если сабмитить под GNU C++, то заходят и 80 итераций, то есть в точности мой код с контеста. Удивительное рядом.

→ Ответить

Ruslan

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

Проверял перед отправкой на вкладке Запуск. MS VC++ на 80 итерациях работал около 2300 мс. Сдал на GNU C++ - максимальное время 1690 мс.

→ Ответить

Fcdkbear

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

Я тоже проверял на запуске - работало порядка 1730 мс, если память не изменяет. Правда значения координат были маленькими.

→ Ответить

Gassa

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

По E прошло решение за C_N⁴ * N. За 1940 миллисекунд. Да!!!

→ Ответить

Jacob

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

О_о, круто.

Вот у меня шаманство с квадродеревом не прошло 2й претест по времени =\

→ Ответить

maksay

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

А как ее решать квадродеревом, если не секрет? Что делается после спуска в некую вершины дерева, у которой нет потомков?

→ Ответить

Jacob

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

Про вершину, у которой нет потомков я не вполне понял вопроса.

Вообще я пробовал 2 подхода:

1) Бинпоиск по ответу с октадеревом для нахождения точки пересечения: жёстко тормозит даже на тесте из условия.
2) Спуск по дереву с поиском минимума: находим значение нашей функции в центре текущей области. Если он больше текущего минимума как минимум на половину "диаметра" области, то отсекаемся иначе спускаемся во все 8 потомков.

→ Ответить

maksay

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

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

→ Ответить

Zlobober

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

Я шизею.
THIS
IS
CODEFORCES!!!!!!!11

→ Ответить

wrong

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

About my solution for problem D:

http://gyazo.com/0b862656e379b4d4512a513fe884ac36

It seems to be correct, but the checker says this is wrong answer.

I want some explanation about this.

→ Ответить

wrong

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

Now I know the problem.

My program's output contains leading '\0's.

That was my program's bug :(

→ Ответить

DaurenMuratov

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

А когда пересчитают рейтинг?

→ Ответить

sdryapko

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

Наберитесь терпения и ждите :)

→ Ответить

.PEIN.

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

there was lot of submission for problem E but only a few passed. What is the solution for this prob?

→ Ответить

FORHAD-SUST-BD

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

I like all problems except C. To understand this problem required Oxford dictionary...

→ Ответить

.PEIN.

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

The only word that could give you prob is 'stuffing'. Others are just noun :)

→ Ответить

bigbrain

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

I just understand that a bun is some kind of cake, and stuffing is something to make it (don't even know exactly) :)

→ Ответить

FORHAD-SUST-BD

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

It should be use common words into the problem statement....

→ Ответить

unprost

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

Код по задаче Е у индийца utkarshl даже с копирайтам какого-то ученого из Цюрихского университета :D Причем код здоровенный... И кусок с копирайтом даже два раза написан

→ Ответить

unprost

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

Да, собственно, не только у него

→ Ответить

AVoz	13 лет назад, # ^ \| 0 а зачем надо было писать что он индус? разве это имеет какое то отношение к делу? просто мне кажется что такими сообщениями вы ухудшаете общее впечатление о нации.... так сказать) → Ответить

unprost

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

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

→ Ответить

t.gogniashvili

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

Hello , can anybody give me the full 5th test of problem D? in the editor only half of it is seen

→ Ответить

Billy_Herrington6

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

Why the rating didn't get updated yet?

→ Ответить

insane

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

Is there a way to know the full test case that my solution fail on? When I'm looking at the Judge protocol it shows only n first bytes of the test case.

→ Ответить

ahm.kam_92

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

There is noway till now :\

→ Ответить

ahm.kam_92

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

← Rev. 2 →

8th on the division and only +97?! I have got +176 before for rank 49th and less number of contestants with approximately the same rating! Is there volatility like TopCoder or what?

→ Ответить

giongto35

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

I feel that when falling to div 2 , it's very hard to return to div 1 because being in top 20 div 2 just add so few rating.

→ Ответить

phantom11

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

Well they are just updated

→ Ответить

Shafaet

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

Another good problemset from ripatti :).

→ Ответить

Fox235

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

Народ объясните, плиз, почему в 3 задаче в 10 тесте:
10 2 13 100
20 1 3 10
20 1 2 6

ответ 32... а не 30???

→ Ответить

maksay

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

3+3+2+2=10
10+10+6+6=32
(#1 #1 #2 #2)

→ Ответить

igorkulev

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

Are the ratings updated for the "out of competition" participants?

→ Ответить

ahm.kam_92

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

"out of competition" contestants are really out of competition :) So there are no new rating for them.

→ Ответить

ibra	13 лет назад, # \| 0 Вы даже не представляете какие глупые решения проходят на задачу Е → Ответить

Zlobober

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

Функция просто очень хорошая. Если бы она не была такой выпуклой, градиентный спуск бы не работал.

→ Ответить

ibra	13 лет назад, # ^ \| 0 даа, надо было мне это решение на контесте писать, после контеста я его блин за 3 минуты написал) → Ответить

ibra

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

[code]

point center;

double iter = 1000000.0;

while(iter > 0.0)

{

iter -= 1.0;

double step = (iter/10000.0)*(iter/10000.0);

int id = 0;

double max_s = 0.0, d;

for(int i = 0; i < n; i++)

{

d = center.dist2(v[i]);

if(d > max_s)

{

max_s = d;

id = i;

}

double dx = p[id][0]-x;

double dy = p[id][1]-y;

double dz = p[id][2]-z;

double s = fabs(dx)+fabs(dy)+fabs(dz);

if(fabs(s) < 1e-8)

break;

x += dx/s * step;

y += dy/s * step;

z += dz/s * step;

}

cout << center.x << " " << center.y << " " << center.z << endl;

[/code]

→ Ответить

ibra	13 лет назад, # \| 0 простое численное решение. Во время контеста я даже писать его не хотел, дкмал как-то глупо. Вообще прикольно) → Ответить

Killever

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

any one can explain what this statement mean in problem "C"

Lavrenty knows that he has a_i grams left of the i-th stuffing

thanks

→ Ответить

daftcoder

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

Lavrenty knows that he has a_i grams left of the i-th stuffing. It takes exactly b_i grams of stuffing i and c_i grams of dough to cook a bun with the i-th stuffing.

With b_i of i-th stuffing (and c_i of dough) baker can make a bun. So if he has a_i grams, he can make at most a_i/b_i (integer division) buns with i-th stuffing.

→ Ответить

wil93

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

Oh, I had a hard time understanding this, seriously.

I misread this way:

Lavrenty knows that he has a_i grams of dough left after using the i-th stuffing. It takes exactly b_i grams of stuffing i andc_i grams of dough to cook a bun with the i-th stuffing.

So I asked a question and the answer was sth like "please read statement" :)

→ Ответить

TLN

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

I read the same thing as you hence I was puzzled for a moment before realizing reading the sentence twice solved my bewilderment.

I guess the following formulation would have been less prone to misinterpretation : « Lavrenty knows that he possesses a_i grams of stuffing i. It takes exaclty ... ».

But part of solving a problem is understanding its statement =)

→ Ответить

ruban

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

← Rev. 2 →

В принципе, решать E можно еще проще, без какого-либо тернарного поиска - этакий метод наискорейшего спуска - light.
Берем произвольную стартовую точку. Для нее выбираем самую удаленную планету. Чуть-чуть двигаемся в сторону самой удаленной планеты (например на 0,1 этого расстояния). И так много-много раз. Потом уменьшаем коэффициент, с которым мы продвигаемся в сторону самой удаленной планеты.
И все.

→ Ответить

Zlobober

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

Выше уже обсуждалось.

→ Ответить

ruban

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

Объяснение тому весьма банальное. Через час после контеста прочитал задачу E - обычный метод градиентного спуска, почти 20 лет как читаю студентам. Жалко, что не прочитал во время контеста, всяко проще и C и D. Наутро закодил и тут же, не прочитав все комментарии (на глаза попались только лишь про тернарный поиск), написал об этом методе.

→ Ответить

ksb

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

Greetings,

During the contest some fatboy hacked my solution for Treasure Island, the verdict was TLE. But when i see other solutions i see that people are doing simple brute force. Now my question is, the problem says "Walk n miles in the y direction" is the form of instructions and i see that accepted solution just jump directly n miles and dont check all the blocks in between. Isnt this wrong? Tell me.

→ Ответить

wRabbits_AlMag

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

Let Up[i][j] will be the maximum free cells Up from (i, j) and Left[i][j] - will be the same for left direction. So, to check is there any block to the North: if (Up[i][j] >= n) that's all, you can jump to the north, having enough free cells for moving.

→ Ответить

dalex

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

Let a[i][j]=1 if the cell is blocked and 0 otherwise.
Then, for example, the way from (x, y) to (x+dx, y) is clear if a[x][y] + ... + a[x+dx][y] = 0.
These sums can be precalculated just after reading the matrix and then obtained in O(1) time.

→ Ответить

vietlong2110

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

I'm sorry but can the author of this round tell me why my program return the wrong answer on test 12 of the C problem on Div2. I ran it on my computer and it return the correct answer. Sorry because I don't know ask you where :D.

→ Ответить

spongebob

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

← Rev. 3 →

Unfortunately I missed this round. but when I was solving problems today I wrote exactly same algorithm for Problem D in java and c++, but java got TLE and c++ got Accepted.
Isn't getting a problem accepted, algorithm dependent and language independent?

→ Ответить

_jte_

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

I believe no, 'cause my java solution got accepted with 420ms as maximal execution time per test. So, if you have good algorithm and realization, u'll pass system tests in majority of cases.

Here is my source code, if any.

→ Ответить

spongebob

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

yeah, you're right, my algorithm wasn't good.
but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.
otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges.

BTW, you used Thread, how much faster is it than using a simple class?

→ Ответить

_jte_

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

but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.- this is wrong in some cases, e.g. some manipulations with memory, etc.

otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges. - This was discussed, and MikeMirzayanov mentioned this will be done some day.

Nowadays using Thread's not much faster than using simple class, it's a kind of tradition)

→ Ответить

riadwaw

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

← Rev. 2 →

I think it's OK that timelimit is same

1) You can choose C++ and be availabale to shooting your legs or choose Java, get safe, but someproblems with timelimit

2) adavydow wrote here about example of set big timelimit for ruby:

> most of string problems solved more easy in Ruby, then in other languages because they are only optimized library function call(writed on C/C++). There are a lot of example of passed O(n^2) ruby solution instead of O(n) C++ ones

Besides, not-standart algo's in Ruby overwise can be not passed, even with good asymptotics

So, as I can see it may solve old problems badly and get new problems

→ Ответить

ray040123

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

Can you tell me how to contact the administrator of the judge machine? Because I think installing numpy for Python is not a bad idea.

→ Ответить

Aries512

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

You can send a message to Mike Mirzayanov through his profiile.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 14:11:49 (j2).

Десктопная версия, переключиться на мобильную.

При поддержке