chokudai's blog

By chokudai, history, 7 weeks 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

»
7 weeks 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)

»
7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve F?

»
7 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Any simpler way to solve F than suffix array?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    How to do it with a suffix array?

    • »
      »
      »
      7 weeks 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)$$$.

»
7 weeks 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.

»
7 weeks 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)

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

»
7 weeks 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...

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    we finally met at the same blog...

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

Can anyone tell how to solve E?

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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.

      • »
        »
        »
        »
        7 weeks 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.

      • »
        »
        »
        »
        7 weeks 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.

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

      Thank you, I didnt know what was 01 bfs and turns out its just optimised dijkstra for a graph whose weight is 0 or 1.

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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! :)

»
7 weeks 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.

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I changed all to integer.Still giving RE

      • »
        »
        »
        »
        7 weeks 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?

        • »
          »
          »
          »
          »
          7 weeks 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.

          • »
            »
            »
            »
            »
            »
            7 weeks 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.

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

              Thanks a lot brother. It worked .But why function returning nothing matters here? I saw on CF judging system, functions return type doesn't even matter as long as you don't use the function return value.

»
7 weeks 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.

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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$$$.

    • »
      »
      »
      7 weeks 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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem — C
I am getting WA on only one test case, what I am doing wrong. please help
MY Submission

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

I'm not familiar with Python. What does this mean in Problem C's tutorial?

Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))}

The whole solution:

H,W,N=map(int,input().split())
X,Y=[],[]
for i in range(N):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)

Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))}
Ydict = {y:i+1 for i,y in enumerate(sorted(list(set(Y))))}

for i in range(N):
  print(Xdict[X[i]], Ydict[Y[i]])