Блог пользователя bully....maguire

Автор bully....maguire, 4 года назад, По-английски

I usually make observations whenever i am not able to solve some problem.

In round 682 , I found that problem C,D,E were not solved by many people but after hints and editorials was given lot of people upsolved them.

Let us take problem E :

I was not able to solve this problem on my own . But if we see the editorial , it's just based on simple observation that sum of elements should have bit higher than border elements . Prove for efficiency is also very easy.

I did not asked these questions to myself while solving the problem.

Usually i see that i have solve lot problems before i am able to solve some problem of similar type.But this way of practicing will take lot of time to become good coder.

You see that understanding the solution is a cakewalk , but coming up by yourself is difficult . Is this due to laziness i.e out brain not used to it ?

So i ask people for their opinions on it.

I would also like to hear the suggestions of people of all colors (from unrated,newbie to LGM).

I have watched stream of these red coders and i see that they solve problems without much thinking but i am sure this was not the case when they were 2 to 3 year experienced in the field.

I genuinely want you people opinions. After getting around -15 votes it will automatically become invisible from recent actions.

  • Проголосовать: нравится
  • -26
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Don't tag me for help with random problem. I answer CF blogs when I have time.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -34 Проголосовать: не нравится

    I don't insist anyone for giving help . I only ask . Be less rude man. If people can bring you to top of ladder they can also pull you down.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      I don't have to help you just because I got a lot of upvotes in Codeforces. It's rude to claim otherwise.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится -29 Проголосовать: не нравится

        Let me clarify this and repeat part of comment : I did not liked the part of your comment Don't tag me for help with random problem.

        It's completely fine if you don't want to help me , but if you are famous person then most likely people will tag you . You can choose to not help since everyone time is limited.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +18 Проголосовать: не нравится

          If a lot of people tag me, I will just stop looking at my notifications. I would prefer a situation where I'm tagged about my problems or it's something really related to me.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится -15 Проголосовать: не нравится

            I am pretty much sure when you started your you tube channel you would have never said that. People change with time i know.

            I have seen you commenting on similar posts and thus i tagged you .But i know you don't need to comment now since gap between you and SecondThread is 10.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I also had similar type of issue in this contest, I was unable to come up with correct approach for D during contest, but after words reading editorial I realized I was approaching this problem in totally wrong way. I think, someone who solve this type of problems easily should suggest some ways/techniques for practice/thinking for relative topics. It would be really helpful for people like me :)

»
4 года назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

For problem C, it helps to think of the grid graph: squares are vertices, edges are drawn between neighboring squares. You may have previously encountered its property we need: the graph is bipartite, so it can be colored using only two colors such that neighbors have different colors. Visualizing the whole board as a chessboard, with its black and white squares, also helps.


For problem D, it helps to look at some general characteristics of the array, trying to find invariant properties. Specifically, what remains constant after the allowed operation? One such property is the xor-sum of the whole array. Now remember that a xor a = 0, a xor a xor a = a, and such. What you get is that, for an odd array, in the end, its xor-sum should be equal to every element, and for an even array, its xor-sum should be zero. Now we see, in particular, that any even-length array with xor-sum not equal to zero gives the answer NO.

Let's focus on odd arrays then. Next, we will try to get any one value which would be equal to $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$. To do that, we can xor $$$(a_1, a_2, a_3)$$$, then xor $$$(a_3^{\mathrm{new}}, a_4, a_5)$$$, then $$$(a_5^{\mathrm{new}}, a_6, a_7)$$$, and so on. In an odd array, what we get for $$$n = 7$$$, for example, is

a_1  ->  a_1 ^ a_2 ^ a_3
a_2  ->  a_1 ^ a_2 ^ a_3
a_3  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5
a_4  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5
a_5  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_6  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_7  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7

Now we can spread the last element back: for example, xor-ing the current values of $$$(a_3, a_4, a_5)$$$ makes them all equal to the xor-sum of all array. Then xor the current values of $$$(a_1, a_2, a_3)$$$ to get them all equal.

The final observation is how it helps with an even-length array. Let us do what we already learned to do, for the odd part, and the last element will remain untouched. So for $$$n = 8$$$, for example, the array looks like this:

a_1  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_2  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_3  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_4  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_5  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_6  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_7  ->  a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7
a_8  ->  a_8

But as the xor-sum is zero (otherwise, we already know to answer NO), we see that a_1 ^ a_2 ^ a_3 ^ a_4 ^ a_5 ^ a_6 ^ a_7 must now be equal to a_8. The actual program might go the other way, comparing them and writing YES or NO as the result.


For problem E, the key idea for me was something like this. Let us fix one end of the subarray, and move the other one away. Suppose we have the inner sum $$$S$$$ equal to the xor-sum of the border values. Then we include one of the border values in the sum. If the included border was large, then the sum increased significantly (to somewhere around $$$2S$$$). So there are only few such events (on the order of $$$\log_2 (10^9)$$$).

I didn't manage to do the next nice observation and the neat symmetric solution, but got something along the above lines, presumably working in $$$O (n \log^2 n)$$$, with another $$$\log n$$$ factor resulting from binary search.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    You explained that better than editorial.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Thanks for the proper and detailed explanation. can you please elaborate more approach for E?
    I am not getting how you are including border values in sum and how it is depended on inner sum.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      In problem E , suppose one of the good subarray is $$$[l,r]$$$.Now according to the definition of good subarray , $$$(r-l)>=2$$$ . Also $$$a_l$$$ xor $$$a_r = a_{l+1}+a_{l+2}....a_{r-1} = S$$$ (I am denoting the sum by $$$S$$$).

      Without loss of generality , suppose maximum bit which is set in $$$a_l$$$ or $$$a_r$$$ is $$$b$$$. If $$$S$$$ has a set bit position higher than $$$b$$$ then $$$[l,r]$$$ is not good since maximum set bit in $$$a_l$$$ xor $$$a_r$$$ is $$$b$$$ .

      Now , set a left position $$$l$$$ with highest set bit $$$b$$$ and you want to find all such position $$$r$$$ such that $$$[l,r]$$$ is good and highest set bit in $$$a_r$$$ is atmost $$$b$$$.

      You can prove that for a given $$$b$$$ a position $$$r$$$ won't be visited more than twice , because suppose it has been for three distinct $$$l$$$ with highest set bit $$$b$$$ , say $$$l_1<l_2<l_3<r$$$ then sum of $$$a_{l_2} + a_{l_3}$$$ will have bit higher than $$$b$$$ and thus $$$[l_1,r]$$$ won't be good.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Thanks a lot Gassa

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sir, can you kindly explain the dfs approach for problem C?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Huh. Perhaps it's the bipartite coloring algorithm?..

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      It is setting up 2sat graph and dfsing from each unmarked vertex and marking them based on what state you hit the vertex first in a dfs. Think of whether you add 1 to position or not as boolean value and how you can make 2sat equation based on whether you add 1 to it and the positions adjacent to it values. If you don't know 2sat, I recommend reading up on cp-algorithms.