chokudai's blog

By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 243.

We are looking forward to your participation!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E ? I did floyd warshall and got WA.

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

    you use floyd warshall, but most likely u didnt find shortest paths with as many edges as possible, cuz i didnt do that at first and i got wa as well. basically instead of if(dist[i][j]>dist[i][k]+dist[k][j]), you should have >=. If you have a graph like the one shown below, you won't delete any edges even though you can remove edge from 2-4 because fw will find that the shortest path is the edge of 2-4, when you want fw to find that the shortest path is 2->3, then 2->4 even though they are the same length.  heres my code if it helps https://atcoder.jp/contests/abc243/submissions/30068875

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

      I do not get it.

      I tried to do floyd-warshal, and counted edges that can be removed because there exists a shorter path.

      But then had to realize that this does not work if there are alternative paths of equal cost. How/Why does this work with your code?

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

        in the triple loop where you calculate distances i check if the intermediate path of i->k,k->j is equal to i->j, because you want floyd warshall to calculate the paths with as many edges as possible. I think this works because you want to use as few edges as possible, so its better to use the already predetermined path rather than new edges that havent been considered yet.

        edit: sorry im really bad at explaining things :(

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

        The intuition is that if there are 2 paths with equal cost, we should favor the one that has a greater number of edges because it consists of sub-paths that are themselves shortest paths and already retained from the original graph so this could save us from retaining an edge that we can remove as illustrated by the example omeganot provided. We can maintain the lengths of the paths and favor the "longest" shortest path. Submission

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

    I did Floyd Warshall, but I modified the graph at first. We copy the graph 2 times, so we got 3 Levels of equal graphs. Level $$$1$$$ is our original level, Level $$$2$$$ and Level $$$3$$$ are below Level $$$1$$$. Now I added new Edges. Instead of moving from $$$u_1$$$ to $$$v_1$$$ you are allowed to move from $$$u_1$$$ to $$$v_2$$$ on the second level for the same cost. The same goes for moving from $$$u_2$$$ to $$$v_3$$$. So while moving to a neighbouring edge, you are allowed to go down exactly one level. You are not allowed to go from $$$u_1$$$ to $$$u_2$$$, the same node on a lower level.

    Now we do Floyd Warshall. Now for each edge $$$u_1$$$ to $$$v_1$$$ from the original graph, I checked whether the distance from $$$u_1$$$ to $$$v_3$$$ is less or equal to the original distance. If it is less, then obviously we can delete it. If it is the same, then we can also delete it, since we had to use at least 2 edges to go down 2 levels.

    My Submission

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

    I used Floyd Warshall to calculate all pair minimum distance,then used the same idea to check if dist[i][k]+dist[k][j]<=dist[i][j] means there is a shorter or equal path present and removed the edge.Finally printed ans/2 as it was counted twice.Sadly finished implementing it 20 mins after the contest. Link

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

Does it makes sense to put such a question in a beginner round, which even Legends are not able to solve during the contest???

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

    Seems you are new to ABCs lmao, Atcoder Beginner rounds are not for beginners :(

    Or maybe their definition of beginners is different but I for sure face difficulties in this beginners contest

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

In problem E. I used Floyd warshall to find the necessary edges which help to get the minimum distance. then just printed m-important_edges.size().

Got WA on 7 test cases.

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

Can anyone tell the approach of D Moves on Binary Tree?

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

    i used a stack to precompute only the important moves. Its important to notice that if theres a U following any L or R, its essentially doing nothing. So i just looped through the string and pushed all Ls and Rs into the stack, if theres ever a U and the stack is not empty, pop the top of the stack. The remaining elements will be the only important ones and you will be able to simulate them directly.

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

    You can turn the current number into a binary string.

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

      Can you explain in detail?

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

        After the contest, I realized 'turn the current number into a binary string' is the easiest approach. It is easier than using a stack. Submission

        I used a stack during contest though.

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

          didnt think abt binary strings, thats pretty genius lol

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

    one 'U' operation counters one(L/R) operation. lets the operations ar LRLU which is the same as

    LR. let's say we are at x position then after 'L' we will be at 2*x but if we do a 'U' operation we will go back to x position. I used an additional vector v; so, you just go in the string from 0 to n-1 and check if s[i]=='U' then v.pop_back() if v is empty just divide x by 2 to go to the parent of x.

    after this you will have a vector of L and R in it.

    Now,

    if v[i]=='L' do x*=2 
    else x*=2,x++;

    x is the final answer.

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

    I used the fact that answer is always <=1e18 so whenever our current node goes more than 1e18 we just maintain a count that how much depth we have gone down and no matter what are the moves we will always come back as the answer <= 1e18 Code

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

Why is this submission for G failing on one test case, I couldn't figure it out https://atcoder.jp/contests/abc243/submissions/30071315

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

    Because of the f*cking sqrt function

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

      Why are you angry? It is well known that it is imprecise, and even if somebody didn't know about it, it makes perfect sense that they learn it in the Beginner contest.

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

    The square root is imprecise for long longs. My square root function fixed your submission: 30080661

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

    Using sqrtl function instead of sqrt Works . Or you can even remove precision error using

    Code
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

ABC is becoming more and more difficult.

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

    Problems A through D are easy, and E through G are reasonable for their score. The only unreasonable problem I see based on the standings is H, which likely was more tedious than actually difficult (judging by the code size of ACs here). Also, it is likely that many people were tricked into thinking about flows after remembering the easier "version" from a recent ABC. Anyway, kenkoooo will soon tell us if there is an objective trend of increasing difficulty (which I don't see).

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

    Indeed ABC is becoming more and more difficult. ABC 242 question C requires DP. In the past, no question Cs required DP. Not that the DP is difficult, but in the past question C used to be easier.

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Solved G but couldn't solve E...

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

How to prove the correctness of Ex?

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

Ask a noob problem, are there any ways to get the test case for atcoder?

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

Editorial for F seems too hard to read, Not able to get Why factorials even get in picture ? any one who can help me out here

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

    Disclaimer: I didn't read the editorial.

    My solution is dp[prizes prefix][draws][different prizes] with transitions of the form "draw $$$i$$$-th prize $$$j$$$ times". To find the probability of such transition we have to

    (i) consider the probability of the prize appearing, which is $$$(w_i/\text{sum }w_i)^j$$$;

    (ii) consider the arrangement of the draws (because drawing 1 2 is different from drawing 2 1).

    Factorials account for (ii), as there are $$$\text{Binom}(j + l, j) = \frac{(j + l)!}{j! l!}$$$ ways to choose $$$j$$$ positions for the draws that yield $$$i$$$-th prize if there already were $$$l$$$ draws for prizes $$$< i$$$.

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

    The factorial appears because if you have $$$K$$$ prizes and there are $$$c_i$$$ prizes of each type $$$i$$$, then the number of unique arrangements of these prizes is:

    $$$\frac{K!}{\prod_i c_i!}$$$

    The solution is easier to understand in the language of polynomials. Let us say we have $$$m$$$ distinct prize types, and we want to know the number of ways to arrange $$$k$$$ prizes, such that we have at least one of each of the types. This is $$$k!$$$ times the coefficient of $$$x^k$$$ in the following product:

    $$$ \prod_{i=1}^m (\frac{x}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^k}{k!}) $$$

    I think it is clear that the coefficient is the same as the formula for the number of arrangements above. Now let us take probabilities into account. The probability that we will get $$$k$$$ prizes such that we have at least one of each of the types is $$$k!$$$ times the coefficient of $$$x^k$$$ in the following product:

    $$$ \prod_{i=1}^m ((\frac{w_i}{W})\frac{x}{1!} + (\frac{w_i}{W})^2\frac{x^2}{2!} + \cdots + (\frac{w_i}{W})^k\frac{x^k}{k!}) = \prod_{i=1}^m P_i $$$

    Again it should be possible to convince yourself about this — it's probably most intuitive to think of the coefficient of $$$x^i$$$ as the effect of taking $$$i$$$ of that prize type. With this knowledge, we can solve the problem using DP.

    Let $$$dp[i][j]$$$ be a polynomial whose $$$k$$$th coefficient indicates the probability that we have $$$j$$$ distinct types after $$$k$$$ draws (divided by $$$K!$$$), when considering the first $$$i$$$ types of prizes. From this, we get the transition:

    $$$ dp[i][j] = dp[i-1][j] + dp[i-1][j-1] \cdot P_i $$$

    With this, we can solve the problem in $$$O(NMK^2)$$$ (or faster with NTT).

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

I read both two tutorials of problem F, but still find it difficult to understand. Would anyone who solved it share any other hints or ideas please. Thanks a lot.