525A — Виталий и пирожок
Для решения данной задачи будем использовать массив cnt[]. В нем будем хранить сколько ключей каждого типа мы уже нашли в комнатах, но пока не использовали, а ответ будем считать в переменной ans.
Проитерируемся по строке s. Если текущий элемент строки si строчная буква (ключ), увеличим cnt[si] на единицу. Если текущий элемент строки si прописная буква (дверь) возможны два случая. Если cnt[tolower(si)] > 0, тогда уменьшим cnt[tolower(si)] на единицу, иначе увеличим ans на единицу. Осталось вывести ответ.
Асимптотика решения — O(|s|), где |s| — длина строки s.
525B — Паша и строка
Сначала нужно понять следующий факт — неважно в каком порядке выполнять перевороты, ответ от этого не изменится.
Пусть элементы строки проиндексированы начиная с единицы. Для решения задачи посчитаем сколько переворотов будет начинаться в каждой из позиций строки. Потом насчитаем массив sum[]. В sum[i] будем хранить количество переворотов подстрок, которые начинаются в позициях, не превышающих i.
Теперь проитерируемся по i от 1 до n / 2 и, если sum[i] нечетно, поменяем местами элементы строки si и sn - i + 1. Выведем ответ — получившуюся строку s.
Асимптотика решения — O(n + m), где n — длина строки s, m — количество переворотов.
525C — Илья и палочки
Данная задача решается жадным образом. Насчитаем массив cnt[]. В cnt[i] будем хранить сколько у нас есть палочек длины i.
Теперь проитерируемся по длинам палочек (len) от максимальной длины до минимальной. Если cnt[len] нечетно и есть палочки длины len - 1 (то есть cnt[len - 1] > 0), сделаем cnt[len]-- и cnt[len - 1]++. Если же cnt[len] нечетно и палочек длины len - 1 нет (то есть cnt[len - 1] = 0), просто сделаем cnt[len]--. Таким образом, мы корректно сделали все нужные спиливания и гарантировали, что cnt[len] четные.
После этого вновь нужно пройти по длинам палочек аналогичным циклом и жадным образом объединять пары из 2 палочек одинаковых длин в четверки. Это и будут длины сторон ответных прямоугольников, осталось сложить их площади. В конце могут остаться две палочки без пары, их в ответе учитывать не нужно.
К примеру, если cnt[5] = 6, cnt[4] = 4, cnt[2] = 4, нужно объединить эти палочки в прямоугольники следующим образом — (5, 5, 5, 5), (5, 5, 4, 4), (4, 4, 2, 2). Две оставшиеся палочки длины 2 на ответ не влияют, так как их не с кем объединить.
Асимптотика решения — O(n + maxlen - minlen), где n — количество палочек, maxlen — максимальная длина палочки, minlen — минимальная длина палочки.
525D — Артур и стены
Для решения данной задачи нужно заметить следующий факт. Если в каком-то квадрате размера 2 × 2 в заданной матрице есть ровно одна звездочка, ее точно нужно заменить на точку. То есть если в матрице из точек и звездочек нет квадрата 2 × 2, в котором ровно одна звездочка (остальные точки), то все максимальные по размеру связные по стороне области из точек представляют собой прямоугольники.
Теперь решим задачу с помощью обхода в ширину. Пройдем по всем звездочкам матрицы, и, если есть квадрат 2 × 2, содержащий текущую звездочку, а остальные элементы этого квадрата точки, заменим эту звездочку на точку и положим эту позицию в очередь. Затем напишем стандартный обход в ширину, в котором будем заменять звездочки на точки во всех получающихся квадратах 2 × 2, в которых ровно одна звездочка.
Асимптотика решения — O(n * m), где n и m — размеры заданной матрицы.
525E — Аня и кубики
Для решения данной задачи воспользуемся методом meet - in - the - middle. Отсортируем заданный массив по возрастанию и разобьем пополам. В первой половине оставим первые n / 2 элементов, во второй все остальные.
Переберем все подмаски всех масок элементов из первой половины. То есть переберем какие кубики из первой половины мы возьмем и на какие из них наклеим восклицательные знаки. Таким образом мы переберем все возможные суммы, которые мы можем набрать с помощью кубиков из первой половины.
Пусть для текущей подмаски мы наберем сумму sumlf, используя tlf восклицательных знаков. Для хранения всех сумм используем ассоциативные массивы map < long long > cnt[k+1], где k — количество восклицательных знаков, которое у нас есть изначально. Тогда для текущей подмаски нужно сделать cnt[tlf][sumlf]++.
После этого, аналогичным образом, переберем все подмаски всех масок элементов из правой части. Пусть для текущей подмаски сумма равна sumrg, а количество использованных восклицательных знаков trg. Тогда в левой части нам нужно набрать сумму (s - sumrg), используя не более (k - trg) восклицательных знаков, где s — сумма, которую необходимо набрать по условию задачи. Тогда переберем сколько восклицательных знаков будем использовать в левой части (пусть это будем переменная cur) и прибавим к ответу cnt[cur][s - sumrg].
Для ускорения работы программы можно сначала проверить есть ли такой элемент в нашем массиве, то есть только если cnt[cur].count(s - sumrg) = true увеличивать ответ. Для перебираемых подмасок можно отсекать перебор по текущей сумме для подмаски и по количеству восклицательных знаков для текущей подмаски. Также понятно, что не имеет смысле наклеивать восклицательные знаки на кубики на которых написаны числа большие 18, так как 19! точно больше чем 1016, что по условию является верхним ограничением для s.
Асимптотика решения — O(3((n + 1) / 2) * log(maxcnt) * k), где n — количество кубиков, maxcnt — максимальный размер ассоциативного массива, k — количество восклицательных знаков.
This is fastest Editorial I've ever seen
Fastest editorial so far! Thanks!
your rounds are awesome :D won't miss any of them :3
Да, я неправ :(
What was test case 4 for problem C??
Now we can see it's 8 5 3 3 3 3 4 4 4. I got 3 WAs on test 4 because of misunderstanding the problem statement
i too misunderstood the problem statement :(
What's that? I don't see it... Where does the "25" come from?
It was the sum of all possible rectangles that could be made. Not the max of those.
I also got to know now ! :(
We can choose {5-1, 4, 4, 4} to make a rectangle and choose {3, 3, 3, 3} to make another one, and we get the maximum total area which is 16 + 9
me too！but I understand it finally
we convert 5 to 4 so we have 4, 4, 4, 4 -> 4 * 4 = 16 and we have 3, 3 , 3 ,3 — > 3 * 3 = 9 so total maximum area is 9 + 16 = 25 not 16 !
In problem C use long long Because the input and Output is large it can't covered by long
Thank you for nice problems:) BTW, for 530E, I think associative array cnt should be map < long long, int >
Подскажите, что нужно было делать в задаче D? Валится на 12 тесте, и потому даже нет возможности узнать, что конкретно работает не так... Делал следующее, шел по массиву, от каждой свободной клетки поиском в глубину находил компоненту связности, где данная клетка лежит. У данной компоненты находит левую, правую, верхнюю и нижнюю границы и всё пространство между границами заполнял точками. Удивился, что падает на WA, а не на TL, в чём может быть проблема?
Да, я делал так же, и у меня тоже WA на 12. Вот тест, на котором не пройдёт:
Видимо, просто эта идея не работает.
Спасибо за тест, действительно упало решение.
Im getting wrong answer on test 4 problem C....why? where 25 comes from?
Make 5 equal to 4 by reducing it and then you have 4,4,4,4,3,3,3,3. So total area = 16+9;
I got it man....i thought that they only need the maximum area not the sum..so i was getting 16
Есть в математике такая вещь ТРАНСНЕРАВЕНСТВО: Пусть {i1,…,in} — некоторая перестановка набора {1,…,n}. Если x1≥⋯≥xn,y1≥⋯≥yn, то x1y1+⋯+xnyn≥x1yi1+⋯+xnyin≥x1yn+⋯+xny1.
отсортировал все палки по длине и разбил на пары с максимально возможнымми длинами, по транснеравенству произведения пар с наибольшими последовательными длинами должны давать максимальное произведение. Не зашел 37 тест(( Такое решение неверно?
Тоже пытался воспользоваться транснеравенством во время контеста, однако забыл про типы данных и зафейлил еще при проверке третьего теста из условия на собственном компьютере. А так — решение рабочее. codeforces.ru/contest/525/submission/10478118
Во втором if'е не хватает фигурных скобок. Под него попадает не весь кусок кода.
Can someone please explain why in Problem C the output for test 4
is 25 instead of 16? Thanks.
You can use 5 (-1), 4, 4, 4 for one rectangle and 3, 3, 3, 3 for another.
4*4+3*3=16+9=25
5 becomes 4, and then the rectangles are: { 4, 4, 4, 4 }, { 3, 3, 3, 3 }. First's size is 16, second's is 9.
man i did the same mistake....i thought they need the maximum possible area....but they needed the sum of all maximum possible area... I think this problem should be reviewed...
I totally agree with you. A lot of people including myself misunderstood the problem statement. It should have been something like:
"..maximum total area of ALL THE POSSIBLE rectangles that Ilya can make .."
Aside from this the round was great. Many thanks to the problems setter =).
I liked E a lot, and I had the idea in contest, but made some stupid mistakes...Anyway, now, after the contest ended, I tried to find the bugs, and, apparently, I found them, but I have TLE because of map(I checked, not at the point when we insert in map, is because of the point where we are "querying" the map).Here is my source: http://mirror.codeforces.com/contest/525/submission/10476721
I really don't know what's so wrong.It inserts me in map in 0.5 seconds and queries in 18 seconds...
On lines 40,41 and 78,79 you make about 2^n iterations, wich is way larger than 3^(n/2), wich is the optimal complexity for finding all the submasks of a mask.
It's not because that.I reimplemented it and it was the same thing.The idea is that I have 2^n and it enters in for just for 3^(n/2) :-P .Here is the new source: http://mirror.codeforces.com/contest/525/submission/10477139 I thought it was easier for someone to look at th first source ant that's why I posted that one.
First, don't try this _j < (1<<n_bit);, it is slow. Second, you could implement 3^(n/2) in a faster way by just iterating the masks from 1 to 3^(n/2) and considering : 0->not taken 1->taken without factorial 2->taken with factorial
Try unordered_map.
I'll try it but I still can't believe that it take it so much to query, knowing that it inserts in 0.5 seconds with the same complexity
As editorial said, "To accelerate our programm we may increase answer only if cnt[cur].count(s - sumrg) = true."
The operator[] creates a new object if it wasn't there before, which will slow down subsequent queries by a bit.
Accepted: 10478038
WOW, it's a really big difference of times just because that...I'll never make the same mistake :))Thanks
Hey, there is a O(n) solution, we can just use BIT and mark the intervals being chosen each day. Then segments having even count sustain their original order and the ones with odd cf, are transformed.
Pasha and string can be solved in O(n) time using BIT. :)
No operation of BIT takes linear time it always involve logn factor
Every operation on BIT takes O(logn) time. How is it O(n)?
Probably a silly mistake on my part, but This code outputs the right answer (8) for the first test case (4, 2 4 4 2) when i debug it on my machine but outputs 4 and fails on pretest 1 when tested on the website. I know the algorithm is greedy and might not be right but why does it have a different output? Thanks in advance!
I figured it out. It seems that par[++i] is behaving different on the website's compiler. Weird.
Please help me with the logic used in the problem 525B especially the 'sum' part ? :
So, let's start with an example word "abcdef".
Our possible operations include:
1 (reversing letters from [1,6]),
2 (reversing letters from [2,5]),
3 (reversing letters from [3,4]),
4 (reversing letters from [3,4]),
5 (reversing letters from [2,5]),
6 (reversing letters from [1,6]),
I will call operations rather by their intervals now, I think it's easier to understand that way.
Now focus on the first letter "a" for a while. It can only change it's place after reverse operation [1,6]. Where it can go? Only at the end, swapping with "f". And after the second one of that type? "a" will go back to the first position again, swapping with "f". No other operation can change position of "a", all other operations will only change something inside the word, between "a" and "f". So how can we now where is "a" after all operations? Well, that's simple, let's count all of the type [1,6], if it's even then "a" stays on the position 1, if it's odd then "a" is swapped with "f". If you can't see it just do few operations [1,6] in your head or on piece of paper and look what happens. Let's store information about number of operations [1,6] in sum[1], you will see why in few seconds.
Ok, moving onto "b". "b" can be swapped with "e" after operations [2,5], but also [1,6]. "Even-odd rule" works there two, as it's really the same thing — only changes "b"-"e" are possible and they come after [1,6] or [2,5]. Ok, so if we store number of operations [2,5] in sum[2] only thing we need to know is number of operations [1,6]. Now sum[1] comes into play :) Only thing we have to do for "b"-"e" is check if sum[1] + sum[2] is odd and, if it's the case, swap "b" with "e".
One thing you may not see now, but it's also the small problem — for position 3 it's easy, just sum up sum[1] + sum[2] + sum[3]. But you would have to do that addition for every position from the first half of the string and for long ones it can be little bit painful. Don;t worry though, there is one Jedi trick :) Just iterate over all i's from 1 and do:
for (int i = start_position; i < s.length() / 2; ++i) {
if (i != 0) sum[i] += sum[i — 1];
//computations here
} In first iteration we have sum[1] in sum[1], in the second one sum[2] + sum[1] in sum[2], in the third one sum[3] + sum[2] + sum[1] in sum[3] and so on. Just what we needed :)
EDIT: My code: http://mirror.codeforces.com/contest/525/submission/10479343
Perfect explanation sir !! Thank u , thanks a lot :)
For E can't we just loop over all k-sets in a maximum of (25 choose 12)=5*10^6 ways and update the sum from one k-set to the next in O(1) by simply changing one factorial to a different factorial? (Of course we ignore factorials which are too big)
В задаче D непонятно почему если в квадрате 2 х 2 есть ровно одна стена, то ее нужно удалить. Кто-нибудь может доказать правильность этого факта?
Три пустые клетки должны лежать в одной комнате, а комната прямоугольная.
Can someone explain to me the solution for #4? I used BFS on a space, then got the width and height of the total room, and within the width and height set everything to a '.'. It gives me a wrong answer on case 20, but the case is too large.
I don't understand solution well enough to explain it, but those are smaller counterexamples to your solution:
the one showing something is wrong with your bfs
3 3
**.
**.
...
and the one showing "one-time" bfs is not enough
3 3
**.
.**
...
Thank you! Did you happen to solve the problem? Can you explain the solution?
In the editorial's solution for Pasha and String
Then we need to count array sum[]. In sum[i] we need to store count of reverses of substrings, which begin in positions which not exceeding i.
I don't get this statement. Could someone explain it in greater detail?
How about reading comments first? :>
http://mirror.codeforces.com/blog/entry/17119#comment-219543
Thanks a lot! That was great explanation! Yet, my code which follows the same algorithm gives a TLE on test case 7. How?
http://mirror.codeforces.com/contest/525/submission/10498956
Again, guess, but only possible answer that comes to my mind is the fact that strlen can be up to linear in time:
http://stackoverflow.com/questions/3388029/strlen-function
Instead, you should store length of the string in variable or use std::string::length WITHIN C++11 standard where it's guaranteed O(1) time.
http://www.cplusplus.com/reference/string/string/length/
Look at complexity of length in C++98 and C++11.
Also, small enhancement, you can use & 1 instead of % 2, since it's the same, but operations on bits are much more faster than very slow modulo operation. It's small factor, much smaller than this with strlen, but why not? :)
Thanks a ton rr_! The strlen was the problem. Wow! I learnt something new. Regarding the modulo, thanks for the tip! I'll keep that in mind. :)
In problem E you don't need to sort the given array.
Пытаясь сдать задачу D, столкнулся с непонятным мне багом: локально (Dev-C++ 4.9.9.2) этот код 10479962 исполняет первый тест правильно, а на Codeforces и Ideone — нет. В чем может быть проблема?
I tried to solve problem D in the following,
Find the connected components from the given maze. And also find the boundary of the connected component.( top,bottom, left,right). And make all the cells in the maze which lies in the boundary to ".".
Also kind of handled case like this with double run of algo.
.... .... ..*.. ...*. ....*
Is there anything wrong with this approach ? This approach was failing for test case 12.
Consider this initial connected components:
When you only draw dots on the boundary you get:
You don't discover that 3 is also part of the 1-2 room.
After you find a boundary ( top, bottom, left, right), my idea is to convert every cell inside the boundary to "." .
hello , your idea is correct, you have a lot of rectangles , but you have to merge rectangles that intersect, and then fill the rectangles with '.'
the most difficult is solve the last part, how do you merge rectangles optimaly???
my idea was make a sweep line on x , and then merge rectangles on y , keep a structure, the code is very difficult , therefore is better analize the problem and make it more easy!!
I used the same method as yours, but I got TLE on test 12. I don't know why I got TLE, because I don't think it would cost such long time.
stafuc, it's not even correct. Assuming you talk about your last try (http://mirror.codeforces.com/contest/525/submission/10503768):
Tiny test case:
Your output:
Not a rectangle ... clearly wrong.
Oh thank you. Getting all rectangles is not enough, I have to merge them. Thanks very much~.
Could somebody help me come up with a case where my solution fails?
I chose to forgo the option of keeping track of how sticks of length L I had. Instead, I sorted the sticks in descending order according to their lengths. Then, I tried greedily choosing the four largest sides, assuming that the difference between the opposing was always less than or equal to 1 (otherwise, I would be unable to cut accordingly). Thanks for your help in advance.
6
10 10 7 5 3 3
thx
For problem E, I din't pass the system test if I used
map(10491477) but passed withunordered_map(10491490). But, interestingly, 10480213 (from which I got the idea because it was easy to understand) passed system test. What is going on?Что не так с этим решением (кроме того, что массив должен быть в 2 раза больше): 10460355?
ans = 0
Действительно, спасибо. Глупая ошибка.
Какую роль играет сортировка в задаче E? По идее ведь что с ней, что без неё, должно быть одинаково, однако без сортировки не заходят тесты, может кто объяснить почему?
Upd.: Извиняюсь, была другая ошибка. Интересно вышло, что при сортировке, ошибочное решение проходило 89 тестов, а без — 26. Всё-таки сортировка не нужна, не понятно зачем авторы указали, что её необходимо сделать.
I get wrong answer for problem c for test case 37. Can somebody provide a counter example for my approach. 10502423
How about reading two comments above first? :P
http://mirror.codeforces.com/blog/entry/17119#comment-219655
Hello, I tried to solve problem D about 20 times but verdict is always "runtime error on test 92". Could you help me, please? Regards 10507530
I also got a runtime error on test case 92.I just changed string to char array and took the input character by character.It got AC.10776197
Can anyone discuss solution of D and proves of solution?
How to prove that the algorithm for Problem D removes the minimum number of walls??
could someone explain where my solution goes wrong for 525C . I am having wrong answer in test case 37 . http://mirror.codeforces.com/contest/525/submission/10501081 . My output : 11234878867001938 jury's answer : 11234878866984153 . Thank you for help
Try the following test case:
Should output 42. But yours outputs 43. Third time through the loop i=1,area=1,count=2. So you add area to totalarea which you shouldn't.
How can one prove the solution to D? (I mean the property of 2x2 matrix)
Can someone explain the solution for D better? I honestly can't understand the editorial's solution, as the writer's English is not the best.
In problem D, my dfs solution is accepted but when the same logic is applied using bfs i am getting tle. Can anyone guide me why is it hapenning ??
Почему валится 10574466, но не валится 10571455 ? Никак не пойму. Код почти одинаковый. В чём тут разница?
Массив маленький.
can anyone explain why am i getting wa !!
TIA
here is maah code
In problem A ,I used unordered multiset to store the keys, but why its getting TLE in test 8?