### PetarV's blog

By PetarV, 8 years ago, # Codeforces Round #169 — Unofficial Editorial

I really enjoyed this round, the tasks required more thinking than coding and that's always a good thing. I'd like to share my solutions to the problems here. Hope you enjoy them!

## A — Lunch Rush

This problem was the easiest one in the competition, and the solution is just the simple implementation of what is given in the task statement — calculate the fun level for each restaurant, and output the maximal value.

Time complexity: O(n)

Memory complexity: O(1).

## B — Little Girl and Game

The key thing to notice in this task is, if we can arrange the characters of the string we have into a palindrome, then there can be at most one character with an odd amount of occurences. This easily gives us the answer: if there are <= 1 characters with an odd amount of occurences in the initial string, then the winner is the first player. Otherwise, the answer is dependant on whether the amount of characters with odd amounts of occurences is even or odd; if it's even then the second player wins, otherwise the first player wins (since the one who is forced to get this amount to one first is going to lose).

Time complexity: O(n)

Memory complexity: O(n).

## C — Little Girl and Maximum Sum

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use the Binary Indexed Tree structure to store cumulative sums with update and retreival times of O(log n) (a great tutorial for this structure can be found here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees).

Time complexity: O(n log n)

Memory complexity: O(n).

## D — Little Girl and Maximum XOR

A XOR of two numbers has the value of the i-th bit set to 1 if and only if their values on this bit differ (i.e. one is zero and the other is one). We can be certain that we can pick two numbers with differing bits on the i-th position and conform to the rest of our solution, if the difference between R and L is greater than or equal to 2^i (because the zeroth bit changes state every 2^0 values, the first one every 2^1 values and so on). When this difference is lesser than 2^i, we use another key observation: within one of those blocks of length 2^i, the sequences of values where the i-th bit is zero and where it is one are contiguous; i.e. we just have to check whether the i-th bit of R differs from the i-th bit of L, and then we know whether or not they're in the same subsequence with respect to that bit. If they are not, we can add 2^i to our solution. We carry on until 2^i is lesser than or equal to R.

Time complexity: O(log n)

Memory complexity: O(1).

## E — Little Girl and Problem on Trees

A key observation on this problem is that when we perform the operation 0 on any node which isn't the root, we increase the nodes at [depth[X] — d .. depth[X] + d] along its chain. Of course, if depth[X] <= d, this will also affect other chains, namely, all depths lesser than d — depth[X] + 1 will be increased as well. To handle this we can store information about each chain in a BIT structure — one for each chain (this structure was mentioned already in solution for task C), and also store information about the global depth updates in another BIT. When we query a particular node, we simply add up the BIT value of its relevant chain and of its depth.

Time complexity: O(q log n)

Memory complexity: O(n). Tutorial of Codeforces Round #169 (Div. 2)  Comments (43)
 » C can be solved with greedy algo, thinking it's easier.
•  » » Ximera can you please explain it.
•  » » » Sorry for my bad English :)At first we should have array. Let's say it will be c[]. So c[i] would be the number of times of using the element with index i. Than we should use the biggest element of array a[] most times, second biggest — second max of c[]. The same goes for the others.Main problem is to fill c[]. I can't explain it on English, but here is my code. Hope you'll understand :)
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   PetarV also used greedy algorithm, but he used binary indexed tree to calculate the array c[].
 » 8 years ago, # | ← Rev. 2 →   Just noticed it's possible to do C in O(n), without a BIT, just using a regular array to calculate cumulative sums. But I think there's nothing wrong with my solution, at least with respect to the given constraints. :)
•  » » 8 years ago, # ^ | ← Rev. 3 →   I beg your pardon, but we still have to sort all the numbers. So it can't beat the bounds of O(n log n)And thanks for the editorial.
•  » » » Oh yes, I forgot that, silly me :)
•  » » » » Oh, you were initially correct. The numbers have a limited range [1,2*10^5]. So they can indeed be sorted in O(n). Sorry for the confusion.
•  » » PetarV Can you please explain why in your solution you have used read(i) instead of read(i)-read(i-1) to know the count of i-th index.
•  » » » Because we are storing the value on some index as its cumulative sum: when we update left index with 1 and right+1 with -1, we increase the cumulative sum from the left to the right index by 1 and not change any other.
•  » » » » Ok Thanks a lot :)
•  » » » » » PetarV: If after all the queries we had to find sum(a,b) ,a
•  » » » » » » 8 years ago, # ^ | ← Rev. 7 →   read(b) — read(a-1), except if a = 1, then just read(b). If I understood correctly that you want to get the sum of the substring [a,a+1,...,b].Or if you mean just the sum of all amounts together (with respect to this problem C), you'd have to iterate through every field separately. It's not possible to do it in O(1) read commands if you store data this way. You'd have to extract the sequence, and then make a new BIT / prefix sum array out of it, if you want to do it with only two read() commands (if we assume the queries have already been loaded and processed).
•  » » » » » » » PetarV: Thanks for the clarification. More precisely I was trying to ask if this problem can be solved using BIT the same way it has been used in problem C because it also involves adding some value (which was 1 for the problem C) to the given interval and then querying for the interval(a,b)(where a=b for problem C here).
•  » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   I think that BIT is not convenient to use there. Segment tree seems like a much better option :)
 » in C for calculating the number of queries at index a, this is enough: num[a] = num[a-1] — close[a-1] + open[a+1] close [a] is the number of queries which the r[i] is a-1 ( closed at index a-1 ) and also open.
 » It is the fastest editorial I've ever seen !
 » Ximera can you please explain it.
 » petar thank you so much for this editorial ....u rock man..
 » 8 years ago, # | ← Rev. 2 →   D. u can find xxx011111...1 ^ xxx100000...0 is maximum http://codeforces.com/contest/276/submission/3192808
