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

• +33

 » 6 weeks 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?
 » 6 weeks ago, # |   0 Starts in five minutes!
 » 6 weeks ago, # |   0 Gentle reminder!
•  » » 6 weeks ago, # ^ |   +12 That was too gentle
 » 6 weeks ago, # |   0 Nice Problemset.<3How to solve F?
 » 6 weeks ago, # |   +4 How to solve D ??Is D hard than E or its only for me :(
•  » » 6 weeks ago, # ^ |   0 No it's pretty easy if you know some basic probabilityty
•  » » » 6 weeks ago, # ^ |   0 Can You please Explain.
•  » » 6 weeks 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
•  » » 6 weeks 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
•  » » » 6 weeks ago, # ^ |   +3 Can you suggest few more problems like this one ?
 » 6 weeks ago, # |   +1 still can't solve F , how to represent the state?
 » 6 weeks ago, # | ← Rev. 2 →   +9 How to do F ? Is it some sort of digit dp ?
•  » » 6 weeks ago, # ^ |   0
 » 6 weeks 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.
•  » » 6 weeks 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"
 » 6 weeks ago, # |   0 Why i am getting WA in just one test case in E? My code
 » 6 weeks ago, # |   0 For D, initially I misread and thought it meant "until the graph becomes fully connected".
 » 6 weeks 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; } } } 
•  » » 6 weeks ago, # ^ |   0 What is the idea with E?
•  » » » 6 weeks ago, # ^ |   0 https://atcoder.jp/contests/abc194/editorial/863This is what he did in his solution
•  » » » » 6 weeks 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.
•  » » » » » 6 weeks 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!!
 » 6 weeks 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.
•  » » 6 weeks 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.
•  » » 6 weeks 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