Блог пользователя chokudai

Автор chokudai, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Gentle reminder!

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +7 Проголосовать: не нравится

    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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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://mirror.codeforces.com/blog/entry/57934?#comment-416190.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My codes for anyone interested

D
E
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is the idea with E?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      This is what he did in his solution

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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!!