# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 166 |

4 | Vovuh | 165 |

5 | antontrygubO_o | 164 |

6 | rng_58 | 161 |

7 | Um_nik | 156 |

7 | majk | 156 |

9 | 300iq | 155 |

10 | farmersrice | 151 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

The 26th Central European Olympiad in Informatics will take place in Bratislava, Slovakia, during **July 23rd-29th 2019**. The most gifted high school students from 13 countries will have the opportunity to prove their knowledge and skills in informatics.

Codeforces will organise the online mirror for this year's competition. The online mirrors will take place after the finish of each of the 2 competition days, having the same scoring format.

The online mirror schedules are the following:

**Contest format**

- The contest will be unrated for all users.
- You will have to solve 3 tasks in 5 hours.
- There will be full feedback throughout the entire contest.
- The scoreboard will be hidden until the end of the contest.
- The tasks will have partial scoring. The maximum score for each problem will be 100 points.
- Among multiple submissions only the one that achieves the maximum score is counted towards the final ranking.
- The submission time does not matter for ranking.
- There will be enough fun for all colours ranging from newbie to international grandmaster. Legendary grandmasters can spice it up by turning it into a drinking game (ask Radewoosh for details).

Link to onsite contest with official rules and scoreboard

**UPDATE**: Much nicer scoreboard than on the first day made by arsijo. Many thanks!

Congratulations to all onsite contestants who battled our unusually hard problemset for 10 hours. You can view the final standings.

Many thanks to KAN for running the mirror, MikeMirzayanov for both platforms, all of our authors, testers and the whole CEOI staff and sponsors!

Day 1 mirror:

Day 2 mirror:

