Всем привет! Хотите вы, или нет, но скоро состоится Codeforces Round #234 (Div. 2) автором которого являюсь я :)
Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, Михаилу Мирзаянову (MikeMirzayanov) за превосходную систему, и Сереже Нагину (Sereja) за то, что любезно (поделился со мной картошкой и беконом, было очень вкусно) согласился помочь в тестировании.
Разбалловку оглашу сразу, как найду. Нашел! Стандартная :)
Всем удачи :)
Sorry for my bad english.
:D
"didn't" happen again !
You right
This is the first round after CF crashed, I'm very excited with this round, also number 234 have several nice coincidence with primes numbers!!!! I Hope be a good round for everyone!!! let's go to upgrade ranking!!! Good luck to everyone!!
J
Glad to see Codeforces back on its feet.
This is my first contest on codeforces,I like ACM. I think it will be successful for me. Good luck for everybody!!!
(deleted)
Wish to become Candidate Master again.
Hope codeforces don't be such a problem again.After all,I really like it.
Hope this contest normally exit and evryone has a fun.
After accident ,i think problems in round will be about crash of the system. Good luck for everybody "Fixing" the system.
а что уже синие могут раунд давать...,как я помню этот автор даже А задачу из DIV-2 не мог здать
Ранг на КФ имеет мало общего со способностью человека придумывать задачи. Да и если сравнивать, кто "круче" — опять же ранг не лучший критерий.
Не то, что бы я придираюсь, но мне все-таки кажется, что синий от фиолетового можно отличить=)
до краха системы — этот автор был синий и если он сам не очень решает,так как он может придумывать задачи
Раунд для второго дива, а не первого) Так что если Вы сегодня решите все задачи, то можете смело писать, что автор Вам не подходит, а пока этого не случилось, давайте все-таки будем уважать чужой труд.
автор не решил ашку из второго дива,как он может давать задачи,мне вот это не понятно
Каким способом автор придумывает задачи — это не наше дело) Если задачи покажутся Вам старыми или простыми, тогда можно будет уже обсуждать, а делать это до начала раунда мне кажется несправедливым.
ДЕЛО НЕ ЗАДАЧАХ...безусловно задачи будут интересные,я усомнился в компетентности автора раунда.
.безусловно задачи будут интересные,я усомнился в компетентности автора раунда.
Прошу прощения, но выше приведенные утверждения противоречивы :)
в чем,можно уточнить
Интересные задачи — это и есть работа автора. Если они интересны — работа сделана, автор компетентен, и наоборот.
возможно visionix переживает, что авторские решения и/или тесты могут быть не правильные. Но для избежания таких ситуаций и существуют тестеры с ВЫСОКИМ рейтингом))
ну вот от Димы было уже 3 или 4 раунда если я не ошибаюсь. У Вас было ощущение что в этих раундах что то не доработано? Как по мне все было идеально для второго дива.
А по поводу А-ки второго дива — у каждого бывают невезения. Я думаю единичный случай — не показатель)
мне например нравятся задачи с предыдущих раундов этого автора. Хорошо подобранной сложности, интересными условиями. А прежде чем говорить о его умениях, надо наверное посмотреть его предыдущие раунды, которые он делал, они довольно хорошие, как по мне. На вкус и цвет конечно.... Но вроде в коментах к предыдущим, такое же кол-во бугурта, как и у остальных.
Воу-воу, серый, притормози.
Last contest people here were saying that 233 is a very lucky number and the website crashed. Stop saying "hope the contest will be lucky". Anything that you say will not affect the contest.
in russian version of this blog it is written "to share delicious potatoes and becon with me" instead of "evening", also there is "potatoes" among the tags (prooflink)
maybe this will help you solve more problems during contest, gl :)
That would only happen if VK servers will fail too.
DistirbutionDistribution will beanouncedannounced assoossoon asfounddecidedThank you, sorry for that typos. "Found" was a small joke about lost distribution :)
Еще перед 220 раундом, Sereja надеялся, что это будет последний контест, который готовит Berezin. Теперь же он и надежду потерял)
Картошка в тегах это небольшой спойлер к задачам? :)
Я думаю это к тому, что его картошкой с беконом угостили) Хотя кто знает...
Hope this contest would be about Inna and Dima. :)
Guess your wish came true :P
Good Luck and Have Fun. High Ratings :)
Dark week of codeforces ending after 234(round)2(div) seconds...
Distribution not found :D
Problem B: simultaneously instead of simulaneously. Please fix it.
I cannot distinguish between these two words. :D
simultaneously
simulaneously (t is missed)
simul-t-aneously vs simul-aneously
Problem D: The way with number i can be described with integers ui, vi and xi mean that this way allows moving energy from bacteria with number ui to bacteria with number vi or vice versa for xi dollars.
ui can go to vi with xi dollars. Does it mean vi can go to ui with xi dollars?
I think so. That is what "vice versa" means, I guess.
Yeah, and the problem didn't say whether ui,vi <= n. Actually, it should describe clear this point.
i submitted peoblem B wrongly 3 times before the announcement was made. will i get +150?
Easy problems.
Especially the two which you couldn't solve, right? :D
Yes! :D
В условии задачи D совершенно нигде не было сказано, что нужно вывести именно МИНИМАЛЬНЫЙ путь между i и j видами:
"Ячейка d[i][j] этой матрицы должна обозначать стоимость передачи энергии от бактерии вида i к бактерии вида j."
Кажется, что можно вывести любой путь, слово "минимальный" в условии вообще нигде не встречается!
Благодаря этому получил -300 баллов, пока дошло. Считаю это большой ошибкой автора.
Плюс еще и в задаче В тесты неправильные. Думаю, раунд должен быть нерейтинговым.
Да условие D'шки вообще укуреное на мой взляд :-D
Почему-то сразу понял, что нужен минимальный путь. Видимо благодаря упоминанию два раза слово "бесплатно": "Конечно, пользование таким оборудованием не бесплатно" "передать энергию от любой бактерии определенного вида другой бактерии этого же вида бесплатно"
Написал Флойда, чтобы минимизировать матрицу. Написал систему непересекающихся множеств, чтобы проверить, что можно внутри бактерий одного вида передавать энергию. Но все равно получаю WA test 9.
Задача D была на умение читать мысли автора, а не условие.
Кто-нибудь знает, как решать оригинальный вариант задачи B?
A sad day for hackers :(
Problem B solution, before the announcement is NP-Complete ?!
Yeah, i think so
first i will answer ur question. no, it is still solvable in
. i solved it well before the announcement was made (albeit after one wrong submission due to problem statement not being very clear).
the problem asked to find minimum number of moves, and we can easily observe that choosing all rows where dwarf has not yet reached candy is the minimum answer.
so i don't think the announcement really changed anything about the solution. in fact it just gave us a hint as to how to solve the problem.
EDIT: sorry, my mistake! please ignore this post!
Wrong, consider example:
The minimum number of moves is 2, not 3.
i don't think u understood the problem correctly. in each move, the player must choose a set of rows and move the dwarf in all these rows to the right, until one of them reaches the candy (or the end of row).
EDIT: sorry, my mistake. i couldnt visualize ur example properly when i wrote the original comment as it wasnt displayed like a matrix then.
That's right, and we can do it in two steps:
I think you are wrong the answer is 3
look at this sample :
3 7 ....G.S
..G...S
G.....S
by your algorithm answer is 3 but answer is 2.
That's not true. For example, consider the testcase:
The optimal solution is to choose row 1 and 3 in the first move and then rows 2 and 3 in the second.
Official test from task B :
Answer: 3
But the answer is 2: firstly choose 3 and 4 lines, then 1,2,3.
Announcement for B problem was too late i thought every step is move not every "lets go " is a move !
I solved problem C, D, E first.
& ?
who cares!
You apparently care enough to post a response.
I thought B is a big problem. @x@
Epic
The problem statement for Problem B was corrected too late.
Impressed with amazing testing speed
Testing does not have unusual speed... The speed you see is because of low number of submissions...
but there were many users registered :/
Just 1800 of them participated...
Was it just me or were the problem statements this time pretty difficult to understand (in English)?
I spent long time in understanding problem D
especially problems B and D!
In problem D can someone explain why the answer for 7 test "yes"?
There is only one bacteria for each type. So all bacterias in one type can gain energy with cost = 0 from a bacteria with same type .
"Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost."
there is 0 operation,so bacterias can not move energy from any bacteria to any other bacteria,am i right?
...to any other bacteria of the same type...
Any other. This condition's satisfied if there's no other bacteria of the same type.
thanks :)
Удалено.
вкладку спрячь хоть....идиот
это не баг, это фича (где-то уже было):)
Что-то мне кажется что оба этих случая связаны между собой. Например, в карты играли на такое желание во время зимней харьковской школы.
шлюхи киев
Кто-то этим скрином попалился — все внимательные сразу поняли, что автор использует Dev C++...
Super вкладки :D
OMG, в D зашел Флоид. Хотя я так и не нашел в условии слова о том, чтобы "путь" был минимальным.
The descriptions of five problems are too lengthy and so difficult to understand...
Horrible problem statements ... :/
Why my submission code1 got WA, but another code2 got AC, but I do think they are the same. Plz help me, thanks much.
May someone tell me why this submission get WA, i don't know why it is printing -1 on test 8
http://codeforces.net/contest/400/submission/5944310
It is because u declared tab[1010][2] as char
I replaced it with int and got accpeted
Submission
thanks
In most implementation, the range of char type is between -128 and 127.
Nice problems... Thanks to author....!!!
In problem E, I submitted this code at first. 5935260
But, I easily found the case which make my code TLE. (n=m=10^5 , a1=a2=...=an=65535, question are repetition of "0 0" and "0 65535")
So, I wrote another code and submiited. And I lost about 900 pts :(
But, I submitted first solution after contest, it passed systest and execution time is less than my second submission!!!
To avoid such things, I want writers to make testcases more powerful...
I agree, it should TLE...
For problem B, why my submission code1 got WA, but another code2 got AC, but I do think they are the same. Plz help me, thanks much.
In the first code, you use
char p[1005]to store the distance between 'G' and 'S'It will overflow.
Oh, I see it. What a stupid mistake. Thanks very much.
How can the answer for the following test case be 3??
Clearly it is 2: 1st move: select 1st row and 3rd row. 2nd move: select 2nd row and 3rd row. but the accepted answer is 3. Can anyone explain why this is so?? Was it a fault or I'm not understanding the problem correctly. Because I wasted a lot of time thinking otherwise. :(
i have the same problem and The author had a mistake: "Problem B. Inna and New Matrix of Candies ***** In problem B was mistake in the statement you must choose all line with dwarf that is not in candy location, not several. Now the statement is correct. Sorry for that."
But the announcement said "you must choose all line with dwarf that is not in candy location, not several" So "all line" means that we can choose several lines in which dwarf is not present on the candy. Isn't it??
Never mind. I got it. Although the announcement was also ambiguous. First saying "all line" and then "not several". Confusing. :(
You are right, answer was 2 before the announcement. But they changed problem in middle of contest to this version : In a move you must chose all of row that G is not arrived to S , but the first problem was a set of rows.
but don't worry, this is just another mistake in codeforces. :)
After your first move ('O' indicates G and S are in the same position):
After your second move:
So you need a third move: select the 3rd row
The problem statement has been changed at the later stage.You have to move in each row where G and S have different index. In the above case — 1 move , 1st row G and S have same index.2nd row **GS.3rd row **G*S 2nd move ,1st row work is already over, 2nd row G and S have same index now.3rd row **GS 3rd move,3rd row G and S have same index now.1st and 2nd row already over.
The statement says that you are not allowed to exclude any possible movement, so, by saying "select 1 and 3", you are excluding a possible movement (moving on row 2), which is not correct according to the final statement. Your point is correct regarding the original statement, tough.
Problem B was so cute. I spent more than an hour to try to figure it out bur failed...Hahahahaha~
Thanks for the testing speed.Hope it will be continued in future contests...
HELLO EVERYONE, TODAY WAS A ERROR IN THE TESTCASES ON PROBLEM D
THE NEXT CASE DONT WAS INCLUYE: 4 2 2 2 2 1 4 0 2 3 0 MY CODE WAS HACKED , BUT ACEEPTED WITH CASE THE CODEFORCES I RECOMMEND ELABORATE MORE CASES !!!! PLEASE
We had some interesting friends join our competition today :D
dibil01 dibil02 dibil03 dibil04 dibil05 dibil07
dibil08 dibil09 dibil10 dibil11 dibil12 dibil13
dibil14 dibil15 dibil16 dibil17 dibil18 dibil19
dibil20 dibil21 dibil22 dibil23 dibil24 dibil25
dibil26 dibil27 dibil28 dibil29 dibil30 dibil31
dibil32 dibil33 dibil34 dibil35 dibil36 dibil37
dibil38 dibil39 dibil40 dibil41 dibil42
Mr. dibil, I applaud your determination, but why have you forgotten about 06? It ruined my beautiful rectangle :(
So Mr dibil, how many brothers are u?
Dibil can be family title too... :P
Mr. dibil, his father, his uncle, his son, his grandfather... everyone is in codeforces ... :P
i think the real owner of all these accounts is Beket. midway through the contest, i saw that he had hacked dibil03's solution for problem A 6 times!
i guess the admins saw this, analyzed the codes of the hacked solutions (
probably they all contained hard-coded wrong output for the hack caseshaving checked the codes, i can now confirm that this is indeed true), and discounted all hacks except the first one.Should be banned!
See these solutions, both are exactly the same except for a special hack case in dibil03's solution!
dibil03's solution and Beket's solution
was it an unrated contest? when the rating will be changed? or won't change?
its updated now
In the beginning I thought the data for B is too weak ....
And I also wrote a wrong code , and want to hack somebody .....
and I get -50 .....
no server error seen in today's contest :) ...... good work codeforces :)
Omg, with such a lot of bugs this round is still rated.
Ratings have changed!
my rating changed from 1694 to 1697! not sure if i should be happy that it increased, or sad that i was so close to going back to Candidate Master!!
کصصصصااافطاا آنریت کنیییین.عوضیا "بی" غلط بووووود in english : nice contest,nice questions
Незнаю, почему большинство не довольно раундом, мне контест очень понравился!!! Задачи были не сложные, условия было очень интересно читать. Спасибо Дима! Делай побольше контестов!
P.S. Ошибки бывают у всех. Не существует идеального человека... Да, и в D по-моему и так все было понятно, почему-то сразу понял что нужен минимальный путь. В В тоже проблем небыло.
UPD: + разбор добавлен очень быстро!
Могу объяснить, почему мне не понравилось.
Во-первых, первые четыре задачи рассчитаны просто на сложность закодить, в них нет никакой идеи, решение очевидное.
Во-вторых, если у тебя с B и D не было проблем, это не значит, что их не было у остальных.
В задаче B я почти сразу же начал пытаться справиться с тем случаем, который ни одно решение не учитывало. Он очевидный. А с поправками в условие, которые, кстати, пришли аж во второй половине контеста, задача вообще не представляет из себя ничего интересного, там просто надо сделать то, что написано в условии. Если бы для меня контест был рейтинговый, то я не смог бы позволить себе почти часовую возню с отправкой вопросов. Почти наверняка я бы пропустил эту задачу.
С условием D лично у меня проблем не возникло, но у других такие проблемы были, их претензии вполне обоснованные.
До окончания контеста я был уверен, что его сделают нерейтинговым.
I need help with understanding problem E. Doesn't procedure look like this:
And the sum is 13? What didn't I understand correctly?
It's bitwise
. So we have
AND, not bitwiseOR.and the sum is 4.
i think u mean
1&2 = 0, not1^2 = 0.He is using the mathematical notation, not C++.
(1 AND 2) = 0
Ups, thank you both! ;-)
У меня два вопроса.
Примерно 900 человек сдали задачу B до объявления. Может быть, условие изначально можно было понять так, чтобы получить авторский ответ — если да, то как?
Условие задачи B поменялось в 1:14 из двух часов соревнования. Сколько до этого было человек с вердиктом
Wrong Answer on test 3и ответом 4 на него — и если много, то почему контест рейтинговый?Отвечу, как сдавший до объявления. У меня абсолютно нет опыта спортивного программирования. Я не умею просчитывать все варианты и только этому учусь. Единственный вариант решения, который увидел лично я — был одинаков с идеей авторского решения — 5935812 то, что возможен иной вариант понял только после клара.
только после конца контеста и жаркого обсуждения понял, что я решал(и решил) не ту задачу которая была написана(на клару не обратил внимание, претесты же пройдены, да и вне конкурса)
+проскользнула в голове мысль "это ж В див2, тут все должно быть просто")
да и в Д строчка 'k <= 500' говорит, что я хочу 'forforfor':)
Вообще мне кажется немного ненормальным то, что почти никто не подумал над B только потому, что это B, что "это же див2".
Я подумал после того, как написал простое решение. Понял, что она вроде как NP-полная, отправил то что было уже написано. Претесты пройдены, следующая задача.
Можете написать условие, которое было первоначально ?
В каждый ход можно выбрать любое подмножество строк — а не только все строки, в которых гномики ещё не дошли до конфет.
Да, это немного ненормально. Ведь автор мог натупить с расположением по сложности. К примеру в div1-раундах В иногда сложнее D. Но немного более правильное "зачем над ней думать, посмотрите, как хорошо ее сдают" — уже вполне подходит.
Это весьма полезный подход. Который популярный в АСМ-контестах "смотрите, даже вон те ребята сдали ее, значит, там заходит брут".
У меня было "её хорошо сдают, но как?!?". Придумав, как с оригинальным условием получить 2 (а не 3) на тесте
сложно это "развидеть".
Poor English translation in this round.
http://codeforces.net/contest/400/submission/5935405 I think it strange,for I compiled the program with my native compiler "GNU GCC Compiler 4.8.2", which seemed to be correct(there is "1x12").However on the onlinejudge, it failed with the same compiler at a lower version.Why is there such a difference?
something stranger:http://codeforces.net/contest/400/submission/5947329 I changed the compiler to MS C++ 2010,while the answer seems to be correct.But there is a runtime error after the output of the answer.I checked it out and found it was because of the wrong exit code.
I also faced a similar kind of problem with this code, on ideone it is showing runtime error and on codeforces WA while it is working fine on my laptop: http://ideone.com/V6GaTw
Do you have a clue of that?
Here: char t[12]; cin >> t; 13 symbols are getting read into t (12 letters plus a zero as the end of line). Change to t[13] and it will get accepted.
Thank you!I did forget the end of string token, and it get accepted now.
In
char t[12], you have to leave space also for the terminating null character. See 5948774.Мне кажется или у многих кто решил Dшку решение повалилось на 53 тесте)
Примерно у 90 из 230 D-шка упала на системном тестировании.
Hi everyone, can anyone explain me why the output of the following input is 9?
10 10 G********S G******S G****S G**S ****G****S *****G***S ******G**S *******G*S ********GS G********S
Because according with the problem you need the number of steps to solve the problem
Step 1: Say Let's go and end when row 8 arrive the candy cell.
Step 2: Say Let's go and end when row 7 arrive the candy cell.
Step 3: Say Let's go and end when row 6 arrive the candy cell.
Step 4: Say Let's go and end when row 5 arrive the candy cell.
Step 5: Say Let's go and end when row 4 arrive the candy cell.
Step 6: Say Let's go and end when row 3 arrive the candy cell.
Step 7: Say Let's go and end when row 2 arrive the candy cell.
Step 8: Say Let's go and end when row 1 and row 9 arrive the candy cell.
So, it is giving me 8 for best answer, what I am missing?
Thanks in advances J
At the very least, there are 10 rows, and you mention only 9.
In step8 row1 and row9 arrive the candy cell, row8 it is not counting because S and G are in the same cell
Still only rows 1–9 in your explanation...
There are 9 rows with numbers from 1 to 9, inclusive.
There are 10 rows in the input, according to the first line.
Sorry the row is missing is the one with the S and G in the same cell,
*In step8 row1 and row10 arrive the candy cell, row9 it is not counting because S and G are in the same cell
Initially, S and G can not be on the same cell.
Otherwise, what is the one single character you read from standard input for that cell?
if that can't happen how you understand row 9:
********GS
?
I though that means they are in the same cell, this is the test3
Quoting the problem statement:
The field for the new game is a rectangle table of size n × m.
...
Next n lines each contain m characters — the game field for the "Candy Martix 2: Reload". Character "*" represents an empty cell of the field, character "G" represents a dwarf and character "S" represents a candy.
Each character in the input corresponds to exactly one cell. So, the string "SG" represents two adjacent cells.
Ohhh, ok now I got it!! Thank you very much!!
"can choose all lines of the matrix where dwarf is not on the cell with candy", it is just 'can', not necessary 'must'. And actually, problem means 'must choose all lines'. This is another point that problem didn't describe clearly.
What's the meaning of "judgement failed" ? I tried to submit a solution of problem C (for practice) but the verdict is like that :
submission
If you go to the ProblemSet Status, you'll see many submissions with verdict "Judgement failed".
technical problem ?
Та же problem,
I am not sure, but last time I got that was because I used a huge array. Here you are using a vector of size 10^5 * 2 so I guess it should be fine.
It seems that there is a technical problem in Codeforces , all recent submissions are getting "judgement failed", check this page
У кого-то codeforces принимает задачи, просто у меня на всех пишет ошибка тестирования
When I register for practice, my submission's verdict is Judgement failed. What was happened?
Just try submit again. It's only temporary
In fact ,I think the problems in this round is very good.But some problem's description is too long too difficult for some Chinese senior high school students,it cost me and my friends a lot of time to understand the meaning of the problems(We not very good at English). So I prefer more problems with simpler description. Thanks.
Up for next Round (#234) !
Can anyone explain me in short steps their solution to problem E? Thanks :)
any editorial? :D
Editorial
Please give the problem E solution