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?
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
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 ?
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.net/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
What 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!!