Results of both days combined: (https://codeforces.com/spectator/ranklist/e354b9b95c3626a3cfdfdb9eb37a7a6f)

Announcement of CEOI 2019 day 1 online mirror (unrated, IOI format)

Announcement of CEOI 2019 day 2 online mirror (unrated, IOI format)

Tutorial is loading...

```
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N; cin >> N;
vector<int> A(N); for (int&a:A) cin >> a;
vector<int> P{1};
int rest = 0, cur = A[0];
for (int i = 1; i < N; ++i) {
if (A[i] <= A[0]/2) {
cur += A[i];
P.push_back(i+1);
} else {
rest += A[i];
}
}
if (cur > rest) {
cout << P.size() << endl;
for (int i = 0; i < P.size(); ++i) cout << P[i] << " \n"[i==P.size()-1];
} else {
cout << 0 << endl;
}
}
```

Tutorial is loading...

```
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main() {
string S; cin >> S;
ll a = 0, b = 0, c = 0;
for (int i = 0; i < S.size(); ++i) {
if (S[i] == 'o') {
b += a;
} else if (i > 0 && S[i-1] == 'v') {
a++;
c += b;
}
}
cout << c << endl;
}
```

Tutorial is loading...

```
#include <iostream>
using namespace std;
constexpr int MOD = 998244353;
int main() {
int R, C; cin >> R >> C;
int X = 1;
while (R--) X = (2*X)%MOD;
while (C--) X = (2*X)%MOD;
cout << X << endl;
}
```

Tutorial is loading...

```
#include <iostream>
using namespace std;
bool prime(int x) {
if (x < 2) return false;
for (int i = 2; i*i <= x; ++i) {
if (x%i == 0) return false;
}
return true;
}
int main(int argc, char ** argv){
int n; cin >> n;
int m = n;
while (!prime(m)) ++m;
cout << m << "\n1 " << n << '\n';
for (int i = 0; i < n-1; ++i) {
cout << i+1 << ' ' << i+2 << '\n';
}
for (int i = 0; i < m-n; ++i) {
cout << i+1 << ' ' << i+1+n/2 << '\n';
}
}
```

Tutorial is loading...

```
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string S; cin >> S;
int N = S.size();
int i = 0, j = N-1;
string A;
while (j-i >= 3) {
if (S[i] == S[j]) {
A.push_back(S[i]);
++i; --j;
} else if (S[i] == S[j-1]) {
A.push_back(S[i]);
++i; j -= 2;
} else {
A.push_back(S[i+1]);
if (S[i+1] == S[j]) {
--j;
} else {
j -= 2;
}
i += 2;
}
}
string B = A;
if (j >= i) A.push_back(S[i]);
reverse(B.begin(),B.end());
cout << A << B << endl;
}
```

Tutorial is loading...

```
#include <iostream>
#include <vector>
using namespace std;
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
public:
inline Field(int x = 0) : v(x) {}
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline explicit operator ui() const { return v; }
private: ui v;
};
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
typedef Field<998244353> F;
int main() {
ios_base::sync_with_stdio(false);
int N, M; cin >> N >> M;
vector<int> C(N); for (int &c: C) { cin >> c; --c; }
vector<vector<F>> D(N+1, vector<F>(N+1, 1));
for (int l = 1; l <= M; ++l) {
for (int a = 0; a + l <= M; ++a) {
pair<int,int> lo = {C[a],0};
for (int i = 0; i < l; ++i) lo = min(lo, {C[a+i],i});
int j = lo.second;
if (j < 0 || j >= l) { D[a][l] = 0; continue; }
F left = 0, right = 0;
for (int u = 0; u <= j; ++u) left += D[a][u] * D[a+u][j-u];
for (int v = j+1; v <= l; ++v) right += D[a+j+1][v-(j+1)] * D[a+v][l-v];
D[a][l] = left * right;
}
}
cout << D[0][N] << endl;
}
```

Tutorial is loading...

```
#include <iostream>
#include <vector>
using namespace std;
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
public:
inline Field(int x = 0) : v(x) {}
inline Field<N> pow(int p){return (*this)^p; }
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline explicit operator ui() const { return v; }
private: ui v;
};
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
typedef Field<998244353> F;
int main() {
ios_base::sync_with_stdio(false);
int N, M; cin >> N >> M;
vector<int> C(M); for (int &c: C) { cin >> c; --c; }
vector<int> W;
for (int i = 0; i < M; ++i) if (W.empty() || W.back() != C[i]) W.push_back(C[i]);
M = W.size();
if (M > 2*N) { cout << "0\n"; return 0; }
vector<vector<int>> E(N);
for (int i = 0; i < M; ++i) E[W[i]].push_back(i);
vector<vector<F>> D(M+1, vector<F>(M+1, 1));
for (int l = 1; l <= M; ++l) {
for (int a = 0; a + l <= M; ++a) {
int lo = W[a];
for (int i = 0; i < l; ++i) lo = min(lo, W[a+i]);
int j = E[lo][0] - a;
int k = E[lo].back() - a;
if (j < 0 || k >= l) { D[a][l] = 0; continue; }
F left = 0, right = 0;
for (int u = 0; u <= j; ++u) left += D[a][u] * D[a+u][j-u];
for (int v = k+1; v <= l; ++v) right += D[a+k+1][v-(k+1)] * D[a+v][l-v];
D[a][l] = left * right;
for (int m = 0; m < E[lo].size()-1; ++m) {
if (E[lo][m] + 1 != E[lo][m+1]) {
D[a][l] *= D[E[lo][m]+1][E[lo][m+1] - E[lo][m] - 1];
}
}
}
}
cout << D[0][M] << endl;
}
```

Tutorial is loading...

```
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T> bool in(T a, T b, T c) { return a <= b && b < c; }
bool fractionGreaterOrEqual(double a, double b, double c, double d) {
return a/b >= c/d;
}
int TOTAL;
/* UpperEnvelope that with O(N) build and amortized O(1) query.
* The updates need be sorted by (m,b), the queries need to be sorted by x, and
* updates need to come before queries. */
namespace LinearEnvelope {
template<typename T> struct Line { T m, b; int id; };
template <typename T>
struct Upper {
Line<T> *V;
T t; int i, s;
Upper(int w) : V(new Line<T>[w]), t(0), i(0), s(0) { TOTAL++; }
~Upper() { TOTAL--; }
//~Upper() { delete []V; }
void clear() { i = s = 0; t = 0; }
void insert_line(T m, T b, int i = 0) {
assert(t == 0);
if (s > 0 && V[s-1].m == m && V[s-1].b >= b) return;
while (s > 0 && ((V[s-1].b < b) || (V[s-1].b == b && V[s-1].m < m))) --s;
while (s >= 2 && fractionGreaterOrEqual(V[s-2].b - V[s-1].b, V[s-1].m - V[s-2].m, V[s-1].b - b, m - V[s-1].m)) --s;
V[s++] = {m,b,i};
}
pair<T,int> advance(T x) {
assert(x >= 0);
t += x;
while (i+1 < s && V[i].m * t + V[i].b < V[i+1].m * t + V[i+1].b) ++i;
return {V[i].m * t + V[i].b, V[i].id};
}
};
};
class RPPS {
public:
vector<vector<int>> E;
vector<ll> A,B,RA,RB;
vector<int> Enter,Exit;
int T;
void dfs(int u, ll a, ll b) {
A[u] += a;
B[u] += b;
Enter[u] = T++;
for (int v:E[u]) dfs(v, A[u], B[u]);
Exit[u] = T;
}
struct Block {
Block(int L, int R, const vector<ll>&A, const vector<ll>&B) : U(2*(R-L)), L(L), R(R), off(0), cur(0) {
for (int i = L; i < R; ++i) W.push_back({{B[i], A[i]*B[i]}, i});
for (int i = L; i < R; ++i) if (A[i] < 0 || B[i] < 0) W.push_back({{-B[i], -A[i]*B[i]}, i});
sort(W.begin(),W.end());
build();
}
void build() {
U.clear();
for (auto &w:W) U.insert_line(w.x.x, w.x.y);
cur = U.advance(0LL).x;
}
void add(int l, int r, ll x) {
if (l >= R || r <= L) return;
else if (l <= L && r >= R) {
cur = U.advance(x).x;
off += x;
} else {
for (auto &w:W) {
w.x.y += w.x.x * off;
if (in(l, w.y, r)) {
w.x.y += w.x.x * x;
}
}
off = 0;
build();
}
}
ll get(int l, int r) {
if (l >= R || r <= L) return numeric_limits<ll>::min();
else if (l <= L && r >= R) return cur;
else {
ll ans = numeric_limits<ll>::min();
for (auto &w:W) {
if (in(l, w.y, r)) {
ans = max(ans, w.x.x * off + w.x.y);
}
}
return ans;
}
}
LinearEnvelope::Upper<ll> U;
vector<pair<pair<ll,ll>,int>> W;
int L, R;
ll off, cur;
};
void solve(istream& cin, ostream& cout) {
TOTAL = 0;
int N, Q; cin >> N >> Q;
E.resize(N);
A.resize(N);
B.resize(N);
RA.resize(N);
RB.resize(N);
Enter.resize(N);
Exit.resize(N);
for (int i = 1; i < N; ++i) {
int p; cin >> p; --p;
E[p].push_back(i);
}
cin >> A >> B;
T = 0;
dfs(0, 0, 0);
for (int i = 0; i < N; ++i) {
RA[Enter[i]] = A[i];
RB[Enter[i]] = B[i];
}
int BS = max(1,(int)sqrt(N/6));
vector<Block> D;
D.reserve(1+(N-1)/BS);
for (int i = 0; i < N; i+=BS) D.emplace_back(i, min(i+BS,N), RA, RB);
ll diff = 0;
for (int q = 0; q < Q; ++q) {
int t,v; cin >> t >> v;
--v;
if (t == 1) {
ll x; cin >> x;
for (Block&b:D) b.add(Enter[v],Exit[v],x);
} else {
ll ans = numeric_limits<ll>::min();
for (Block&b:D) ans = max(ans, b.get(Enter[v],Exit[v]));
cout << ans << '\n';
}
}
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
RPPS solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
```

Tutorial is loading...

```
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef long long ll;
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
/** Successive shortest paths algorithm. Runs in O(maxFlow * (|E| + sumCosts)). */
template<typename Cap = int, typename Cost = int>
struct SSPA {
struct Edge{
Cost c; Cap f; int to, rev;
Edge(int _to, Cost _c, Cap _f, int _rev):c(_c), f(_f), to(_to), rev(_rev){}
};
int N, source, sink;
vector<vector<Edge>> G;
SSPA(int N, int source, int sink): N(N), source(source), sink(sink), G(N) {}
void addEdge(int a, int b, Cap cap, Cost cost) {
assert(cap>=0);
assert(a>=0&&a<N&&b>=0&&b<N);
if(a==b){assert(cost>=0); return;}
G[a].emplace_back(b, cost, cap, G[b].size());
G[b].emplace_back(a, -cost, 0, G[a].size()-1);
}
pair<Cap, Cost> minCostMaxFlow() {
/* Vertex potentials. These are maintained so that all edges with non-zero
* residual have non-negative length. Thus, Dijkstra can be used instead of
* Bellman-Ford in each step of the algorithm. */
vector<Cost> Pi(N, 0);
Cost infty = std::numeric_limits<Cost>::max();
Cap totFlow = 0;
Cost totCost = 0;
while (true) {
vector<Cost> D(N, infty);
vector<int> Prev(N, -1);
D[source] = 0;
vector<vector<int>> Q{{source}};
for (int i = 0; i < Q.size(); ++i) {
for (int j = 0; j < Q[i].size(); ++j) {
int u = Q[i][j];
if (D[u] < i) continue;
for (auto &e: G[u]) {
if (e.f > 0) {
Cost c = D[u] + e.c;
if (D[e.to] > c) {
D[e.to] = c;
while (c >= Q.size()) Q.emplace_back();
Q[c].push_back(e.to);
Prev[e.to] = u;
}
}
}
}
}
// if sink is unreachable, flow is optimal
if (D[sink] == infty) break;
// reconstruct some shortest path
int v = sink;
vector<int> Path;
while (v != -1) { Path.push_back(v); v = Prev[v]; }
reverse(Path.begin(),Path.end());
// found the minimum of the edge residuals along the path
Cap augment = std::numeric_limits<Cap>::max();
int L = Path.size();
for (int i = 0; i < L-1; ++i) {
int u = Path[i], v = Path[i+1];
for (auto&e: G[u]) {
// be careful, there might be multiedges
if (e.to == v && e.f > 0 && D[v] == D[u] + e.c) {
augment = min(augment, e.f);
break;
}
}
}
for (int i = 0; i < L-1; ++i) {
int u = Path[i], v = Path[i+1];
for (auto&e: G[u]) {
if (e.to == v && e.f > 0 && D[v] == D[u] + e.c) {
e.f -= augment;
G[v][e.rev].f += augment;
break;
}
}
}
// store the cost & flow size
Cost cost = Pi[source] - Pi[sink] + D[sink];
totFlow += augment;
totCost += cost * augment;
// remove potentials from costs
for (int i = 0; i < N; ++i) {
for (auto &e: G[i]) {
e.c -= Pi[e.to] - Pi[i];
}
}
// add potentials to costs again
for (int i = 0; i < N; ++i) {
for (auto &e: G[i]) {
e.c += (Pi[e.to] - D[e.to]) - (Pi[i] - D[i]);
}
}
// update potentials based on the results
for (int i = 0; i < N; ++i) Pi[i] -= D[i];
}
return {totFlow,totCost};
}
};
class Stock {
public:
void solve(istream& cin, ostream& cout) {
int N; cin >> N;
vector<int> A(2*N), B(2*N);
for (int i = 0; i < 2*N; ++i) {
cin >> A[i] >> B[i];
}
// find T: O(N log MAX log N)
int T = bsl(0, 1000000000, [&](int t) {
// ( (price at 0) x (-price at t) x (is initial stock) )
vector<pair<pair<int, ll>, bool>> Stocks(2*N);
for (int i = 0; i < 2*N; ++i) {
Stocks[i] = {{B[i], -(A[i]*ll(t) + B[i])}, i<N};
}
sort(Stocks.begin(),Stocks.end());
ll best = 0;
vector<ll> CanHave, Required;
for (int i = 0; i < 2*N; ++i) {
best = max(best, -Stocks[i].x.y);
if (Stocks[i].y) {
CanHave.push_back(best);
} else {
Required.push_back(-Stocks[i].x.y);
}
}
sort(CanHave.begin(),CanHave.end());
sort(Required.begin(),Required.end());
for (int i = 0; i < N; ++i) {
if (CanHave[i] < Required[i]) return false;
}
return true;
});
if (T == -1) {
cout << -1 << endl;
return;
}
vector<pair<pair<int,ll>,int>> Begin(2*N);
vector<pair<ll, int>> End(2*N);
for (int i = 0; i < 2*N; ++i) {
ll end = A[i]*ll(T) + B[i];
// bigger start => process later
// bigger end => process earlier
Begin[i] = {{B[i], -end}, i};
// bigger end => process later
// bigger id => process earlier
End[i] = {end, -i};
}
sort(Begin.begin(),Begin.end());
sort(End.begin(),End.end());
reverse(Begin.begin(),Begin.end());
reverse(End.begin(),End.end());
// SSPA, using O(dijkstra * flow)
SSPA<int,int> G(6*N+2, 6*N, 6*N+1);
for (int i = 0; i < 2*N; ++i) {
if (i != 2*N-1) {
int j = Begin[i].y;
int k = Begin[i+1].y;
G.addEdge(N+j, N+k, N, 0); // perform exchange at t=0
j = -End[i].y;
k = -End[i+1].y;
G.addEdge(3*N+j, 3*N+k, N, 0); // perform exchange at t=T
}
if (Begin[i].y < N) {
int j = Begin[i].y;
G.addEdge(6*N, j, 1, 0); // super source
G.addEdge(j, N+j, 1, 1); // exchange for something at t=0
G.addEdge(j, 3*N+j, 1, 0); // hold until t=T
}
if ((-End[i].y) >= N) {
int j = -End[i].y;
G.addEdge(N+j, 5*N+(j-N), 1, 0); // was kept from t=0
G.addEdge(3*N+j, 5*N+(j-N), 1, 1); // was exchanged at t=T
G.addEdge(5*N+(j-N), 6*N+1, 1, 0); // super sink
}
G.addEdge(N+i, 3*N+i, N, 0); // hold between 0 and T
}
auto res = G.minCostMaxFlow();
assert(res.x == N);
cout << T << ' ' << res.y << '\n';
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
Stock solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
```

Hi!

On Jul/20/2019 18:35 (Moscow time) we will host Codeforces Global Round 4.

It is the fourth round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

You will be given 8 problems and 150 minutes to solve them. The scoring distribution will be **500-750-1250-1750-2000-(1500+1500)+3250+4000**.

The prizes for this round:

- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over the whole series get sweatshirts and place certificates.

The problems of this round were developed by me. I will be available on Discord to discuss the problems after the contest.

I would like to thank:

- arsijo for his help in the round's coordination,
- 300iq, Aleks5d, arsijo, Ashishgup, Jeel_Vaishnav, khairy, _kun_, ksun48, Learner99, Noam527, StasyaCat, TonySnark, Um_nik for testing the round,
- MikeMirzayanov for Codeforces and Polygon,
- Pretest for being so strong, TLE for being so rare, system_test for being so fast and Editorial for being ready right after the contest finishes.

UPD: The round is finished. I hope you enjoyed the problems! I am very sorry about the issue on E.

UPD2: Editorial

UPD3: Congratulations to:

UPD4: The results after four rounds.

Announcement of Codeforces Global Round 4

Announcement of Codeforces Global Round 4

I realised I have too much contribution anyway, so I write this blog about G of today's contest.

This problem was plagued by technical issues from start to finish. When you read some of them, you will probably ask yourself how the hell did I get red in the first place.

Originally, the problem had *n* a product of just 2 primes. We then decided to raise it up to 10 primes. I was really confused that I had two types of runs — either they passed with runtime 30ms, or they got TLE or ILE. I added time measurement to the interactor itself, and found out that the 30ms solutions in fact took more than couple seconds to run. The same solutions reported run time of couple seconds in Gym contest that we used for testing. During post contest discussions with MikeMirzayanov I realised that I still don't understand how Polygon and Codeforces measure time for interactive problems.

I am not the fastest duck in the pond, so I investigated my Tonelli Shanks implementation for bugs, found and fixed a couple, but it was still too slow. Only at this point I actually calculated the number of operations needed to find a square root modulo a prime and facepalmed. I realised that only about 10 queries can fit into time limit in the worst case. 10 queries were too few to achieve reasonable success probability even for 2 prime factors.

Luckily, if the prime is of format 4*k* + 3, one can find the square root with just 1 modular exponentiation instead of 5 - 10 for Tonelli Shanks solving the general case. So the problem was changed to only support these primes, the TL and success probability was suddenly more than enough.

We made a way for the contestants to understand the implications of the runtime of the interactor, and were happy with the problem. Oh, how wrong we were! (Side note: After the contest, Mike suggested a better way of doing that, and I will change the problem for practice using this suggestion.)

Fast forward to contest — there is a crashing solution of Shik getting TLE on interactor. I don't see the interaction log in CF interface, so at first glance it seemed to me that he simply used too many queries and the time accumulated. Mike proved me wrong, as his logs showed that my interactor never returned answer to some of the queries.

I took the test case and the queries and modified the interactor so that it just uses stdin/stdout, and I can test and debug it manually outside of Polygon. For some strange reason the GCD was not returning the answer in a timely manner.

In the ensuing chaos we misjudged the situation and introduced the query limit of 100, but it only made matters worse.

I was looking at my GCD implementation like an idiot. More precisely, it is not *my* GCD implementation -- I am using someone else's library for big integers! I've made a few changes to it, but I considered it good, as it never failed me in a contest. Everything seemed fine except it wasn't. Then arsijo pointed out this loop:

```
do {
b >>= b.count_trailing_zeros();
if (cmp_abs(a, b) > 0) a.words.swap(b.words);
sub_unsigned_overwrite(b, a);
} while (b.size() > 0);
```

You don't need to know too much about my implementation to understand that this is roughly equivalent of:

```
do {
if (a>b) swap(a,b);
b -= a;
} while (b != 0);
```

You don't need to be a freaking red to understand that this is really stupid way of writing gcd.

I sighed, changed it to `a = Num::mod(a, b)`

and ran it against Petr's and mine solution in Polygon. You don't need to be freaking red to understand that this is an incorrect fix. You need to have some Polygon experience to understand that this will use your CPU quota in Polygon and lock you out for 5 minutes, which is definitely something you appreciate when you have 10 potentially frustrated/angry contestants getting Denial of judgement.

I sighed again, changed it to `b = Num::mod(b, a)`

, committed the problem and asked arsijo to test it. He managed to lock himself out for some reason as well, and then the polygon returned HTTP 502 for some time. Magic MikeMirzayanov fixed it, saw that it runs correctly and pushed the change to Codeforces. It didn't change the verdicts in the slightest, but luckily it was just a case of a stale cache and it was fixed promptly.

We added a few minutes to the contest duration, but I understand that for some people the contest was already quite unfair or broken. I hope that during the post-contest investigation we found the least possible unfair solution. I would like to thank arsijo and MikeMirzayanov for the immense help with this difficult situation.

For anyone who managed to read this far: the downvote button is just below this sentence, and it looks like a triangle standing on one of its vertices.

**Update**: I realised I forgot to talk about one more important subject. Why the hell did we not find the issue with gcd during contest preparation? I think I know why. All of our solutions apparently did something along the lines of:

- find random
*x*in [1,*N*) - ask for square root of
*x***x*

The crucial thing is that in expectation *x* is *N* / 2, hence *x*^{2} is *N* / 4. For these values, the subtraction gcd seems to run fast in expectation, and we never noticed the issue. When contestants did something else, suddenly things broke. For me, this is an important lesson about testing my problems.

Tutorial is loading...

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b, c;
cin >> a >> b >> c;
cout << min(a + 2, min(b + 1, c)) * 3 - 3;
}
```

Tutorial is loading...

```
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
int main() {
int N; cin >> N;
vector<pii> O(N), T(N);
for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y;
for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y;
sort(O.begin(),O.end());
sort(T.begin(),T.end());
reverse(T.begin(),T.end());
vector<pii> Ans(N);
for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y};
sort(Ans.begin(),Ans.end());
cout << Ans[0].x << ' ' << Ans[0].y << endl;
}
```

Tutorial is loading...

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
ll N; cin >> N;
vector<ll> ans;
for (ll i = 1; i*i <= N; ++i) {
if (N%i==0) {
ans.push_back(N*(i-1)/2 + i);
if (i*i!=N) {
ans.push_back(N*(N/i-1)/2 + N/i);
}
}
}
sort(ans.begin(),ans.end());
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << " \n"[i==ans.size()-1];
}
}
```

