Hello Codeforces,
I would like to invite you all to participate in the 2017 JUST Programming Contest 2.0 of Jordan University of Science and Technology. The contest was originally held on 1st of April, and it will launch in Codeforces Gym tomorrow; Friday 7 April 2017 13:00 UTC.
The problems were prepared by justHusam and Lvitsa.
Thanks to Vendetta. for testing the problem set.
The duration of the contest is 4 hours, and the registration will be open 6 hours before the start of the contest.
Good luck for everyone, and I wish you all Accepted solutions.
UPD: Registration is currently open. 
UPD: The contest will start in 30 minutes.
Is there gonna be editorial for the problems?
How to solve A?
You buy Kth time from Nth shop. So you must have bought (K-1) times from some of the (N-1) shops.
P(success) = p, P(Failure) = (1.0 — p). We need to find success (K) times in (N) shops, with a compulsion that Kth must be from Nth shop.
The answer is choose(N — 1, K — 1) * [ P(fail)^(N-K) ] * [ P(success)^(K) ]
Hi there,
I tried approaching the problem with DP ... and I didn't see the O(1) formula ! Great work... I understood how to computer the probability. But, I'm struggling with getting the answer into the output format the question is asking.
I know how to compute the answer in terms of getting probability as a floating point number.
Can you explain ... given a floating point number f, how to get a fraction p/q, and from there get a y such that y*q = p (mod 1e9 + 7) ?
Thanks.
You can get the floating number x using string. The multi x 1000. So p/q = x*1000/1000.
I didn't understand. Can you elaborate ?
I think your question's answer is calculating the probability in inverse element. My poor English.
No Problem ! Can you just write the piece of code that does what you say ? Then, i can understand. Or maybe some Wikipedia links ... I appreciate your help. By inverse, do you mean inverse in the modulo group 1e9 + 7 ?
Yes.Maybe my words is this p / q can be changed to p * inverse of q.
If p is the inverse of q, does it mean that
pq = 1 (mod 1e9 + 7) ?
This is what I understood.
How do I convert the floating point number to this p/q form ? Please help.
How to solve J?
Hi! Quite late, but hopefully it will help someone. Perhaps my solution is too complicated, I would love some feedback.
Remove all such arrays which are wholly contained within another array.
Model the problem as a graph. Each array is connected to every other array. The edge weight is the "saving" you do when you connect them, i.e., the number of elements in common from one end. We can assume A->B means overlap A's right end with B's left end. Hence, dist[A][B]!=dist[B][A]. I took the edge weights as negative.
Create a dummy vertex connected to every other vertex with edge weight 0.
TSP (it should run as you have at most 16 vertices).
In my case, as edge weights were negative, I simply output the sum of lengths of all arrays + total saving.
Hope this helps :) Please let me know if some part of my explanation is not clear...
How to solve B by DP ?
Make dp, dp[i] — count of ways we can divide prefix of length i into beautiful substrings. We want to calc dp[i]. Iterate j from i to 1 and break when not all numbers in [j, i] are unique otherwise add dp[j — 1] to dp[i] (making split before position j). Initial values: dp[0] = 1 (if you have indexes from 1). Solution O(n * a), where a = 10. There is also solution O(n) using two pointers.
Can you explain the Two pointers solution ?
Our dp can be presented as follows: f[i] = sum(f[i — 1] + .. + f[j — 1]), where j is the least index such that substring [j, i] is beautiful. When we are going to (i + 1) j won't decrease. So we can store our current sum of f[j..i] and when we want to calculate f[i + 1] subtract f[j] from sum and increase j by 1 while [j, i] isn't beautiful. Code