atcoder_official's blog

SuntoryProgrammingContest2024（AtCoder Beginner Contest 357） Announcement
By atcoder_official, history, 5 months ago, In English

We will hold SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）.

We are looking forward to your participation!

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

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

Excited and Hoping for the best ABC Round!

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

Auto comment: topic has been updated by atcoder_official (previous revision, new revision, compare).

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

only 5 contributions away from the top-contributors.

→ Reply
»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

wu~hu~qi~fei~

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

glhf

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

Problem E is similar to this!

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

E was exactly same as this. Probably that explains so many submissions on E.

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

what is hand_00.txt in D? only failed that test :/

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

    \begin{equation} \sum_{i=0}^{len(s) — 1}(\frac{10^{n * len(n) + i} — 10^{i}}{10^i — 1}) * d[i] \end{equation} where $$$len(n)$$$ is no of digits in $$$n$$$ and $$$d[i]$$$ is the $$$i$$$ th digit.

    need to be careful when calculate the numerator it might overflow: AC

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

    n*len(n) can overflow. Maybe you missed that ?

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

    thanks for trying to help guys. I realized I was using the built-in pow to calculate pow(10, len(n)) instead of the pow in my mod template :(

    I changed pow(10, num_digits(n)) to pow((mlong)10, num_digits(n)) and got AC now

    WA AC

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

How to change my name?

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

I spent over 40 mins implementing E only to find out here that it was available on Leetcode :/

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

Why there are so many D&C NTT problems in ABC, but almost no problems about suffix array or suffix automaton ??? I think they are educational too :)

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

how to solve F?

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

    I personally didn't solve it, but my idea was correct. We maintain 3 arrays: $$${a_i}, {b_i}, {v_i}$$$. The first two should be self-explanatory and $$$v_i=a_ib_i$$$. To maintain these arrays, we can use many RURQ data structures (I used Sqrt Decomposition). Maintaining $$${a_i}$$$ and $$${b_i}$$$ should be simple as it is just a classic RURQ problem. To maintain $$${v_i}$$$, we notice that when $$${a_l, a_{l+1}, \dots, a_r}$$$ are each incremented by $$$x$$$, then $$${v_l+v_{l+1}+\dots+v_r}$$$ is incremented by $$$x\times\left(b_l+b_{l+1}+\dots+b_r\right)$$$. This allows us to maintain array $$$v$$$ lazily. You can see the editorials for clearer explanations. Also, if anyone finds the problem in my implementation, I would appreciate it.

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

    Some segment tree magic. I misread statement and solved for $$$\sum_i \sum_j A_iB_j $$$

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

    Segment Tree

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

Why submission giving WA on test_03.txt :(

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

Joined 1 hour late (on accident), but still solved ABD.

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

WA — https://atcoder.jp/contests/abc357/submissions/54368958 AC — https://atcoder.jp/contests/abc357/submissions/54381026

Can somebody explain why my first submission was not accepted whereas the other one was accepted and the only difference both have is that in the not accepted one, I have define k = 1+(int)log10(n) whereas, in the accepted one I have define k = to_string(n).size()

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

Reduced problem D to Geometric Progression, and then utilised the sum of first N terms formula. We can split the original number multiply it later and make a GP serious out of multipliers of powers of 10. a = 10^(N*d — d), r = 1/(10^d). Final ans = N * a(1-r^n)/(1-r)

Here d = no. of digits in the original given number. Have taken care of fermat's theorem too by applying (mod-1) for huge numbers in exponents. Why does it fail in 15 and passes 13 test cases. What is wrong in the solution ? https://atcoder.jp/contests/abc357/submissions/54378604

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

Anyone please explain me the logic or Intution of Problem D.

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

Only solved first two, sad, suggest some topic.

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

Can anyone help me with problem F? I used lazy segment tree. code

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

@atcoder_official try to add more general editorial instead of any snippet, sometimes its get hard to understand .

→ Reply