Tutorial is loading...

```
#include <iostream>
#include <vector>
using namespace std;
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
inline ui inv(ui a){return pow(a,N-2);}
public:
inline Field(int x = 0) : v(x) {}
inline Field<N> pow(int p){return (*this)^p; }
inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
inline bool operator==(const Field<N>&o) const { return o.v==v; }
inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
inline explicit operator ui() const { return v; }
inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}
typedef Field<998244353> FF;
int main(int argc, char* argv[]) {
int n; cin >> n;
auto F = FF::fact(n);
auto I = FF::invfact(n);
FF ans = n * F[n];
for (int i = 1; i < n; ++i) ans -= F[n]*I[i];
cout << ans << endl;
}
```

Tutorial is loading...

```
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 500000
int N;
int A[MAXN];
long long sum;
#define TOO_SMALL -1
#define OK 0
#define TOO_BIG 1
int is_score(int value) {
vector<int> C(N+1,0);
for (int i = 0; i < N; ++i) ++C[A[i]];
++C[value];
int less = 0;
long long left = 0, right = 0;
for (int k = 0, i = 0; k <= N; k++) {
int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];
left += val;
--C[val];
right -= min(val, k);
less += C[k];
right += N-k-less;
if (left > right + (long long)(k+1)*k) {
return (i == k) ? TOO_BIG : TOO_SMALL;
}
}
return OK;
}
int main(int,char**) {
ios_base::sync_with_stdio(false);
scanf("%d", &N);
sum = 0;
for (int i = 0; i < N; i++) {
scanf("%d", A + i);
sum += A[i];
}
sort(A,A+N,greater<int>());
int parity = sum & 1;
int lo = 0, hi = (N - parity) / 2, lores = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (is_score(2*mid + parity) == TOO_SMALL) {
lo = mid + 1;
} else {
lores = mid;
hi = mid - 1;
}
}
lo = lores;
hi = (N - parity) / 2;
int hires = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (is_score(2*mid + parity) == TOO_BIG) {
hi = mid - 1;
} else {
hires = mid;
lo = mid + 1;
}
}
if (lores == -1 || hires == -1) printf("-1\n");
else {
for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);
printf("\n");
}
}
```

