AtCoder Beginner Contest 349 Announcement

7 месяцев назад, # |

was f related to sos dp?? how to solve f??

→ Ответить

brenner1

7 месяцев назад, # ^ |

← Rev. 3 →

+33

Consider the way of computing LCM by taking the maximum of exponents in prime factorization. For example, $$$LCM(2^{3} \cdot 3^{5}, 2^{4} \cdot 3^{1}) = 2^{max(3, 4)} \cdot 3^{max(5, 1)}$$$. Factorize $$$M$$$ and compute $$$num_i = prime_i^{exponent_i}$$$ in $$$M$$$. If some $$$a_i$$$ does not divide $$$M$$$, we can ignore $$$a_i$$$ (the exponent of some prime is bigger in $$$a_i$$$ than in $$$M$$$). For each $$$a_i$$$ that divides M, let's assign a bitmask to it. The j-th bit will be on if $$$num_j$$$ divides $$$a_i$$$. If it does not divide, it means that $$$a_i$$$ has a lower exponent on this prime that in $$$M$$$, so choosing $$$a_i$$$ in a subsequence won't contribute into getting LCM = $$$M$$$ in this particular prime. Note that this mask will have at most $$$13$$$ bits. So now your problem is: given some bitmasks, count in how many ways you can choose a subset of these bitmasks such that their bitwise OR is equal to the complete bitmask. We can do this with DP. $$$dp_{mask}$$$ = how many ways there is to choose a subset of bitmasks to form $$$mask$$$. This can be done by iteratively considering each bitmask, for a total of $$$O((2^{k})^{2})$$$, where $$$k = 13$$$. Submission

→ Ответить

7 месяцев назад, # ^ |

← Rev. 3 →

deleted

→ Ответить

7 месяцев назад, # ^ |

← Rev. 2 →

deleted

→ Ответить

7 месяцев назад, # |

-18

What is any adequate time complexity solution to F? How to solve it in any way other than fucking constant optimizing O(d(m) * 2^P) (where p is nr of distinct prime divisors of m)?

→ Ответить

7 месяцев назад, # ^ |

-10

upd: why would you allow factorizing in O(sqrt(1e16))?

→ Ответить

Rideris

7 месяцев назад, # ^ |

← Rev. 2 →

I did it in $$$O(4^P)$$$ xd

upd: as for factorization, i copied fastest code on Library Checker.

→ Ответить

7 месяцев назад, # ^ |

yeah, after reading others' codes already realized it was possible

which, however, raised question about why would anyone intentionally set such constraints for M if factorizing in O(sqrt) was intended

→ Ответить

Rideris

7 месяцев назад, # ^ |

most probably because then there can be at most 13 distinct prime divisors for $$$m$$$, then that will cut off some unintended solutions? idk

→ Ответить

Dominater069

7 месяцев назад, # ^ |

my code takes 300ms, 1e8 really isnt a lot of operations.....

they set such constraints to allow sqrt factor but not allow O(4^p) [it didnt work tho ig, sad]

→ Ответить

7 месяцев назад, # ^ |

I believed 4^p can't work slower than 1e8 operations with modulo...

Was wrong sadly :D

→ Ответить

Dominater069

7 месяцев назад, # ^ |

oh 4^p isnt intended though? i have 3^p

→ Ответить

ComeIntoCalm

6 месяцев назад, # ^ |

it can be solved in $$$O(13^2\times(2^{13}))$$$ by fast mobius transform indeed, and the other bound is checking all divisors of $$$M$$$ in $$$a_i$$$.

→ Ответить

ash432

7 месяцев назад, # |

How can I see the testcases? When will it be available in this link https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0

→ Ответить

rock_nroll

7 месяцев назад, # |

Can anyone please explain the solution of F-Subsequence LCM.

→ Ответить

akshatjoshi

7 месяцев назад, # |

Can anybody tell why does this submission https://atcoder.jp/contests/abc349/submissions/52354451 TLE?

→ Ответить

Repkironca

7 месяцев назад, # ^ |

I think your problem lies in floor(log2()), as it calculates the 'exact value' before taking the floor, and this wastes too much time when N is as big as 2^60. I modified your code and achieved an AC here: https://atcoder.jp/contests/abc349/submissions/52361678. (Actually, you don't even need to conduct << if using binary exponentiation)

→ Ответить

akshatjoshi

7 месяцев назад, # ^ |

Ah, Thanks for the help!

→ Ответить

Repkironca

7 месяцев назад, # |

← Rev. 2 →

I think I did something wrong since I can't understand second the example of pE. Let's say Takanashi chose {1, 1}, {1, 3}, {2, 1}, {2, 2}, and {3, 2} (1-based, define the top-left corner as {1, 1}), than it's a draw. He got -1 +0 -4 -2 -1 = -8 points, while Aoki got -13 points, how can the answer be Aoki?