•  » » How short your code is !
•  » » » assume L=xx..x0abc..d(B) R=xx..x1efg..h(B) obviously L<=xx..x011..1
•  » » Your code is right but your explaination is not a good one or may be a wrong one.
•  » » » His explanation is perfectly coherent to his solution. I had the same theoretical idea during the contest but I didn't succeed to code it.
•  » » » » during the contest ,i am so stupid that i have no idea about D.the next day,i find this conclusion
 » 8 years ago, # | ← Rev. 2 →   3192927Here is the way i did Problem C using DP method of storing Freq.Lets go through the method. Sample Test case: 3 3 5 3 2 1 2 2 3 1 3 first sort the array in decreasing order. Concept is "You have to fix the biggest element from array to the index that is queried most times and then second biggest element to second most queried element .. so on " here, index — 1 2 3 Freq- 2 3 2 query "1 3" also include elements from 1 to 3(Obvious). now we have to figure out way to calculate frequency of each index efficiently here is what i followed. int freq[n+1]; // n is size of array ,(taking n+1 has a reason, you will see later) memset(freq,0,sizeof freq); // initialization with zero for query a b, means all element from index "a" to index "b" are there. so update freq[a]++; and freq[b+1]--; (since b+1 can be >n . that's why i took freq of size n+1) here in queries freq will look like +2 +1 -1 -2 to get final frequency just iterate from starting from 0 till n-1 and doing this freq[i]+=freq[i-1] .(i>=1) so we got freq : 2 3 2 now sort this in same order as you did initial array and now just multiply it. and you got answer here is freq- 2 2 3 arr — 2 3 5 answer is= 15+6+4 = 25.i hope this will help!!
•  » » 8 years ago, # ^ | ← Rev. 3 →   You have essentially did the same thing mostly everybody else did — storing cumulative sums. The only difference between your solution and mine is that my access/update times are O(log N) and yours are O(1). And it has no overall effect on the complexity because you need O(N log N) to sort the sequence anyway (unless you use a non-comparison sorting method i.e. counting sort).
•  » » Why do you call your method DP?
•  » » » because the method to calculate frequency of index depends on previous one .. that's why
 » For those who don't know it yet, there's a nice trick to solve D-problem with only 2 lines of code. The main problem was to find the position of the highest set bit of the number L^R and then you already know what follows. So, to do this there's one of the __builtin functions ( __builtin_clz ) which returns the number of leadings 0-bits in a given number, using this nice function it's possible to solve the problem in the following way:#include  int main(){ long long a,b; scanf("%lld %lld", &a,&b), printf("%lld",(1LL<<(64-__builtin_clzll(a^b)))-1LL);}
•  » » what is the intuition behind this trick?
 » very good explanation, thanks
 » Its too late, but attempting this contest as a virtual contest, I found an easier solution to Div2 B.I don't know if its just me, but I found author's solution a little less intuitive than my solution.Link to solution: http://codeforces.com/contest/276/submission/28716955
 » In the code of problem C(by PetarV) I managed to understand how frequency of indices are computed using BIT (by working on sample test cases with pen and paper). But the logic behind this part is still not clear to me. Can somebody explain this? Thanks in advance.  update(x,1); update(y+1,-1); Can someone give the proof of this part?
•  » »
 » in the problem b test case 2: "abca" the answer is given "second". but shoudn't it be "first" as if the first player remove b or c it would be a palindrome...i really can't think why it's not first,please someone explain.TIA
•  » » Player 1 removes b. It means he didn't win because it's not a palindrome. Therefore Player 2 wins. If Player 1 removes c. It means it's still not a palindrome. Player 2 wins. In case 1: aba, player 1 doesn't remove anything. Therefore, it's already a palindrome and player 1 wins because it was his turn that he doesn't have to remove anything.
 » Can C be solved greedily?
•  » » 5 months ago, # ^ | ← Rev. 2 →   Yes, I solved it greedily, have a look here solution
 » For Problem D I found it here Explanation.
 » In B, the given solution fails for a cases such as: aab : the winner is Second but the solution yields First aabc : the winner is First but the solution yields Second I think test cases like these were not tested for. Please correct me if I am wrong.
•  » » hi ,FIRST CASE 1 -->removes a ( ab ) 2 --> removes a ( b ) <-- b can also be removes ( first wins )SECOND CASE 1 --> removes a ( abc ) 2 --> removes c ( ab ) 1 --> removes a ( b ) <-- second winsNote that in problems involving games each plyer will moves in such a way that opponent's probability to looses is highest possible .Also if you are able to understand it , can you answer who is the winner in this case aabb
 » C doesn't need a BIT/Fenwick Tree and can be done simply using 2 sorts and a difference array. My solution: https://codeforces.com/contest/276/submission/116987498