Tutorial is loading...

```
#include <iostream>
#include <vector>
#include <string>
typedef long long ll;
using namespace std;
int main() {
int N; cin >> N;
vector<ll> L(N);
for (ll &l: L) cin >> l;
string T; cin >> T;
bool hadWater = false;
ll time = 0, stamina = 0, twiceGrass = 0;
for (int i = 0; i < N; ++i) {
if (T[i] == 'L') {
time += L[i];
stamina -= L[i];
if (stamina < 0) {
/* not enough stamina, walk or swim "in place" to gain it */
time -= stamina * (hadWater ? 3 : 5);
stamina = 0;
}
} else if (T[i] == 'W') {
hadWater = true;
stamina += L[i];
time += 3 * L[i];
} else {
stamina += L[i];
time += 5 * L[i];
twiceGrass += 2*L[i];
}
/* no more than stamina/2 of walking can be converted to flying to save time,
* otherwise there would not be enough stamina at this point */
twiceGrass = min(twiceGrass, stamina);
}
if (stamina > 0) {
// convert walking to flying
time -= (5-1) * twiceGrass/2;
// convert swimming to flying
time -= (3-1) * (stamina - twiceGrass)/2;
}
cout << time << endl;
}
```

Tutorial is loading...

```
import random
def isPrime(n):
"""
Miller-Rabin primality test.
A return value of False means n is certainly not prime. A return value of
True means n is very likely a prime.
"""
if n!=int(n):
return False
n=int(n)
#Miller-Rabin test for prime
if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:
return False
if n==2 or n==3 or n==5 or n==7:
return True
s = 0
d = n-1
while d%2==0:
d>>=1
s+=1
assert(2**s * d == n-1)
def trial_composite(a):
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
return False
return True
for i in range(20):#number of trials
a = random.randrange(2, n)
if trial_composite(a):
return False
return True
def gcd(x, y):
return x if y == 0 else gcd(y, x % y)
n = int(input())
divs = [n]
def split(parts):
global divs
divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1]
while not all([isPrime(x) for x in divs]):
x = random.randint(0, n - 1)
g = gcd(n, x)
if gcd(n, x) != 1:
split([g, n // g])
continue
y = int(input('sqrt {}\n'.format(x * x % n)))
if x == y:
continue
a, b = abs(x - y), x + y
g = gcd(x, y)
split([a // g, b // g, g])
print('!', len(divs), ' '.join(str(d) for d in sorted(divs)))
```

