chokudai's blog

AtCoder Beginner Contest 296 Announcement
By chokudai, history, 21 month(s) ago, In English

We will hold AtCoder Beginner Contest 296.

We are looking forward to your participation!

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

Comments Comments (28)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Key observation $$$1$$$: Swapping $$$(i, j)$$$ in $$$A$$$ and $$$(i, k)$$$ in $$$B$$$ is equal to swapping $$$(i, k)$$$ in $$$B$$$ first followed by swapping $$$(i, j)$$$ in $$$B$$$. Therefore, we can always fix $$$A$$$ and operate on $$$B$$$ to make $$$B$$$ equals to $$$A$$$. Note that $$$(i k)(i j)$$$ could be merged into a rotation of three words, we call them $$$3$$$-rotations.

    Key observation $$$2$$$: The answer is "Yes" iff $$$B$$$ is an even permutation of $$$A$$$. $$$B$$$ always swap even times, so if $$$B$$$ can reach $$$A$$$, $$$B$$$ is an even permutation. On the other hand, it is well-known that the alternative group $$$A_n$$$ (which consists of all even permutations) are generated by $$$3$$$-rotations $$$\{(123), (124), ..., (12n)\}$$$, therefore, if $$$B$$$ is an even permutation, then $$$B$$$ can convert into $$$A$$$.

    Key observation $$$3$$$: If the content of $$$A$$$ and $$$B$$$ are different, it is impossible. Otherwise, if there are duplicate elements in $$$A$$$, it is always possible, as we can add a dummy swap between two elements with the same value to make an even permutation. Finally, we only need to consider the case where all elements are distinct. We can use the merge sort to calculate its inversion number in $$$O(nlogn)$$$.

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

      I didn't get the first obs.,

      can you please elaborate?

      → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Solve $$$A, B, C, E, F$$$ but WA on $$$D$$$ $$$8$$$ times. How $$$D$$$ please?

Upd: I am an idiot. I wrote something like $$$n \times n$$$ which easily overflows.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I looked up for a and b upto sqrt(m).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give a hint for E?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Build a functional graph which consists of edges $$$i \rightarrow a[i]$$$. Then T can win at $$$i$$$ iff $$$i$$$ is in a circle. To find all elements not in a circle we can utilize the toposort.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Can you share your submission? I thought the element which is in circles can be reached whatever the value of k will be. Atcoder editorial is quite complex to understand.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think he wins iff i is in a circle.

        → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Spoiler

what's going wrong in this 51 TestCases Passes and 5 Failed.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I faced this 5 WA too. The solution is to check if n*n is overflow.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    n can be 1e12. n*n can become 1e24 which is too big.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In $$$G$$$ was killed by just only one case: when query point is equal to rightmost point in polygon.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you approach G?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is mostly implementation based problem without any thinking. There is algorithm for checking if point lies in convex polygon.

      First we do cyclic shift on polygon such that its leftmost point becomes minumum. Then for all other point $$$atan2(y[i] - y[0], x[i] - x[0]) \in [-\frac{\pi}{2}, \frac{\pi}{2}]$$$. Then we precalc for every $$$i$$$ this $$$atan2$$$. This is increasing array.

      We have a query point. We have to check in which triangle of points with indices $$$0, i, i+1$$$ does in lie. Use lower_bound to do it in $$$log{n}$$$. Now we have to check, if point is in corresponding triangle and is on corresponding segment. To remove many ifs and epsilons and make life easier, we just apply these checks to all $$$[max(0, i - 3), min(n - 1, i + 3)]$$$.

      Now we only have to check, if point is on segment, and if point is in triangle. This can be done in integers.

      → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

F is similar to 1585D - Yet Another Sorting Problem / 1591D - Yet Another Sorting Problem

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc296/submissions/40253903 can someone give a example where this fails.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Submission — one of the shortest solution to problem E using binary jumps

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the approach?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it
      Step 1
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can we always win if i is on a cycle

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Take such vertex on the cycle which will equal $$$i$$$ after $$$k_i$$$ steps

          → Reply