### chokudai's blog

By chokudai, history, 6 weeks 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 (26)
 » This contest will be also hold on the old rating system, right?Btw, when will the contests hold on the new rating system?
 » Starts in five minutes!
 » Gentle reminder!
•  » » That was too gentle
 » Nice Problemset.<3How to solve F?
 » 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
•  » » » Can You please Explain.
•  » » 6 weeks 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?
 » 6 weeks 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
•  » » » » 6 weeks 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!!
 » Regarding problem D."Your answer will be considered correct when its absolute or relative error from our answer is at most 10^(-6)"However, why changing the last line from: cout << sum << endl;to: cout << fixed << setprecision(10) << sum << endl;Get the answer accepted? I could not understand my error at first. But why would it make a difference? Sum is a double, and this is the only change between two consecutive submit.
•  » » Without setprecision, the floating-point number will be truncated to 4 decimal places, which may cause a large relative error. So, you fix the precision of the number to something greater that 6 to stay within the range of the specified relative error.
•  » » I now understand. Double internal representation has largely enough precision. Default double "printed" precision is indeed "6" BUT this is the number of significant digits, not the precision of he fractional part!!!! I learned something for next time :D https://en.cppreference.com/w/cpp/io/manip/setprecision