Блог пользователя chokudai

Автор chokudai, история, 12 месяцев назад, По-английски

We will hold AtCoder Beginner Contest 296.

We are looking forward to your participation!

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Looking forward to participate and getting most of it

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

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

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

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

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

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

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

    Can you give a hint for E?

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

      I looked for cycle, got idea from the odd-even explanation of the last test case.

    • »
      »
      »
      12 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Spoiler

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    How did you approach G?

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

      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.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain the proof of D in more detail?

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

    Why does imposing a <= b does not restrict set of integers?

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In D, i did binary search

My thought process was like from the array[1,2,3,...N] we will take l=1, r=N take mid as (l+r)/2 , then WLOG consider mid as "a" then select b from the array as ceil (M/a) , if my b <=N , then our ans will be a*b ans we will move to the left of search space , otherwise will move to the right of search space

I am not able to think why this is not working i am not able to think of any corner case.

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

    There is a proof of why it works in editorial but it's confusing, if you understood the proof please explain it to me!

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

    Can you explain the approach?

    • »
      »
      »
      12 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
      Step 1