### chokudai's blog

By chokudai, history, 3 years ago, 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! Comments (19)
| Write comment?
 » This contest will be also hold on the old rating system, right?Btw, when will the contests hold on the new rating system?
 » Gentle reminder!
•  » » That was too gentle
 » How to solve D ??Is D hard than E or its only for me :(
•  » » No it's pretty easy if you know some basic probabilityty
•  » » 3 years ago, # ^ | ← Rev. 5 →   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 nodesExplanation : 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 ) / nWorking 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
•  » » 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
•  » » » Can you suggest few more problems like this one ?
 » still can't solve F , how to represent the state?
 » 3 years ago, # | ← Rev. 2 →   How to do F ? Is it some sort of digit dp ?
 » 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.com/blog/entry/57934?#comment-416190.
•  » » It's like a problem about "the expected number of girl friends you have in order to have all 12 of the constellations"
 » Why i am getting WA in just one test case in E? My code
 » For D, initially I misread and thought it meant "until the graph becomes fully connected".
 » My codes for anyone interested D#define ld long double using namespace std ; int main(){ int n ; cin >> n ; ld ans =0 ; for(int k=n-1;k;--k) ans+=(ld)n/k ; cout<>n>>m ; vectora(n) ; for(int &x:a) cin>>x ; vector>p(n+1,{0}) ; for(int i=0;i=m){ cout << i << '\n' ; return 0; } } } 
•  » » What is the idea with E?
•  » » » https://atcoder.jp/contests/abc194/editorial/863This is what he did in his solution
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   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 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.
•  » » » » » 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!!