Дамы и господа!
23 июня в 19:35 по московскому времени состоится очередной раунд на Codeforces для участников обоих дивизионов. Мы в течение долгого времени подбирали и решали задачи и надеемся, что они окажутся достаточно интересными.
Задачи под предводительством руководителя нашего кружка по информатике Endagorion (Михаила Тихомирова) готовили выпускники этого года разных московских школ — cdkrot (Дмитрий Саютин), ch_egor (Егор Чунаев), themikemikovi4 (Михаил Сорокин) и я. Для нас это уже второй раунд на Codeforces с задачами для обоих дивизионов.
Хотелось бы поблагодарить координатора GlebsHP (Глеба Евстропова) за помощь в подготовке задач и MikeMirzayanov (Михаила Мирзаянова) за чудесные системы Polygon и Codeforces. Кроме того, без помощи Endagorion (Михаила Тихомирова) у нас бы ничего не получилось.
Участникам каждого из дивизионов будет предложено по 5 задач. Наборы задач будут пересекаться, но не совпадать. Разбалловка будет опубликована позже.
Удачи всем на раунде!
UPD: Все условия написаны по сказке Х. К. Андерсена "Снежная королева".
UPD2: Разбалловка:
Div. 1: 500-1250-1250-2000-2250
Div. 2: 500-1000-1500-2250-2250
UPD3: Поздравляем победителей!
Div. 1:
Div. 2:
UPD4:
После проведения проверки на списывание возможны небольшие флуктуации рейтинга.
UPD5:
Разбор выложен здесь.
Before 3 days , that's too early !
thanks at all
Road to 1720+
Road to 1800+
EZ PZ +1720
HI EVERYBODY!!!!!!!!!! try pressing the the Caps Lock key O THANKS!!! ITS SO MUCH EASIER TO WRITE NOW!!!!!!! fak me
What's your meaning?
Feel like you are drunk.
No, it is a joke.Just the high rating can understand it.
Okay then. Wish I will understand it someday.
ROAD TO FUCKING +1720
don't think you can fuck a number
I see you are humorist.
This will be my first Div1 contest! Hope I don't do anything silly!
It's strange, I also hope I don't do anything silly, but it's not my first div 1 round :-? wonderful! isn't it?!
Your commitment counts more than your performance. Looking at your history you definitely have commitment and I have the utmost respect for that!
My rating has been dropping since forever. Hope i do not do anything stupid and finally increase my rating. :)
and your contribution.
EDIT: ignore my reply, I mistook the post for something else, not a big deal
This glitch has been around for as long as I can remember, hope it gets a quick fix
Which glitch are you talking about? If I am not mistaken, I don't see any glitch there.
Sorry my bad, I thought the entries were doubled
Its just the right time, the contest is just being held on the day without Euro
Lucky you :D , it's the contrary here, the timing couldn't be worse for any rated round as I have to do stuff in the middle having only 1.5 hours at best :(
Your last round was a round for hackers, not for coders, I hope we won't see the same tomorrow...
Actually, last time we just didn't put the overflow test in Div2A pretests.
Of course, in some problems we will exclude some special cases from pretests. The process of dividing tests on pretests and system tests has many functions that are not related to the testing speed. For example, some people may learn to test their code after they get hacked.
And of course, we try to make the round interesting to solve. We didn't expect to have so much hacks on integer overflow. Hope this particular mistake is an exception rather then the rule.
So as you wish, this round there were no hacks (at least in Div.1)
And also in Div.2 :V
Надеюсь, без геомы в этот раз :)
Интересно какие они условия взяли с сказки.
Наверное они просто "накинули" сказку на свои задачи, потому-что сказки в условиях редко бывают (я лично не встречал ни разу), либо условия прекрасно под неё отлично "ложились" .
Вот топовая сказка от Shlakoblock: http://mirror.codeforces.com/gym/100812.
Текст сказки знать обязательно? :)
Нет, не обязательно.
просто ничего не выйдет решить:)
Палю задачу, парни! Даны буквы, надо определить, можно ли из них составить слово "eternity".
This is one of the reasons that make codeforces a special site.. Its attractive way of announcements. Thanks platypus179
it's summer and the contest labeled with " The Snow Queen " , Nice name in wrong time
I`m quite sure that Snow Queen will ask us for a help because of such a nice(not for her) weather.
It's summer only in the Northern Hemisphere.
platypus179 Said, "the round is possible only because of Endagorion's help ". And I love Endagorion's Problems.
What's up with so many downvotes on simple good luck wishes or hopeful comments? :O
because these comments are common and annoying.
The only time I've got rating rise is when I'm in a foul or depressed mood. This isn't good I'm afraid
How can a contest be based on a fairy tail? Can anyone explain? Thank u.
Something like that: http://mirror.codeforces.com/blog/entry/13247.
I wish the time of the contest will be any time instead of breakfast time for muslims people in ramadan :/ , there is many contest in this time , can any one who will create a new contest can make it any time but not in our breakfast time ?, i think there is many Programmers will join it
time comfortable for you maybe uncomfortable for someone else
i think so :/ , but i need to change my rating :"(
Happy Ramadan
Thanks :) !
I wanted to write something insulting here about muslims misconceptions, but didnt find proper words.
It's so sad. I have two exams after tomorrow and the time of the contest is too late for me. So I can't take part in this contest.I really want to be a div.1 player.
It's so sad that I have two exams after tomorrow. But I can't help but give up this contest because the time of the contest is too late for me to have a good sleep. I really want to be a Div.1 player.
So sad.
Who can tell me what the picture means?
The Snow Queen shows a young boy how it is to participate in a Div1 contest.
Seriously, what explanation do you expect? If you're interested in the story then google "Andersen Snow Queen".
Thank you
This has a complete explanantion of the story and of the picture. Here is what it says about the picture: "The following winter, Kay goes out with his sled to play in the snowy market square and — as was the custom — hitches it to a curious white sleigh carriage, driven by the Snow Queen, who appears as a woman in a white fur-coat. Outside the city she reveals herself to Kay and kisses him twice: once to numb him from the cold, and a second time to make him forget about Gerda and his family; a third kiss would kill him. She takes Kay in her sleigh to her palace."
Good luck to all !
The scoring distribution will be announced later？
You have to form the word "eternity" from pieces of ice to know the score distribution
The score distribution shows D and E have same points...this one is going to be a tricky contest :D
мне кажется в задаче С Див 2 условие задачи немножко неправильно там написано на запись числа 0 требуется 1 разряд, а на самом деле на запись цифры 0 требуется 1 разряд
исправьте если я не прав
Разве не одно и тоже?
P.S. Первые две задачи очень лёгкие, но на С присел, чую можно простым перебором за 2 секунды с ограничением на разряд сделать, но не вижу как.
Если суммарно больше 7 цифр, то ответ 0, т.к. все не могут быть разными по принципу Дирихле. Иначе перебираем втупую и проверяем, перебор — 7^7 операций, выходит довольно быстро.
Максимальная длина числа не может быть больше 7 разрядов (так как цифры обязательно будут повторяться): 65432107
По этому критерию мы уже отфильтровываем числа n > 82354310 = 77
Зная максимальное число цифр (допустим оно равно 7), мы можем определить минимальное число, начиная с которого нам стоит проверять числа. Если максимальное число содержит 7 разрядов 65432107, то минимальное число, с которого нам нужно проверять — это 00123457.
Summary of my participation:
-Solves A relatively fast-
-Solves B relatively fast-
"Hey, C is as hard as B so that shouldn't take long."
-Proceed to dwell for an hour and a half without any results-
I god damn hope C has some very magical and easy observation that leads to an elegant solution, cause else that scoring was atrocious :D
How to solve your B?
Don't know if you meant the division 1 B, but for Div2 I brute forced it, manually swapping two elements at a time when necessary and after every swap checking if it's sorted.
I don't say div.2 B!
Yeah, you can simply check all pairs if sum of number of digits in the first one and the second one is <= 7, there are not many of those pairs I assume :D
He's talking about Div.1 C I believe.
I don't think he is talking about div2 C :P
Oops, I forgot that there was a Div1, not used to it, sorry!
In C I moved to 4-dimensional space: (x, y, z) - > (x + y + z, x + y - z, x - y + z, x - y - z) and used binary search in which I just intersected 4-dimensional cubes. But it's not enough to check that the intersection is not empty, you should also check that it has nonempty preimage.
I used the same approach but failed. It might be easier if the distance was asked instead of the actual point :(
I can't understand, can you elaborate please? How does 4 dimension help? Also, can anyone suggest some problems which can be solved in similar way?
In Manhattan metric sphere is octahedron. Mentioned transform maps it to hypercube. Intersecting hypercubes is done coordinate-wise. After that we need to check that intersection has nonempty preimage. If
a = x + y + z,
b = x + y - z,
c = x - y + z,
d = x - y - z,
then
x = (a + d) / 2 = (b + c) / 2,
y = (a - c) / 2 = (b - d) / 2,
z = (a - b) / 2 = (c - d) / 2.
So the image of
contains all integer points in hyperplane a - b - c + d = 0 with a ≡ b ≡ c ≡ d(mod 2). So we need to intersect that hyperplane with our cube and check some cases.
There was similar problem on IOI 2007(link, problem "pairs").
Don't worry, it could have been much worse :D
-Solves A relatively fast-
-Solves B relatively fast-
-Codes C relatively fast-
Then try to debug WA for 1 hour. The only mistake in the code? I was checking if the number was odd by doing "number % 2 == 1".
What is wrong with that check?
-1 % 2 is -1, not 1 :(
Ok, I've forgotten about negative numbers.
Yeah, this test was put in statement by exactly same reason.
Solving B after 50 minutes seems relatively slow for you :p
Do DIV 2 4th has a solution with binary search and dfs at each node?
Yes, it can be done with binary search. First , we need to decompose the tree into chains using a dfs, by moving from a node to its largest sized sub-tree . Centroid of the subtree of node v, will lie somewhere on the chain consisting of v,below v.
Now independently solve each chain. Suppose our chain has size x and we want to find the centroid for ith node in this chain , say chain[i].
Now the centroid of chain[i] will be the first node chain[j] , i < = j < = x , such that maxChildSubtreesize[j] < = Subtreesize[i] / 2 . Also , maxChildSubtreesize[j] is a decreasing function since we are moving down the tree. So, we can apply binary search with lower bound as i and upper bound as x.
Overall Complexity :O(nlogn)
Code
Was O(log3(1018)) enough in C? I implemented O(log(1018)) but damn, that wasn't easy.
What's your solution?
I implemented binary search to get 4 inequalities A<=x +/- y +/- z<=B (assuming that 3d solution should be similar to 2d vesrion) and then realized that I have no idea how to actually find some integer solution (x,y,z) from these inequalities, or at least how to check that there exists one :)
Ternary search on one coordinate z. For fixed z I have four inequalities and I claim that the value of answer is maximum of distances between parallel inequalities. This allows to find optimal z but not to find optimal x, y then.
Maybe I should then ternary search the next coordinate but I think it's hard to implement. So instead for the found four inequalities I imagines drawing four lines, then I found two intersections (an intersection of leftup and leftdown lines, and an intersection of rightup and rightdown lines) and then the answer should be in the middle of segment connecting the two intersections. I didn't know if I can round the answer (found x, y) to closest integers so I checked brutally all 22 possibilities of rounding.
Is this correct for 2D version ?
and you can get answerX and answerY from this
I used same solution for 3D (4 coordinates for each point) , but got WA 6
It is a bit more complicated. You have constrains on x + y + z, -x + y + z, x — y + z, x + y — z.
The problem is about solving them
Same, I got WA4. I'm 99% sure it's correct for the 2D case, and some version of this idea really ought to work for the 3D one.
One mistake which I couldn't fix in time: Adding 3 coordinates (or even 6 when taking average by (min+max)/2) can get you an overflow! Did you avoid that?
after WA#5 I checked x-3..x+3 y-3..y+3 z-3..z+3 , and it helped for test #5 :D
It really is the same, you can consider: x + y + z, x + y — z, x — y + z and y + z — x. Transforming a point in such a tuple, it becames similar to 2D version(the rotation in 2D) and binary searching is enough. The very very stupid thing is that you really have to take care of overflow and of some parities as well and it's pretty ugly. The problem would have been much nicer if they fixed the limita 10^17 and the problem had a higher score. I didn't even had time to think at the other tasks and still have to write some more lines...I guess that in k-D plane, you have 2 ^ (D — 1) elements in tuples. I really liked that the rotation can be generalizate but the overflow really destroy the task
I thought about overflow, but I don't think I can get any number out of range {-6*10^18 .. 6*10^18 }
Ohh never mind, thought the long long limit was around 2*10^18. No idea what my mistake was, in this case...
Try this test: 1 3 10 10 10 10 9 10 10 10 9 This is a test where, in my source, at least, I had to take care at parity. I think I solved it now but I am unable to submit because it seems that they didn't enable the practice session yet
That is a counterexample indeed, thanks!
Could you explain how you got overflow?
Proposed solution fits in long long quite well.
Well I didn't but theoretically some lines could get overflow so I thought a lot about how to improve them. For example, as in editorial, let's fix L the maximum distance, we had relations like maxA — L <= a <= minA + L and so on and we had one more for their sum maxS — L <= a + b + c <= minS + L. We had to intersect the intervals [maxS — L, minS + L] with [maxA + maxB + maxC — 3 * L, minA + minB + minC + 3 * L]. The ends of the later are very big in worst case...I hardly came up with a solution to treat those overflows.
Ouch, i see now. I should have set 1017 bound.
My solution got over this trouble because of parity handling, when replacing a = 2a' + r, not only parity restriction goes away, but coordinates also become twice less.
Yeah, I made the same mistake once in one of my problems — 611G - New Year and Cake.
We realized about possible problems with overflow in the day of the contest and I didn't have time to decrease constraints from 109 to 108. In hurry I added two tests designed to cause overflow (because if such malicious tests are valid then a setter should add them) and I put one of them in pretests. One participant had a bad luck and his solution passed pretests but didn't pass the other overflow-test and thus got WA on systests. Fortunately, he won anyway.
One thing is that I should have set 108 in the first place. But since there was no time, I should have include both malicious tests in pretests. I learnt a lesson that day.
Let x+y+z=C, x-y+z=D, x-y-z=E, x+y-z=F.
There is integral solution to system if and only if C,D,E,F all have the same parity and C-D+E = F.
What I did was, for each possible parity, take C,D,E to be the smallest possible and calculate value of C-D+E. Then try to make it fit into range of F inequalities by increasing C/E (if C-D+E is too small) or increasing D (if C-D+E is too big).
Turns out that bruteforcing a 3x3 cube around the non-integer solution works. No need to do any parity fiddling.
18693710
Seems this was the worst difficulty estimation I made this year :)
But problems were nice and there were no issues. #smallmiracles
And I liked the fact that pretests were strong.
True. No hacks in Div1, only 5 hacks in Div2
No, it wasn't. O(log) is proposed solution.
Div2-C дайте пожалуйста 11 претест.
Одно или оба числа — степень 7, например 7 7
Выдает 0 для степеней 7.
к сожалению, нет) можно, например 0:1
часы перебираются [0..6], с минутами аналогично.
Дай пять. Я на нем же запоролся.
The problem C sucks. Don't know what the statement want to say. My poor English. :(
I loved the contest — the tasks were challenging but I hope I did 4 tasks correctly, we'll see :)
Желаю человеку, поставившему в задаче C координаты до 1018 при том, что на кфе нет __int128, гореть в аду.
Всем привет.
Авторское решение влазит в long long.
Моё тоже, после некоторых костылей.
Мне костыли не потребовались. Подождите, скоро будет разбор.
Unexpected typing contest :P I thought Div1D was relatively easy than Div1C, and wanted to submit it T.T
Testcase 11 div2 C :|
same here
Did you take log(n) or log(n — 1) ?
I also stuck at that testcase
but after change (hourlength+minutelength > 6) to ( > 7)
it passed.
i was also stuck on that tc, implemented a recursive descent solution, testing out all possible combinations of different numbers. then i realised that i need to make room for 0 to n-1, instead of 0 to n so i think the tc is something like: 343 2401, where my program would output 0, while there is a solution :(
just had to do a n--,m--; at the start done the same mistake :(
Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)
LOL same xD
Don't remind me :"( That pretest 11, I really wonder what it is.
How to solve E ? I have a O(n m) solution that runs in 1450ms on a random test of maximum size, how to do better ?
What is 11 pretest in Div2C?
try this one:
7 7
the answer is 42
Answer?
Shouldn't it be 0? Any single digit hour will have leading zero and so the single digit minute too? 01:02. Then 0 is duplicated (?)
You need only one digit for hours and one digit for minutes.
not 01:02 but 1:2
No, the watch will only have 1 digit because 1 digit is sufficient to represent 0-6. (6 = n — 1 = 7 — 1)
Oh shit, forgot than numbers are in range 0, n — 1 and 0, m — 1.
same here. forgot to n--;m--;
Answer to the Ultimate Question of Life, the Universe, and Everything...
Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)
Div1 B and C having same score doesn't even sound funny...
Problem B is classic. So many people know it. I remember have solved it! It's not fair!
How do you solve it? I've never seen finding centroid before...
My idea is tree dp. Here's a brief sketch of my idea :
Do standard subtree size dp. For each node, determine the maximum subtree size of its children. Then, we calculate the answer for each node which is closest to the root. (actually I think I implemented something slightly different in my solution) We consider whether the node itself is actually a centroid and also which nodes to take from the childrens. This sketch is not very detailed but this is briefly what I did.
UPD : It got Accepted! Basically, I stored a "jump pointer" on each node, which is initially the answer for that node (after we finish dfsing the node). Then, when we process the parent, this "jump pointer" jumps depending whether jumping to the parent will yield a better centroid (better centroid means maximum subtree size is lesser, with ties broken using distance from root). Using this, for each child of a node that we're currently processing, if the node itself is a centroid, we take the node. Otherwise, we check the jump pointers in the childrens.
Code
Why closest to the root? And what's the time complexity?
It's ~3am here so I'm lazy to go over the details. Actually, it doesn't need to be closest to the root I think, it's something like this.
Time Complexity should be O(n) I think.
Brief basica idea:
It is enough to start with the centroid on the largest child and move up by parents until you find the centroid of the v. Amortized time os O(n).
Div1C: I found a possible overflow bug 10 sec before the end, couldn't submit in time... I REALLY hope that wasn't my only mistake and I didn't mess up by literally less than a minute :D
Why is the memory limit so tight in Div1-D? My solution went a few MB over. :(
We know solution with linear amount of memory.
The solution in the editorial uses O(nk) memory. I had two arrays of size n*k each, they require some 228 MB. 256 MB memory limit definitely seems too strict if you intended to allow O(nk) memory solutions to pass.
In task E (div. 2) we need to find min-size enclosing octahedron, but it turns out a little bit difficult...
My solution for D went stack-overflow on my computer but passed the pretest :v Guess it will fail the system test :v
Same happened with me. I wasted 25 minutes on this issue. Later I tested it through custom invocation and it worked.
Same with me. I resubmitted in panic, only to realise it wasn't necessary!
Too stuck on C.
Can someone give hint for DIV2 C ? Cheers =)
bruteforce , the max length of answer can be 7 as for answer more than 7 , atleast 1 digit will be repeated.
My bruteforce seems to give TLE on pretest 13. Plz look at this code: http://mirror.codeforces.com/contest/686/submission/18685502
dont use strings
Why do they take more time as compared to arrays?
I used strings and didn't get TLE
Though an overkill, you can use digit dp to solve it too O(log(N) * 210 * log(M)) which is O(logN * log(M)) (Not really :P ).18689097
I had to code both the solutions as digit dp didn't pass as I was missing returning 0 when the input was 0 in the base_7 function, so eventually writing this code so fast was of no use.
Somehow misread that m ≤ 1000 (instead of correct 200'000), invented a n3 / 32 solution, implemented it... and finally noticed that I'd misread the constraints.
***k.
Офигительное условие задачи С. На русском: "Обратите внимание, для записи числа 0 требуется один разряд". Окей, значит правильно не 000:23, а 0:23. Хорошо, понятно.
Почему во 2 тесте нет среди ответов (0:1)? Откроем английскую версию. "Note that to display number 0 section of the watches is required to have at least one place.", что переводится как для отображения ЧИСЛА 0 требуется КАК МИНИМУМ один разряд.
Что это за условие такое? Я до сих пор не понимаю, что значит эта строчка.
Имелось в виду "для цифры 0", видимо.
Вероятно, имелось в виду, что 0 записывается как "0", а не как пустая строка. Это важно в тестах, где n = 1 или m = 1.
Окей, читаем: "В-третьих, если значение часа или минуты умещается в меньшее число разрядов, чем есть в соответствующей части часов, то запись дополняется нулями слева."
Для записи числа "0" требуется 1 разряд, остальные разряды, согласно условию, дополняются нулями. В чем ваша проблема?
зачем вообще эта строчка? я тоже залажал на ней:)
Going through the stats:pretest ones: Div 2 Problem B was solved by 2700+ and Div 2 Problem C was solved by only 791 which suggests that C should be of more points as compared to B
Good thing it is I guess?
Python is really troublesome:
A: O(7^7) [7^7 is less than 1 million] run in >3s on custom invocation, need O(7!) [7 factorial] to pass pretest.
B: Fast I/O required, otherwise it will be TLE on pretest 3, (I'm not sure if it can pass systest even after using fast I/O)
So for this contest I spend most of my time optimizing slow pyhon solution.
From next contest, I'll use faster language, goodbye beautiful Python!
Hello div2:Dthis round is hard but interesting.
what is the solution of Div2E,Div1C ?
А в Div1B есть решение без сливаемых сетов? Я долго верил, что B не должна быть на них, пытался придумать решение без, плюнул и написал с ними.
У меня вообще нет сетов(( Оно не пройдет?((
Берем ответ из наибольшего поддерева и подымаем его, пока он не станет корректным.
Это работает за O(N), так как по каждой вершине подымется не более чем один ответ,
Ураааа, у меня то же самое
У меня такое решение.
Заведём функцию f(v) — номер самого толстого сына.
Предподсчитаем и сохраним f(v), f2(v), f4(v), f8(v), ... .
Дальше будем спускаться по этим значениям двоичным поиском в каждом запросе.
Двоичные подъёмы вниз. Нужно каждый раз идти в самого большого сына.
Написал дерево отрезков. Для поддерева вершины v находим вершину с минимальным размером её поддерева, но не меньше чем (size[v] - 1) / 2 (size[v] — размер поддерева). Вроде можно за
но я не умею, кодил 
Вроде нельзя за N log N, написал за N log^2 N тоже во время соревнования :)
А emaxx говорит, что вроде можно http://e-maxx.ru/algo/segment_tree там где про каскадирование
How to solve Div 2B?
Bubble sort is the easiest way — just swap two neighbours, and there will be no more than n*(n-1)/2 swaps (approx 5000) so it should pass every test.
You can just sort the animals with bubble sort, and just print all the swaps you do. Since bubble sort has complexity n^2 it is guaranteed to do no more than n^2 swaps. From the constraints of the problem, the maximum value for n is 100, so the bubble sort will do at most 10000 swaps (less than that really, but it doesn't matter). So you are always guaranteed to make less than 20000 swaps.
Submitted at the last minute with this for div1 E...
It should be "Yes"/"No" instead of "YES"/"NO"....
Isn't checker case-insensitive? I think it is by default. Are you sure you get correct answers on sample tests, besides case?
The checker is case-insensitive for a single yes-no. For a sequence of Yes\No wcmp is used, and it's not case-insensitive.
Can this be made case-insensitive? Such inconsistency is a bit confusing.
Testlib checkers' home is here. Perhaps one can combine
yesnoandfcmp/wcmp, and then propose a pull request to add it to the default checkers? Or just make a case-insensitivefcmp/wcmpversion.Nothing that I have against it, but I sometimes wonder why problem setters not have binary values as output (0/1) instead of ("YES/NO", "ALICE/BOB") etc.
Are you saying 0/1 is better than Alice/Bob? How? The former one needs explaining in the statement, the latter doesn't.
So would you have got AC if you hadn't made this mistake?
Fortunately, Nope. It got TLE with time complexity O(NM).
However, I still get AC with another O(NM) solution which has less constant.
Yeah, Div2C/Div1A had a really bad english problem statement. I managed to understand it, but it must have been hard for some contestants whose first language is not english.
The pretests were too strong. I didn't see any hack during the contest.
Yeah. But I have nothing to complain. I would have failed in two problems if they were weak. LOL
Можете проверить у меня задача А отправилось 2 раза? 18677724 и 18677705
Anyone stuck on pretest 4 in Div 2 C ? If passed some test cases please ...
check for n=1 or m=1 case
You may also want to check for n = 7^3 and m = 7^4, or 1 and 7^7
В Div1 за E обещали 2250, а в табличке 2500.
Why Div1E's Time limit were set too strict?
Maybe intended solution is O(N2 + M)
I don't think so. And I agree that it is too strict.
If it's really O(NM) it becomes very easy, strict, stupid problem
English is not my native language, for problem DIV2 D / DIV1 B what does "Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)." means?
Take a node in a tree. Remove it. You get some disconnected components (corresponding to the edges the node had). If none of these components contains more than half of the original tree, that node is a centroid.
If a tree has n nodes, then the centroid of that tree is a node such that when you remove that node (and its edges), the remaining graphs that are left from the tree all have at most n/2 nodes.
OMG!!! 2 weeks ago on a Xellos's SRM hard problem was like "count centroid for every subtree and do something easy". Today's problem B was "count centroid for every subtree". On that SRM I did that problem and took 4th place, so I simply copy-pasted my code and printed computed centroids, but I got TLE on 14th test. After few tries of optimizing constant I thought that there is probably something wrong with the idea and maybe I was just lucky on SRM, because maybe proof of time amortization was not right. I thought that one of authors saw my description in the discussion of that SRM, found a counterexample and thought it is a good idea to give that as a problem on CF. That would be perfectly cruel, right :P? However it turned out, that I got that incredibly idiotic piece of code
computing number of vertices outside guy's subtree when restricted to v's subtree, whereas it should have simply returned sz[v] — sz[guy] --__--. I'm such a moron xd. On SRM that code passed because input was given by a random number generator there. "Broom test" obviously makes my solution TLE here. However that code was written at ~4AM, maybe that could be forgiven xD.
Shit, looks like I have to start competing in SRM again (
Можете проверить у меня задача А отправилось 2 раза? 18677724 и 18677705
Wow, you're red and you can't handle broom test in tree problems.
I totally did the same thing during the roundOn Petrozavodsk camp there was a problem where many contestants had got AC even though broom test would have made almost all of them TLE :P.
What is broom test? I couldn't find what it means
In that case: parent[i] = min(i - 1, n / 2)
Wow, I've should understand from "broom" xd
It's not like we didn't have a problem in a rated contest in which the editorial solution used to TLE on broom test :P
Edit: I now see they changed the editorial to the official solution, which is correct :)
My E is still in queue :o
My E is still in queue :o
Edit: It is judged now.
Why does systest always get stuck on 100%?
I think that's to eliminate the cases of cheating.
that's called suspense
What I did for Div 2-D (Div 1-B) got Accepted, but it took 2 seconds and I'm having a hard time analyzing the time complexity.
I computed centroids bottom up. So for current node u, if it is a centroid of the subtree rooted at u, great, else set the current node to the centroid of the largest subtree of the current node. While the current node isn't the required centroid, go to either the centroid if its largest subtree, or to its parent depending on which direction the centroid should lie (using sizes).
I precomputed the largest subtree and the size of the subtree for each node in O(n) in advance.
Can someone estimate the time complexity of this solution? Thanks a lot.
You're visiting every node at most 2 times. First time when computing it's answer, second time when testing it for another node's answer. (Assuming that you're breaking the loop that goes up after finding the centroid). 2*n -> O(n)
Hi,
Sorry I didn't completely understand. Could you give me an intuitive reason why a node will only be tested once for another node's answer?
I did the same, it's O(N), surprisingly.
Consider the paths formed by only taking the edges from each parent to its largest subtree child. These are the paths where you'll be "moving the centroids upwards", so to speak, so that part is O(number of edges) = O(N), and the rest are simple — e.g. finding the child with the largest subtree is also O(number of edges) = O(N).
Hi,
Sorry I didn't really understand why those particular edges (connecting a node to its largest subtree) will be the only ones where I'll move centroids upwards. Also, why would each such edge be used only once?
My explanation was pretty bad actually :D It's kind of hard to explain though. But I'll try again in more detail.
The centroid of a tree is always either its root or some node in its largest child subtree. If it's the latter, it's always the root of the subtree or in the largest "sub-subtree" of that subtree and so on. Therefore, when you want to calculate the centroid of a tree and you start "moving" the centroid of its largest subtree upwards, you're always following such "largest-subtree-edges", so to speak.
As for why they each occur only once: Imagine taking the leaf, then following these edges upwards, each time calculating the centroid of subtree rooted at your current position. Since you're following these "largest-subtree-edges", at each step, you're going to adjust the previous subtree's centroid by moving it upwards. And you never move it down.
So the only situation when you have to examine the possible movement of the centroid on the same edge multiple times is when you have chosen not to move it previously. But when you don't move the centroid, you finish calculating it for the current subtree, so there can be no more than N non-moving examinations. And each moving examination looks at a different edge, so there are also no more than N of those. All in all, it's O(N) checks!
Phew, that was hard to clear rigorously... Hope it helped somewhat.
Thanks a lot!
I understand why the complexity is O(N) now.
Is it right then, that my second check (searching for the centroid further down) was unnecessary as the centroid can only move up (after initially setting it to the centroid of the largest subtree)?
Indeed, you're right :)
Yes. You're adding more nodes to the subtree at its top, so the centroid is going to move upwards, intuitively. (Unless you add so many nodes to the top that the previous subtree is not even the largest, in which case you'd pick a different child of the new root and you're never going to visit this subtree again.)
I think there should be atleast one problem with weak pretests. Otherwise there is no meaning of keeping the hacking feature.
Why Div1-C's points are 1250???? I think this problem is very hard...
This is how people deal with C.
It looks perfect when there are no fakes in div2 top
I bet tourist will compete in next round!
Well Div2C is quite a tricky problem. You just have to decrement n and m then start solving, it is mentioned (numbers from 0 to n — 1/m — 1) And when converting a number to base 7 just make sure that you are considering the case of 0. I couldn't solve it in contest because of those two bugs.
Can somebody show me just one valid pair for div2C TC11: 16808 7 ?
I just can't understand how there are 720 valid pairs
012345:6
ohhh, I thought we should take 2 places for 7
but we need only 1 place for 7-1 = 6
congratulations for the first Arabic/Egyptian Grandmaster TsunamiNoLetGo
Thanks :)
Why do I get WA (=5040) for my submission 18687880 for test case 7 (problem C)
344 344whereas on my compiler and ideone I get the correct answer = 0.
Any help is appreciated.
log is at fault here.
fault where, at the CF server?
No, the
logfunction (and floating point computation in general) is only an approximation. They do their best to implement the closest answer, but they are not necessarily exact. For example, in your solution, you haveint(tmp), wheretmpis a double. This simply truncatestmp(it does not round it). So iftmp=24.999999.., it would simply be truncated to 24 instead of giving the exact answer of 25 as you would expect.The take home message is to not use floating point computations unless you actually need to. If you have to use them, you should always check that no significant errors have occurred. Here are some common functions that lots of people mess up on:
pow,sqrt,fabs,log.Can anyone help me debug this?
This solution got accepted http://mirror.codeforces.com/contest/686/submission/18688448 And this got Wrong Answer: http://mirror.codeforces.com/contest/686/submission/18688414
However, the only change I made was comparing the subtrees of the centroid pretender and the current node, at line 28. This shouldn't change the program's behaviour. I'm following this solution: http://mirror.codeforces.com/blog/entry/45556?#comment-301968
sub[cur] - sub[cen[cur]] > sub[cur]/2andsub[cen[cur]] < sub[cur]/2are not equal becausesub[cur]/2will round down. For example, lets saysub[cur]is 3 andsub[cen[cur]]is 1. 3 - 1 > 3 / 2 is true while 1 < 3 / 2 is false.Thanks, it works declaring sub and msub as double. Didn't think this would affect.
Hi,
Not sure, but I think that in the second submission, your condition sub[cen[cur]] < sub[cur]/2 should use a <= sign?
Actually not. If it compares equal, the candidate is necessarily a centroid, as there would be a subtree with n/2 nodes and another (or more than one) with n/2-1 nodes.
Is Petr going to cross tourist next time?????? Or tourist is gonna come back to defend the title???????????????? Keep watching on Codeforces!!!!!!!!!!! Yayyyyyyyyyyyyyyy :D
I think your keyboard may be broken. Some keys keep getting stuck.
э а где разбор
The "optimal point" problem only uses well known school topics.
You needed to know how to expand module inequalities:
|x - x1| ≤ A if and only if x1 - A ≤ x ≤ x1 + A.
And then notice the simple replacement of variables.
Very surprised about number of Ac's.
I don't think you can do anything with it in this problem. Did you get accepted?
He is author btw
But did he get accepted? :D
Unfortunately, this is not clear enough. And the fact that you don't have the editorial makes it look even worse.
The editorial is been prepared, please wait.
UPD. It is here: http://mirror.codeforces.com/blog/entry/45558
We don't have the editorial yet but we are working on this issue...
Measuring difficulty in terms of required knowledge is not a good idea. If you measure difficulty that way then why did you set E as E :)? Indeed this problem doesn't require sophisticated knowledge and I got a right idea pretty quickly, but got a hard time figuring out the details and carefully implementing it (at which I failed). And as already pointed out what you have said does not seem to be sufficient to describe main idea. However maybe there is some significantly easier solution than those I already know.
In Codeforces Round 359 (Div. 2) Problem 686B - Little Robber Girl's Zoo sample test cases Outputs were wrong. Correct me if i am wrong.
If it was wrong, how can 1000 users solve it?
If it was right then check outputs of 18671047 . I am talking about sample testcases. Take a look at written outputs in sample testcases of problem and outputs of the submission (which has been accepted) .
Test case output is correct.
This problem allows to have multiple correct solutions.
But it is not mentioned in English version.
<<Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.>> (C) statement.
Ohh My mistake. I wish i had read that during contest time.Thank you for pointing out cdkrot. I had already solved that using Bubble sort but, i thought it is wrong since it was not matching with sample test cases.
As Written on problem :
Output of 18671047
How can it become correct ?
Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.
It was not mentioned in the Problem statement that "any solution" that minimize the number of operations will be accepted.
Just scroll down to the notes section.
It would be nice if in some of these problems, you would provide a formal definition using mathematical symbols to avoid ambiguity.
"Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)."
That isn't correct English. I think "at least two times smaller" is the main problem :(
Editorial posted.