atcoder_official's blog

AtCoder Beginner Contest 349 Announcement
By atcoder_official, history, 7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Instresting survey.=)

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why a different scoring distribution?

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

GLHF & Guess

Good :
OK, not bad :
Bad :

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope Everyone one got a AK!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GL&HF!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← 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
»
7 months ago, # |
  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
  • »
    »
    7 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

    → Reply
  • »
    »
    7 months ago, # ^ |
    ← 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
    • »
      »
      »
      7 months ago, # ^ |
        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
      • »
        »
        »
        »
        7 months ago, # ^ |
          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
      • »
        »
        »
        »
        7 months ago, # ^ |
          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
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          Was wrong sadly :D

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.

→ Reply
»
7 months ago, # |
  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
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, what's PIE?

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

        → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got it. Thanks! Also learned it, awesome concept

        → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
»
7 months ago, # |
  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 > 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
  • »
    »
    7 months ago, # ^ |
    ← 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
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Hacker Move Sir!!

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

      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 ?

      → Reply
  • »
    »
    7 months ago, # ^ |
    ← 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
»
7 months ago, # |
← 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
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    1 1
1

    Your code prints 2, the answer is 1.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thank you , I shoud handle the case when m = 1 separately.

      → Reply
»
7 months ago, # |
  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
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me why https://atcoder.jp/contests/abc349/submissions/52364933 got ac while https://atcoder.jp/contests/abc349/submissions/52364920 got wa?

→ Reply
»
7 months ago, # |
← 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
»
7 months ago, # |
  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
»
7 months ago, # |
  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