atcoder_official's blog

AtCoder Beginner Contest 425 Announcement
By atcoder_official, history, 12 months ago, In English

We will hold UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 425).

We are looking forward to your participation!

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
12 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Good Luck & Have Fun~!

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

ABC is so cute awa.

Hope can AC E

:D

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

GLHF everyone!

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

GOOD LUCK TO EVERYONE!!

→ Reply
»
12 months ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

qp

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

Good contest. My last participation in ABC is about 1.5 years ago. Hope I'll get to 1000 rating.

G is a good problem but I can't solve it :(

Good luck for every one!

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

Is O((2^n)*n) supposed to be TLE in F?

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

How to solve $$$E$$$?

→ Reply
  • »
    »
    12 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it
    $$$ \text{Answer}=\dfrac{\left(\sum_i C_i\right)!}{\prod_i(C_i!)} $$$
    → Reply
    • »
      »
      »
      12 months ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      yeah I did just that along with the fact that there're like 669 prime under 5000 then doing some stupid optimization like using gp_hash table in stead of map to eliminate log factor, adding superstitious pragma 👀 then pray it to AC since it keeps failing the last(51th) case, then finally got it in the 3rd submission after precaling some function I need in 2-dimentional array 😭

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

        You can implement a handwritten 'prime factorization' class, and that way you can easily pass problem E

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

      Actually python will get TLE because of this. (I try to use this during the contest but failed all the time)

      You need to use alternative way if you are using python, if frequency is f1, f2, f3, f4... fn, then answer = comb(f1,f1) * comb(f1+f2, f2) * comb(f1+f2+f3, f3) ..... * comb(f1+..+fn, fn), and you can precompute the comb using the formula comb(i,j) = comb(i-1,j) + comb(i-1,j-1).

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

How long will rating get updated?thx

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

Thanks for the nice problems.

Screencast of me solving the problems. Solved A-F. Very close to solving G (submitted a TLE solution just before the contest ended — had to do memoization and it got AC). https://www.youtube.com/watch?v=Pv3beKRAGhY

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +14 Vote: I do not like it

Bad E.

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

Bad E. Why can't you give us a prime $$$M$$$?

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

Fail to upgrate to 1 Dan again :(

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

I think E had a bad quality where it doesnt implicitly tell you that you have to precalc binomials. I told myself that multitest times 5k factorizations should be enough and got 50/51 ac 1/51 tle. My idea was to say that answer is $$$\frac{sum!}{c_1! \cdot c_2! \cdot \ldots}$$$ do two pointers and keep track of how many factorials contain each number from 1 to $$$sum$$$, so i know how much it contributes to the answer. Limits are tight enough so this doesn't pass and not tight enough to convince me the approach shouldn't work and I should do something else instead.

F's intended solution is nice. I just AC'ed hashset to keep track which transitions I already used.

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

Solved all problems in this round, but I hadn’t done that before.

I hope my account won’t be banned.

It’s absolutely not the case that I cheated in contests. Why I’m asking here is just because I’ve seen previous incidents when the commenter did nothing wrong and was inadvertently banned

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

Don't laugh.If u laugh,you will get TLE on this kind of ***t problems.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Can we please get editorial for G ?

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

    My solution:

    Consider solving for a fixed $$$x$$$ first.

    We can build a trie of $$$A$$$ then traverse it to find the $$$A_j$$$ that minimize $$$x \oplus A_j$$$. Which can be found it the following manner:

    Start from the root, and assume the current bit we are consider is $$$i$$$-th bit.

    • if there is a child correspond to the $$$i$$$-th bit of $$$x$$$, go to that child
    • otherwise, go to the only child, which will incur $$$2^i$$$ cost because $$$i$$$-th bit of $$$x \oplus A_j$$$ must be $$$1$$$.

    Then to deal with all $$$x \in [0, M)$$$, notice that all $$$x$$$'s go to a child would still be consecutive under $$$\pmod {2^i}$$$, so to maintain all $$$x$$$'s go to a child, we store (first term of the consecutive $$$x$$$'s, the number of $$$x$$$'s) then everything can be dealt easily. (ex. $$$(2, 7)$$$ under $$$\pmod {2^2}$$$ represent $$$[2, 3, 0, 1, 2, 3, 0]$$$)

    More specifically, we start from root with $$$(0, M)$$$ and traverse the trie with a BFS. Assume we have $$$(s, len)$$$ currently.

    • if there is two children, split all integers in $$$(s, len)$$$ into two group by their $$$i$$$-th bit, then send two group to their respective children.
    • otherwise send all integers to the only children, if the only child represent $$$1$$$, this would incur a cost of $$$2^i \cdot (\text{the number of integers in (s, len) with i-th bit being 0})$$$, and vise versa.
    → Reply
  • »
    »
    12 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +4 Vote: I do not like it

    My solution of this G is a simple divide and conquer algorithm.
    In the below,we extend every a to 30 digits.
    Consider this greedy algorithm:There is a fixed x,you want to find the minimum value of $$$x\oplus a[i](l\le i\le r)$$$ which is guaranteed that the first t-1 digits of $$$a[i](l\le i\le r)$$$ are the same
    Let the answer be $$$x\oplus a[i_0]$$$
    if the t-th digit is same among $$$a[i](l\le i\le r)$$$:add 1 from t
    otherwise:$$$a[i_0]$$$ must have the same t-th digit with x
    Sort a in increasing order,let $$$f(m,l,r,t)=\sum\limits_{x=0}^{m-1}\min\limits_{l\le i\le r}((x\oplus a_i)\bmod 2^t)$$$.The transition is easy.

    my code

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

Who knows how to solve G?

→ Reply