maroonrk's blog

AtCoder Regular Contest 167 Announcement
By maroonrk, history, 6 months ago, In English

We will hold AtCoder Regular Contest 167.

The point values will be 300-500-700-700-800-1200.

We are looking forward to your participation!

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

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Why is F given 1200 score...

→ Reply
»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Wish I won't drop back to 1 Kyu.

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

emm...

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

Stuck at C for more than 45 minutes before trying D and realizing that it is pretty doable.

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

Is there any O(T) solution for E?

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

    Oh I found such a submission. I only thought of solutions for S=2k,3k,3k+2, but there's a simple solution for S=2k+1.

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

    In fact only one in-contest submission used extended gcd while the other 12 are $$$O(T)$$$

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

my last formula of my sol is similar to editorial >>why it give me wa on B

my solution
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Because ans may not be even before you divide by 2. Correct answer is floor(ans/2).

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

can anyone explain about this? It seems that there exict a O(1) solution of problem E. https://atcoder.jp/contests/arc167/submissions/46638239

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

Can anyone get me clear on the concept behind B? i did not get the editorial

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

Can anyone please explain why is my submission getting TLE for some cases where as it is running under 2 ms for all other cases.

I'm doing exactly what editorial says : B * product of (e_i * B + 1) for all powers of prime factors, finally dividing it by 2.

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

    Overflow probably

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

      Yes, indeed it is. for loop condition : j * j <= A got overflowed thus making it endless loop.

      Thanks a lot for the help!!

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

why my solution fails?: problem B

my approach: we gonna factorize A and focus on one prime from the factorization: I need to know how mcuh p there is in the product of the divisors of a^b suppose a=p^k * .. so the number of this prime in the product is: (sum from 1 to k*b)* product of (ki +1) where ki is the power of the otehr primes sequencially.

after that I just divide by k why this fails? : https://atcoder.jp/contests/arc167/submissions/46638531

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

    It's wrong. You don't divide by k, you multiple by B then divide by 2. You also have to make sure if the number is odd before dividing by 2. This is doable by checking if all the numbers you're multiplying are odd

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

Can someone explain solution of problem C?

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

    I will try to explain my $$$O(n^2)$$$ solution, which is independent of $$$k$$$ in the problem. The editorial lists a different $$$O(n(k+\log n))$$$ solution.

    My solution relies on the following observation, for fixed permutation $$$p$$$ applied to the array of values $$$A$$$:

    There exists an MST where for each index $$$j \gt 1$$$ , there is an edge from $$$j$$$ to the index with the minimum value (after having applied the $$$p$$$ to $$$A$$$) among $$$A[j-k], A[j-k+1] \dots A[j-1]$$$.

    To prove it, you can apply induction and in the inductive step, we can apply an exchange argument that relies on the fact that in the MST, the suffix from $$$j$$$ will be connected to the prefix before $$$j$$$. So you can apply the exchange argument according to which edge from the suffix component you remove and replace with the edge from $$$j$$$ to its prefix.

    After this observation, the problem becomes simple: fix index $$$j$$$ and value of element $$$i$$$, and then count how many arrays exist with $$$max(A[j], min(A[j-k], A[j-k+1] \dots A[j-1])) = i $$$.

    Submission

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

I think problem E would be a good math problem, but I don't think it's a good CP problem. It's so tricky that you can find 4 people who's rating is under 1600 among 13 people who solve the problem during the contest:(

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

About Problem B :Can anyone tell me why I set the mod 998244353 the answer was WA,but when I changed it to 998244353*2 ,it was AC ?

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

I wonder how the checker.cpp of problem E is implemented.

In other words, how to calculate the number of squares in a triangle satisfying the restrictions mentioned in the problem.

→ Reply