Всем привет!
Совсем скоро начнется Bayan Programming Contest 2012/13 — Elimination Round.
Комплект задач был подготовлен сотрудниками компании Bayan. Мы постарались сделать его как можно более интресным, а также немного необычным! Мы выражаем свою благодарность Михаилу Мирзаянову (MikeMirzayanov) и Геральду Агапову (Gerald) за помощь в подговке задач.
Данное соревнование индивидуальное, оно будет проходить по правилам ACM-ICPC. Условия будут доступны только на английском языке. Также, оно будет рейтинговым только для участников из Div-1, но участники из Div-2 также могут поучаствовать в соревновании.
Соревнование будет длиться 3 часа, участникам будут предоставлены 7 задач. Как и на большинстве ACM-ICPC соревнованиях, задачи будут располагаться в произвольном порядке, то есть не обязательно в порядке увеличения сложности. Не забывайте, регистрироваться на соревнование можно вплоть до конца соревнования.
Лучшие 20 участников будут приглашены на финал соревнования — Участники из Тегерана и лучшие 100 участников получат суверирные футболки. Детальнее про призы можно прочитать в нашем предыдущем посте.
Будьте честными! Во время соревнования запрещается использовать несколько аккаунтов. Также вы не должны обсуждать с кем-либо задачи до конца соревнования.
Удачи!
Геральд: Из-за необычного расчета рейтинга для данного соревнования. Рейтинг будет обновлен с задержкой.
what??????????? Why is it not rated for div-2 competitors?.what is it???
it's not rated because it's going to be a hard contest!
Nooooooooooooooooo
I hope you can make it rated for div.2 participants, it can make div.2 participants more interesting, so they can solve the problems better (because all of the participants want to make their rating higher).
what's the problem if the contest will be rated for both div. I think if they put each Div in separated rooms ,it will be fair like any contest each div has it's own standing and rooms but this time will be the same problems. I think also some div2 blue coders have ability to compete with div1 thanks
Rooms are meaningless since there are no hacks in contests with ACM ICPC rules.
It's not a very good decision to make it unrated for the 2nd division. I destroys competitiveness, contest will become usual training.
Do you think CF-admins didn't think about making some slightly different problemset for div.2 competitors? Obviously, there's some problem about it — too much people competing (compare to middle-crowded Codeforces round) or some trouble with native (i mean, Iranian) organizers or so. Don't cry and get ready for Codeforces Round #148 (Div. 2)!!
Could you please explain your reasoning for making the contest unrated for div. 2?
Do you really want to hear the answer on your question? Maybe, you won't like it ;-) ... or maybe it's too complicated to understand (and forgive, either) for div.2 competitors:-)
I'll be frank: I don't like it no matter what the reason.
But I still want to know, because if I do know the reason, it won't make me feel any worse and at least I'll be able to understand better.
I think the problems are too hard for Div 2, so there would be many contestants who solved 0 problems.
I don't get it. It seems to me that your better understanding is the reaction on getting the answer you wanted. But you say, this is the cause. Makes my head go round, really.
UPD Besides, here you could see some people giving you two good reasons for that: 1) overcrowded server. 2) hard problems.
Why would my better understanding be the reaction on the answer I want? I don't want a specific answer, I wouldn't ask if I did!
And what I want to know is the responsible ones' reason. If it's like saying "div. 2 guys, this ain't for most of you".
Once again — is prewritten code allowed just as in a typical Codeforces round?
Yes
Thanks!
input/output will be standard or files? I'm sorry, if this is written somewhere, I didn't find it :) thanks
Unable to parse markup [type=CF_TEX] I get that when i try to open problem A. What's the problem? ///EDIT : It got fixed atleast for me
when i try to open problem A:
Unable to parse markup [type=CF_TEX]
UPD: just fixed
Sorry, i haven't see previous post.
in problem C, can i shoot to the edge of mirror? will i give points and will the beam be reflected?
It seems not a good idea to make it unrated for div-2.it is 2’clock in china..and now it seems a wasting -time night for me..
Don't be all about rating, the main idea is to learn something after all + it would've been quite unfair to make it rated because most of the div2 participants would've get their rating decreased, the tasks are too hard for div2.
Не знаю, задумано так или нет. Но за ошибку на первом тесте в задаче G не дается штрафа. А он ведь единственный. С этим ничего делать не планируется?
Это не баг, это фича)
А если серьезно, то сейчас уже поздно что-то менять. Хотя, как мне кажется, было бы лучше сделать WA1 для неверного формата аутпута и WA2 для верного формата, который все же не валит код из условия.
В том коде, который в условии, есть еще какие-то принципиальные баги, кроме глупой константы 300? Если нету, то там довольно сложно пихнуть рэндом.
Я внимательно прочитал код, других багов там явно нет.
Вроде нет. Там конструктивчик. Первый радиус большой, скажем 1000000, следущие 300 равны 300, 299, ..., 1. x[i] для i=2,...,301 подбираем, чтобы все радиусы сработали, а последний 302-й берем (1000000, 1000000). Тогда в S будет 301 элемент и именно на 301 сработает RELAX
Собственно говоря, я так и сделал.
Мне уже тоже стал интересен ответ от кого-то из админов на вопрос Павла.
Я вот сначала отправил "немного неправильное решение" (с промежуточными радиусами 1..300, а не 300..1), потом увидел, что минуса в таблице нету, и решил на приколе послать рэндом несколько раз:) И только потом исправил решение.
Лично для меня начисление/снятие штрафов ничего не меняет. Но если кто-то использовал неначисление штрафов сознательно (как я), и ему навешают тонну штрафов, в результате чего он потеряет поездку на онсайт или хотя бы футболку, то это как-то неправильно.
А если не менять ничего... С одной стороны, если логично подумать, то о наличии такой лазейки можно догадаться. С другой — а много ли таких людей было, которые догадались до того, как послали первое бревно?
Кстати, действительно серьезная проблема. Если всем дадут штрафные очки по G, я поднимусь мест на 20, и я явно не один такой.
а я опущусь мест на 1000
Мда... Ничего исправлять не стали и уже рейтинг пересчитали. Идиотизм какой-то.
По-моему пересчитывать штраф было бы еще большим идиотизмом. Хотя да, весьма странно было, что про такое не подумали. (Подумали, но забили?)
самое хреновое, что такой прокол уже был, правда в тренировке, и все равно не учли это
Если начнут исправлять, то пострадают такие люди, как я. Я когда увидела, что не считается ВА1, начала спокойно засылать различные варианты. А если бы они считались, я бы сделала сабмитов на 20 меньше.
Вообще пофиг кто пострадает, надо исправлять, чтоб все по правилам было. Аргументы типа "Я не получил минус и подумал что теперь все можно" по-моему просто детский сад. Что-то типа я пошел в магазин, украл жувачку, меня за руку не поймали, ну я и подумал, что теперь можно так всегда отовариваться...
по правилам не считать ва1, не?
В ЧАВО написано, что
Все сомнительные вердикты ("Ошибка тестирования" и др.) не учитываются при подведении результатов, равно как и решения, упавшие на тесте 1 (в задачах, где более одного теста).
Означает ли это, что в этом случае должны были учитываться? Я, по крайней мере, так понимаю написанное.
What's test #8 in problem F?
You are not allowed to go through other junctions when you is travelling between two on the list
And what's the problem? If I travel along shortest path between two junctions, it's a straight line. Obviously, if there are junctions on it, it's impossible to travel between these junctions.
Well, at least for me that fixed problem (I assigned weights for edges based on time)
a9999999b
1#######1
c1111111d
It's better to go from junction "a" to "b" througth "c" and "d".
Go to brom b to c.
There is an ambiguity in the problem statement. Let k be 4 in the last sample. Then in 4-th minute we are in the process of traveling from one block to another and it is unclear what to output. I have WA9 when output the final position and get AC in other case. Maybe this may helps.
UPD. All above examples are wrong since the junctions in the input are exactly those junctions that we meet during travel.
Can authors tell me, where exactly in the problem statement it's said that you have to pass only these junctions.
I think, that path abc, goes through ac too.
"We know the initial position of the Old Peykan and the sequence of junctions that it passes to reach its destination"
It hints that all junctions Peykan passed are in this sequence.
And I absolutely agree that it's strange to write about shortest path when mentioning the only permitted path.
This sentence sounds closer to the one, that we were supposed to understand, but anyway it's not formal enough.
Your expression "it hints" is good one, yes it just hints.
I asked about ambiguity in shortest paths, but I was answered that input is so, that there is unique shortest path.
Maybe the test, where the shortest path between some pair of junctions lies across another junction. I solved this test by replacing Floyd matrix with the original one.
Ok, then consider the following example:
3 3 3 a1b 1#1 d1c 2 1 ac 3 2
The path goes from 2 1 to 1 1 and then it has two options — go through 'b' or go through 'c'. So there are two different answers.
Such test is prohibited. They say that string contains ALL junctions in order that the hero passes.
In this case, such test is invalid too and I see no reason for WA8.
This test is correct because we have an edge between "a" and "b". And according to the problem statement you must use this very edge and not any shortest path between these nodes.
So, although we could get from "a" to "b" by "acdb" path we should use "ab" directly.
I found the problem, but I got wrong answer at #9 all the time.:(
Read my comment here http://www.codeforces.ru/blog/entry/5722#comment-110211. I also had WA9 but quickly realized what the problem.
Полчаса где-то пытался понять, почему не 110 на втором тесте С (если убрать стену с ценой 120). Печаль...
How to solve E?
In E we have a system of inequalities d[j] — d[i] <= 2 and d[i] — d[j] <= -1, if there is an edge (i, j). It can be solved by the standard method with Ford-Bellman algorithm.
Yeah, I've already read some AC codes and understood the solution. Thanks anyway!
По поводу задачи С — я убил почти час, пытаясь решить такую же задачу, но заменив отверстия "в точках на стенках" на отверстия "от низу стенки до высоты hl/hr". И все удивлялся, что задачу сдают за 0.03 с нолем памяти.
Задача в моей формулировке решается как-то более-менее адекватно? В моей формулировке получается, что луч выпускают из любой точки левой стенки, которая не выше hl, и он долен попасть в любую точку правой стенки, которая не выше hr. Остальное — как в правильном условии.
Она-то решается, только кодить намного больше и сложность больше. Если размножить нашу полоску, то получится O(N2) отрезков в сумме. Рассмотрим множество всех концов отрезков, а также добавим туда концы изначальных вертикальных отрезков. Тогда у нас есть множество из O(N2) точек.
Понятно, что оптимальная прямая проходит через какие-то 2 точки из этого набора. Получаем решение за O(N6): перебираем пару точек и для пары проверяем все отрезки. Довольно просто это можно ускорить до O(N4·log(N)): переберем точку, затем отсортируем остальные по полярному углу относительно нее и сделаем заметание по углу. Наверное, можно еще ускорить.
How to solve problem C?
I want to know ,too
According to the Dirichlet principle, a laser ray can be reflected only N times, so you can just naively trace it to the position, where it'll get after [0; N] reflections (I mean: you should "unroll" the box vertically).
Whoops, I missed the fact that the beam can not reflect from the wall. Thank you.
In case this technique isn't known to anyone, it's described in the analysis of Google Code Jam 2012 QD.
Let 1<=C<=N is number of intersected mirrors. You may reflect all picture a lot of times.
So the ray is the straight line with finish
r +/- 100 * Cor100-r +/- 100*C. (depends of parity C)Then check if line intersect mirrors.
I'm disappointed with Problem F (Races) statement. I may be missing something in the text, but:
First, it is not stated that the shortest path is unique, and if it is not, which of the paths should be considered.
Second, it is not obvious what is the exact position of Old Peykan while he moves between two consecutive blocks for several seconds.
So I had to submit two clarification requests to figure that out.
However, if these are indeed ambiguities in the problem statement (and not my fault of not noticing the answers to the above points), I believe the best judges' action would be to broadcast these answers and not just reply to me.
Well, in the end, I didn't accept the problem, and being unsure whether it's my bug or another statement ambiguity is a bad feeling for a contestant.
Nevertheless, thank you for the contest! I liked the problems.
UPD: I found out the third point I missed in the statement, and I consider it's poorly formulated, too.
It should be emphasized that we can not pass other junctions when moving between two consecutive junctions from the string. Otherwise, it could be understood the other way: we are given the sequence of junctions, and we should visit these junctions in this sequence; however, it is not prohibited to visit other junctions between the junctions of the required sequence.
For now, I don't see any direct contradiction with this understanding in the problem statement. If there is indeed no such contradiction, please consider rejudging the problem so that both understandings can pass.
As I think, this condition doesn't really matter, does it? Well, if there is path between junctions that does not pass through others, it's a straight line. So, it's the shortest path and solution which looks for it (without condition) should work perfectly.
As moving through different blocks takes different time, it is natural to consider a path to be shortest if it takes the least time to travel, not the least number of blocks.
I see, thank you.
It would be true if all transfer times were same. Unfortunately, time needed for moving from one cell to another can vary.
If he can pass another junction there are tests like
with multiple solutions when moving from
atod. As there is no sentences like "if there are multiple solutions ...", I thought that the junctions list is full.If you see the ambiguity, that is, ask yourself "can we visit other junctions while traveling between two consecutive points of the given route?", there are indeed a few hints in the statement that the answer is "No".
The problematic case is when you see only the "Yes" alternative: there seems to be nothing that contradicts it and forces you to invent that question. I read it like "some points are to be visited in the given order, and the path should be the shortest", and the statement didn't help me to figure out that there are additional restrictions on the path.
My contradiction was described above. Actually, I thought that I've just missed this in statement.
Well, I also thought "can there be multiple solutions", submitted a clarification request, and the judges answered "No". They perhaps thought "No, it is obvious from the problem statement", but with my understanding, I misinterpreted it as "No, we guarantee that there are no such test cases".
Problems are interesting, especially the last one (Problem G). I hope someday I can create some problems like this and then make a contest here.
Today I'm a bit luck, my randomized solution passed problem D. (Though I don't know why it can pass.) And then I become red again. :)
Great and interesting problems.
But there is a bug in penalty time calculation for problem G.
No matter how many times you WA on G, you got 0 penalty time.
Can we get this fixed?
In codeforces if you fail test 1 you don't get penalty (to avoid submission mistake). No one got penalty for G because G has only one testcase.
That is under the assumption that test 1 is the sample test 1. However, problem G is different and I think it makes sense to have penalty for test 1.
During the contest a lot of coders could think "There is no penalty for problem G, so I can submit as many times as I want". If there will be penalty for this problem, it will be not fair for those contestants.
There are only 2 ways to realize there is no penalty for G during the contest.
It's not true. Wrong submissions are marked in the standings as -n.
I think there's some people who will give up participating Bayan onsite because of the flight expenses.
Then,I wonder that , invited contestants will be only people whose rank is lower than or equal to 20th, or include some people whose rank is upper than 20th.
They also have to consider if the rankings will be affected by the penalties from problem G (as said before, right now no one gets penalties). I think they should :)
And I have similar question about top10, whose flight expenses are paid. It will be top10 from the contest or top10 among contestants who will take part in onsite round.
I'm wondering if anyone above the 10th place will pay for the flight out of their pocket.
If someone in the top20 just gives up the chance, will the chance be handed down to the following contestants?BTW, it's quite expensive to fly there..and poor for the 11th,who was just so close to get a free flight..
For Problem D, Gassa's AC code 2482976 make assumption that for n = 63 and every p, there is always a solution for this problem. I just tried the case when the input is just 1, ..., 63 in order, and every prime p ≤ 50000, and the assumption does hold. Anyone know how to prove this?
Edit: Just tried 63, ..., 1, and the assumption holds too.
I just thought that for n = 63 (actually it is 127 in the submitted solution), there are 263 subsets which we can take, something like 263 / 64 of them have zero XOR, and these subsets "behave randomly" modulo p, so the probability of finding the solution is very high.
If p and 10 (base) are somehow dependent, the randomness assumption can break. The only valid cases are p = 2 and p = 5 but these numbers are too small to break the solution. However, my solution could be wrong for non-prime p such as multiples of 10 000.
I have thought about that too, so I strongly believe that the assumption is true. But I still want to find a complete proof.
By the way, would there be editorial for this contest?
Hi there, Can anyone tell me what's wrong with this? Thanks in advance ;)
F — Race
This is an old Peykan.
Isn't it a Javanan? :D
There are some troubles with the show of problem.Please check it.
UPD:Now it is fixed.
"суверирные" поправьте...
Has anyone received the T-shirt?
I've just received it in Vinnytsia. It's a pity, but T-shirt is one size smaller than I expected it to be.
I also did not receive it :(
Today I received one. it's cool,but I think its' a polo shirt and not a T-shirt.
I have received it today in Riga, thanks! :)