chokudai's blog

AtCoder Beginner Contest 194 Announcement
By chokudai, history, 4 years ago, In English

We will hold AtCoder Beginner Contest 194.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

Comments Comments (19)
| Write comment?
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

This contest will be also hold on the old rating system, right?

Btw, when will the contests hold on the new rating system?

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

Gentle reminder!

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

How to solve D ??
Is D hard than E or its only for me :(

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

    No it's pretty easy if you know some basic probabilityty

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

    Let dp[i] be the expected number of moves required to connect remaining i nodes,

    Then dp[i] = dp[i — 1] + (n / i)

    Our answer is dp[n — 1] because we need to connect remaining n — 1 nodes

    Explanation :

    Lets say I still need to connect x nodes, then there are n — x already connected nodes. If I make a move now then the probability to connect a unconnected node is ( x / n ) and for already connect node is ( n — x ) / n

    Working on this,dp[i] = (dp[i — 1] + 1) * (i / n) (I connect a unconnected vertices and hence i-1 remain) + (dp[i] + 1) * (n — i / n) (I connect a already connected vertices)

    Rearranging this equation, you would get above equation

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

    Each vertex must be choosen at least once.

    https://blogs.sas.com/content/iml/2011/07/20/how-many-times-must-you-roll-a-die-until-each-side-has-appeared.html

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

      Can you suggest few more problems like this one ?

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

still can't solve F , how to represent the state?

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

How to do F ? Is it some sort of digit dp ?

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

I didn't manage to solve D(I would be very grateful if someone could explain it), but I definitely learnt something new from this round, with problem E: https://codeforces.net/blog/entry/57934?#comment-416190.

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

    It's like a problem about "the expected number of girl friends you have in order to have all 12 of the constellations"

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

Why i am getting WA in just one test case in E? My code

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

For D, initially I misread and thought it meant "until the graph becomes fully connected".

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

My codes for anyone interested

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

    What is the idea with E?

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

      https://atcoder.jp/contests/abc194/editorial/863

      This is what he did in his solution

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

        Sorry, I do not get that kind of language. What does it mean pos_i: an array of j such that A_j=i, in the increasing order?

        Edit: Ok, I think I understood.

        pos[0] is a list of positions of all 0 in A[]. Then we iterate pos starting at 0. Foreach list of positions of value i we check if there are two such positions with a difference bigger than M. Because if there is such difference, then this means that there is a subarray in A[] of size at least M without that i.

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

          In above solution, p[i] stores all positions at which i occurs in the given array. Now, let say i occurs at index j1 and j2(j1 < j2). j1 and j2 are consecutive indexes at which i occurs. so if j2-j1-1 >= m( occurs at distance greater than m) it can be our possible answer. As, he is traversing from 0 to n, first such number will be the answer (as we need minimum value).

          Hope it helps!!

          → Reply