Tutorial is loading...

```
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
struct Sieve : public std::vector<bool> {
// ~10ns * n
explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) {
at(0) = false;
if (n!=0) at(1) = false;
for (ui i = 2; i*i <= n; ++i) {
if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false;
}
}
vector<int> primes() const {
vector<int> ans;
for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i);
return ans;
}
private:
int n;
};
constexpr int M = 2e5;
auto P = Sieve{M}.primes();
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
vector<int> G(M, 0);
int Q = P.size();
for (int i = 0; i < Q; ++i) {
for (int j = i; j < Q; ++j) {
if (ll(P[i])*P[j] >= M) break;
P.push_back(P[i]*P[j]);
}
}
bitset<M> PB;
for (int p : P) PB[p] = true;
int N, F; cin >> N >> F;
PB[F] = false;
vector<bitset<M>> W(100);
W[0] = PB;
for (int i = 1; i < M; ++i) {
while (W[G[i]][i]) G[i]++;
W[G[i]] |= PB << i;
}
cerr << *max_element(G.begin(),G.end()) << endl;
int g = 0;
for (int i = 0; i < N; i++) {
int r,w,b;
cin >> r >> w >> b;
g ^= G[w-r-1];
g ^= G[b-w-1];
}
if (g == 0) {
cout << "Bob\nAlice\n";
} else {
cout << "Alice\nBob\n";
}
}
```

