Всем привет!
snuke, EnumerativeCombinatorics и я приглашаем всех поучаствовать в Codeforces Round #263. Он состоится во вторник 26-го августа в 18:00 по московскому времени. Обратите внимание на необычное время старта раунда.
Спасибо Gerald за помощь в подготовке раунда, MikeMirzayanov за создание платформы для проведения соревнований, а Delinur за перевод условий.
В задачах нашего раунда вы будете помогать двум персонажам: Яблов (англ. Appleman) и Тостов (англ. Toastman). Удачи и удовольствия от решения задач на раунде!
UPD. В обоих дивизионах (Div.1 и Div.2) распределение баллов по задачам будет стандартным: 500-1000-1500-2000-2500.
Today is Saturday, the 23rd.
Contest is on Sunday, the 26th.
OK.
Oh, I missed fixing. Thanks.
And I was surprised by how fast you found this post :)
:)
Seriously, What kind of contest was that?!
Top 20 of Div2, had totally hacked 118 solutions. And so on for other contestants :|
Good Job ! It's time to fight in div1 .hope to up rating ^_^
A Div1 + Div2 round :)) It 's time for the "newly registered army" to take off their mask ^^
Www,long time no see div.1
Open your mouth!
Come On, Who dare who!
What happened ? calm down,please.
Just a joke :)
I think problems will be very hard and logical.
Thanks for your opinion, it means so much to me!
i hate to see this comment getting too much down votes!
Okay, let me translate how I understood it: "STFU NOBODY CARES ABOUT THAT!". Would you not downvote it?
what a coincidence!! i understood it as "STFU NOBODY CARES ABOUT THAT!" too! we have a lot of common man! you might up-voted it as i did it so.
Finally a round by animals (cat, wolf and squirrel, right?) from Japan!
Oh, god, the start time is 7:00 am in LA, it will be a tough round for me. :)
It's a chance to keep early hours for you ;)
Maybe one of them is a pony.
.
Tough round for red contestant, yes, sure...
Why there's still no upcoming contest now???
Wow, blog is earlier than upcoming contest list.
Wow. So early blog post
And I like the contest time which is a bit early than usual :D don't have to stay up to midnight :D
At least, names of heroes are easy to pronounce this time :D
Compared to other characters, they have a bit longer names, though ;)
OMG ..
In korea the time is 23:00.. and I'll be home at 12:30...
I can't participate this round :<
at last a DIV1 round after 2 contests :)
My first div1 round ever.. so.. lets hope for math!
According to your comments on CF i suppose that you love math very much:)
Appleman looks much better than official Apple logo. :)
Let's not hope for math, and for dp and graph theory [by the way kudos to SRM 630 writers].
Also, I knew that this will be a lucky contest for me right after I saw the apple. Apples are graphs >:D.
Let's also hope for clear problem statements! Sometimes I become confused reading them for the first time!
+long editorial :)
Good Luck.
Let's also hope short problem statement , short solutions :)
also Good Luck.
good time for contest :) hooooray !
Waiting for a great contest! Hope the problem easy to understand.
Continuous rating down......
If we fail pretests 2 times is the penalty = -(50*2) or (-50) ? Same question for failed hacks .
-50 for every failed pretest (not counting failed on pretest 1), but only if you eventually solve the problem. -50 for every failed hack. So that means two failed pretests are -100 and so as two failed hacks.
How much penalty for failing pretest 1 two times ?
Failing pretest 1 doesn't give any penalty (because the reason might be selecting the wrong file, among other things, that is just a minor error). So failing pretest 1 twice doesn't take any points either.
"selecting the wrong file". Happens with me most of the time.:/
IGNORED
look on the bright side — then u will be able to compete in Div-2 only contests. :)
All the best!. :D
Wow, long time no see Div1!Come on, let's enjoy it~ ^+^
Solo!
Come on!Who pa who!
Can I join in you, if you guys don't mind?
Wahaha,come on!Together if solve 0 problems then eat keyboard(or xiang?)!
The contest is a little early in the day than usual. Its coinciding with my mess timings for dinner! :(
as a BITSian who has participated in contests at such time, let me tell u this.
we both know that the mess food sucks. so
That is quite prudent. I agree.
Well I think I will most probably compete then ! :) No more excuses for not participating !
give yuo a plus please — http://mirror.codeforces.com/blog/entry/13439 !!!
P. S. not minus me !!!
Oh , I missed to be Candidate master with (4) rating last contest. I hope to raise to Div1 tomorrow :)
All the best!! :)
"May the Odds be in your favor!" :D
Hope for good problem, long time no see div.1. Good luck and have fun for everyone.
I hope you will not use fake account this contest
kuangbin kuangbin1 kuangbin2 kuangbin3 kuangbin4 kuangbin5 kuangbin6 kuangbin7 kuangbin8 kuangbin9 kuangbin10
we should register only one account. :)
kuangbin11 and kuangbin12 also!
probably they will become Candidate Master in the next two Div-2 only contests.
Bad new for kuangbin
kuangbin13 isn't emtpy anymore
Bad news for you, if you are the one who took the handle, they may ban you :)
Good news for me
He isnt me :D
HAHA, these are not my handle~~~
I've seen those accounts being posted around a few times already and it's clearly against the rules to make more than one account and compete, so can someone tell me why the hell isn't he banned?
we can't agree more !
Well it just quite angers me. I see blogs and comments non-stop complaining "there are so many fakes in Div2, why would they do this" and then when you see someone with 10 accounts, all of them with participations only until they reach Div1, which is obviously cheating, no one really cares. I thought people wanted to reduce fakes? I mean, as JuanMata showed, he has 2 more waiting for a Div2 round, doesn't seem like he will stop doing it.
ofcourse we want to reduce fakes!
but i don't agree with no one really cares — i mean, surely one of the reasons why muratt posted these two comments was so that admins could see them and ban those accounts.
as to why these accounts don't get banned — probably the admins want to prove without doubt that they are fakes before taking any action, lest they ban an innocent newly registered user (who will have no idea wtf just happened, and start disliking CF for wrong reasons)!
I get that you post this so the admins can see it, but my point was that this is not the first time someone posts names of obvious cheaters. Thing that frustrates me is that sometimes I see posts from months ago where someone reported a cheater, and when I check the cheater's account, it is perfectly unharmed!
Now I get the "prove without doubt" part, and I don't try to sound arrogant in some way since I'm not familiar with the things admins can do, but couldn't they simply check the IPs of the users? Surely that would still leave room for cheating as you can hide it or change it, but most of them will most likely use the same IP. Obviously if your cheating accounts have just another digit added to the end of their name, I doubt you'd go as far as hiding your IP.
I guess you could argue further that same IP is still not reliable (a brother, a friend from your computer) but in some cases such as the above one it's just kinda obvious that cheating is going on.
We care
Stierlitz still was never so close to a failure...
It is outraging to see this in Div. 1. Previously I thought such detestable things only occurred in Div. 2.
kuangbin have really ability.He always have good rank in my contry's match！this is a evidence(recent match)：http://www.bnuoj.com/v3/contest_show.php?cid=4340#standing maybe you misunderstand him! I have studied much knowledge from his blog. so I am very like him!
long time no taking div2:) Ok, let me do it tonight!
2 часа до раунда, а перевода на русский всё нет... косяк. Надеюсь, хоть задачи не забыли перевести.
"В задачах нашего раунда вы будете помогать двум персонажам: Яблов"
Наверное, зря я ругался, что нет русского перевода...
Главному герою тоже не нравится его фамилия, судя по картинке
What do you guys do before contest?
Live.
I have a question: Can I participate in div 2 contest? or just Div 1?
If your rating is >=1700 you can not participate in Div2 contests when a div1 contest is scheduled at the same time.
However if there is a solo div2 contest and the organizers allow , then you can participate in it, but that would be unrated for you.
If you can do all problems in both, why not.
Яблов? Эт что, гугл переводил?
Неа, гугл догадался не переводить имена собственные.
Wow! Amount of div1 participants is very close to amount of div2 participants. :D Amazing)
1329 registrants for Div1 and 3988 for Div2.
Yes you are right, very close :|
yep last digit of two numbers 8 & 9 is very close :D
How sir?
he didn't mention he is joking :D
When I wrote that comment, they were very close. Why --------?? You can't understand it without my hint? (Sorry for bad English :D)
Nope. You wrote that comment 15 minutes before the contest started. Are you implying 2500 users registered in 10 minutes? Because I won't believe that.
Toastman is him.
He appears in this problem.
Чем японский раунд отличается от китайского?
hello ~ why my B problem hack failed...
my generate program is
thx~
consider endlines
I think it's not good to publish a generator to B, which would break 50% of submissions, before the contest ends...
mine is broken too :(
The worst feeling in the world — when you lock your solution to problem B for in D2 and realize minutes after that you are not going to pass the system test cases...
At least I got some points back by hacking people in the rooms. How lucky some people are! With 15 hacks on the same problem, while I only got 7...
I made some stupid mistake at A and B, and it results in -100p for A and -50p for B =='
Problem D & E are hard for div2 ==' btw problem B is a nice problem for hacking...
Awful problem statements (were they in english !?) .
It doesn't matter how good your problems are if they are not readable .
it is pretty obvious when three geek red coders prepare some round. they don't speak english/japaneese/chineese or russian. they only speak c++ :p
English is pretty much of a prerequisite for coding, as most of textbooks available are in English language and not in Russian! And since they are geeks, which more or less means that they have read A LOT and know A LOT, they should now English to a sufficient level (maybe ECPE is too much, but ...)!
its not about knowing English sir, its about using right word at right place. its about explaining something, making something understandable to me. Except B all the problems were well written , i think. though it would be fine if the explanation of problem E would express test case one completely instead of just updates. but I think it was fair enough...
My suggestion would be to evolve at least one purple coder to test div2 problems.
totally agree.I submitted so late problems A and B because they were not clear. Wasted much time in understanding the problem statement.
Доминируй, властвуй, унижай!
:'( nah, hard problems, but I still love it :)), I love the way I can't solve this :'(
Мир жесток(
По Div2C — Div1A задаче встретил чувака, который писал такое:
У меня переполнение стека в Visual Studio вышло в n = 100 000, при ограничениях n <= 300 000. В "запуске" codeforces переполнение удалось получить только на n = 30 000 000
Hacking is really fun :D
Wow!
No simple for problem D,E Div2
Contest's ended. How to solve 462D - Appleman and Tree?
DP on states "there's 1 black vertex in subtreee of v left" and "there's 0 black vertices in subtree of v left"
Would you care to elaborate. If your solution is correct, please explain it.
I'm kind of lazy here, so:
if you want to think about how to solve the problem, this should be enough of a hint
if you don't, just wait for the editorial
Thanks anyway.
Dynamic on tree, save two value — how many ways to get black from component with root in current vertex and how many to get white from it. Then answer will d[0].black.
What do you mean by: "how many ways to get black"?
I've never seen so many hacks..that's amazing.
It's not that much, anyway (Codeforces Beta Round 60)
wow! just crazy, nothing to say :-)
I've never seen so few hacks (granted, I usually don't watch them, but div1 was as poor in that regard as div2 wasn't).
A lot of participants in room 58 were inactive, would have been even more interesting had more people taken the contest :P
Nice problems... :)
And nice round for
Hack Lovers... :DThe hack swarm had to happen :-P
No hacks this round. :)) Liked it though. I'm curious about A's proof, liked B and nearly finished C. Keep it up.
Div1 C, случайно, не декартовым деревом решается?
Я так извратился, например. Но можно намного проще: мы в каждый момент заворачиваем не левый конец, а тот, который короче. Тогда никаких реверсов не требуется, можно заворачивать "в лоб", только надо чуть аккуратнее разбираться со вводом.
C вообще по-моему получилась легче чем В. Для В надо извратное дп писать, а в С простое дерево отрезков
hack with OVERFLOW :)
C(div1) is a joke :D. Didn't have enough time to code it unfortunately. Great contest anyway.
Размышления по Е:
Оптимальная стратегия для Яблова такова: строка s построена оптимально тогда, когда использован максимальный суффикс, являющийся подстрокой t и её префикс без учёта этого суффикса также построен оптимально.
Отсюда вытекает такая контр-стратегия для Тостова — загадать строку так, чтобы на каждом её префиксе такой суффикс был минимальной длины. Как мне показалось, это можно сделать так — в суффиксном автомате посчитаем для каждого состояния дополнительные переходы next[i]. То есть, такие, что при переходе в них мы получим минимальную длину совпадения суффикса. Если у нас можно так перейти только по одной букве — то всё понятно. А если по нескольким, то нужно перейти по той, которая потом первой даст суффикс минимальной длины. Утверждается, что наша строка быстро станет периодичной с периодом в худшем случае не больше O(n), хотя и, наверное, с каким-то предпериодом и потом можно для неё посчитать ответ, как для периодичной.
Что вы думаете по этому поводу? Есть где-то логические несостыковки? Если нет, то как можно посчитать переходы быстро и правильно? Я за время контеста так и не справился с этой задачей :(
Я в конце пытался так. Во-первых, сделаем такой граф из суфф автомата:
Тогда в этом графе нам надо найти самый длинный путь из истока весом не более N. Это вроде можно сделать двоичным подъемом, не задумываясь о периодах.
UPD: А вот и АС в дорешку, не хватило буквально пяти минут на контесте: 7596132
Можно подробнее о том, что представляют собой переходы между буквами и почему это работает? А то из описания выходит, что *-А-В-С не менее хороший путь, чем *-А-С
Серым обозначены "важные" узлы, это те которые непосредственно доступны из корня при переходе по одной из четырех букв.
Размышляю так: если воспроизвести то, что делает игрок с получившейся строкой, то получится, что он будет ходить по этому автомату, периодически возвращаясь назад. Причем возвращаться он всегда будет в один из "важных" серых узлов, потому что он будет начинать искать новый суффикс. Ребра для возврата назад на рисунке не обозначены, но по смыслу они там должны быть везде, где нет настоящего перехода (т.е. эти переходы назад по сути заменяют суффиксные ссылки в автомате). Нам надо, чтобы игрок как можно больше раз вернулся назад, соответственно при фиксированном начальном и конечным сером узле нам желательно, чтобы этот путь был как можно короче. Минимальный путь у меня считается в функции calc(), нужные значения легко считаются по автомату.
Строим граф — оставляем только "важные" узлы и добавляем ребра с весом равным "расстоянию" в автомате. Веса этих ребер можно вывести в моем коде, если раскоменнтировать строчку в самом конце (строка 183, примерно 15-я снизу). Для этого примера получим что-то такое:
Например, переход А->В имеет вес 2, это означает, что если текущий рассмотриваемый суффикс состоит из одной буквы "А", то чтобы "сброситься" в суффиксном автомате до суффикса, равного "В", нужно использовать как минимум две буквы (после А). Для перехода А->В это будут буквы "BB". Если пройтись из серого узла А в автомате по этим двум буквам, то как раз после второго перехода "сброситесь" в В.
Дальше, как я уже, писал добавляем исток и ребра с единичными весами из него все имеющиеся вершины.
Ищем максимальный (по количеству ребер) путь с суммарным весом не более N из истока в любую вершину. Это и будет ответ.
Почему A div1 такая простая? Почему у человека решающего A div2 в среднем за 5 минут ушло 5 минут на A div1?
Взломы, просто взломы...)
UPD: извиняюсь, перепутал с div 2 B.
прост))
В зависимости от очевидности/шаблонности задачи
Сортировка массива и ответ a * mass[0] + (a+1) * mass[1] — слишком очевидно, чтобы думать над задачей полчаса
А то бывает и сложность как у D, и решальщиков столько же
В том то и дело, сложность задачи зависит от входных данных, ограничений, условия (вот я в MemSql B полчаса перечитывал, чтобы понять, что он меня хотят вообще), времени реализации, а самое главное — сложности идеи, которая должна прийти в голову.
Если бы эту задачу поменяли бы местами с А div2 — уверен, это ничего бы не изменило (разве что было бы тоже очень много взломов из-за переполнения), а еще лучше, если бы с B div2, которая вроде бы простая, но опять же, из-за переполнения было много, даже очень много, взломов.
Вон мы командой решали B div1, так она была элементарной, максимум тянула на A div1, но вообще B div2 по уровню. Но в ней было несколько частных случаев (а в этой задаче их нет), которые, плюс ко всему, намеренно не проверялись претестами. Задача была создана для взломов.
В общем, про(Яблов)ли сложность задач в этом контесте.
http://mirror.codeforces.com/contest/461/hacks Взломов по Div1 А капля, и все относятся к неправильным частным случаям. Ответ везде был представлен как по шаблону — типом long long. Был, правда, человек, который ответ находил рекурсией в n вызовов, только у меня на компьютере 100 000 (при n <= 300 000) вызовов уже делали Stack Overflow, а в "Запуске" хватало только 30 000 000 вызовов :)
Три года назад задачи легче были, и в первом дивизионе были все, кому не лень — http://mirror.codeforces.com/blog/entry/3064 Надо решать как можно ближе к сегодняшнему состоянию задачи
В B div2 все взломы ведь были основаны на переполнении? Я так думаю, что во втором дивизионе участники меньше обращают внимания на такие вещи, так что будь эта задача для них — то и упавших решений было бы больше. Зачастую участники, зная что вряд ли решат С, даже не читают её.
delete
I was at the blessing room. 19 successful hacks :D
Какое там, в теории один символ может стоить 2500 очков и часа потерянного времени
3000 (не забываем про гиперсложные задачи и динамическую разбалловку).
Please make the difficulty distribution of questions more uniform. for example 1-3 were submitted by about 1500 coders and count dropped to about 100 in 4th question.
BTW enjoyed the contest. Waiting for editorial
Is this the correct solution for Div 2 C? http://ideone.com/AhciAN
Edit: It's not.
In Div,1 contest, half of submissions are for problem A. It seems that no one fail system tests on A. I think it's a quite simple problem, therefore, the number of participants today is much more than other contests.
982 official users in div 1
Awesome!!
I don't think i've ever loved integer overflow so much :D
Am I right saying that in Div1D 4x4 corner determines all other cells, because rows and columns have to be periodical with period 4?
No, it's not true.
Thanks, I realized my mistake while ago. I had to mess something during the contest.
Very simple example:
What you can do is fix the first row and then there is exactly one way to fill the rest (it's obvious that there is not more than one, and you just believe that it's always possible after looking at small cases with brute force)
In fact, the first row determines all other cells. Moreover (I didn't prove that, but the brute-force showed that), it seems that each combination of white and black cells in the first row generates a correct board.
// Oops, too late answer :D
What do you mean by "each combination"? It has to be consistent with already filled cells.
So you can guess that he means "for an empty board".
Okay, I forgot to add that if there are no cells which are already set, then we can color the first row in any way we want and generate exactly one correct solution from it (as yeputons said).
This observation (as long as the very similar one: if we set 'O'=1, 'X'=0, then the value (mod 2) of each cell can be computed very easily from the values of the first row). Look at the example:
(the addition is mod 2, i.e. the same as xor). If we count the prefix sums of the same parity (that is: 0, a0, a0+a2, a0+a2+a4, a0+a2+a4+a6, ... and 0, a1, a1+a3, a1+a3+a5, ...), we are able to write all the constraints in the form
[one prefix sum] xor [another prefix sum] = (c=='o'). Number of such solution (and existence of them) can be computed/checked easily. Somehow I got WA, so maybe I'm not that right... :DYes. We take x = 0 and o = 1. If we put ui = A[1][i], then we can write explicit formulas for A[i][j] int terms of ui. Each formula is like u2s + u2s + 2 + ... + u2t or u2s + 1 + ... + u2t + 1. So we have system of equations in F2n. We can find the number K of independet equations using Find-Union, Polish guys knows that trick from KUGLARZ (potyczki 2014).
The answer is 2K or 0...
Lool, that is indeed a Kuglarz problem :D. Nice. So bad that I messed computations and came up with other formulas, Kuglarz was so nice it would be really fun to use that task in other problem. Btw, hi Maciek :).
Sorry, doubled post, CF was not responding xd.
Div1 — A was easy than usual and and Div1 — B was hard than usual.
Why i got WA 19 div2A ? code
You need to check the boundary conditions of the 2-d array. For example
if(x[i-1][j]=='o')should be changed toif(i>1&&x[i-1][j]=='o').Similarly for all boundaries.
Hope this helps.
but why ?
Congratulations : — Div 1 : YuukaKazami — Div 2 : yyt16384
Compare Div 2 A with Div 1 D and Div 2 B with Div 1 E
IGNORED
I still see unrated genius users in Top 10 Div2...
I misunderstood problem C's description... This point specifically: Each time Appleman gets a group consisting of a single number, he throws this group out.
What I understood was that if the group consisted of equal numbers, then he throws that group but it turns out this meant that a group is thrown away if group consists of a single number(Just as the sentence said...). Never thought of it that way until one of my friends explained.
Just wanted to mention it so that if someone did the same, he wouldn't be puzzled too much.
For the next time , look at the explanation of the test cases to avoid such mistakes :D
I did indeed but the explanation was working well with my assumption :D
how could so many people hack problem B(div.2) solutions? mine is also hacked as well, but i can't find my mistake. can anybody please tell me why this could happen? thanks :)
Integer Overflow :D
overflow occurred when you calculate bonus*bonus :(
ah as i expected, but the answer must be integer right? as the problem says : "print a single integer"
I don't think "integer" in the problem does not mean int type
i see, i will take that as a lesson for future contests :) thanks for helping me..
In your code variable bonus should be long long.
i see, thanks for the correction :)
you have taken bonus in int and that will overflow.Imagine test case like 100000 100000 DDDDDD.....(100000) times so 100000*100000 would overflow int range
How long does it usually take, after the contest, to recalculate the rating of each participant? This is my first time competing on Codeforces. I was on a train for the first half of the competition, and didn't realize that the points for each problem decrease over time :\
Depends. Sometimes a few minutes, sometimes a few hours.
I was just about to use Splay in problem C when I found interval flip operations are not really needed. ...
Anyway, the problems are nice.
yeputons, can you please explain how you solved 462D - Appleman and Tree?
Codeforces do not send any kind of notification for mentions in comments at all.
Algorithm: we have system of linear equations modulo 2 (each variable is one cell of the field), there are n2 equations from the statement, and k equations from the input.
Improvements and some ideas:
(L,R)lexicographically, it's easy to see that on each step of elimination all equations are still in the form 'xor of variables from L to R...', which is cool, because we don't have any problems with memoryYou have answered Div1D, however dude above had asked you about Div2D which is Div1B :)
Whoops. I'm sorry, didn't notice that, I saw 'D' and answered :)
however, your answer on Div1B would be appreciated :)
Done, hope that helps.
I am sorry, but I do not really get yours "I use the 'merge smaller to the larger and it'll be NlogN' trick here." Could you kindly clarify it? p.s. I spent come time looking into your code, but for me it looks like O(N2) :(
I think the thing that confuses you in my submission (7594572) is
by just inserting all elements of A to B. Here is the magic:
MagicSet. This structure is a set of some items with one addition: I can append one set to another. Obviously, I can add set A to set B inIf I do the job in
instead of just 
and I move elements instead of copying (i.e. each element can be in one set only at every moment — like in Disjoint Set Union), the whole thing works in 
(amortized). Analysis is very simple and similar to what is used for DSU: let's take a look at each element. When it's moved from one set to another, the 'holder' set's size is increased twice at the least. There cannot be more than 
of such operations for each element, therefore we have 
operations with sets and the whole thing takes 
time. I'd also like to notice that one of these logs is from amortized analysis and has very little impact on constant factor, i.e. this 
is rather fast.
Thanks for clarification! I like your solution even more because it is clear you invented it by your own.
btw, your trick works thanks to C++0x and its moving semantic, right? I mean this line: if (sz(this->data) > sz(b.data)) this->swap(b);
Well, it's pretty well-known trick. In the several past years I met it dozen times, starting with summer school training camp 2011 and IOI-2011 (problem 'race') which followed it. I've also met this on some Codeforces rounds for sure, on Petrozavodsk training camp...
No, move semantics is not used here. You know the
swapfunction from STL (likeswap(a, b)), and almost every STL structure has member function with the same name:a.swap(b), which does the same in constant time (for example, to swap two vectors you just need to swap two pairs of pointers, no need to copy the content). It was in C++03 for sure. Moreover,std::swapis overloaded for some STL structures to work without copying everything too. I personally prefer usinga.swap(b)in places where I definitely need constant time complexity, because I don't remember exactly whether or notstd::swapis overloaded.If you look in my code, you can see that I implemented this
swapmember function myself (usingset<>::swapinside)Could you kindly tell me a couple problems to solve? I think to really understand problem one has to solve a couple of similar ones.
Wrong problem, I'm sorry.
Well, it's very straightforward for me: if you have tree (especially rooted one) and have to select some subset of vertices/edges and minimize/maximize some function of the resulting partition, you're gonna have a tree DP.
Usually tree DP in partition problems looks like this: you've already partioned some sub-tree and are currently constructing a component to which a root of the subtree belongs. In this particular problem the only required property of a component is whether or not it contains one black vertex. It's the state of DP. Transition is another simple DP (please don't be scared by that): you start with one obvious way (depending on subtree's root's color) and then add children one-by-one. There are several possible ways of merging a child: it either has or not black vertex already, and you and also just cut an edge leading to the child.
You can look at my code (7583221) for details —
dfs()is doing the DP. I don't store results of DP anywhere — it's just passed as return value ofdfs().can you please explain how we can calculate the merging of childs , I mean if color of x is one , then we must cut all the edges to children right?cause If we add the edge then there will be an component with two black vertices. But , what are the calculations if x is white?
Learned a lot from your comment, thank you ! It would be great if you can provide some related problems which uses this method. (links to OJ problems would be appreciated)
IGNORED
Nice problem! D&E is really interesting to solve :).
I am so lucky to get E right at 1:58:) ...
Also It is my 7-th CF win!(For my darling sevenkplus :) )... Many years passed since I join CF, and the pleasure I get from it never decreased :).
Congratulations! <3
Congratulations! Wish to enjoy yourself with 7k+~!
Congratulations. Wonderful problems! Especially problem E. Although I have failed to discover the most important part :(
Professional!(which is a typical way of congratulating others or just greeting in Japanese geeks. In reply to this, one usually answers "Hobby")
how to know what was the test case used by another person to hack my solution in the contest?
you can't see it during the contest
You can't =(. But you can ask him/her directly =P
http://mirror.codeforces.com/blog/entry/13563 Please upvote if u agree :)
When will div 2 rating be updated ? Div 1 rating is already updated.
congrats :)
aah today I forgot to hack :)
Finally DIV1 ,Now I can RIP :D
What do you want to rip so much that you'd write it in caps? :D
RIP stands for "Rest In Peace" , I didn't want to rip anything Xellos :D :D
I hoped the :D at the end would make it clear that I know and it's a joke. Oh well.
yep I know you are joking and the same :D :D at the end of my sentence make it clear that I know you are joking and I make another joke replying to your joke :D
Me too =P
Congraaaaaats :)
after 111 contests, u have finally become Div-1.
maybe this means that ur lucky number is 1. :)
Yep you are right 1 is my lucky number also I have contribution 111 on my 111 contest :D :D
congratulation! :D
I try to say congratulations to you, from rating update, but there is a message issue :(
Thanks :)
You're welcome :)
Please can anyone give the proof for why the solution for div1 A / div2 C works ?
You can prove by induction.
Let's consider that for all arrays with sizes n' < n it is true that the next algorithm Alg is optimal:
1) Sort an array.
2) Divide an array from left to right, taking at each step first element.
Suppose we have an array a and it's size n. res = Alg(a). Let's sort it and divide by any index q. By induction we know that it's optimal to use Alg for these subarrays. But it's easy to see that the result sum ≤ res.
Why did I get WA even when I used long long for sum?? http://mirror.codeforces.com/contest/462/submission/7590781
sum+=(F[i]*F[i])*1LL;When F[i] = 100000 , (F[i]*F[i])*1LL = 1410065408 when you have declared F[] as an int array (I tried it on custom invocation)
Hence overflow !
What change will u suggest?
sum += F[i] * 1LL * F[i];
Either declare F as
long long F[SIZE]or elsedo
sum += ((long long)F[i]*F[i])Edit: Or you can do as in the above comment
Your approach still does not work ??
http://mirror.codeforces.com/contest/462/submission/7597974
You have written
(ll)(F[i]*F[i])but I suggested((ll)F[i]*F[i])Still not working ... plz help me out
http://mirror.codeforces.com/contest/462/submission/7598137
read my reply to your question bellow.
7597800
you should multiply 1LL by first operand in F[i]*F[i].
but it's easier to declare your variable 'long long' instead of 'int'.
How is Div2 E supposed to be solved?
What is the purpose of custom invocation ?
How can we lock our solution ? What is its advantage?
Custom invocation: in case you're too lazy to actually get a compiler/interpreter of your language of choice and want to test out codes with Codeforces platform.
Locking solution: You can now hack other solutions for possible points if you're correct.
This is my submission for : Div 2 C
It passed tests for similar sized inputs but failed on the 24th test case. I've used Python 2.7 to submit that. Isn't it unfair that I have been penalized just for using Python? My algorithm uses a priority queue and is O(nlogn)
Here is exactly the same algorithm used in Java 8. Submission in Java 8
I have used the SAME algorithm and it comfortably passed the tests.
Yes, when you see large input, don't rely on Python. You can blame the problem setters for having no better problem to put where every language can pass, or you can try learning a faster language. I decided to pass on this contest for the same reason.
Well there should be some sort of additional time for Python to process large inputs then. I lost out on a lot of points because of that. I think the organizers of the contest should look into it. Nevertheless, I think I will use Java from the next round. It's quite frustrating to lose out on points just because of a language choice!
I think there was a discussion about giving time limit multiplier (so Java has double time, Python has triple time, etc) long time ago, but it hasn't been pursued ever since.
That's sad! I will Java from now on.
You should C++ from now on.
I had a similar situation recently, but outside a contest. I had a simple integral and binsearching on it, written in Python. But it wasn't accurate enough (I needed to take differences of close values), so I needed to improve the precision by increasing the number of steps. But Python's slow and it would've ran for hours — so I didn't complain that the time limits are slow and instead rewrote the solution in C++, resulting in massive increase in precision (from "powerful random numbers' generator" to "sufficiently accurate") and decent time.
Programming is about improving runtime, not increasing time limits to fit your code.
Thanks for the advice!
Is Java also too slow for programming contests on Codeforces and other platforms? I already use Java well so learning C++ will require some additional effort. If it doesn't matter that much then I would rather use Java.
edit: yet again, doublepost
It probably is, I don't really know since I don't use it, I just heard what people said here. If you can use it well, then it's okay, but it still seems to have more speed-related fails compared to C++.
edit: quadruplepost due to CF not responding
edit: quadruplepost due to CF not responding
edit: quadruplepost due to CF not responding
:-) Hello
Some stats about hacks can be found here.
and here for Div. 1.
Офигеть имена — Яблов и Тостов. Почему нельзя было литературно перевести Яблочков и Тостиков?
Или перевести по-символьно: Эпллмэн, Тоастмэн. В конце концов Бэтмэна мы же не зовём Летомышов.
why my summission is skipped? Your text to link here...