Всем привет! :)
Рад пригласить Вас на очередной Codeforces Round #148. Я (Hamed Valizadeh) автор этого раунда.
Я благодарю Gerald (Геральд Агапов), MikeMirzayanov (Михаил Мирзаянов), Delinur (Мария Белова), и Saeed_Reza (SaeedReza Seddighin) за помощь в подготовке этого раунда.
Распределение баллов по задачам стандартное в обоих дивизионах: 500-1000-1500-2000-2500.
Надеюсь задачи Вам понравятся.
Good luck and have fun ;)
Update. Соревнование закончилось. Мои поздравления победителям обоих дивизионов! :)
Div1:
Div2:
Поздравляю участника Endagorion — единственного, кто решил задачу 238D - Ленточное Программирование.
Кстати, я надеюсь, что вас не сильно расстроила скучная задача!
Update 2. Разбор готов. Прошу прощения за задержку. http://mirror.codeforces.com/blog/entry/5765
Two consecutive contests with Iranian authors, very good :-)
also problems with Iraninan characters and stories :)
questions are going to be VERY hard :|
Why do you think so ?
fahmidan sualasham sakhte che berese be hale suala
may be the only reason why he's taken this low rate is that he's written it in phinglish(in farsi means writing persian in english).it's the translatoin: even understanding the questions is hard so how U wanna solve it??!
Thankyou -- Good luck and have fun — -
Codeforces Round #148 will lucky for div 2, :)
148 div 2 = 74
and you mean that will not lucky for div 1?
if this Round will be lucky for div 2 this is not mean that will not for div 1,
For div 1 also: 148 div 1=148
be Sure that Question will be So hard ! :) Do not Put your Rating in Danger !!! =))) GL everyone !
why are they going to be hard?
Because it has had a Three month Preparing Process and its Tasks Have been prepared in This Months :D and its Authors Are Havaliza + Saeed_reza
Please, do not scare me!!! I hope get DIV1 today :(
Good and Hards Tasks... Now I am DIV 1 contestant!!!
I think there's going to be a lot of math in this contest.
When the lags will be fixed?
When the first contestants will give up ;) (seriously, I hope that the lag will not alter too much the contest :/ )
Again it is — the crash!
This is not the first contest which gives me "**Bad gateway**" errors (502 — 504) instead of a contest start. I understand that is not supposed to be so, however, I would want to hear what exactly goes wrong with the server. Moreover, I believe there are plenty of nice guys over here who could probably be very experienced and helpful in configuring network/servers. Why don't we post some CodeForces issues as a public discussion? This kind of a solution would allow CF users to help the platform somehow.
Pressing the F5 Key all the time...
Hope this is getting fixed soon!
Maybe the servers work has worsened because of you and some other users pressing F5 all the time?)
Isn't it better to start on the 5 PM than 4.55 PM ?
It would be better if they would do it like that!!!
http://www.quickmeme.com/meme/3rmsct/
nooooooooooooooooooooooooooooooooooo
всем удачи!!!
В шапке сказано, что CF поддерживает VK. В чём заключается поддержка? У них то уж точно есть опыт в работе с high-load проектами.
I think Codeforces should use safe mode during contest time as they did few times in past. Server down before contest is ok but this may happen in contest time too. Topcoder also closes practise rooms during contest.
Friends, nothing is perfect!!!!
Блин, не успел зарегистрироваться — сайт лежал... В таких случаях обычно контест минут на 10 откладывают, чтобы все успели зарегаться
The server needs to be upgraded.
Почему последовательность (0, 1, 3) не является корректной нешерстянной последовательностью?
Потому что в ней есть подпоследовательность (0).
l = r = 1
Потому что число 0 как подстрока дает xor = 0
А что насчет 1 2 3 4 5 ? При l = 2, r = 5, получаем 2 ^ 3 ^ 4 ^ 5 = 0
Имеется ввиду, что вместо исходной последовательности мы рассматриваем последовательность частных xor-сумм:
b[0] = 0
b[1] = a[1] = b[0] ^ a[1],
b[2] = a[1] ^ a[2] = b[1] ^ a[2],
b[3] = a[1] ^ a[2] ^ a[3] = b[2] ^ a[3],
...
Ясно, что a[l] ^ ... ^ a[r] = 0 равносильно b[r] = b[l-1] (играет свойство ксора a ^ a = 0). Кроме того ясно, что b[i] все лежат от 0 до 2^m-1. Кроме того, по b[] можно восстановить a[] как a[i] = b[i] ^ b[i-1]. И для любой b[] с элементами от 0 до 2^m-1 восстановленная a[] будет с таким же свойством.
Поэтому задача равносильно подсчету последовательностей длины n с элементами от 1 до 2^m-1 (0 нельзя так как b[0] = 0), все элементы которой различны.
Спасибо огромное! Теперь все ясно.
Div 2 — B is not well defined. When we erase a character at position n and cp points to the character at position n+1, does it still point to that character (now at n) or does it remain at n+1?
Why the negative votes and no replies? Is there any place where we can ask questions to the organizers?
Yes, we can ask questions about the problems during contest. There is a big button 'Ask a question' which can be found here: http://mirror.codeforces.com/contest/239
What does the number 239 in the link? 239 is cool number=)
Contest ID...
Very easy problems. Thx!
Easy for you?
I never felt as stupid as I did on this contest =D even in div2
Teach me, master, I want them to be easy for me too.
WTB editorial!
I think, you cannot make the conclusions becouse of first and second tasks.
Looks like its going to take a while to reach division one :s
Carry On~
In problem D, div 2: I think just care the case n==3, another case the anwser is "2 2 2 2 2 ...". Is it right?
no but there are only two options: two smallest in one subsequence or each in a different one. there is no way to decrease the maximum value of F so we have to increase the minimum of F.
No, the answer is without doubt "2 2 2 2 2 ..." only when n==2. In other cases we should check more conditions.
it looks problem E,DIV 2 was easier than D...:D
and it was the opposite in div 1 !!!!
I recall a similar problem, at least on the surface, which also asked the minimum number of edges which direction you had to change. Maybe some people solved that problem and chose this instead of D, since it looked very familiar.
You can't erase your comment, prepare to receive minus by the non-contestants who will not get it now that the system test phase is ended ;)
Are the pretests of С (div1) strong enough? I wrote solution 5 minutes before the end and realized that sometimes it can't find solution. So I just put line: if (best == INF) cout << 2. And it passed pretests! I'm 99% sure my solution is wrong but maybe someone can prove it? :)
It depends on your algorithm ... Maybe you can always find a solution?
I think it doesn't work on bamboo graphs (e.g. O-O-O-O). Idea is the following: Choose one vertex i = 1..n and run DFS on tree to mark for every vertex: is the parent edge forward or backward. If this edge (to vertex j) is backward, we claim pair (i, j) to be good. If both pair (i, j) and pair (j, i) is good, we can relax answer with number of backward edges on the way from the root minus one.
P.S.: Ouch, looks like I deleted some lines and now it relaxes just if pair (i, j) is good :)
Aw .. I'm a little confused .. Hope you pass it!
I liked the contest. At the beginning problems confused me a lot, especially problem A. But when I thought a bit about them, they turned out to be solvable.
Unfortunately my Div 1 C failed...
I can't agree more ~ The problems are all interesting and skillful.
ahhh... at last system test started. hope it won't take long time to finish.
Judging in not working!
Edit: Now working
I missed a hack on problem B :( Someone in my room outputs "1 1" if n == 2...
Without 0 in first line?
Yes
I found same bug in first solution which I saw :P
i guess that's me what's the problem with that?
So am I :(((
B Div 2 много у кого упала ...
I did not spend much time on the problem E because of the following test:
7 8
1 2
2 4
1 3
3 4
2 5
5 7
3 6
6 7
3
1 4
2 7
3 7
The answer is 2 but if we consider only stops reachable in any case for each bus route we don't find a solution. I am wondering how many of those who submitted this problem know about this test?
Very nice problems...But I'm lack in experience and my solution of B got FST...TAT
I'm unluky :( ;(
Pleeeease, don't make us wait, update the rating.
Can smb explain to me how to solve problem C(Div2) or A(Div1)? Thanks in advance
hey, count how many number you can put in the place of a1, then how many number you can put in the place of a2 and so on .
2^m — 1 ways for the first number, 2^m — 2 for the second etc.
f(n) = f(n-1) * (2^m — (n-1) — 1), f(1)=2^m-1. Here 2^m — (n-1) -1 means you have this number of ways to append a number to the valid sequence with length n-1. "-1" since you cannot use 0.
I don't understand.
Why can you simply add unused numbers (apart 0) to a sequence of length n-1?
Look at this sequence (n=3,m=3): 5 (101), 2(010), 7(111)
All numbers are different, but 5^2^7 = 0.
So it is a wool sequence: l=1,r=3
Why am i wrong?
At begining you have only "0" as foribbden element.
After first addition, you have one more foribbden element (the added one).
After second addition, you have next foribbden element (first ^ second). And so on.
So, you must look at "accumulate xor" not (simply) values.
Thanks for your explanation.
I had misunderstood the meaning of "n-1".
And you can also be sure that all of the "n-1" accumulated XORed values will be different, so that there are exactly n-1 distinct numbers to be excluded:
Else, it implies the previous n-1 elements would be a wool sequence:
If XOR (1 -> x) = XOR (1 -> y), y>x would imply that XOR(x+1->y) = 0, implying it was a Wool sequence.
Impressive how some people solved it within minutes =|
I wish this contest were the Elimination Round for BAYAN ... Thank you for the good contest :)
I think so...:)
Finally "Expert"! :)
Multi account is bad. There is a lot of "Ashvili" account on Kutaisi, with one or two contests on the history, like if they create a new account when they are too low to gain a lot of rating. The codes present the same style (same freopen (why not, its common), but reduced indentation too), and you said "Finally Expert" like if it wasn't your first contest, but in your profile, you are a new contestant. Suspicion...
More: the header "cmath" is often more present than "math.h" for C++, but here, for all the bukhnikashvili, there is "math.h".
Psst: You should answer "But I have brothers/sisters who program too, and we share the same code style. And I have said Finally expert because I have trained a lot, and was waiting the first contest impatiently" ;)
There is a lot of "Bukhnikashvili" account on Kutaisi
I do not need lies,I had only one accaunt lasha-buxo(which password I forgot with noactivated mail) and there is no more "Bukhnikashvili",Do you have any problem?
Epic fail, didn't know that the suffix "ashvili" was so common for georgie, sorry ;)
Nothing,:) Good luck in the next rounds :)
Thanks, you too :)
All of these are your accounts:
[user:Lasha-buxo,2012-11-05] LashaBukhnikashvili nodam ahmed.iliu asrsrsr notnothing iamnotscared andiiiiiiiii
How do you know?
I have seen "//lasha-buxo" on the submission of create, but for the others, don't know how do you deduce this.
No one can compete with Lasha-buxo in negative contribution (< -50) xD
http://mirror.codeforces.com/top-contributed/friends/false/page/15 :)
Anyway, he does not hide anything :D
@Lashabuxo I'm hope that you remain blue after a few contests :)
Haha. Better to sit quiet if you're cheating! :P
Nice Contest :D hope to see the Editorial soon..
Контест просто класс!
Задача E, Почему ответ на третий тест — -1? 4 8 1 4 1 2 1 4 2 1 2 3 3 1 3 2 3 4 4 1 2 2 1 2 4
Тут же есть маршрутка, которая равновероятно ездит по маршрутам 2-1-4 и 2-3-4. Значит, когда-то она приедет к первой вершине, и парень поедет на свидание без пересадок.
В понимании авторов задачи худшим случаем может быть событие вероятности 0 видимо. Не понятно правда зачем тогда написано слово случайно.
Чтобы не формализировать понятие "Автобусы играют против нас".
Понял. Обидно, опять не понятно условие задачи без вмешательства других участников. F на прошлом раунде еще прекрасней.)
В условии в нескольких местах написано "в наихудшем случае". В твоем примере наихудший случай имеет вероятность 0, но от этого он не перестает быть наихудшим.
Слово "случайно" там не к месту. Имеется ввиду, что надо рассматривать худший случай. А это значит, что она может никогда не приехать к первой вершине. Я, конечно, не рашил задачу. Но отсутствие слов "выведите ожидаемое число автобусов с такой-то точностью" и присутствие фразы "на какое наименьшее количество автобусов ему придется сесть в наихудшем случае" намекает на мое понимание.
Я понял по-другому именно из-за "равновероятно". "Мое" условие примерно такое: мы можем кататься по любому кратчайшему пути каждого из автобусов, но по какому именно маршруту мы едем сейчас, не знаем.
Can someone explain why in the sample test for div2 b: 7 4 1>3>22< 1 3 4 7 7 7 1 7 the answer for call l = 1 and r = 7 is 2 3 2 1 0 0 0 0 0 0.
1>3>22<
last 6 numbers are ignored for convenience
1-> CP=1 DP=R MAP=0>3>22< X= 0 1 0 0
2-> CP=2 DP=R MAP=0>3>22< X= 0 1 0 0
2-> CP=3 DP=R MAP=0>2>22< X= 0 1 0 1
2-> CP=4 DP=R MAP=0>2>22< X= 0 1 0 1
2-> CP=5 DP=R MAP=0>2>12< X= 0 1 1 1
2-> CP=6 DP=R MAP=0>2>11< X= 0 1 2 1
2-> CP=7 DP=L MAP=0>2>11< X= 0 1 2 1
2-> CP=6 DP=L MAP=0>2>10< X= 0 2 2 1
2-> CP=5 DP=R MAP=0>2>00< X= 0 3 2 1
2-> CP=5 DP=R MAP=0>2>0< X= 1 3 2 1
2-> CP=5 DP=L MAP=0>2>< X= 2 3 2 1
2-> CP=4 DP=R MAP=0>2> X= 2 3 2 1
2-> CP=5 END
If i can solve 3 problems in div2 & 2 problems in div1...Whose 1 will be better???
It may vary between man to man. But according to my opinion, solving 3 in div II is only better confirming that any 2 of these 3 also appear on div I(Like 2 from (C-E))
I see some ppls failed Problem B (div1) on test 6, giving the same wrong answer 190 (P.S. correct answer would be 200).
Is that a coincidence?
Many people have the same, good, algorihtm. Similarly, many people have the same, but incorrect algorithm :P Just coincidence :)
;) But when you think carefully, there is no way you can come up with a combination which is even better than the best case, even with an "incorrect" algorithm.
What you can do with an "incorrect" algorithm, is to get a worse answer. Am I right?
Oh no I got WA on #6 and my answer was 190...However,I don't know why it's wrong = =
I would suggest that you might have calculated the minimum value of the maximum value and the maximum of the minimum value separately while they might not be achieved at the same time.
eh..no..I have thought about this — -...It's so kind of you to view my solution 2500928 (cause my poor english I cannot describe it TAT)
int min1=a[0].first+a[1].first+(i==1?h:0);
This give me accepted. thx
oh no I misunderstood the problem,I thought f(i,j)=Ai+Aj+h if at least one of i and j is in the first subsequence!!Ahhh terrible~~~~~
Where else can i find the current contest questions being discussed????????
wait for the editorial
Сложный раунд=(
if this was an answer to my question then sir plzzzzz give link coz i dont understand Russian............plzzzzzzz provide the link.......
You should use translator or simply skip comments in Russian ;)
He wrote something about 'complex round =('
And... here is right place to discuss this round's problems
maybe he meant "Hard round"
Почему в С не заходит такое
ВА8.
Не очень понятно, но ошибка скорее всего в том, что от второй вершины может быть много достижимо вверх по дереву если исправить некоторые правильные ребра при данном корне на обратные. Пример
9
1 2
3 2
4 3
5 4
5 6
7 6
8 7
9 8
1 10
1 11
1 12
1 13
При фиксированной первой вершине 1 можно выбрать второй вершину 9 и исправить только одно ребро 5 6. Не знаю валит ли этот тест все решение в целом если перебирать остальные вершины, но надеюсь, это то, что нужно.
Вот еще один тест на котором я получил удачный взлом:
15
2 1
3 2
4 3
4 5
6 5
7 6
8 7
9 1
10 9
11 10
11 12
13 12
14 13
15 14
Может он больше поможет.
там чушь
По сути я такое же сдал, только почему подотрезок с максимальной суммой? Нам нужно минимальное количество элементов поменять на противоположные, чтобы вектор принял вид (сначала сколько-то -1, потом сколько-то 1).
Ну и ещё все остальные поддеревья тоже надо учитывать.
там чушь
Спасибо за тесты. на первом у меня 1, на втором 4. 4 — это правильно?
И я не совсем понял, что вы имеете в виду. Зачем нам идти вверх по дереву? Ведь мы затратим строго больше поворотов ребер, потому что при спуске в недоступные из корня поддеревья мы все равно повернем те ребра, которые нужно повернуть, чтобы эти вершины были доступны из корня.
На втором тесте ответ 2 — надо свапнуть (4 5) и (11 12)
Как решать Е (div 2) ?
Зафиксируем одну вершину из ответа и подвесим за неё дерево. Для каждой вершины посчитаем сколько ребёр, направленных "вверх" в её поддереве и запустим dfs. Пусть мы хотим узнать ответ для корня и текущей вершины в обходе. Понятно, что все рёбра, не находящиеся на пути из корня до этой вершины надо просто повернуть, иначе никак. Далее посмотрим на путь от корня до вершины(обозначим за 1 — рёбра вверх, за 0 — иначе) и представим, что мы считаем di — сколько надо сделать операций, чтобы все рёбра до i - го повернуть вниз, остальные (на пути) повернуть вверх. di — количество единиц на [0, i] + количество нулей на [i + 1, end]. Надо только узнавать минимум в этом массиве для текущей вершины за O(1). Заметим, что когда мы добавляем в конец массива d ноль (проходим по правильному ребру), то к минимуму в нём добавляется единица (ко всем значениям +1 на самом деле), а значение нового равно значению последнего (количество единиц осталось таким же). Если проходим по ребру "вверх", то в конец добавляется единица, значение остальных di остаётся таким же, значение нового — это значение последнего +1. Всё это просто можно передавать в dfs.
Вот, дописал через 5 минут после конца вчера)
where can I find the solutions to the problems in contests?
Try to take a look at others' solutions but don't copy them.
Какой ответ в задаче С (для div.1 А) при n = 100000 и m = 60083? Все решения, прошедшие полное тестирование дают ответ 0, хотя там никак 0 не может быть, или я что-то не так понял/не смог понять?
UPD: более формально это все такие m и n, что
Скорее всего, 0 там получился вследствие одного из 99999 умножений по модулю 10^9+9, поэтому дальнейшие умножения ничего не изменили. Или просто (2^60083-1) mod 10^9+9 < 99999, тогда начальный множитель при уменьшении 100% когда-то дойдет до нуля и обратит в ноль все произведение.
Выходит, что 0 получается, когда один из множителей (2^m — i) кратен модулю?
Да, но это можно проще сформулировать — если n > (2^m-1 mod 10^9+9).
Is there any editorials?
UPD Ok it's published now
hey guys can anyone tell me how to solve Div 2 Problem C
try to make a new sequence of n numbers for each valid answer sequence that i'th element of new sequence would be equal to xor of first i elements of answer sequence . each element of new sequence will be different form others and it's between 1 and 2^m -1 ... so for every n and m number of answer sequences would be equal to this :
(2^m -1)*(2^m -2)*...*(2^m -n)
I hope this will help you :)
I can't get the first sentence at all...did you really mean the second word "sequence"? Each element of new sequence will be different from others? Are you sure? I thought (1,2,1,2) is valid since 1^2^1^2 == 0.
But the request is to count the sequences that are NOT a wool sequence...So (1,2,1,2) is invalid..
When the next contest start?