The end of the December is fast approaching and it is time for the ~~best~~ last contest of the year! The Good Bye 2018 round will take place on Sunday, December 30, 2018 at 14:35 UTC.

As the people who already engaged in discussions about the ultimate problem suspect, I am the problem writer. As such, I'd like to thank to:

- arsijo and KAN for the round coordination and one of the problems,
- AlexFetisov, cyand1317, Errichto, Jeel_Vaishnav, lewin, misof, winger for testing and invaluable suggestions,
- MikeMirzayanov and everyone involved in building and running Codeforces and Polygon platform.

The round will last for 2:30 hours and you will be given 8 problems for both divisions. There will be an interactive problem.

You have the last opportunity to reach Your rating goals for 2018. Good luck!

UPD: The top 3 participants eligible for ICPC 2019/20 season can win a great prize.

UPD2: The scoring distribution is 500-1000-1750-2250-3000-3000-3750-4000.

UPD3: Round is finished. I hope you enjoyed the contest! I am really sorry for the duck-up in problem G. I'll share more details once the important things (systest, editorial ...) are taken care of. The systest might be slightly delayed because of that.

UPD4: Editorial

UPD5: We apologize for the issue with problem G. We are still investigating this issue. Verdicts “Idleness limit exceeded” may be changed to other. We will write a full report about it later.

