We will hold AtCoder Beginner Contest 194.

- Contest URL: https://atcoder.jp/contests/abc194
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210306T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: Kmcode, sheyasutaka, YoshikaMiyafuji, QCFium, kyopro_friends
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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.<3

How 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.

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

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?

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

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

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

fullyconnected".My codes for anyone interested

DEWhat is the idea with E?

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

This is what he did in his solution

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.

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:

to:

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.

https://en.cppreference.com/w/cpp/io/manip/setprecision

https://www.learncpp.com/cpp-tutorial/floating-point-numbers/#:~:text=Double%20values%20have%20between%2015,how%20many%20bytes%20it%20occupies.