atcoder_official's blog

AtCoder Beginner Contest 349 Announcement
By atcoder_official, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 349.

We are looking forward to your participation!

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

Comments Comments (36)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

GLHF!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Instresting survey.=)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

GLHF!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +33 Vote: I do not like it

    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

    → Reply
»
2 years ago, hide # |
 
Vote: I like it -18 Vote: I do not like it

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)?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -10 Vote: I do not like it

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

    → Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +8 Vote: I do not like it

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

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

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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]

        → Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +37 Vote: I do not like it

    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

    → Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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 .

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Can someone tell me where I went wrong ? https://atcoder.jp/contests/abc349/submissions/52354647

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why in problem $$$D$$$ always taking the largest power of two that divides works? Any proof?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

When will the official editorials be translated into English? Youtube is prohibited in Chinese Mainland..

→ Reply