awoo's blog

By awoo, history, 23 months ago, In English

1772A - A+B?

Idea: BledDest

Tutorial
Solution (BledDest)

1772B - Matrix Rotation

Idea: BledDest

Tutorial
Solution (BledDest)

1772C - Different Differences

Idea: BledDest

Tutorial
Solution (BledDest)

1772D - Absolute Sorting

Idea: BledDest

Tutorial
Solution (BledDest)

1772E - Permutation Game

Idea: BledDest

Tutorial
Solution (Neon)

1772F - Copy of a Copy of a Copy

Idea: BledDest

Tutorial
Solution (awoo)

1772G - Gaining Rating

Idea: BledDest

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +50
  • Vote: I do not like it

| Write comment?
»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

By the way, a more "natural" way to deduce the relations for D (without doing a lot of casework) is to square both sides of the inequality, because if $$$|x| \leqslant |y| \Rightarrow x^2 \leqslant y^2$$$. This gives $$$(a_i - x)^2 \leqslant (a_{i + 1} - x)^2$$$ for all valid $$$i$$$. This implies that $$$a_i^2 - 2a_ix + x^2 \leqslant a_{i + 1}^2 - 2a_{i + 1}x + x^2 \Rightarrow (a_i^2 - a_{i + 1}^2) - 2(a_i - a_{i + 1})x \leqslant 0 \Rightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \leqslant 0$$$, and then we can continue in the same way as editorial.

  • »
    »
    23 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It's more natural to just binary search the answer 185850639 (I suppose)

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      interesting, could you explain your approach a bit in detail?

      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        First, let's denote min(a) as L, max(a) as H and M as (L + H) / 2, it's pointless to look for a solution where x > H or x < L because they will give array of the same (sortness) as H and L. try x = 5, 6 and x = 3, 2 on a = [5, 3, 5] for example, it'll give [0, 2, 0], [1, 3, 1] and [2, 0, 2], [3, 1, 3], respectively. every binary search loop iteration you loop through the array and check for any abs(M — a[i]) < abs(M — a[i — 1]) (which makes the result unsorted obviously), in case we found it we need to prolong the distance between M, a[i] and shorten it between M, a[i — 1] so we updaet H = M — 1 in case a[i] > a[i — 1] or L = M + 1 in case a[i] < a[i — 1]

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

          how do we know when to do h=m-1 or l=m+1

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

            absolute value means distance so if abs(m-a[i]) < abs(m-a[i-1]) that means m was closer to a[i] than a[i — 1] when it should have been further or equal, so we we make it closer to a[i-1]. if a[i] > a[i — 1] we need to make m smaller by doing h=m-1 and vice versa

            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              so we should check all abs(a[i]-m)
              my question is in this case what should i do : a[1]-m<a[2]-m at the same time a[3]-m>a[4]-m

  • »
    »
    23 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    If you want to do it more natural, you can apply difference of squares identity: $$$a^2 - b^2 = (a - b)(a + b)$$$ i.e. $$$(a_i−x)^2\le(a_{i+1}−x)^2 \Leftrightarrow (a_i−x)^2 - (a_{i+1}−x)^2 \le 0 \Leftrightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \le 0$$$

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

I still don't understand the strategy used in Permutation Game. For me at least, the only possible outcome was a tie, because the other player can mess with the correct ordered ones. For example: 1 2 3 5 4 The first one colors 5 1 2 3 B5 4 The second colors any other to not let the first payer win B1 2 3 B5 4 The first color the last element B1 2 3 B5 B4 The second starts to mess the order of elements B5 2 3 B1 B4 And we have at least two elements out of order for player one, and it will require at least two first movements, but for any of them the other player will undo that movement. So what's the strategy?

  • »
    »
    23 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can swap more than two blue elements in one turn. You can reorder them as you want, the only condition is that all red elements stay on their positions.

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought the swap was meant for only two elements, thanks.

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

        Why cant 2nd player win in [2,3,1] . Why the answer is Tie.

        first player [2B,3,1]

        2nd player[2B,3B,1]

        1st player skips

        2nd player exchanges [3B,2B,1]

        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If the starting configuration is [2,3,1], 1st player wouldn't start by making the 2 blue. The game would go like this:

          1st player [2,3,1B]

          2nd player [2B,3,1B]

          1st player skips

          2nd player skips

          1st player skips

          2nd player skips . . .

          Neither player can arramge the numbers in their goal orders, and making the 3 blue would allow the opponent to win, so bot players just skip turns and it's a tie.

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

For Problem G, why can we assume that we require a whole cycle in the reasoning for $$$x+k(p-m) \geq t_p$$$? What if $$$x$$$ exceeds $$$t_p$$$ mid-cycle? Then the number of wins in this particular cycle iteration would be $$$p+1$$$ and not $$$p$$$.

  • »
    »
    23 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    The $$$t_p$$$ is the rating you need at the start of the cycle to be able to win the $$$p$$$-th opponent (i.e. first $$$p+1$$$ opponents). If your $$$x < t_p$$$ at the start of the cycle — you can't win against the $$$p$$$-opponent.

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      can we keep for each i, t[i] = a[i]-i and b[i] = a[i]+1 ?
      instead of if and else in for loop?
      
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Nope, suppose array $$$a = [5, 5, 5, 6]$$$. Arrays $$$t = [5, 4, 3, 3]$$$ and $$$b = [6, 6, 6, 7]$$$ don't make any sense.

»
23 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

The checker got me wrong answer to have the array which is not in ascending order in question C. Is this a bug? 186207153

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

can someone confirm How many operations can we make in one second in codeforces ?

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

1172A- A+B is very easy solution in python 227321207

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

The tutorial for D, the conditions are x <= a[i], and x <= (a[i] + a[i + 1]) / 2 so the union isn't

a[i] <= x <= (a[i] + a[i + 1) / 2.

It had me confused so I'm writing for anybody that might come across the same thing.