### fcspartakm's blog

By fcspartakm, 5 years ago, translation, , ## 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 = 6, cnt = 4, cnt = 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. Tutorial of Codeforces Round #297 (Div. 2) 297, Comments (84)
 » 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??
•  » » 5 years ago, # ^ | ← Rev. 2 →   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
•  » » I also misunderstood the problem. #Confusing Problem
•  » » 5 years ago, # ^ | ← Rev. 2 →   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 8 5 3 3 3 3 4 4 4 is 25 instead of 16? Thanks.
•  » » 5 years ago, # ^ | ← Rev. 2 →   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 =).
 » 5 years ago, # | ← Rev. 3 →   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.com/contest/525/submission/10476721I 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.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<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
•  » » 5 years ago, # ^ | ← Rev. 2 →   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 ? :
•  » » 5 years ago, # ^ | ← Rev. 3 →   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, 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 only thing we need to know is number of operations [1,6]. Now sum comes into play :) Only thing we have to do for "b"-"e" is check if sum + sum 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 + sum + sum. 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 in sum, in the second one sum + sum in sum, in the third one sum + sum + sum in sum and so on. Just what we needed :)EDIT: My code: http://codeforces.ru/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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   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 bfs3 3**.**....and the one showing "one-time" bfs is not enough3 3**..**...
•  » » » Thank you! Did you happen to solve the problem? Can you explain the solution?
 » First you need to understand the following fact — it does not matter in what order to carry out coups, the answer will not change.Let the elements of the row indexed starting at one. To solve the problem count how many revolutions will start in each of the positions of the line. Then counted array sum []. In sum [i] will store the number of revolutions of substrings that start at positions that do not exceed i.Now Let us iterate over i from 1 to n / 2, and if sum [i] is odd, exchange row si and sn — i + 1. We derive an answer — the resulting string s.Asymptotics of the solution — O (n + m), where n — length of the string s, m — the number of revolutions.
 » In the editorial's solution for Pasha and StringThen 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?
•  » » » 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.com/contest/525/submission/10498956
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   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-functionInstead, 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.
 » 5 years ago, # | ← Rev. 3 →   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: ********* *1******* *1******* *1***3*** *111***** *1******* *1*22222* ********* When you only draw dots on the boundary you get: ********* *1112222* *1*1***2* *1*1*3*2* *111***2* *1*1***2* *1122222* ********* 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 "." .
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   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.com/contest/525/submission/10503768):Tiny test case: 3 3 *.. ... ..* 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.
•  » » 610 10 7 5 3 3
•  » » » thx
 » For problem E, I din't pass the system test if I used map(10491477) but passed with unordered_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
•  » » » thanks I got it
 » 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
•  » » 5 years ago, # ^ | ← Rev. 3 →   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.com/contest/525/submission/10501081 . My output : 11234878867001938 jury's answer : 11234878866984153 . Thank you for help
•  » » Try the following test case: 6 7 7 6 6 6 4 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.
 » 5 years ago, # | ← Rev. 3 →   In Problem C , My Code passed test cases with N=93073,96751.. but got TLE in test39 with N=1000? solutionYour text to link here...: http://codeforces.com/contest/525/submission/10522211
 » I get a wrong answer in problem D. But I already pass 31 datas and the 32nd data is too huge to find the problem. Can u email me that data or help me with finding the bug in my program. http://codeforces.com/contest/525/submission/10528685
 » 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 please explain the logic of 2x2 in problem D and proof of its correctness?
 » 5 years ago, # | ← Rev. 3 →   Hello.Here is my submission for problem A.Can anyone help me with a test instead of test 8?
 » Hello.Here are my 2 submissions for problem B: 1st submission and 2nd submission.I used a map in the first one and got TLE on test 41. However, I replaced the map with an array in the second one and got TLE on test 29.Can anyone help me?
 » can anyone help me why i am getting wa on test 37 for problem c. here is my code
 » 4 years ago, # | ← Rev. 2 →   can anyone explain why am i getting wa !! TIAhere is maah code
 » 4 years ago, # | ← Rev. 2 →   In problem B : How I should approach if given problem is like given index l and r . You have to reverse the string the string from a[l] to a[r]. What would be its approach ?
 » Hi... .Would you please tell me why my solution is wrong for 525A - Vitaliy and Pie?submission: 21233075
•  » » I had the same problem and I've been thinking about it for the past few days ,unfortunately I couldn't find the reason for the wrong answer but I just resubmitted my code with some changes and became accepted out of nowhere! All i did was storing the keys before checking anything else ,and then as soon as you face a door you check whether you have got its key or no! The problem seems to be with priority of checking and storing but I still can't get the problem with my previous submission:21360440 which had this extra comparison of same keys and doors that I have no idea how it causes trouble!
•  » » » Corrected... . submission: 21589121
•  » » Corrected... . submission: 22328351
 » The first question is not that clear...To clarify, We can collect the keys from rooms if the key is not used in that room, this way we can use the key to open some other lock in some other room.
 » In problem A ,I used unordered multiset to store the keys, but why its getting TLE in test 8?