btw can we really define " play optimally for victory" ? In real world, we'll think much. For instance, we try to avoid our opponents from getting an " L-shape ".

Answers by brute force will keep every possibilities that is a draw, including the unreasonable ones.

→ Ответить

little_dog

7 месяцев назад, # |

F could be solved with PIE and bitset in $$$\mathcal O(\sqrt m + \dfrac{2^kn}{w})$$$ ($$$k = 13$$$ here)

→ Ответить

drgrenkenstein

7 месяцев назад, # ^ |

Sorry, what's PIE?

→ Ответить

7 месяцев назад, # ^ |

Principle of Inclusion-Exclusion. You can read about it CP Handbook

→ Ответить

kadamrohan0215

7 месяцев назад, # ^ |

← Rev. 2 →

I used the same logic still i am getting 9 TLE and 2 WA. Can you point out the mistake?? My Submission

→ Ответить

7 месяцев назад, # ^ |

int overflow.

Spoiler

for(int i = 2; i*i <= x; i++){

→ Ответить

kadamrohan0215

7 месяцев назад, # ^ |

Thanks issue solved.

→ Ответить

drgrenkenstein

7 месяцев назад, # ^ |

Got it. Thanks! Also learned it, awesome concept

→ Ответить

Insanity_123

7 месяцев назад, # ^ |

aryan can you briefly explain your PIE ? I understood till where we represent each number as mask of exponents of prime of M. We essentially want to calculate or sum to all bits set, calculating this in 4^k where k is number distinct primes is easy, how do we use IE here in terms of each bit and what is to be included/excluded ?

→ Ответить

little_dog

7 месяцев назад, # |

And there is an easy greedy solution for G:

Lets iterate $$$i$$$ from $$$1 \to n$$$:

If position $$$i$$$ is covered by previous positions (i.e. there exists $$$j$$$ that $$$j + a_j > i$$$), then we already know $$$s_i$$$. Then, add a constraint $$$s_{i+a_i-1} \ne s_{i-a_i+1}$$$.
Else, find the smallest number $$$x$$$ that satisfying all constraints and let $$$s_i = x$$$. Then add a constraint $$$s_{i+a_i-1} \ne s_{i-a_i+1}$$$.

It is not hard to prove that if the solution exists, we can find the smallest one by this.

How to check if the solution exists? We can simply run a manacher to check it.

Time complexity : $$$\mathcal O(n)$$$.

→ Ответить

7 месяцев назад, # ^ |

← Rev. 2 →

+37

My idea is completely different.
My solution was an extension of my submission of 103388L - Listing Passwords

My idea was as follows -
We create a DSU size $$$2*N$$$.
Nodes in the same component denote that values at those places are same.
We start by merging $$$i$$$ and $$$2*N-i-1$$$ in DSU.
Now, $$$S[L,R]$$$ is a palindrome if $$$S_L=S_R$$$, $$$S_{L+1}=S_{R-1}$$$, $$$S_{L+2}=S_{R-2}$$$, and so on...
Let $$$U=L$$$ and $$$V=2*N-R-1$$$
Because of the above merge nodes, we can also merge $$$U+i$$$ with $$$V+i$$$ for each $$$0 \le i \le R-L$$$

Doing this natively with just one DSU will lead to TLE.
So, we maintain $$$\log N$$$ DSU.
If $$$L$$$ and $$$R$$$ are in the same component in $$$i$$$ DSU. It denotes, $$$(L+j,R+j)$$$ are in the same component for each $$$0 \le j \lt 2^i$$$.
We can split $$$(U+j,V+j)$$$ merging into $$$O(\log R-L+1)$$$ different merges of sizes of powers of 2.

At last, if any conflicting pair is in the same component we print NO. Otherwise, the answer is YES.
We can greedily find an assignment for YES.
My submission

→ Ответить

Snapper_001

7 месяцев назад, # ^ |

Hacker Move Sir!!

→ Ответить

lnw143

6 месяцев назад, # ^ |

← Rev. 2 →

Should the time complexity of the function mergeSeg2() in your code be $$$O(n \log n)$$$ ?

if so, how to prove that it wouldn't TLE ?

→ Ответить

7 месяцев назад, # ^ |

← Rev. 2 →

great solution, i was trying to do something like this only but rather than checking this(there exists j that j+aj>i) i was trying to greedily put choose si and then choose all j such that j>i && j-aj<=i, but could not think of quick way of doing it, you solution is good.

→ Ответить

Mr_7ammoda

7 месяцев назад, # |

← Rev. 3 →

could somebody help why this submission WA or provide a test case for problem F?
https://atcoder.jp/contests/abc349/submissions/52362844

→ Ответить