Tutorial is loading...
Python Solution
T = int(input())
for tc in range(T):
s = [c for c in input()]
n = len(s)
i = 0
while (i < n):
if (s[i] == '?'):
prv = 'd' if i == 0 else s[i - 1]
nxt = 'e' if i + 1 >= n else s[i + 1]
for x in ['a', 'b', 'c']:
if (x != prv) and (x != nxt):
s[i] = x
break
else:
i += 1
ok = True
for i in range(n - 1):
if (s[i] == s[i + 1]):
print("-1")
ok = False
break
if (ok == True):
print("".join(s))
Author: isaf27, prepare laoriu, I_love_Hoang_Yen
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 239;
int n, p[M], x;
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
p[x - 1] = i;
}
int l = n;
int r = 0;
string ans = "";
for (int i = 0; i < n; i++)
{
l = min(l, p[i]);
r = max(r, p[i]);
if (r - l == i)
ans += '1';
else
ans += '0';
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Author: isaf27, prepare isaf27
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
map<int,int> c;
forn(i, n) {
int pi;
cin >> pi;
c[-pi]++;
}
vector<int> pp;
for (auto p: c)
pp.push_back(p.second);
bool ok = false;
int g = pp[0];
int i = 1;
int s = 0;
while (s <= g && i < pp.size())
s += pp[i++];
if (g < s) {
int b = 0;
while (b <= g && i < pp.size())
b += pp[i++];
while (i < pp.size() && g + s + b + pp[i] <= n / 2)
b += pp[i++];
if (g < b && g + s + b <= n / 2) {
ok = true;
cout << g << " " << s << " " << b << endl;
}
}
if (!ok)
cout << 0 << " " << 0 << " " << 0 << endl;
}
}
Author: MikeMirzayanov, prepare MikeMirzayanov
Tutorial is loading...
C++ Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
map<int, int> hs;
cin >> hs[0] >> hs[1] >> hs[2] >> hs[3];
int total = hs[0] + hs[1] + hs[2] + hs[3];
for (int st = 0; st < 4; st++) if (hs[st]) {
vector<int> res;
auto ths = hs;
ths[st]--;
res.push_back(st);
int last = st;
for (int i = 0; i < total - 1; i++) {
if (ths[last - 1]) {
ths[last - 1]--;
res.push_back(last - 1);
last--;
}
else if (ths[last + 1]) {
ths[last + 1]--;
res.push_back(last + 1);
last++;
}
else {
break;
}
}
if ((int) res.size() == total) {
cout << "YES\n";
for (int i = 0; i < (int) res.size(); i++) {
cout << res[i] << " \n"[i == (int) res.size() - 1];
}
return 0;
}
}
cout << "NO\n";
return 0;
}
Author: laoriu, prepare laoriu, I_love_Hoang_Yen
Tutorial is loading...
C++ Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 119 << 23 | 1;
int inv(int a) {
int r = 1, t = a, k = MOD - 2;
while (k) {
if (k & 1) r = (long long) r * t % MOD;
t = (long long) t * t % MOD;
k >>= 1;
}
return r;
}
int main() {
int n; cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD;
int a = 1, b = 0;
for (int i = 0; i < n; i++) {
a = (long long) a * inv(p[i]) % MOD;
b = (long long) b * inv(p[i]) % MOD;
a = (a + (long long) (p[i] - 1) * inv(p[i])) % MOD;
b = (b - inv(p[i]) + MOD) % MOD;
}
cout << (long long) (MOD - b) * inv(a) % MOD << "\n";
return 0;
}
Author: chemthan, prepare laoriu, I_love_Hoang_Yen
Tutorial is loading...
C++ Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 119 << 23 | 1;
int fpow(int a, int k) {
int r = 1, t = a;
while (k) {
if (k & 1) r = (long long) r * t % MOD;
t = (long long) t * t % MOD;
k >>= 1;
}
return r;
}
int main() {
string s; cin >> s;
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
vector<int> f(n + 1);
for (int i = 0; i < n; i++) {
f[i + 1] = f[i];
f[i + 1] += s[i] == '?';
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
if (s[i] != '(') {
dp[i][j] += dp[i + 1][j];
dp[i][j] %= MOD;
}
if (s[j] != ')') {
dp[i][j] += dp[i][j - 1];
dp[i][j] %= MOD;
}
if (s[i] != '(' && s[j] != ')') {
dp[i][j] -= dp[i + 1][j - 1];
dp[i][j] += MOD;
dp[i][j] %= MOD;
}
if (s[i] != ')' && s[j] != '(') {
dp[i][j] += dp[i + 1][j - 1];
dp[i][j] %= MOD;
dp[i][j] += fpow(2, f[j] - f[i + 1]);
dp[i][j] %= MOD;
}
}
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Author: chemthan, prepare laoriu, I_love_Hoang_Yen
Tutorial is loading...
C++ Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 119 << 23 | 1;
struct node_t {
int prd;
int val;
node_t() {
prd = val = 0;
}
};
node_t operator + (node_t a, node_t b) {
if (!a.prd) return b;
if (!b.prd) return a;
node_t c;
c.prd = (long long) a.prd * b.prd % MOD;
c.val = (long long) a.val * b.prd % MOD;
c.val = (c.val + b.val) % MOD;
return c;
}
int inv(int a) {
int r = 1, t = a, k = MOD - 2;
while (k) {
if (k & 1) r = (long long) r * t % MOD;
t = (long long) t * t % MOD;
k >>= 1;
}
return r;
}
int main() {
int n, q; cin >> n >> q;
vector<int> p(n);
for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD;
vector<node_t> st(n << 2);
auto upd = [&] (int p, node_t val) {
for (st[p += n] = val; 1 < p; ) p >>= 1, st[p] = st[p << 1] + st[p << 1 | 1];
};
auto query = [&] (int l, int r) {
node_t lres, rres;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
lres = lres + st[l++];
}
if (r & 1) {
rres = st[--r] + rres;
}
}
return (lres + rres).val;
};
for (int i = 0; i < n; i++) {
node_t c;
c.val = c.prd = inv(p[i]);
upd(i, c);
}
set<int> ss;
ss.insert(0);
int res = query(0, n - 1);
for (int i = 0; i < q; i++) {
string op; int u; cin >> u; u--;
auto it = ss.lower_bound(u);
if (it == ss.end() || *it != u) {
it = ss.insert(u).first;
int lo = *(--it);
it++;
int hi = n;
if (++it != ss.end()) {
hi = *it;
}
res -= query(lo, hi - 1);
res += MOD;
res %= MOD;
res += query(lo, u - 1);
res %= MOD;
res += query(u, hi - 1);
res %= MOD;
}
else {
int lo = *(--it);
it++;
int hi = n;
if (++it != ss.end()) {
hi = *it;
}
res += query(lo, hi - 1);
res %= MOD;
res -= query(lo, u - 1);
res += MOD;
res %= MOD;
res -= query(u, hi - 1);
res += MOD;
res %= MOD;
ss.erase(u);
}
cout << res << "\n";
}
return 0;
}
Author: chemthan, prepare laoriu, I_love_Hoang_Yen
Tutorial is loading...
C++ Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 119 << 23 | 1;
int inv(int a) {
int r = 1, t = a, k = MOD - 2;
while (k) {
if (k & 1) r = (long long) r * t % MOD;
t = (long long) t * t % MOD;
k >>= 1;
}
return r;
}
int main() {
string s; cin >> s;
int k = s.size() + 1;
int a = 0, b = 0, c = 0, d = 0;
for (char e : s) {
if (e == ')') {
b++;
}
if (e == '?') {
d++;
}
}
map<int, vector<int>> dps;
auto calc = [&] (int a, int b, int c, int d) {
int x = b + d - a;
if (x < 0) return 0;
int k = c + d;
if (k < x) x = k;
if (dps.count(k)) return dps[k][x];
auto& dp = dps[k];
dp.resize(k + 1);
int t = 0, w = 1;
for (int i = 0; i <= k; i++) {
t += w;
t %= MOD;
dp[i] = t;
w = (long long) w * (c + d - i) % MOD;
w = (long long) w * inv(i + 1) % MOD;
}
return dp[x];
};
int res = 0;
for (int i = 0; i < (int) s.size(); i++) {
char e = s[i];
if (e == '(') {
a++;
}
if (e == ')') {
b--;
}
if (e == '?') {
c++;
d--;
}
if (e == '(') {
res += calc(a, b, c, d);
res %= MOD;
}
else if (e == '?') {
a++, c--;
res += calc(a, b, c, d);
res %= MOD;
a--, c++;
}
}
cout << res << "\n";
return 0;
}
Author: chemthan, prepare laoriu, I_love_Hoang_Yen
Tutorial is loading...
C++ Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; cin >> n >> m;
vector<int> d(n);
vector<vector<int>> g(n, vector<int>(n));
vector<vector<int>> f(n, vector<int>(n, 1));
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v; u--, v--;
d[u]++;
g[u][v] = 1, g[v][u] = 2;
f[u][v] = f[v][u] = 0;
}
priority_queue<pair<int, int>> heap;
for (int i = 0; i < n; i++) {
if (d[i] < n - 1) {
heap.push({-d[i], i});
}
}
while (!heap.empty()) {
int u = heap.top().second;
heap.pop();
queue<int> que;
vector<int> vis(n), from(n);
que.push(u), vis[u] = 1;
int id = -1;
while (!que.empty()) {
int v = que.front(); que.pop();
int found = 0;
for (int w = 0; w < n; w++) if (w != v && !g[v][w]) {
found = 1;
break;
}
if (found) {
id = v;
break;
}
for (int w = 0; w < n; w++) if (!vis[w] && g[v][w] == 2 && f[v][w] == 1) {
que.push(w), vis[w] = 1;
from[w] = v;
}
}
if (id == -1) {
continue;
}
for (int v = 0; v < n; v++) if (v != id && !g[id][v]) {
g[id][v] = 1, g[v][id] = 2;
break;
}
while (id != u) {
int nid = from[id];
swap(g[id][nid], g[nid][id]);
id = nid;
}
d[u]++;
if (d[u] < n - 1) {
heap.push({-d[u], u});
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
cout << 0;
}
else {
cout << 2 - g[i][j];
}
}
cout << "\n";
}
return 0;
}
Author: chemthan, prepare laoriu, I_love_Hoang_Yen
Another cool problem: WEICOM.
Tutorial is loading...
Python Solution
n,a,d=map(int,input().split())
print(368131125*a%10**9*12*10**9+1,368131125*d%10**9*12*10**9)
Author: chemthan, prepare laoriu, I_love_Hoang_Yen
Bonus: another beautiful problem.
Was eagerly waiting for the editorial. Thanks.
Problem 1264E has a similar which can be found at https://www.luogu.com.cn/problem/P4249, I have used the code in https://www.luogu.com.cn/problemnew/solution/P4249 to solve 1264E during the contest, which was published in 2018.
Thus some people's (such as jiangly, Rose_max, LiWenHaoTianXiaDiYi, disposrestfulIy, SpiderDance and me) submissions was skipped by mistake, they are unrated. But it's not fair.
Can you help us to solve this problem? Greatly thanks.
The skipped submissions are jiangly/66346874, Rose_max/66347301, KotonohaKatsura/66350584, disposrestfulIy/66342618, yuguotianqing/66351221, SpiderDance/66352851.
Let ask MikeMirzayanov.
Thanks.
please help us.. i am really anxious now
Thank you very much, my rating has come back lol. BTW, MikeMirzayanov is a very nice admin.
https://codeforces.me/contest/1264/submission/66453921 — Div 1C WA4
Looking at the comments my idea is similar, we first calculate answer with no checkpoints (which works, since I pass Div2E), and afterwards if we add a checkpoint j in interval [i, k], we have to decrease the answer by prod(i, j — 1) * prod(j, k) and add val[j — 1], when we delete j we need to merge intervals [i, j — 1] and [j, k], we do the opposite (add products, subtract val). This fails on first checkpoint addition on big test, so I cannot research that manually. Any ideas on what I did wrong?
Your formula for updates is wrong.
Try this testcase:
The answer is 4, but your output is 5.
Can someone please explain,how to solve Beautiful sequence(1265D) as there was a lot of confusions while trying to get the proper solution.Also explain how did you get to the solution please. Thanks in advance.
What I tried to do is this. I tried to make a pattern of $$$01010101|21212121|23232323$$$ form. The $$$01$$$ sequence needs to terminate with a $$$1$$$, the $$$23$$$ sequence needs to start with $$$2$$$. Now, if there are too many $$$0$$$'s than $$$1$$$'s, the sequence cannot be formed as you need $$$1$$$'s beside the $$$0$$$'s. So, if $$$a\geq b+2$$$ or $$$d\geq c+2$$$, answer is $$$NO$$$. The other cases are also similar. The code is pretty much self-explanatory, so I'd suggest you have a look at it. My submission: 66486337
Please be aware that the tutorial is not completed yet. There may be some typo or ambiguous sentences. We are fixing them gradually.
Better late than never
1265E is a super standard bayan problem
Problem E div 2
By the definition of expectation value and its basic properties, the following must holds for all 1≤i≤n:
ei=1+pi×ei+1+(1−pi)×e1
I know the definition of expectation value, but this equality is not obvious for me.
Can somebody explain this formula or give some information about expectation value to learn?
It is the linearity of expected value, i.e. if $$$X$$$ and $$$Y$$$ are two random variables, then $$$E[\alpha X+\beta Y] = \alpha E[X] + \beta E[Y]$$$ for any $$$\alpha,\beta$$$ constants. The variable $$$X_i$$$ is the number of days to get happy if she's at the $$$i$$$-th mirror. For this random variable, we must have the relation $$$X_i = p_i\cdot(1+X_{i+1}) + (1-p_i)\cdot(1+X_1)=1+p_i X_{i+1} + (1-p_i) X_1$$$, since with probability $$$p_i$$$ she can move on to the next mirror with a day gone, and with $$$1-p_i$$$ she goes back to the first. Now, $$$E[X_i] = E[1+p_i X_{i+1} + (1-p_i) X_1] = 1+p_iE[X_{i+1}]+(1-p_i)E[X_1]$$$.
Or, without intuitive useage of random variables, you could say that the probability of $$$X_i$$$ taking the value $$$d$$$ (i.e. exactly $$$d$$$ days to get happy), we must have $$$P(X_i=d) = p_i\cdot P(X_{i+1}=d-1) + (1-p_i)\cdot P(X_1=d-1)$$$, since after passing $$$i$$$-th with $$$p_i$$$ probability she has to get happy in exactly $$$d-1$$$ days from $$$i+1$$$-st, or failing at the $$$i$$$-th gives her $$$d-1$$$ days to pass from the first one. So we need only the definition of expected value to get
where
means
Finally this leads to
Here's my approach to 1264F - Beautiful Fibonacci Problem, hoping it provides some additional insight:
I was aware that the Fibonacci sequence is periodic for any modulus, and the period is called Pisano period. I checked that for $$$x\geq 3$$$, the Pisano period $$$\mod 10^{x}$$$ is $$$15\cdot 10^{x-1}$$$. At first, I was considering an easier task, with limits at $$$10^3$$$ instead of $$$10^6$$$, i.e. I was looking for arithmetic sequences of indices such that the corresponding Fibonacci numbers contain all the $$$3$$$-length digit substrings, hoping to discover some useful relation. I found out that over a period, the last three digits won't produce all substrings, so i was looking at the next block of $$$3$$$ digits, for which i realized that if I jump the lengths of Pisano period $$$p=1500$$$ in the index, then the numbers $$$F_{1+k\cdot p}/1000 \mod 1000$$$ (the second $$$3$$$-digit blocks from the end of the number) are in arithmetic progression $$$\mod 1000$$$, and since in this case $$$F_{1+1\cdot p}/1000 \mod 1000 = 949$$$ is relative prime to $$$1000$$$, so it generates all the digit strings. I will provide a proof in the end of this post.
Now, the value of index $$$k$$$ in order to have the string $$$001$$$ in $$$F_{1+k\cdot p}$$$ is easy to get by Euler-theorem, it is $$$k=949^{\varphi(1000)-1}\mod 1000=949^{399}\mod 1000 = 549$$$. So, if we need a digit string $$$a$$$ to be found, we could just take $$$F_{1+a\cdot k\cdot p}$$$, since the strings are generated in arithmetic progression, as I mentioned before. Moreover for $$$a+l\cdot d$$$ we could choose $$$F_{1+(a+\cdot l\cdot d)\cdot k\cdot p} = F_{1+a\cdot k\cdot p + d\cdot l\cdot k\cdot p}$$$, i.e. obviously the indices here would be in arithmetic progression too, so we can simply output our answer $$$b=1+a\cdot k\cdot p$$$ and $$$e=d\cdot k\cdot p$$$.
The same holds if we have the problem's original limits and we need the $$$6$$$-length substrings: consider the above with $$$\mod 10^6$$$, when the Pisano period is $$$p=15\cdot 10^5$$$, get the generator of the $$$6$$$-length digit strings $$$F_{1+1\cdot p}/10^6 \mod 10^6 = 677499$$$, compute the index of $$$000001$$$ which is $$$k = 677499^{399999} \mod 10^6 = 445049$$$, and so the answer is $$$b=1+a\cdot 445049\cdot 15\cdot 10^5$$$ and $$$e=d\cdot 445049\cdot 15\cdot 10^5$$$.
Link to submission: 66473963
The fact that the numbers $$$F_{1+k\cdot 15\cdot 10^{x-1}}/10^x \mod 10^x$$$ are in arithmetic progression $$$\mod 10^x$$$ can be verified for the given limits by a simple program, but we can prove it formally too: for this, we need the formula $$$F_{1 + (k+1)\cdot p} = F_{1+kp}\cdot F_{1+p} + F_{kp}\cdot F_{p}$$$, which is a special case of the formula mentioned by the editorial, but nonetheless its easy to verify either using the generator function or the recurrence matrix of the sequence. Since $$$p$$$ is the Pisano period, we know that both terms of the second product are congruent to $$$0 \mod 10^x$$$, i.e. they end with $$$x$$$ zeroes, so the product ends with at least $$$2x$$$ zeroes, so it won't affect the second $$$x$$$-length digit block from the end, consequently $$$F_{1+(k+1)\cdot p}/10^x \mod 10^x = (F_{1+kp}\cdot F_{1+p}) / 10^x \mod 10^x$$$. The last $$$x$$$ digit block in both of these right hand side terms is $$$00\ldots 01$$$ (by Pisano period), so the second $$$x$$$ digit block from the end (notating by $$$B_l$$$ the second $$$x$$$ digit block of $$$F_l$$$ for any $$$l$$$ index), is obtained by multiplying blockwise
to get $$$X\cdot 10^{2x} + (B_{1+kp}+B_{1+p})\cdot 10^x + 00\ldots 01$$$, i.e. $$$B_{1+(k+1)p} = B_{1+kp}+B_{1+p}\mod 10^x$$$, the second $$$x$$$-digit block is the sum of the second $$$x$$$-digit blocks of the $$$1+kp$$$ and $$$1+p$$$ Fibonacci numbers, thats what we wanted to show.
Thanks. It is better to read participant's solution because it is more natural than author's one.
How to derive the mathematics formula for D2?
Would this approach work for 1265E Beautiful Mirrors?
Since we need to calculate expected number of days..
So let Pi=Probablity of becoming happy at ith day
So that implies that P1,P2,....P(n-1) = 0 as he cant be happy on days he's not asking the last mirror,
So , he can be happy on Pn,P2n,..... days.
Now probability of having success on nth day is = p1*p2*p3*....*pn
And on (2n)th day is =(Pn)*(Pn)
And on (3n)th day is =(Pn)*(Pn)*(Pn)
And so on...
So now according to formula
E= n*(Pn) + (2n)*(P2n) + (3n)*(P3n) + .......
=> E = n*(Pn) + (2n)*(Pn)^2 + (3n)*(P3n)^3 + .......
So now the answer turns out to be an infinite Arithmetic-Geometric Progression series
and we should now be able to use the summation formula for it,
Would this approach work??
You can't say probability for having success on 2nth day is Pn*Pn. because in doing that, you are ignoring things like: 1--->2---->1---->2--->1---->2---->…… 1 (after n steps we are at 1) --->2---->3--->4---->n(in next n steps we reach the end, but this scenario is not even considered in your formula) Also, how can you square Pn , because once you have achieved Pn, it means you have reached the right end.... if probability of success of first day of something is p then probability of success on second day is NOT p^2, it is (1-p)*p AS FIRST DAY IS A FAILURE DAY So, your formulas won't work like this. Another approach is needed
Thanks a lot for the reply .. I had been thinking about this for hours, Thanks for clearing the doubt.
We can solve the Div2E problem WITHOUT having to find the modular inverse of all the $$$P_i$$$ existing. Let, $$$E_k$$$ is the expected number of days after having asked $$$k$$$ mirrors i.e. about to ask the $$$k+1^{th}$$$ mirror. So, clearly from this definition, $$$E_n=0$$$, and $$$E_0$$$ is our answer to this problem. Now, we can see that
$$$E_k = 1 + \frac{P_{k+1}}{100} \cdot E_{k+1} + (1-\frac{P_{k+1}}{100}) \cdot E_0$$$
Let this be eqn1, which holds for all $$$k (0\leq k \leq n-1)$$$. Let’s express every $$$E_k (0\leq k \leq n)$$$ in $$$constant + efficient \cdot E_0$$$ form. So, $$$E_n = 0 + 0 \cdot E_0$$$. Using that, we can find $$$E_{n-1}, E_{n-2}…E_0$$$ by plugging in the values of $$$constant$$$ and $$$efficient$$$ in eqn1 and updating them. So, at the end of the iteration, we will have $$$E_0 = constant + efficient \cdot E_0$$$. Thus, $$$E_0 = \frac{const}{1-eff} \% MOD $$$ . Do your modular operations properly, be careful of overflow, and it will lead to the answer. All we need to do is to evaluate modular inverse of $$$100$$$ at the beginning, and that of $$$(1-eff)$$$ towards the end. My submission: 66363163
This was my approach too. Unfortunately, I think it's harder to get the insight needed to solve the Div1 version from this approach.
Completely agreed. After looking at the problem of div1 version and the editorial of div2 version, I also thought the same. Now I'm trying to solve the div1 version in "my" way. If I can't, I will try the way it's showed in the editorial. Let's see what happens.
Let us solve D by dp!!! you may say are you crazy?Be patient,my friend we can naively denote the status dp[i][e][a][b][c][d] is when we are at i position and the end is "e"(0,1,2,3) element we has a zeros ,b ones ,c twos ,d threes ,so the transform is obvious so, we have many status....TLE? NO,many status can just be neglected let us denote x,y is the element we want to put ,and denote nd:=min(cnt[x],cnt[y]) nd+1,nd is the number we can put ,other condition in fact will finally transfer into the status my code: Your text to link here...66490372
Can Anyone Explain me why my solution is wrong for Div2(b) — Beautiful numbers. https://codeforces.me/contest/1265/submission/66503775
Because your logic was wrong. You solution failed on this simple test case:
Checkout the editorial for more details.
In problem B new_posmin = max(old_posmin, posm)? this should be new_posmin = min(old_posmin, posm).
Thanks for pointing out. Fixed.
Your Problem E's std Time Complexity is(O(n*logn)) https://paste.ubuntu.com/p/PYdVxM3VZB/
This link is O(n)
On the editorial C++ solution of 1265E: What is the idea behind the code?
It seems that a is always equal to one at the end of each cycle. Also why b is taken negative?
Actually, it a simple approach as described here.
Can anyone tell me why I am getting this error for Problem C Beautiful Region ` 66646880
What is no problem splits between gold and silver?
It means there is a gold medalist and a silver medalist solved the same number of problems.
seems that there's a typo in d1D(hard ver.) Let a be the number of '(' before the i-th position i, b be the number of ')' after the i-th position.
I fixed it. Thanks for pointing out.
Why $$$F_{n+1} = 8t10^k +1$$$ ?
Do induction or just directly calculating.
How to solve D ?
In the solution to 1265C, the following step may be redundant in my opinion:
while (b <= g && i < pp.size()) b += pp[i++];The goal is to greedily maximize the bronze medals while the awardees are less than
n/2. However, this step only ensures that there are more bronze than gold medals. Funnily enough, the number of bronze medals are maximized ton/2right after this step.Last day, a similar problem was questioned in the contest Codeforces Round 848 (Div. 2) (problem D).
Here is my solution for the problem E:
Let $$$F_i$$$ denotes the expected number of times until we are able to go to the next mirror when we are at the mirror $$$i$$$. For the sake of simplicity, call $$$P_i$$$ the probability of being beautiful at the mirror $$$i$$$. Now the mirror either tells us we are beautiful with probability $$$P_i$$$ and allows us to switch to the other mirror, or we start again with the first mirror with probability $$$(1 - P_i)$$$. With these observations, we can write the general formula
$$$F_i = 1*P_i + (1 - P_i) * (1 + F_1 + F_2 + F_3 + ... + F_i)$$$
If we rearrange the formula and use a variable named $$$sum_i$$$ that keeps the prefix sum of F, we get
$$$F_i = (1 + (1-P_i) * sum_{i-1}) / P_i$$$
We can compute all F_i one by one now.
By definition, $$$F_i$$$ gives us the expected number of times to switch $$$(i+1)$$$ th mirror from $$$i$$$ th mirror. To get the answer, we must jump from the first mirror to the second, from the second mirror to the third, and so on. So in conclusion, we can express the equation
$$$answer = F_1 + F_2 + F_3 + ... + F_n$$$
Thanks for the very intuitive and beautiful explanation. Extremely helpful. However, I believe there is a slight mishap in writing, the correct generalization should be
Derivation:
Hi, you can regulate your equation and see it's the same as mine. Despite this, I realized I had miswritten $$$sum_i$$$, it should be $$$sum_{i-1}$$$. I fix it now. Thanks.