525A — Vitaliy and Patty
To solve this problem we need to use array cnt[]. In this array we will store number of keys of every type, which we already found in rooms, but didn't use. Answer will store in variable ans.
Now, we iterate on string. If current element of string si is lowercase letter (key), we make cnt[si]++. Else if current element of string si uppercase letter (door) and cnt[tolower(si)] > 0, we make cnt[tolower(si)]--, else we make ans++. It remains only to print ans.
Asymptotic behavior of this solution — O(|s|), where |s| — length of string s.
525B — Pasha and String
At first we need to understand next fact — it doesn't matter in wich order make reverses, answer will be the same for all orders.
Let's numerate elements of string from one. To solve given problem we need to count how many reverses will begin in every position of 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.
Now iterate for i from 1 to n / 2 and if sum[i] is odd swap si and sn - i + 1. After that it remains only to print string s.
Asymptotic behavior of this solution — O(n + m), where n — length of string s, m — count of reverses.
525C — Ilya and Sticks
This problem can be solved with help of greedy. At first count array cnt[]. In cnt[i] will store how many sticks with length i we have.
Now iterate for len from maximal length of sticks to minimal. If cnt[len] is odd and we have sticks with length len - 1 (that is cnt[len - 1] > 0), make cnt[len]-- and cnt[len - 1]++. If cnt[len] is odd and we have no sticks with length len - 1 (that is cnt[len - 1] = 0), make cnt[len]--.
In this way we properly done all sawing which we need and guaranteed that all cnt[len] is even. After that iterate similary on length of sticks and greedily merge pairs from 2 sticks with the same length in fours. It will be length of sides of sought-for rectangles, left only summarize their squares in answer. In the end can left 2 sticks without pair, we must not consider them in answer.
For example, if cnt[5] = 6, cnt[4] = 4, cnt[2] = 4, we need to merge this sticks in following way — (5, 5, 5, 5), (5, 5, 4, 4), (4, 4, 2, 2). Two sticks with length 2 are left, we must not count them.
Asymptotic behavior of this solution — O(n + maxlen - minlen), where n — count of sticks, maxlen — maximal length of stick, minlen — minimal length of stick.
525D — Arthur and Walls
To solve this problem we need to observe next fact. If in some square whith size 2 × 2 in given matrix there is exactly one asterisk, we must change it on dot. That is if in matrix from dots and asterisks is not square 2 × 2 in which exactly one asterisk and three dots, then all maximum size of the area from dots connected by sides represent rectangles.
Now solve the problem with help of bfs and this fact. Iterate on all asterisks in given matrix and if only this asterisk contains in some 2 × 2 square, change this asterisk on dot and put this position in queue. Than we need to write standart bfs, in which we will change asterisks on dots in all come out 2 × 2 squares with exactly one asterisk.
Asymptotic behavior of this solution — O(n * m), where n and m sizes of given matrix.
525E — Anya and Cubes
To solve this problem we need to use meet-in-the-middle. At first sort given array in increasing order and divide it in two parts. In first part must be first n / 2 elements, in second part — other.
Iterate all submasks of all masks of elements from first part. That is iterate which cubes from first part we take and on which from them we paste exclamation marks. In this way we iterated all possible sums, which we can get with cubes from first part. Let for current submask we get sum sum_lf and use tlf exclamation marks. To store all such sums we use associative arrays map < long long > cnt[k + 1], where k — count of exclamation marks which we have in the beginning.
After that similary iterate all submasks of all masks of elements from second part. Let for current submask sum is sumrg and number of used exclamation marks is trg. Then from first part we need to get sum (s - sumrg) and we can use only (k - trg) exclamation marks, where s — sum which we must get by condition of the problem. Then iterate how many exclamation marks we will use in first part (let it be variable cur) and increase answer on cnt[cur][s - sumrg]. To accelerate our programm we may increase answer only if cnt[cur].count(s - sumrg) = true.
For submasks in iterate we can cut off iteration on current sum for submask (it must be less or equal to given s) and on current count of exclamation marks (it must be less or equal to given k). Also we should not paste exclamation marks on cubecs with numbers larger than 18, because 19! more than 1016 — maximal value of s.
Asymptotic behavior of this solution — O(3((n + 1) / 2) * log(maxcnt) * k), where n — count of cubes, maxcnt — maximal size of associative array, k — count of exclamation marks.
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 >
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
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://codeforces.net/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://codeforces.net/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
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://codeforces.net/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)
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://codeforces.net/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://codeforces.net/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.
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://codeforces.net/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?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://codeforces.net/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?
could someone explain where my solution goes wrong for 525C . I am having wrong answer in test case 37 . http://codeforces.net/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 ??
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?