PetarV's blog

By PetarV, 5 years ago, In English,

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.

My code: http://www.codeforces.com/contest/276/submission/3180631

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).

My code: http://www.codeforces.com/contest/276/submission/3181475

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).

My code: http://www.codeforces.com/contest/276/submission/3182445

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.

My code: http://www.codeforces.com/contest/276/submission/3183526

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.

My code: http://www.codeforces.com/contest/276/submission/3187958

Time complexity: O(q log n)

Memory complexity: O(n).

 
 
 
 
  • Vote: I like it  
  • +45
  • Vote: I do not like it  

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C can be solved with greedy algo, thinking it's easier.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ximera can you please explain it.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like 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 :)

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        PetarV also used greedy algorithm, but he used binary indexed tree to calculate the array c[].

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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. :)

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yes, I forgot that, silly me :)

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok Thanks a lot :)

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          PetarV: If after all the queries we had to find sum(a,b) ,a<b,where a and b are the indexes of first and last element.How can it be solved using BIT because now read(i) stores the total count of i-th index ?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 7   Vote: I like it 0 Vote: I do not like it

            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).

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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).

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                I think that BIT is not convenient to use there. Segment tree seems like a much better option :)

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It is the fastest editorial I've ever seen !

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Ximera can you please explain it.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

petar thank you so much for this editorial ....u rock man..

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

D. u can find xxx011111...1 ^ xxx100000...0 is maximum http://codeforces.com/contest/276/submission/3192808

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How short your code is !

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      assume L=xx..x0abc..d(B) R=xx..x1efg..h(B) obviously L<=xx..x011..1<xx..x100..0<=R,and xx..x011..1 xor xx..x100..0 is maximum

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is right but your explaination is not a good one or may be a wrong one.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        during the contest ,i am so stupid that i have no idea about D.the next day,i find this conclusion

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

3192927

Here 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!!

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you call your method DP?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      because the method to calculate frequency of index depends on previous one .. that's why

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 <cstdio> int main(){ long long a,b; scanf("%lld %lld", &a,&b), printf("%lld",(1LL<<(64-__builtin_clzll(a^b)))-1LL);}

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very good explanation, thanks

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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