### chokudai's blog

By chokudai, history, 2 months ago,

We will hold AtCoder Beginner Contest 296.

We are looking forward to your participation!

• +47

 » 2 months ago, # |   0 Looking forward to participate and getting most of it
 » 2 months ago, # |   0 How to solve F?
•  » » 2 months ago, # ^ | ← 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)$.
 » 2 months ago, # | ← 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.
•  » » 2 months ago, # ^ |   +3 I looked up for a and b upto sqrt(m).
•  » » 2 months ago, # ^ |   0 Can you give a hint for E?
•  » » » 2 months ago, # ^ |   0 I looked for cycle, got idea from the odd-even explanation of the last test case.
•  » » » 2 months ago, # ^ | ← 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.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 2 months ago, # ^ |   0 I think he wins iff i is in a circle.
•  » » » » » 2 months ago, # ^ |   0 Sorry, critical typo.
 » 2 months ago, # | ← Rev. 2 →   0 Spoilerif(n*n=m){ res = min(res,i*y); } } cout<
•  » » 2 months ago, # ^ |   0 I faced this 5 WA too. The solution is to check if n*n is overflow.
•  » » » 2 months ago, # ^ |   0 how to fix it did you use sqrt to compare and in result did you use LLONG_MAX?
•  » » » » 2 months ago, # ^ |   0 Yes, my submission
•  » » 2 months ago, # ^ |   0 can you tell what your ceil does?
•  » » » 2 months ago, # ^ |   0 ll ceil(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} 
•  » » 2 months ago, # ^ |   +1 n can be 1e12. n*n can become 1e24 which is too big.
•  » » 2 months ago, # ^ |   0 change if(n*n
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 worked thank you guys!!! didn't think of overflow during contest!! 😭
•  » » 2 months ago, # ^ |   0 what was the reason for checking it only till root m?
 » 2 months ago, # |   0 In $G$ was killed by just only one case: when query point is equal to rightmost point in polygon.
•  » » 2 months ago, # ^ |   0 How did you approach G?
•  » » » 2 months ago, # ^ |   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.
 » 2 months ago, # | ← Rev. 2 →   0
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 Can someone explain the proof of D in more detail?
•  » » 2 months ago, # ^ |   0 Why does imposing a <= b does not restrict set of integers?
 » 2 months ago, # | ← 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 spaceI am not able to think why this is not working i am not able to think of any corner case. SpoilerAfter bunch of WA, i just guessed and traversed from 1 to 1e6 and for every "a" keep finding b and updating ans as a*b. I dont know why it works, but it works
•  » » 2 months ago, # ^ |   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!
 » 2 months ago, # |   0 https://atcoder.jp/contests/abc296/submissions/40253903 can someone give a example where this fails.
•  » » 2 months ago, # ^ |   +3 3 2 3 2 The answer is 2
•  » » » 2 months ago, # ^ |   0 Thanks achvanov
 » 2 months ago, # |   +3 Submission — one of the shortest solution to problem E using binary jumps
•  » » 2 months ago, # ^ |   0 Can you explain the approach?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +3 Step 1If $i$ is on a cycle, then we always win. Step 2If $i$ is outside of the cycle, then our opponent can pick $k_i = N$ and he always wins. Step 3Pair of intersected cycles don't exist in this graph. Step 4So, the answer is the sum of lengths of cycles. FinallyLet's do $2^{20}$ (or $2^{30}$, or $2^{60}$ — some value, which we can choose) steps for each vertex with using Binary Jumps technique. We will finish on the cycle (always) for each vertex. No one vertex on cycle will be missed because we are doing equal number of steps. Total number of distinct results (set.size()) is the total number of vertex on cycles — answer on the problem.
•  » » » » 2 months ago, # ^ |   0 amazing!! thanks a lot! the problem basically reduced to topo sorting. Awesome problem!
•  » » » » 2 months ago, # ^ |   0 How can we always win if i is on a cycle
•  » » » » » 2 months ago, # ^ |   0 Take such vertex on the cycle which will equal $i$ after $k_i$ steps