chokudai's blog

We will hold AtCoder Beginner Contest 213
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 213.physics0523

We are looking forward to your participation!

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

Comments Comments (38)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +138 Vote: I do not like it

Why are there $$$8$$$ problems in recent ABCs?
UPD: please upvote the announcement (the contest deserves much more contribution than my comment lol)

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

In D, forgot that I had to sort my adjacency vector as well. Got two WA and kept waiting for like 20 minutes. My bad :") Still got it at the last minute, GG.

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

how to solve F? there's no editorial for it

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

How to solve F?

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

Any simpler way to solve F than suffix array?

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

    How to do it with a suffix array?

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

      Build the suffix array and LCP array.

      Now, let $$$pos[i]$$$ denote position of suffix starting at index $$$i$$$ in the suffix array. $$$ans[i]$$$ will be sum of minimums of all segments ending at position $$$pos[i]-1$$$ and sum of minimums of all segments starting at $$$pos[i]$$$ (in the LCP array). Also an additional $$$n-i$$$ for LCP with itself.

      To find minimums on segment, we can find next smaller and previous smaller elements in the LCP array and using them precalculate the contribution of each prefix and suffix in $$$O(n)$$$.

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

For Problem H I tried a very simple approach. For each node we have an array $$$ans$$$ with $$$T+1$$$ values counting the amount of paths with length $$$t$$$ to this node. I iterate $$$t$$$ from $$$0$$$ to $$$T-1$$$ and on each step I walk all paths from each node and update $$$ans[t+k]+=ans[t]*paths[k]$$$. This yields correct answers but obviously this is $$$O(MT^2)$$$ and gets TLE.

What is the intended solution here?

Edit: Editorial is out, it's Divide & Conquer with FFT. Guess it is time to learn FFT for me.

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

PLEASE MAKE ABC PROBLEMS E F G H EASIER !!! IT IS A "BEGINNER" CONTEST!!! (I know that it's my problem, but they are yellow, orange, and red difficulty)

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

    I think they are meant to be educational in a sense that you get to learn about advance techniques/data structures while solving them, and in many cases they tend to be easier (relatively) than the average problems that require such techniques/DS.

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

    I think it's not bad though: although you might not be able to solve them this time, the problems are very educational and you can learn to solve problems like them in the future.

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

Is LCP array well-known? Never heard of it and it came out of nowhere @ 500 points problem so...

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

    I mean the first codeforces edu videos are about suffix array and they also teach you about lcp arrays there. I’m pretty sure it’s a well known data structure for solving string problems and also has real-life applications

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

      I don't know why, but I dislike string algorithm/problems by instinct.. so never knew them. Thanks, on my list to study.

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

    we finally met at the same blog...

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

Can anyone tell how to solve E?

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

    0-1 Bfs where 0 cost is when the adjacent squares are empty, and the 1-cost is when you punch a 2x2 right next to you

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

      But, let's say I'm at 'T' in the below grid — 

      ....
.T##
.###
###.

      Now let's say I punch a neighbor — now there will exist a punch that lets me go through 2 hash symbols with 1 cost. How is the cost of second hash symbol handled if we don't track the state of cells?

      i.e. I don't understand how 0-1 BFS handles the case where I'm at the SECOND destroyed cell after punching.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it 
        21112
11111
11011
11111
21112

        If you stand in 0, and everything else is a wall, you can reach "cell 1" by one punch, and can reach "cell 2" by two punches.

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

        You can mark every block you can reach with curent_num_of_punches + 1. Cause there no sense going some direction and from that path break back to current path — or else you would break it through in that second spot. And when you finish with all the cur cells — you goto cur+1.

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

    I have uploaded a video editorial here that you may find useful: https://www.youtube.com/watch?v=UWGMq3oT9h0

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

      Thanks a lot! Your drawing helped clarify it — what made it click for me was that we're redefining each cell's adjacency list to include cells that are up to two hashes away.

      Thanks! :)

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

Can any one suggest me why My Problem D Solution is giving RE.

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

    I haven't looked at your code but have explained my solution here: https://www.youtube.com/watch?v=-y2VIFMkz50

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

    I guess if you change line 16 from ll i = 0 to int i = 0 it'll work

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

      I changed all to integer.Still giving RE

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

        Its giving you RE even on samples. Is there anything stoping you from running it locally and considering error output?

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

          It's running fine locally. All the samples are giving correct output. Strange situation.

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

            On line-14, change the data type of dfs from int to void. Should get you AC then.

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

Another solution for H:

Consider the naive dp,$$$f(u,i)=\sum_{e:(u,v)}\sum_t f(v,i-t)p(e,t)$$$

Let $$$F_u=\sum_{i=0}^T f(u,i)x^i$$$,then we have $$$n$$$ variables(Polynomial) and $$$n$$$ equation. They are polynomials,so we can't use gauss's method directedly.

let's take $$$L(L\ge n,L=2^k)$$$ roots of unity,$$$\omega_L^0,\omega_L^1..\omega_L^{L-1}$$$,replace $$$F_u$$$ with $$$F_u(\omega _L^k)$$$ for $$$k\in [0,L)$$$,and do gauss's method for them.

then do IDFT to calculate the polynomials for the $$$L$$$ points values.

$$$O(Tn^3+T\log T n)$$$

update: it's wrong,see the comments below to see reasons.

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

    Also,we could solve problem G in $$$O(2^nn^2)$$$,by subset convolution.

    My code

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

    If I understood correctly, by

    we have $$$n$$$ variables(Polynomial) and $$$n$$$ equation

    you mean equations like $$$F_u = \sum \limits_{e : (u, v)} F_v \cdot p(e)$$$. These equations do not hold because the degree of LHS is $$$T$$$ but degree of the RHS is $$$2T$$$.

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

      Oh yes,it's wrong.

      I want the equations hold $$$\mod x^{T+1}$$$,but if take $$$\omega_L^0...\omega_L^{L-1}$$$,the equations hold $$$\mod (x^{T+1}-1)$$$ (don't take mod,the roots exist,but may have infinity degree,so the results after taking mod are not the same.)

      Thanks a lot for pointing out my mistakes.

      → Reply