### chokudai's blog

By chokudai, history, 16 months 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!

• +33

 » 16 months ago, # |   +17 This contest will be also hold on the old rating system, right?Btw, when will the contests hold on the new rating system?
 » 16 months ago, # |   0 Starts in five minutes!
 » 16 months ago, # |   0 Gentle reminder!
•  » » 16 months ago, # ^ |   +12 That was too gentle
 » 16 months ago, # |   0 Nice Problemset.<3How to solve F?
 » 16 months ago, # |   +4 How to solve D ??Is D hard than E or its only for me :(
•  » » 16 months ago, # ^ |   0 No it's pretty easy if you know some basic probabilityty
•  » » » 16 months ago, # ^ |   0 Can You please Explain.
•  » » 16 months ago, # ^ | ← 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 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
•  » » 16 months ago, # ^ |   +3 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
•  » » » 16 months ago, # ^ |   +3 Can you suggest few more problems like this one ?
 » 16 months ago, # |   +1 still can't solve F , how to represent the state?
 » 16 months ago, # | ← Rev. 2 →   +9 How to do F ? Is it some sort of digit dp ?
•  » » 16 months ago, # ^ |   0
 » 16 months ago, # |   +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://codeforces.com/blog/entry/57934?#comment-416190.
•  » » 16 months ago, # ^ |   0 It's like a problem about "the expected number of girl friends you have in order to have all 12 of the constellations"
 » 16 months ago, # |   0 Why i am getting WA in just one test case in E? My code
 » 16 months ago, # |   0 For D, initially I misread and thought it meant "until the graph becomes fully connected".
 » 16 months ago, # |   0 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; } } } 
•  » » 16 months ago, # ^ |   0 What is the idea with E?
•  » » » 16 months ago, # ^ |   0 https://atcoder.jp/contests/abc194/editorial/863This is what he did in his solution
•  » » » » 16 months ago, # ^ | ← 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.
•  » » » » » 16 months ago, # ^ |   +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!!
 » 16 months ago, # |   0 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.
•  » » 16 months ago, # ^ |   -10 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.
•  » » 16 months ago, # ^ |   0 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