UPD6: The results are final, rating will be recalculated shortly. Congratulations to the winners:

Announcement of Good Bye 2018

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Lyft Level 5 Challenge 2018 - Elimination Round

Hungry for yet another contest? On Sunday, October 7, 2018 at 17:05 UTC the Lyft Level 5 Challenge will start with the Round 1! This is a **combined round** having 7 problems and lasting 2 hours, and it will be **rated**.

The top **100** participants of this round will win a Lyft Level 5 Challenge **t-shirt**. The top 30 contestants located in the San Francisco Bay area will be invited to the Final Round.

In the **Final Round** the top three onsite contestants will fight for the cash prizes:

- First place: $2000
- Second place: $1000
- Third place: $500

Many thanks to:

- arsijo for the round coordination,
- fhlasek, KAN, Nasic_number_one, Sonechko, StasyaCat, zubec for testing the round
- MikeMirzayanov for Codeforces and Polygon platforms
- Lyft for sponsoring the round
- Alice and Bob for playing a crucial role in some of the statements

I'll be on the community Discord server shortly after the contest to discuss the problems.

**UPDATE 1:** The scoring distribution will be 500-1000-1500-2250-2750-3250-4000.

**UPDATE 2:** The contest is over and there is an editorial.

**UPDATE 3:** Congratulations to the winners:

