Всем привет! :{
Мы очень рады пригласить Вас поучаствовать в очередном Codeforces Round #173, который был подготовлен A.K.Goharshady, LGM и мной (havaliza). Я хочу традиционно поблагодарить Gerald, MikeMirzayanov и Delinur за помощь в подготовке раунда. Также большое спасибо dani1373, hhoomn, mruxim, MMJ и xorfire. Они тестировали задачи и в целом очень сильно нам помогли.
Кстати, сегодня день рождения у LGM's, а вчера был у gpac's. Давайте поздравим с днем рождения этих ребят! ^.^
Я надеюсь вам понравится сегодняшний раунд, и вы получите от него много фана! :)
Happy Birthday!!!
ALL say HappyBirthday No one ask for score distribution :D
Hi. And tomorrow is my birthday. Hope to have a good contest to enjoy my birthday much more. :D
And Happy Birthday you guys. Glad to know it. Wish you bests in whole LIFE.
HF & GL!
I want to participate,but I'm too tired:(
Happy birthday to you guys(LGM,gpac,S.HASHEMI)!!! ^.^ and also Congratulations to havaliza,keivan,fab,dani1373 ,because of being selected for IOI team of IRAN for next year!!! hope you win 4 gold medals for IRAN!!!
Thanks a lot. :D Wish you bests.
Your prev contest was great! (at least for me!) I hope it will be like the prev! How is score distribution?
I was surprised a lot! thank you havaliza :)
Happy birthday gpac. Wish you get rank 1 today. :D
Happy Birthday to you too! I hope you have the best day of your life and have a professional contest. Let's go to infinity and beyond it!!!!
Taxiiiiiii.....
Infinity please.
Happy birthday to you guys:)I hope you also will get present from codeforces like me)I had birhtday in 25.02 and codeforces gave me +61:) http://mirror.codeforces.com/bestRatingChanges/213901:)
happy birthday boys <:-P And special thanks for preparing the contest :-)
A bunch of Problemsetters from IRAN :D
Happy Birthday
Happy Birthday guys :) god bless you !!
wow! More than 3000 registered users :D .
due to iranian setter :D
please tell us about score distribution ?
since it's no announcements about it, i think it's standard
Вот так наркомания...
Срочно задача С: тест два — там опечатка или нет?
А что там не так? Вроде всё верно. Строки могут иметь разную длину.
...d
Problem B: jury solution for test 3 1000 0 998 2 503 497
is "222". W T F???
0+2+497=499
499<=500
Oh, i found my mistake :(
Who solved D and how?
For n=1 the situation is clear. For n=2 (two non-zero integers) if a[0]=a[1], first player wins, elsewhere he loses. For n=3 (three non-zero numbers) there are (300^3)/6 possible situations (excluding permutations of those), and for each of them we can calculate if the first player wins or loses in O(1).
in testcase 2 1 5 your solution is wrong. because first player can make situation 1 2 which is bad for the second player and first will win
update a[0]=1 a[1]=5 2 is for n
2 2 3
I think you meant vice versa for case n=2. didn't you?
Fine, we can iterate through all (300^2)/2 situations as well.
Sorry. I was Wrong :|
if n=2 you are logically wrong
because if a[0]!=a[1] you said that second is winner but the first player can make a move that makes also a[0]!=a[1] then and become the second then he is winner , so how become both first and second winners?
e.g
let n=2 , a[0]=1 , a[1]=3
the first is the winner and the winning move is subtract 1 from a[1]
I know, mate. Just didn't think about it well.
Use dp[i][j][k] to stand for whether (i,j,k) is a state in which the first person will win. It can be easily proved that the number of (i,j,k) such that dp[i][j][k] is false is O(n^2). We can use dp[i][j][k]=false to update dp[i+t][j+t][k+t] dp[i+t][j][k] dp[i][j+t][k] dp[i][j][k+t]. And it takes O(n). So we can get an O(n^3) solution by this way.
May you please give further explanation about the O(N^2) bound on losing situations (i,j,k) ?
Because if (i,k,j) is false than (i',j,k) is true when i'>i, which means the number of tuples (i,j,k) that is false is O(1) for each pair (j,k).As there is O(n^2) such pair (j,k), it is obvious that the number of tuples (i,j,k) that is false is O(n^2).
My submission 3308449
How to solve E?
3306281 0_o
Well, I don't think, this solution will survive system tests :D
Does it work for the numbers (in binary):
1000 , 10 , 10 , 100, 1, 1100
You say it should find 1111 but I don't see how it can.
give 0 to right and give 6 to left it will be 0 ^ 1111 ? Edit:I got it.
Isn't <1,7,2,1> a counterexample for this solution?!!!
No, since it's permitted take <1,7> and <1> for 7 points.
<1,1,2,2,4,4,8,8,16,16> breaks it, though.
oh, your right. thanks.
It can be solved by greedy algorithm using trie.
but dude what isn't it possible to make 63 for this:
but judge says 62.I mean we can give 0 to right and 6 to the left .Than the pleasure will be 111111^0=63 ?
Edit: I got it.
I notice a code will get TLE so I make generation to this testcase
so what's wrong he till me Invalid Input
FAIL Input can't contain two or more consecutive spaces, but line 31 (1-based) contains [validator wfval.exe returns exit code 3]
Maybe, you should make "endl" after second "cout"?
but error say Input can't contain two or more consecutive spaces
Maybe you mistook "code generator" and "input" just like me last time.
It is really hard to solve problems in Java, and Petr is really great, because he uses Java and he is the fastest coder.
Come on mate , This should have been well thought before taking petr as prefix in your handle. Now you are expected to code in Java :P
Problem C was very interesting....a lot of people's solutions ( and also my solution!! ) has been hacked
I hacked 2 user with this testcase:
I also hacked with:
:D
I hacked about 9 users with :
0 0
Lol.
I found a hackable solution just before the contest was over. I guess C is the most trick one in this contest.
Very simple problem, but it has some pitfalls.
Why do you have this weird if statement in your code?
After some analysis you will know that one can construct every string(except a '0'-string that consists only of '0's), iff we have at least one '1' in our string.
Yes, I think i was very lucky that my solution has been hacked, because my algorithm has a lot of bugs and finally I found the answer!!
I hoped my soloution had been hacked too, then I could submit the correct one... Grammere jomlam dorost bud??
нет, ребята, так пить нельзя. Только решая Е вспомнил что такое на самом деле xor и переделал С) в результате сдал одну задачу через 3 минуты после начала и одну за 3 минуты до конца. Пора менять систему подготовки к раунду
I'm waiting system testing, for lunch!!! Please, hurry up... :D
Deleted.
И пусть этот момент длится вечно :D
XOR — фишка контестов на Codeforces:)
уже в печёнках эти ксоры...
Testcase for problem C is to much (about 100 test). Systest will run very low.
there are more than 100 test cases for D problem too
Where is sence to make so many tests for so easy task?..
Here: 3303326
It's bad example. If you know right solution — ( put "YES" only if '1' exists in both strings or doesnt exist in both ) you can make about 10-20 tests to check all the solutions. But not 100.
c1*r1 == 0 (mod 2^32), funny mistake!
Great Contest! I realy Liked problems D and E even though i didn't solve them
А возможно ли глянуть тест, на котором свалился?
да, после систетов на странице своего решения
После системных тестов.
После окончания проверки.
Today during the contest I got two messages from MIT_1996 who was in my room, asking for help in problem B with algorithm. Where should I report ??
i think you should forgive him and not report this.
You could have asked where to report a dishonesty without saying the name of the competitor in public chat. Is not a good practice to a shame people for such reasons in front of all.
thx! very nice contest:)
Появился вопрос. Отправил решение С. WA3.
3303367
Забыл дать начальное объявление переменным f, g. Задал. AC.
3304751
Вопрос: По какому принципу в с++ задается начальное значение переменным?
Вроде бы случайным образом.
То есть если не задать начальное значение, то на одном тесте можно получить несколько ответов?
Конечно, странно что с таким опытом соревнований, Вы еще этого не заметили о_о
Даже хуже: в Visual Studio ответ будет зависеть от режима компиляции -- Debug или Release. В Debug значение хоть и будет мусорным, но стабильно одним и тем же, что может создать иллюзию правильности работы программы, а в Release раз от раза разным. Соответственно, если контестер проверяет решение, скомпилировав его в Realease, то ответ в контестере и локально может быть разным. (Навеяно недавним опытом по поиску ошибки в решении одного из моих олимпиадников. Решение проходило все наши тесты, а на контестере ловило огромное количество WA. Помог анализ кода и соображалка -- дело оказалось в значениях по-умолчанию. См. выше.)
Да просто надо отучиваться от паскаля и объявлять переменные по мере необходимости, а не в начале программы.
Всё верно. Лично я так делаю давно и подобных ошибок не получаю. И постоянно на эту тему делаю замечания. Но что делать тем кто учится по дурацким учебникам C++ или кого так учат...
Да учитель ништяковый, просто обычно объявляю в глобальной, а там таких проблем нет.
Все глобальные переменные изначально инициализируются нулями(это верно для g++, про VS ничего не могу сказать). Если переменная локальная, то, вроде бы, радномно
Глобальные переменные обнуляются, локальные — нет.
Правильно ли я понял, что тут http://www.codeforces.ru/blog/entry/6954#comment-125915 человек выложил решение задачи E до конца контеста?
Но зачем?
Это загадка.
Кстати нашел некоторых, кто воспользовался этим. Интересно, как на это смотрит жюри? Ведь тот кто скопирвал не виноват, в том что просто увидел решение и решил проверить.
Те, кто скопировал, виноваты ровно на столько же, сколь и тот, кто заспойлил решение. Мы тут занимаемся спортивным программированием, а в спорте есть такое понятие — fairplay. Ну и совесть, конечно же.
That was a nice contest, thanks to havaliza and happy birthday to LGM and gpac...
I cant't exactly understand the meaning of problem E ! We are asked to find the maximum of what ? (BitHaval and BitAryo) what does 'and' mean here?
"The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness."
tnx
would u explain about test case 3 ?
2 1000 1000
The sausages can be empty, so give 1000 to BitHaval and nothing to BitAryo :D
tnx, sorry, one more please :D test 8: 4 1 2 4 12 the answer is 15, why?
for example, all to BitHaval: 4 xor 1 xor 2 xor 4 xor 12 = 15
I mean test 8, that is : n = 4 and the numbers are : 1 2 4 12
Oh, sorry. In this case, give 1,2 to BitHaval and 12 to BitAryo.
Oh! I got it now. :|
very good contest but I think test 26 from problem D should be in pretest , so many person got WA due to this test , thanks.
that was a nice contest thanks to havaliza but why Bitlandians are weird they are amazing
Thats funny. I solved my solution using Delphi compiler: http://mirror.codeforces.com/contest/282/submission/3302945 The same code, using FPC: http://mirror.codeforces.com/contest/282/submission/3311282
Thats not funny I think... :D exactly like the diffrence between visual studio compiler and GNU...
Something i have experienced while using CodeBlock for C++ and G++ compiler !!
.
Разница будет 0)
Почему так ?
Потому что яйцо будет стоить 0 у A.
When will the plus and minuses appear on the graph???
painting eggs is a very ancient and attractive custom in Iran and the children still do this
Very nice problems. Thanks to authors!
Люди, во многих решениях задачи D я для случая n=3 видел выражение a[0]^a[1]^a[2]. Выходит, в этом случае игра превращается в обычный ним. Но плиз, объясните, почему.
Черт, во время контеста разобрал случай для н=2. Надо было для 3х послать ним. Ждем разбора, чтоб узнать, почему это работает.
Например, это можно доказать вот так.
Достаточно показать, что из тройки с неулевым XOR-ом можно попасть в тройку с нулевым, а из тройки с нулевым нельзя попасть в другую тройку с нулевым. Очевидно, что это и есть требуемое.
Из тройки с ненулевым XOR-ом можно попасть в тройку с нулевым также, как в случае нима.
Из тройки с нулевым XOR-ом можно пойти или как в ниме, то есть в ненулевой XOR, либо из тройки a, b, c (a xor b xor c = 0) в тройку a — x, b — x, c — x (x > 0).
Предположим, что (a — x) xor (b — x) xor (c — x) = 0. Так как a xor b xor c = 0, то последние биты a, b, c либо две единицы и ноль, либо три нуля. Аналогично c (a — x), (b — x), (c — x). Отсюда легко понять, что последний бит x нулевой. Аналогично второй с конца бит x нулевой и так далее.
Да конечно контест был довольно интересен но будет ли рейтинг обновлен?
Happy birthday to all of you guys (gpac, LGM and S.HASHEMI)!!! and I hope that we get 4 Gold medals from havaliza, dani1373, fab and keivan!
The contest was very cool! Thank you for problems.
This is now 4 hours after contest but ratings had not changed yet... when does it want to change?? And I am right here in the site since the contest started... :D
Has anyone solved problem 'E' without a trie or with a easier solution to implement ?
I have no idea what this does, but it looks suspicious: http://www.codeforces.com/contest/282/submission/3303893
It seems to be the same ideia using trie. However, the code is a lot more clear and simply.
Well, what I did was following: I replaced the given array by an array, where
. BTW, The given array was a[1..n], I just added the 0th element to indicate we didn't give the first person anything to eat. Now imagine we gave the first person a piece [0..l] (it is equivalent to [1..l]) and the second — [r..n]. Then the tasty value of this is 
. We can replace the value r - 1 to m. Now we want to maximize 
. Notice two things: 1) l and m is the only variables since n is fixed, 2) 0 ≤ l ≤ m ≤ n. Then just sort the array s and then for any 0 ≤ m ≤ n use binary search for digits in the binary representation of 
to find l. Total complexity is 
.
My submission: 3304910
Thank you a lot ! For me this solution is much easier than author's :)
i think this my solution still wrong, but get accepted http://mirror.codeforces.com/contest/282/submission/3309655
because 'is' never change,
and did this solution true after i add is++? http://mirror.codeforces.com/contest/282/submission/3312416
Problem D was a nice DP problem. I calculated the losing scenarios offline and found a formula for it. Then just applied the formula and solve the problem in O(1). It was very fun. Problem E was a very nice problem too. I scratched my head for a little while to make it run in time, until I thought of building a trie, and I really like building tries :)
Thanks for really interesting problems! But what mean's verdict Skipped? My solve of problem C — XOR and OR received Accepted in final tests. I see Skipped and only two solved problems today.
hmm this is weird thing..happened to one once. let see if someone can explain it
I was actually shocked that problem B had a greedy solution to it. I was trying so hard to partition the numbers :P. But after end of competition when i saw some solutions which had got accepted i was surprised and confused. But then i came up with an inductive proof for the greedy method. Had fun. Will have to improve myself.
I thought about knapsack problem,but when i saw many accepted code I wrote greedy solution.Now i know why this solution is correct(with an inductive proof,as you say).
I love this contest.