Условие A (eng.) https://docs.google.com/document/pub?id=1ie3NIzfcXYPbvmUrj9VW112nwkdnWj2eKw-3gVRGT98
Условие G (eng.) https://docs.google.com/document/pub?id=1gvx2yZ7O-L0SeY0VOQD4R4rmPjrWXhnx6KuvOS5yPio
Объяснения A, G (eng., укр.) https://docs.google.com/viewer?a=v&pid=explorer&srcid=1f3XsMQ_4mKzL05Gqpo38LiV8Kantw_Oc4PuZrZ4qJI3GmU_itLo-6M71xIAx
Условия могут незначительно отличаться от окончательных, розданных непосредственно на соревновании. Например, точно помню, как на бумаге во время соревнований видел "zoom ration" (???), хотя в более старой (выложенной тут) версии zoom ratio, как собсно и должно быть.
Лично меня интересуют отзывы именно на эти задачи, т.к. я их готовил. (Разумеется, отдельной благодарности заслуживает также украинский методический комитет, помогший, в частности, но не только, с грамотным английским.)
В частности, интересует, что задачу G решали, и, по слухам, значительная часть совсем не тем способом, что я. Vasyl[Alphacom] (Васыль Билэцькый) кратко рассказал о том, как прикрутить туда RMQ, но, увы, сегодня вчера я понял, что не понял его :(
И, увы, что-то сегодняшний вчерашний codeforces соревнуется со вчерашним соревновался с позавчерашним PC^2-ом в виде спорта "кто круче не даст ничего сдать/написать".
Там мельком что упоминалось о задаче палиндромах и дате в формате ДД/ММ/ГГ и проблемах с несоответствием тестов в ней.
Имеет ли эта задача что-то общее с этой? (условий пока в Интернете нет, поэтому мучаюсь догадками)
Ну пожалуйста, ну расскажите мне, как по-другому решать G.
А то закостенею в своём недоразвитом состоянии и начну работать по принципу "чем придумать хорошие тесты, гораздо легче напихать в них лишних слэшей" ((с) aRSeniy)
Минусующих прошу давать развёрнутые комментарии: в чём именно неправ человек, желающий знать, какие могут быть альтернативные способы решения задачи. Ну, или почему это должно быть хорошо для участника но плохо для автора.
Первые два абзаца, если кто не понял, написаны в иронично-саркастичном ключе. Но неужели кто-то может отрицать, что в этой шутке немало правды?
Мы решали чуточку по-другому.
Идея такова: сожмем задачу основываясь на параметре "пиксели". Заведем на основе сжатой задачи дерево отрезков(для нахождения максимума). Элементы дерева - зум для каждого пикселя. Еще заведем set, в котором храним пару "цена, индекс запроса". Тогда при обработке запроса вида P добавляем элемент в set, модифицируем дерево отрезков. При запросе С делаем следующее:
До тех пор, пока set не пустой или ответ не найден:
1) Вынимаем из set первый элемент.
2) Смотрим, нет ли фотоапарата с таким же параметром "пиксели" и больши зумом. Если есть - удаляем элемент из сета, идем к пункту 1.
3) С помощью дерева отрезков ищем максимум зума среди всех элементов, у которых парметр "пиксели" больше нашего текущего. Если этот параметр больше или равен текущему зуму - удаляем элемент из сета, идем к пункту 1.
4) Если пункты 2 и 3 не верны - ответ найден, выводим его.
И да, это решение легко меняется под случай "больше-больше", обсуждаемый ниже. Удаляем пункт 2, в пункте 3 меняем "Если этот параметр больше или равен текущему зуму" на "Если этот параметр больше текущего зума". Если не ошибаюсь, все
Точно-точно?В том числе и в случае, когда есть
(pix = 1000, zoom = 2, cost = 1),
(pix = 2000, zoom = 2, cost = 3),
(pix = 1000, zoom = 12, cost = 5)?
Sorry, для этого примера всё работает...
In problem G I think the part "which is strictly better by any one property and not worse by another" was unnecessarily complicated and led to a lot of WAs. Also one of my teams used the first idea from the solution and the got WA instead of TLE.
Unfortunately, I have no own on-line judge ;) Speaking more seriously -- I need to receive permissions from official SEERC judges and from somebody who have on-line judge.
One more aspect is that so happened that I sent tests, and some time after made some small, non-principal changes, and sent changed tests. I don't know exactly which of them were finally officially used. AFAIK, both tests sets are correct, but... I don't want to say "these are the same problems with the same tests" when I'm not sure.
"complicated part" -- well, I'm listening to propositions how could I formulate it better. I did not want to use programming-language expressions or mathematical expressions which are too alike to programming-language ones.
What do you mean by "the first idea"? Ignoring possibility of different propositions with the same number of pixels and the same zoom ratio? But if so, why do you wonder it was WA?
If I understood correctly, they stored the cameras in a set, found the upper end of the region by one criteria (pixels or zoom) by lower_bound, then iterated over every element in the region and chose the ones with the appropriate value from the other criteria.
(sorry for using word "propositions" in previous post, it should be read as "offers")
I still think that criterion "either (>, >=) or (>=, >)" was a good choice.
(>=,>=) -- surely no. It's unnatural to prohibit different offers of the same model (equal both pixels number and zoom ratio), so I did not want to do it just for simplify the problem. And it's extremely unnatural to say that such offers makes this model outdated.
Considering "outdated iff (>,>)" -- principally possible, but as far as I can see, complicates a lot my solution,
and (as I found just now, after contest) makes practically impossible solution posted (in Russian) in this blog by Fcdkbear.(not sure)About the last paragraph of your post -- I'll try to reply you later. If anyone else can reply smth clever -- you are welcomed to join discussion.
Maybe tests published at acm.ro will be helpful.
But, from other side, I can click on the link "All problems including input and output data", but download doesnot actually start... Maybe we need to wait.It was a temporary problem, some minutes later I downloaded them at good speed.