### 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[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.

• +110

 » 5 years ago, # |   0 Fastest editorial so far! Thanks!
 » 5 years ago, # |   +8 your rounds are awesome :D won't miss any of them :3
 » 5 years ago, # |   0 What was test case 4 for problem C??
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 years ago, # ^ |   0 i too misunderstood the problem statement :(
•  » » » » 5 years ago, # ^ |   0 What's that? I don't see it... Where does the "25" come from?
•  » » » » » 5 years ago, # ^ |   0 It was the sum of all possible rectangles that could be made. Not the max of those. I also got to know now ! :(
•  » » » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   0 me too！but I understand it finally
•  » » 5 years ago, # ^ |   0 I also misunderstood the problem. #Confusing Problem
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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 !
•  » » 5 years ago, # ^ |   +1 In problem C use long long Because the input and Output is large it can't covered by long
 » 5 years ago, # |   0 Thank you for nice problems:) BTW, for 530E, I think associative array cnt should be map < long long, int >
 » 5 years ago, # |   0 Im getting wrong answer on test 4 problem C....why? where 25 comes from?
•  » » 5 years ago, # ^ |   0 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;
•  » » » 5 years ago, # ^ |   +5 I got it man....i thought that they only need the maximum area not the sum..so i was getting 16
 » 5 years ago, # |   +2 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 →   0 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 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 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...
•  » » » 5 years ago, # ^ |   +5 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 →   +1 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...
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   0 First, don't try this _j < (1<not taken 1->taken without factorial 2->taken with factorial
•  » » 5 years ago, # ^ |   0 Try unordered_map.
•  » » » 5 years ago, # ^ |   0 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 →   +18 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
•  » » » 5 years ago, # ^ |   +8 WOW, it's a really big difference of times just because that...I'll never make the same mistake :))Thanks
 » 5 years ago, # |   -12 Pasha and string can be solved in O(n) time using BIT. :)
•  » » 5 years ago, # ^ |   +1 No operation of BIT takes linear time it always involve logn factor
•  » » 5 years ago, # ^ |   0 Every operation on BIT takes O(logn) time. How is it O(n)?
 » 5 years ago, # |   0 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!
•  » » 5 years ago, # ^ |   0 I figured it out. It seems that par[++i] is behaving different on the website's compiler. Weird.
 » 5 years ago, # |   0 Please help me with the logic used in the problem 525B especially the 'sum' part ? :
•  » » 5 years ago, # ^ | ← Rev. 3 →   +2 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.ru/contest/525/submission/10479343
•  » » » 5 years ago, # ^ |   +3 Perfect explanation sir !! Thank u , thanks a lot :)
 » 5 years ago, # |   0 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)
 » 5 years ago, # |   0 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 →   +1 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**..**...
•  » » » 5 years ago, # ^ |   -8 Thank you! Did you happen to solve the problem? Can you explain the solution?
 » 5 years ago, # |   0 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.
 » 5 years ago, # |   0 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?
•  » » » 5 years ago, # ^ |   0 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 →   0 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? :)
•  » » » » » 5 years ago, # ^ |   0 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. :)
 » 5 years ago, # |   0 In problem E you don't need to sort the given array.
 » 5 years ago, # | ← Rev. 3 →   0 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.
•  » » 5 years ago, # ^ |   +3 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.
•  » » » 5 years ago, # ^ |   0 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 →   +1 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!!
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   0 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.
•  » » » » » » 5 years ago, # ^ |   0 Oh thank you. Getting all rectangles is not enough, I have to merge them. Thanks very much~.
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   +5 610 10 7 5 3 3
 » 5 years ago, # |   0 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?
 » 5 years ago, # |   0 I get wrong answer for problem c for test case 37. Can somebody provide a counter example for my approach. 10502423
•  » » 5 years ago, # ^ |   0 How about reading two comments above first? :Phttp://codeforces.ru/blog/entry/17119#comment-219655
•  » » » 5 years ago, # ^ |   0 thanks I got it
 » 5 years ago, # |   0 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 →   0 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
 » 5 years ago, # |   +1 Can anyone discuss solution of D and proves of solution?
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   +3 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.
 » 5 years ago, # |   0 How can one prove the solution to D? (I mean the property of 2x2 matrix)
 » 5 years ago, # |   0 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 →   0 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
 » 5 years ago, # |   0 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
 » 5 years ago, # |   0 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 ??
 » 5 years ago, # |   0 Can anyone please explain the logic of 2x2 in problem D and proof of its correctness?
 » 5 years ago, # | ← Rev. 3 →   0 Hello.Here is my submission for problem A.Can anyone help me with a test instead of test 8?
 » 5 years ago, # |   0 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?
 » 4 years ago, # |   0 can anyone help me why i am getting wa on test 37 for problem c. here is my code
 » 4 years ago, # | ← Rev. 2 →   0 can anyone explain why am i getting wa !! TIAhere is maah code
 » 4 years ago, # | ← Rev. 2 →   0 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 ?
 » 3 years ago, # |   0 Hi... .Would you please tell me why my solution is wrong for 525A - Виталий и пирожок?submission: 21233075
•  » » 3 years ago, # ^ |   0 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!
•  » » » 3 years ago, # ^ |   0 Corrected... . submission: 21589121
•  » » 3 years ago, # ^ |   0 Corrected... . submission: 22328351
 » 2 months ago, # |   0 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.