Hello! On Saturday 15th September 16:00 UTC the contest HackerEarth HourStorm #3 will take place. It’s the third version of a short contest, that runs for 1 hour! The problem set consists of 3 traditional algorithmic tasks of various difficulties.

For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. Keeping the IOI tradition alive, the order of the difficulty of getting full points might be different from the order of difficulty of getting partial points, so make sure you read all the tasks. Check contest page for more details about in-contest schedule and rules.

I am the author of the tasks; but don't despair, they'll be (slightly) easier than my last CF round! Many thanks to jtnydv25 for testing and valuable feedback. As usual, there will be some prizes for the top three competitors:

- $75 Amazon gift card
- $50 Amazon gift card
- $25 Amazon gift card

In addition, top 5 on the scoreboard with rating less than 1600 will win HackerEarth t-shirts.

Good luck to everyone, and let's discuss the problems after the contest!

UPD: Contest finished. Winners:

Topcoder SRM 736 is scheduled to start at 15:00 UTC, August 15, 2018. Note that as per the new Topcoder Open Algorithm rules (see associated discussion on CF) this round counts towards 2019 Topcoder Open Online Stage 1.

The tasks were prepared by me. I'd like to thank misof and paulinia for comments and testing.

You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.

Refer to this guide to set up your environment for competing.

Good luck, have fun, positive rating!

UPD: Congratulation to the winners:

UPD2: Editorial

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of VK Cup 2018 - Round 1

The round 1 of VK Cup 2018 will take place on March 10 at 18:35 MSK (check your timezone). The contest "VK Cup 2018 — Round 1" is for teams qualified from two Qualification Rounds. The top 400 teams will advance to the Round 2, along with teams that qualify in the Wild Card Round 1 a week later. As usual, there will be two parallel rounds for those ineligible to participate in VK Cup, one for each division.

I'd like to thank KAN for steering my crazy ideas into a coherent unit, the coordination and also for suggesting one of the problems, AlexFetisov, qwerty787788, winger, Errichto, Tommyr7 and misof for testing the problems, MikeMirzayanov for building Codeforces and Polygon and VK for organising the contest.

All three rounds last **2 hours**, and all are **rated**. The VK Cup and Div. 1 will have **six** identical problems while the Div. 2 contest will consist of **five** problems. The scoring distribution will be announced before the contest.

The main heroes of this round will be Alice and Bob. Beware that Eve might attempt to foil their plans.

This is my first round on Codeforces and hopefully not the last. Wish you many submissions, high hacks and successful rating.

UPDATE: The scoring in Div.1 and VK Cup round 1 is 500-1000-1500-1750-2250-3000. For Div.2, it is 500-1000-1500-2000-2250.

UPDATE2: The round is finished. I hope you enjoyed it. Tune in a bit later for editorial.

UPDATE3: Congratulations to winners!

Div.1

Div.2

VK Cup

- Perforator, BledDest
- Andrew_Makar, BigBag
- Moskupols, Skird
- SmallBoy, Na2a
- AllCatsAreBeautiful, arsijo

UPDATE4: Editorial

Announcement of VK Cup 2018 - Round 1

Announcement of VK Cup 2018 - Round 1

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/14/2019 00:48:27 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|