### atcoder_official's blog

By atcoder_official, history, 6 weeks ago,

We will hold AtCoder Beginner Contest 349.

We are looking forward to your participation!

• +59

 » 6 weeks ago, # |   0 Good luck to everyone!
 » 6 weeks ago, # |   0 GLHF!
 » 6 weeks ago, # |   0 Instresting survey.=)
 » 6 weeks ago, # |   0 why a different scoring distribution?
 » 6 weeks ago, # | ← Rev. 2 →   -18 GLHF & GuessGood : OK, not bad : Bad :
 » 6 weeks ago, # |   0 GLHF!
 » 6 weeks ago, # |   0 Hope Everyone one got a AK!
 » 6 weeks ago, # |   0 GLHF!
 » 6 weeks ago, # |   0 GL&HF!
 » 6 weeks ago, # |   0 was f related to sos dp?? how to solve f??
•  » » 6 weeks ago, # ^ | ← 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
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 deleted
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 deleted
 » 6 weeks ago, # |   -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)?
•  » » 6 weeks ago, # ^ |   -10 upd: why would you allow factorizing in O(sqrt(1e16))?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +8 I did it in $O(4^P)$ xdupd: as for factorization, i copied fastest code on Library Checker.
•  » » » 6 weeks ago, # ^ |   +1 yeah, after reading others' codes already realized it was possiblewhich, however, raised question about why would anyone intentionally set such constraints for M if factorizing in O(sqrt) was intended
•  » » » » 6 weeks ago, # ^ |   0 most probably because then there can be at most 13 distinct prime divisors for $m$, then that will cut off some unintended solutions? idk
•  » » » » 6 weeks ago, # ^ |   0 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]
•  » » » » » 6 weeks ago, # ^ |   0 I believed 4^p can't work slower than 1e8 operations with modulo...Was wrong sadly :D
•  » » » » » » 6 weeks ago, # ^ |   0 oh 4^p isnt intended though? i have 3^p
•  » » » » » » » 5 weeks ago, # ^ |   0 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$.
 » 6 weeks ago, # |   0 How can I see the testcases? When will it be available in this link https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
 » 6 weeks ago, # |   0 Can anyone please explain the solution of F-Subsequence LCM.
 » 6 weeks ago, # |   0 Can anybody tell why does this submission https://atcoder.jp/contests/abc349/submissions/52354451 TLE?
•  » » 6 weeks ago, # ^ |   0 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)
•  » » » 6 weeks ago, # ^ |   0 Ah, Thanks for the help!
 » 6 weeks ago, # | ← Rev. 2 →   0 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.
 » 6 weeks ago, # |   +3 F could be solved with PIE and bitset in $\mathcal O(\sqrt m + \dfrac{2^kn}{w})$ ($k = 13$ here)
•  » » 6 weeks ago, # ^ |   0 Sorry, what's PIE?
•  » » » 6 weeks ago, # ^ |   0 Principle of Inclusion-Exclusion. You can read about it CP Handbook
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 I used the same logic still i am getting 9 TLE and 2 WA. Can you point out the mistake?? My Submission
•  » » » » » 6 weeks ago, # ^ |   +6 int overflow. Spoilerfor(int i = 2; i*i <= x; i++){ 
•  » » » » » » 6 weeks ago, # ^ |   0 Thanks issue solved.
•  » » » » 6 weeks ago, # ^ |   0 Got it. Thanks! Also learned it, awesome concept
•  » » » » 6 weeks ago, # ^ |   0 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 ?
 » 6 weeks ago, # |   +4 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)$.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +37 My idea is completely different.My solution was an extension of my submission of 103388L - Listing PasswordsMy 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
•  » » » 6 weeks ago, # ^ |   +3 Hacker Move Sir!!
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 6 weeks ago, # | ← Rev. 3 →   0 could somebody help why this submission WA or provide a test case for problem F?https://atcoder.jp/contests/abc349/submissions/52362844
•  » » 6 weeks ago, # ^ |   0 1 1 1 Your code prints 2, the answer is 1.
•  » » » 6 weeks ago, # ^ |   +8 Thank you , I shoud handle the case when m = 1 separately.
 » 6 weeks ago, # |   -8 void yes() { cout<<"Yes\n"; } void no() { cout<<"No\n"; }int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); string S; string T; cin>>S>>T; int val=0; string t=to_lower(T); for(auto x:t){ size_t pos=S.find(x); if(pos!=string::npos){ val++; } } if(val==3||(val==2&&(T.back()=='X'))) yes(); else no();return 0; }anyone please what's wrong in this can't figure it ?? Problem C .
•  » » 6 weeks ago, # ^ |   0 the order of letter in S or T should be same lac LCA
•  » » » 6 weeks ago, # ^ |   0 got,it. thanks!!
 » 6 weeks ago, # |   0 can anyone tell me why https://atcoder.jp/contests/abc349/submissions/52364933 got ac while https://atcoder.jp/contests/abc349/submissions/52364920 got wa?
 » 6 weeks ago, # | ← Rev. 2 →   0 Can someone tell me where I went wrong ? https://atcoder.jp/contests/abc349/submissions/52354647
•  » » 6 weeks ago, # ^ |   0
•  » » » 6 weeks ago, # ^ |   0 I didn't get this ? okay just a comment ?
 » 6 weeks ago, # |   0 why in problem $D$ always taking the largest power of two that divides works? Any proof?
 » 5 weeks ago, # |   0 When will the official editorials be translated into English? Youtube is prohibited in Chinese Mainland..