1030A - In Search of an Easy Problem

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int curMax = 0;
for(int i = 0; i < n; i++) {
int curAns; cin >> curAns;
curMax = max(curMax, curAns);
}
puts(curMax > 0 ? "HARD" : "EASY");
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int n, d;
int m;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> d;
cin >> m;
for(int i = 0; i < m; ++i){
int x, y;
cin >> x >> y;
bool ok = true;
if(!((x - y) <= d && (x - y) >= -d))
ok = false;
if(!((x + y) <= n + n - d && (x + y) >= d))
ok = false;
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
```

1030C - Vasya and Golden Ticket

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
int sum = 0;
for(int i = 0; i < n - 1; ++i){
sum += s[i] - '0';
bool ok = true;
int pos = i + 1;
int sum2 = 0;
while(pos < n){
sum2 = s[pos++] - '0';
while(pos < n && sum2 + s[pos] - '0' <= sum){
sum2 += s[pos] - '0';
++pos;
}
if(sum2 != sum) ok = false;
}
if(sum2 != sum) ok = false;
if(ok){
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
return a? gcd(b % a, a) : b;
}
int main() {
//freopen("input.txt", "r", stdin);
long long n, m, k;
cin >> n >> m >> k;
bool isEven = k % 2 == 0;
long long p = n * m;
if(isEven) k /= 2;
if(p % k != 0){
cout << "NO" << endl;
return 0;
}
long long x = gcd(n, k);
k /= x;
long long a = n / x;
x = gcd(m, k);
k /= x;
assert(k == 1);
long long b = m / x;
if(!isEven){
if(a < n)
a += a;
else{
assert(b < m);
b += b;
}
}
cout << "YES" << endl;
cout << "0 0\n";
cout << 0 << ' ' << b << endl;
cout << a << ' ' << 0 << endl;
return 0;
}
```

1030E - Vasya and Good Sequences

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 9;
int n;
long long a[N];
int b[N];
int cnt[2][N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i <n; ++i){
cin >> a[i];
b[i] = __builtin_popcountll(a[i]);
}
long long res = 0;
int sufSum = 0;
cnt[0][n] = 1;
for(int i = n - 1; i >= 0; --i){
int sum = 0, mx = 0;
int lstJ = i;
int add = 0;
for(int j = i; j < n && j - i < 65; ++j){
sum += b[j];
mx = max(mx, b[j]);
if(mx > sum - mx && sum % 2 == 0) --add;
lstJ = j;
}
sufSum += b[i];
add += cnt[sufSum & 1][i + 1];
res += add;
cnt[0][i] = cnt[0][i + 1];
cnt[1][i] = cnt[1][i + 1];
if(sufSum & 1) ++cnt[1][i];
else ++cnt[0][i];
}
cout << res << endl;
return 0;
}
```

1030F - Putting Boxes Together

**Tutorial**

Tutorial is loading...

**Fenwick Solution**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
const int MOD = int(1e9) + 7;
int norm(int a) {
if(a >= MOD)
a -= MOD;
if(a < 0)
a += MOD;
return a;
}
int norm(const li &a) {
return norm(int(a % MOD));
}
int mul(int a, int b) {
return int((a * 1ll * b) % MOD);
}
const int N = 200 * 1000 + 555;
int n, q;
int a[N], w[N];
inline bool read() {
if(!(cin >> n >> q))
return false;
fore(i, 0, n)
assert(scanf("%d", &a[i]) == 1);
fore(i, 0, n)
assert(scanf("%d", &w[i]) == 1);
return true;
}
li fW[N], fAW[N];
void inc(li f[N], int pos, li val) {
for(; pos < N; pos |= pos + 1)
f[pos] += val;
}
li sum(li f[N], int pos) {
li ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ans += f[pos];
return ans;
}
li getSum(li f[N], int l, int r) {
return sum(f, r - 1) - sum(f, l - 1);
}
int getNSum(li f[N], int l, int r) {
return norm(sum(f, r - 1) - sum(f, l - 1));
}
inline void solve() {
fore(i, 0, n) {
a[i] -= i;
inc(fW, i, w[i]);
inc(fAW, i, mul(a[i], w[i]));
}
fore(_, 0, q) {
int x, y;
assert(scanf("%d%d", &x, &y) == 2);
if(x < 0) {
x = -x - 1;
inc(fW, x, -w[x]);
inc(fAW, x, -mul(a[x], w[x]));
w[x] = y;
inc(fW, x, w[x]);
inc(fAW, x, mul(a[x], w[x]));
} else {
x--;
li sum = getSum(fW, x, y);
int lf = x, rg = y;
while(rg - lf > 1) {
int mid = (lf + rg) >> 1;
if(2 * getSum(fW, x, mid) > sum)
rg = mid;
else
lf = mid;
}
assert(x <= lf && lf < y);
int ans = norm(mul(a[lf], getNSum(fW, x, lf)) - getNSum(fAW, x, lf));
ans = norm(ans + norm(getNSum(fAW, lf, y) - mul(a[lf], getNSum(fW, lf, y))) );
printf("%d\n", ans);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

**Segment Tree Solution**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 1, int(v.size())) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
int norm(int a) {
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
int norm(const li &a) {
return norm(int(a % MOD));
}
int mul(int a, int b) {
return int((a * 1ll * b) % MOD);
}
const int N = 300 * 1000 + 555;
int n, q;
int a[N], w[N];
inline bool read() {
if(!(cin >> n >> q))
return false;
fore(i, 0, n)
assert(scanf("%d", &a[i]) == 1);
fore(i, 0, n)
assert(scanf("%d", &w[i]) == 1);
return true;
}
li TW[4 * N], TAW[4 * N];
void addVAl(li T[4 * N], int v, int l, int r, int pos, int val) {
if(l + 1 == r) {
assert(l == pos);
T[v] += val;
return;
}
int mid = (l + r) >> 1;
if(pos < mid)
addVAl(T, 2 * v + 1, l, mid, pos, val);
else
addVAl(T, 2 * v + 2, mid, r, pos, val);
T[v] = T[2 * v + 1] + T[2 * v + 2];
}
li getSum(li T[4 * N], int v, int l, int r, int lf, int rg) {
if(l == lf && r == rg)
return T[v];
int mid = (l + r) >> 1;
li ans = 0;
if(lf < mid)
ans += getSum(T, 2 * v + 1, l, mid, lf, min(mid, rg));
if(rg > mid)
ans += getSum(T, 2 * v + 2, mid, r, max(lf, mid), rg);
return ans;
}
int getNSum(li T[4 * N], int l, int r) {
if(l >= r) return 0;
return int(getSum(T, 0, 0, n, l, r) % MOD);
}
pair<int, li> getPos(int v, int l, int r, int lf, int rg, li val) {
if(l == lf && r == rg) {
if(TW[v] <= val)
return make_pair(INF, TW[v]);
if(l + 1 == r)
return make_pair(l, 0);
}
int mid = (l + r) >> 1;
int res = INF;
li sum = 0;
if(lf < mid) {
auto cur = getPos(2 * v + 1, l, mid, lf, min(mid, rg), val);
res = min(res, cur.x);
sum += cur.y;
}
if(rg > mid && res == INF) {
auto cur = getPos(2 * v + 2, mid, r, max(lf, mid), rg, val - sum);
res = min(res, cur.x);
sum += cur.y;
}
return make_pair(res, sum);
}
inline void solve() {
fore(i, 0, n) {
a[i] -= i;
addVAl(TW, 0, 0, n, i, w[i]);
addVAl(TAW, 0, 0, n, i, mul(a[i], w[i]));
}
fore(_, 0, q) {
int x, y;
assert(scanf("%d%d", &x, &y) == 2);
if(x < 0) {
x = -x - 1;
addVAl(TW, 0, 0, n, x, -w[x]);
addVAl(TAW, 0, 0, n, x, -mul(a[x], w[x]));
w[x] = y;
addVAl(TW, 0, 0, n, x, w[x]);
addVAl(TAW, 0, 0, n, x, mul(a[x], w[x]));
} else {
x--;
li sum = getSum(TW, 0, 0, n, x, y);
int pos = getPos(0, 0, n, x, y, sum / 2).x;
assert(x <= pos && pos < y);
int ans = norm(mul(a[pos], getNSum(TW, x, pos)) - getNSum(TAW, x, pos));
ans = norm(ans + norm(getNSum(TAW, pos, y) - mul(a[pos], getNSum(TW, pos, y))) );
printf("%d\n", ans);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

1030G - Linear Congruential Generator

**Tutorial**

Tutorial is loading...

**Dynamic Connectivity Solution**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int MOD = int(1e9) + 7;
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int M = 2000 * 1000 + 555;
const int N = 200 * 1000 + 555;
int n, p[N];
inline bool read() {
if(!(cin >> n))
return false;
fore(i, 0, n)
assert(scanf("%d", &p[i]) == 1);
return true;
}
int minD[M];
vector<pt> ps[M];
void precalc() {
iota(minD, minD + M, 0);
fore(i, 2, M) {
if(minD[i] < i)
continue;
for(li j = i * 1ll * i; j < M; j += i)
minD[j] = min(minD[j], i);
}
fore(i, 2, M) {
int v = i;
ps[i].clear();
while(v > 1) {
int md = minD[v];
if(ps[i].empty() || ps[i].back().x != md)
ps[i].emplace_back(md, 0);
ps[i].back().y++;
v /= md;
}
}
}
int baseA[M], cntNotZero = 0;
int a[M];
int mark[M];
void insert(int v) {
if(a[v] < 1) {
a[v] = 1;
mark[v] = 1;
return;
}
for(auto p : ps[v - 1]) {
a[p.x] = max(a[p.x], p.y);
if(mark[p.x]) {
mark[p.x] = 0;
insert(p.x);
}
}
}
vector<int*> pnt;
vector<int> val;
void upd(int &pos, int nval) {
pnt.push_back(&pos);
val.push_back(pos);
pos = nval;
}
void roll_back() {
*(pnt.back()) = val.back();
pnt.pop_back();
val.pop_back();
}
bool ok[N];
int cntSame = 0;
vector<int> Top[4 * N];
void addOp(int v, int l, int r, int lf, int rg, int val) {
if(l == lf && r == rg) {
Top[v].push_back(val);
return;
}
int mid = (l + r) >> 1;
if(lf < mid)
addOp(2 * v + 1, l, mid, lf, min(mid, rg), val);
if(rg > mid)
addOp(2 * v + 2, mid, r, max(lf, mid), rg, val);
}
void insertDC(int v) {
if(a[v] < 1) {
upd(a[v], 1);
upd(mark[v], 1);
if(a[v] == baseA[v])
upd(cntSame, cntSame + 1);
return;
}
for(auto p : ps[v - 1]) {
if(a[p.x] < p.y) {
upd(a[p.x], p.y);
if(a[p.x] == baseA[p.x])
upd(cntSame, cntSame + 1);
}
if(mark[p.x]) {
upd(mark[p.x], 0);
insertDC(p.x);
}
}
}
void calcAns(int v, int l, int r) {
int curOp = sz(pnt);
for(int cv : Top[v])
insertDC(cv);
if(l + 1 == r) {
ok[l] = cntSame == cntNotZero;
} else {
int mid = (l + r) >> 1;
calcAns(2 * v + 1, l, mid);
calcAns(2 * v + 2, mid, r);
}
while(sz(pnt) > curOp)
roll_back();
}
inline void solve() {
memset(baseA, 0, sizeof baseA);
memset(a, 0, sizeof a);
memset(mark, 0, sizeof mark);
fore(i, 0, n)
insert(p[i]);
cntNotZero = 0;
fore(i, 0, M) {
baseA[i] = a[i];
cntNotZero += a[i] > 0;
}
memset(a, 0, sizeof a);
memset(mark, 0, sizeof mark);
fore(i, 0, n) {
if(i > 0)
addOp(0, 0, n, 0, i, p[i]);
if(i + 1 < n)
addOp(0, 0, n, i + 1, n, p[i]);
}
calcAns(0, 0, n);
int lcm = 1;
fore(i, 1, M)
lcm = mul(lcm, binPow(i, baseA[i]));
int add = 0;
fore(i, 0, n)
if(ok[i])
add = 1;
cout << (lcm + add) % MOD << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
precalc();
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

**Greedy Solution**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int MOD = int(1e9) + 7;
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int M = 2000 * 1000 + 555;
int minD[M];
vector<pt> ps[M];
inline void precalc() {
iota(minD, minD + M, 0);
fore(val, 2, M) {
if(minD[val] < val)
continue;
for(li j = val * 1ll * val; j < M; j += val)
minD[j] = min(minD[j], val);
}
fore(i, 2, M) {
int v = i;
ps[i].clear();
while(v > 1) {
int md = minD[v];
if(ps[i].empty() || ps[i].back().x != md)
ps[i].emplace_back(md, 0);
ps[i].back().y++;
v /= md;
}
}
}
int n;
vector<int> p;
inline bool read() {
if(!(cin >> n))
return false;
p.assign(n, 0);
fore(i, 0, n)
assert(scanf("%d", &p[i]) == 1);
return true;
}
int a[M], cnt[M];
inline void solve() {
sort(p.begin(), p.end(), greater<int>());
for(int& cp : p) {
if(a[cp] == 0) {
a[cp] = 1;
cnt[cp] = 1;
} else {
cp--;
for(auto np : ps[cp]) {
if(a[np.x] < np.y) {
a[np.x] = np.y;
cnt[np.x] = 1;
} else if(a[np.x] == np.y)
cnt[np.x]++;
}
}
}
int add = 0;
for(int cp : p) {
bool un = false;
for(auto np : ps[cp])
un |= (a[np.x] == np.y && cnt[np.x] == 1);
if(!un)
add = 1;
}
int lcm = 1;
fore(i, 2, M)
lcm = mul(lcm, binPow(i, a[i]));
cout << (lcm + add) % MOD << endl;
}
int main(){
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int t = clock();
#endif
cout << fixed << setprecision(10);
precalc();
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - t << endl;
#endif
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define PII pair <int, int>
const int N = 1e6 + 7;
int n;
int in[N];
int ans[N];
bool used[N];
vector <int> unused;
int cnt;
deque <PII> cur;
vector <PII> getEqual;
set <int> S;
vector <int> place[N];
vector <pair <int, int> > order;
bool check(){
if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1])
return false;
for(int i = 1; i + 1 < n + n; ++i)
if(in[i] == in[i + 1] && in[i] != 0)
return false;
for(int i = 1; i < n + n; ++i){
if(in[i] == 0)
continue;
if(place[in[i]].size() == 0)
order.push_back({i, in[i]});
place[in[i]].push_back(i);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j < place[i].size(); ++j)
if(place[i][j]%2 != place[i][j - 1]%2)
return false;
S.insert(n + n);
sort(order.begin(), order.end());
for(auto v: order){
auto it = S.lower_bound(v.first);
if(*it < place[v.second].back())
return false;
for(int c: place[v.second])
S.insert(c);
}
return true;
}
inline int get(){
if(unused.size() == 0){
puts("no");
exit(0);
}
int ret = unused.back();
unused.pop_back();
return ret;
}
void go(){
deque <PII> help;
while(help.size() + cur.size() >= 3){
if(help.size() < 3){
help.push_back(cur.front());
cur.pop_front();
continue;
}
PII v1 = help.back(); help.pop_back();
PII v2 = help.back(); help.pop_back();
PII v3 = help.back(); help.pop_back();
if(v1.st == 0 && v2.st != 0 && v3.st != 0){
ans[v1.nd] = v3.st;
help.push_back(v3);
}
else{
help.push_back(v3);
help.push_back(v2);
help.push_back(v1);
}
if(cur.size() == 0)
break;
help.push_back(cur.front());
cur.pop_front();
}
while(help.size()){
cur.push_back(help.front());
help.pop_front();
}
}
void solve(int root){
int need = (cur.size() + 1) / 2 - cnt;
if(need < 0){
puts("no");
exit(0);
}
deque <PII> help;
while(cur.size()){
auto v = cur.front();
cur.pop_front();
if(need > 0 && v.st == 0){
--need;
v.st = get();
ans[v.nd] = v.st;
}
help.push_back(v);
}
while(help.size()){
cur.push_front(help.front());
help.pop_front();
}
go();
if(root == -1 && cur.back().st == 0){
root = cur.front().st;
ans[cur.back().nd] = root;
cur.pop_front();
cur.pop_back();
solve(root);
return;
}
reverse(cur.begin(), cur.end());
go();
while(cur.size() > 0){
auto v = cur.front();
cur.pop_front();
if(v.st == 0)
ans[v.nd] = root;
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i < n + n; ++i){
scanf("%d", &in[i]);
used[in[i]] = true;
}
if(!check()){
puts("no");
return 0;
}
if(in[1] != 0)
in[n + n - 1] = in[1];
else if(in[n + n - 1] != 0)
in[1] = in[n + n - 1];
for(int i = 1; i <= n; ++i){
if(!used[i])
unused.push_back(i);
used[i] = false;
}
for(int i = 1; i < n + n; ++i)
ans[i] = in[i];
for(int i = 1; i < n + n; ++i){
if(in[i] == 0){
getEqual.push_back({in[i], i});
continue;
}
if(used[in[i]]){
cnt = 0;
while(getEqual.back().st != in[i]){
if(getEqual.back().st > 0){
++cnt;
used[getEqual.back().st] = false;
}
cur.push_front(getEqual.back());
getEqual.pop_back();
}
solve(in[i]);
continue;
}
getEqual.push_back({in[i], i});
used[in[i]] = true;
}
cnt = 0;
while(getEqual.size()){
if(getEqual.back().st > 0){
++cnt;
used[getEqual.back().st] = false;
}
cur.push_front(getEqual.back());
getEqual.pop_back();
}
solve(-1);
puts("yes");
for(int i = 1; i < n + n; ++i)
printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' ');
return 0;
}
```

Editorial launched even before System testing. I'm loving this !

Next time, editorial before contest ends!

It happened already check https://codeforces.com/blog/entry/60209

Why not before contest starts?

:( For most of the time I thought that you can only do one swap per integer in Div1B, guess I need to read more carefully next time

I thought there were zeros in the array :(

The functions that defines the limits of the x — y values are changed on the B's picture.

Yes they are. Overlooked it when drew the picture.

Why is

`mymap.erase(it)`

giving runtime error. I know that`it=mymap.erase(it)`

should be done. But the first one is running in all other compilers like hackerrank, codechef, my mac laptop. Why is it not running here in codeforces?Iterating and Erasing simultaneously causes undefined behaviour.

Why is it running on almost all other compilers then?

Also I came to know a few days back that

`long`

and`long long`

are not the same in codeforces but same on almost all other compilers.Why is codeforces compiler different?

`long`

is 4-byte data type while`long long`

is 8-byte. In which compiler they have the same range?See this.

All other ide's at https://wandbox.org https://ide.geeksforgeeks.org https://www.codechef.com/ide and my macbook gave the ouput as 9223372036854775807 for both.

Strange.

It's not.

In 64-bit systems

`long`

will be the 8-byte data type.It's C++ standard. You can read more here: cppreference: Fundamental types.

And

`int`

has to be less than`long`

but it's not similar on different compilers. Also read cppreference.Check it yourselves.

Codeforces output:

`4 4 8`

My pc output (64-bit):

`4 8 8`

No. In the C++11 standart method "erase(iterator)" returns iterator on the next element in container. So "it = mymap.erase(it)" is correct code.

Can someone explain solution for D? How do you get to sides a and b? Why are we dividing k by 2 if it is even, why are we multiplying later, etc.

area of the triangle will be (a*b)/2 = (n*m)/k writing it as a*b = (2*n*m)/k we are calculating a in terms of n and b in terms of m. so we could've done something similar to link

But it will be just writing extra code.

If a>n can be true how you sure that in 2nd if condition

hereb>m will be always false. Can you please explain??

sorry for bad english.

since a*b = (2 * n * m) / k; if( a > n ) => b < (2*m/k) since, k>=2 => k/2 >= 1 => b < m / (k/2); => b < m

Let's consider only the case when one point is at $$$(0,0)$$$. For other cases, you can always move to this case (by shifting the points).

We'll build a rectangle inside the rectangle $$$n \times m$$$, with area equal to $$$2*m*n/k$$$, and we'll split the rectangle to get the triangle.

When $$$k$$$ is even ($$$k=2t$$$), we need to build a rectanble with area $$$m*n/t$$$. This number must be an integer, so $$$m*n$$$ must be divisible by t. This leads to the solution in the editorial. $$$g = gcd(t,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = t/g$$$ and $$$a,b$$$ is the sides of the rectangle

When $$$k$$$ is odd, $$$m*n$$$ must be divisible by $$$k$$$. Similarly, we have: $$$g = gcd(k,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = k/g$$$. Note that at this time, $$$a$$$ and $$$b$$$ is the sides of the rectangle with area $$$n*m/k$$$. We need to double one side to get the desired rectangle.

If $$$a < n \rightarrow g \geq 3$$$ (because $$$g$$$ is neither 1 nor even) $$$\rightarrow a \leq n/3 \rightarrow 2a < n$$$

If $$$a = n \rightarrow g = 1 \rightarrow g' = k \geq 3$$$ (note that $$$k$$$ is odd). Similarly, we get $$$2b < m$$$

So we can always double $$$a$$$ or $$$b$$$.

Thanks for your effort in writing this editorial.

I wasn't able to solve problem

Div.2 E.When I read the editorial I find you are writing

for the key idea of the problem."It can be proven"Please mention the proof or mention the intuition behind the two conditions.

Make

`0`

is equivalent to pairing ones in such way that there is no pair with ones from the same number. If`max>sum/2`

it's obviously impossible. Otherwise, just divide all ones in two groups of the same size in such way that there is no more than one number with ones in both groups. And there is always a way to pair ones from different groups.I was confused about this . Thanks a lot.

Thanks adedalic. I would just like to point out that we can prove that such a division is always possible since

And then we can just match pairs from different groups.

Can someone help me understand why I was failing Div 2E, pretest 8? Would be really grateful

https://codeforces.com/contest/1058/submission/43335816

P.S. I used the same approach that the editorialist used

I figured it out — it should have been tot[i-1] instead of tot[i], and j-1 instead of j. Passes now

My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972

I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.

You must check "KpartitionsPossible" until 9 * n

The problem is not that, the problem is that the code is giving correct output on codeblocks and codechef ide but not here.

you didn't check 'pos' != -1 in line 28

UPD: i changed line 28

and it was accepted

43343643

Thanks for your effort. But why does this give the correct answer on codeblocks and codechef IdE and other compilers?

because ide can eat some bugs and re)

So how do I even make sure that my code is correct? This way i'll never know for sure if my code is correct or not before submitting. I still feel this has been a little unfair to me.

When you try access an index out of bounds, many times, compilers on codechef or other online ones, tend to return zero or garbage value. Basically, it tries to access element at pos*(data_type_size) from the base of the array. So, if pos is -1, it access the element before 0th element of the array.

Thanks a lot for your help. I guess i can't even trust compilers when it comes to codeforces. :(

The problem is not in the compiler. Suppose you have the code:

What this code is supposed to print? There is no certain behaviour because you haven't assigned anything to 'arr'. It will just print what was laying there in the memory and it may differ from launch to launch. The same thing happened in your case.

Thanks a lot. Made this completely clear to me.

Who cares about rating? There's a contest like every 3-4 days.

But when your contest is going good and you would have achieved blue in this very contest and you did not because of such errors,it does feel sad. :(

The tutorial for Div 1E claims that if you have two equal values then there is a subtree between them which can be solved independently of the rest of the problem. But that's not necessarily true e.g. given the input 1 2 0 3 1 the only right answer is 1 2 1 3 1, and the interval 2 1 3 does not describe an Euler tour of a subtree of 1.

I wrote this tutorial about month ago, now I see a lot of small mistakes in it. This is

O(n) solution:SolutionAnd a little bit modified tutorial:

TutorialFirst let's try to find some conditions whether it is possible to recover correct euler tour. Of course for every euler tour

a_{i}≠a_{i + 1}anda_{1}=a_{2n - 1}(because we start and finish in root).Moreover if there exist four index

i_{1}<i_{2}<i_{3}<i_{4}such thata_{i1}=a_{i3}anda_{i2}=a_{i4}anda_{i1}≠a_{i2}than answer isNO(because vertex is an ancestor of another or there is no relation between them) — let's call it "crossing elements" condition.There are more conditions — parity of positions of all occurences of element

xare the same (because we visit every edge in our subtree twice) and between two equal elements with distance 2kthere can be at mostkdistinct elements.It turns out that those conditions are sufficient — we will prove it by constructing an answer.

So first let's observe that if we have to equal elements it means that there is subtree (or maybe subtrees) between them — we can solve it almost independently from the rest of a tree (all we need to remember is root of this subtree) and then forget about this subtree. So as long as we have two equal elements

i<jthan we can first solve euler tour between them and then delete elementsi+ 1,i+ 2...,j. So now we want to solve euler tour where no element occur more than once.Let's say that this tour has length 2

k- 1 then if we have less thankelements we can replace any 0 with any unused elements. We can't have more because of our conditions.Now if there are three elements in a row with values

x,y, 0 or 0,y,xthan we can replace them withx,y,xand replce it withx. If we get rid of all triplets like this than we have tour in form ofa_{1}, 0,a_{2}, 0, ..., 0,a_{k}. It's easy to observe that we can replace every 0 with our root (subtree's root). There is a special case when we don't have any root (if solving for whole tree), than we have to find any vertex which can be root and then solve our problem. Straightforward implementation will beO(n^{2}) but it can be easily reduced toO(nlogn) and it can be even reduced toO(n), butO(nlogn) was enough to be accepted.To solve this in

O(n) we should start with making check of some conditions. It's easy to check most of them except "crossing elements" condition and count the number of distinct elements between two equal elements. We will deal with the second condition while generating correct answer. For "crossing elements" we can for every valuexcompute valuer_{x}equal to number of distinct elements which appears in input before first occurence ofx. Now just iterate over every non-zero element (in order from 1 to 2n- 1 with deque/vector of elements with smallerr_{x}than our current element. Then with some easy checks we can determine if our condition is true.After checking conditions we want to create a vector of unused elements (with 0 occurences in our tour). Now we can iterate over array as long as there are no two equal elements in our prefix, if we find two equal elements then we can solve part between them and delete them from our current prefix (details in code).

Now add elements as long as in our part of length 2

k- 1 there are less thankelements. If it turns out that we don't have enough "unused" elements it means that the last unchecked condition doesn't hold.How to find all triplets in

O(n)? We can make two steps — in first steps find all tripletsx,y, 0 (iterate with stack from left to right) and in second step find all triplets 0,y,x(similarly iterate from right to left). At the end replace all zeroes between with root.Big thanks to Grzmot who wrote great statement and helped me with proving that this solution is correct!

Can someone explain the second condition of Div2E

`maximal element should be lower or equal to the sum of all other elements`

UPDGot it! :)Explain it, please.

Suppose you have numbers:

Can you change the position of bits so the xor of the numbers equals to zeros?

In total you can only remove 4+2+2 bits but you have 10 bits in the number 1111111111 so you cannot remove two last bits and thus this sequence is bad.

Can You please explain why these two conditions are sufficient?

Let me give it a try.

I hope you understand why, even bits are required. Let me try to explain the other condition.

Lets say for in a subarray for size

K, [a1,a2,a3,...,ak] is count of set bits (setbits array). Also, lets assume a1 >= a2 >= a3 .. >= ak, so a1 is the maximum in the setbits array. Now, I will try to greedily nullify the a1 bits. So, first I nullify a2 bits of a1 using a2. Now, (a1-a2) bits of a1 are left, and a2 is nullified. Now I will greedily use, a3 bits to nullify those (a1-a2) bits of a1. Two cases arise:a3 <= (a1-a2)

a3 > (a1-a2)

For the first case, I use, all of a3, and now I need to nullify (a1-a2-a3), so I go ahead with using a4, and move ahead. Again, two similar cases arise.

For the second case, so I can at max use (a2-a1) bits of a3, and will be left with (a3-a2+a1) bits,(say x, for simplictity) of a3. I don't want that.

So, basically, what I will do is, I will take x bits from a2, and x bits from a3, such that, a2+a3-2x = a1, so now a1 can be nullified, and then x bits from a2 and x from a3 can nullify each other, so we are left with zero.

Although, this is not a very formal proof, I hope I was able to give enough intuition for the constructive algorithm to arrange the bits when the two conditions are satisfied.

Thank you lohit_97.

Hello what about this exapmle 1111 1111 1100 sum of 1's is even and max elemnt is lower or equal to sum of all others but those numbers do form not good sequence! UPD:I got it

I not understand the editorial for Div2-F.Please can you or someone else explain that too?

Thanks!

I also need that. Can someone please explain us??

For the second case your explanation gives x=(a2+a3-a1)/2.How do u prove that this is an integer?

If it isn't then there is a number with an extra bit after it which will help us nullify it.

EDIT: I was so waiting for someone to ask this :P

Loved the tutorial of problem E.....Thanks a lot.

Roms Test cases of D problem seems to be weak :( . Some users coded for smaller k like k=2(and the test cases don't include 'yes' with k=3 or more for the worst case) and got AC.

Can provide link to one such submission?

https://codeforces.com/contest/1058/submission/43318617 : works for 5s on k=3,n=m=1e9-1

It also depends on the processor of your machine. Maybe your machine is slow.

I checked it on custom invocation, btw the solution is O(sqrt(n*m/k)), which takes O(1e9) in worst case

Pretest 10 was 1000000000 1000000000 2

LOL

"the test cases don't include 'yes' with k=3 or more for the worst case"

Hi! I tried my best to understand the editorial for Div2-F https://codeforces.com/contest/1030/problem/F but could not understand it.

My doubts are in understanding the proof that keeping 1 box unmoved is optimal and how does that total cost of shifting left parts in the end equal to a_k*S(l,k-1) — sum(w_i*a_i)?

Thanks!

Can somebody explain DIV2 E editorial with the sample test case 1?

F can also be done with only BIT in

O(logn)You are right, so did segment tree.

How?

In tutorial of the problem Div:2-D, how to prove b=(m/k') is always an integer.

Notice that the area is always a multiple of one-half.

So after you divide k by 2 ,(n*m)/k' will be a integer.

Let's make an assumption that m/k'=x/y (gcd(x,y)=1),

Because (n*m)/k' is a integer,n/(gcd(n,k))should be a multiple of y,

That comes to a contradiction because you should divide n by y(both n and k have the factor--y).

As a result,m/k' is always an integer.

In problem E, How to prove that if maximal element is lower or equal to the sum of all other elements then the subsequence is good ?

if this condition holds and the sum of the sequence is even, you can decrease the two biggest numbers by one and preserve this property. so, at every step you can decrease the sum of the sequence by 2 and eventually it's sum will become zero, which means this squence is good.

proof: let k be the number of occurences of the maximal number x in a sequence with even sum and 2*x<=sum. in case k=1 or k=2: the operation above decreases the maximal number at least by one and decreases the sum exacly by two so the invariant still holds.

in case k>=4, after the operation there are at least two numbers with max value x so the sum is at least 2*x which means the invariant holds.

in case k=3, after the operation the max element is x and the sequence has sum of at least x+(x-1)+(x-1)=3*x-2 which is greater or equal 2*x for every x>=2. the case x=1 can't happen because the sum of the sequence will be odd, so also in here the invariant hold

"and eventually it's sum will become zero, which means this squence is good." why this means sequence is good? Me also waiting proof of this

Decrease two numbers corresponds to position two ones in the binary representation of the original numbers at the same place. When the ones are at the same place in both numbers, the XOR will cancel one with the other, and we can ignore them. If the sum of the sequence reached zero it means that every one has another which cancels it, and the XOR result is zero.

Ah, thanks. I was thinking about partition problem. I was trying to find counter example that if you have array satisfying this two conditions, and it can't be devided into two of equal sums. But your proof is not related to partition problem, because here you can use bits of single number in any pair.

Can someone explain to me why doubled area of any triangle with integer coordinates is always integer? How can we demonstrate that?

https://en.wikipedia.org/wiki/Cross_product

Area of triangle (0, 0), v = (x1, y1), u = (x2, y2) is |x1 * y2 — x2 * y1| / 2

you can draw the minimal rectangle with sides parallel to the x and y axis that blocks the triangle (for example, the rectangle corrisponding to triangle (0,0), (1,5) , (2,4) is (0,0) , (5,0), (5,4) , (0,4)). it's divided into 4 triangles, the original one and 3 more Straight-angle triangles. it's clear that each one of them has integer doubled area, and the rectangle's area is also an integer, so the original triangle must also have integer doubled area.

Thank you!

In problem F, how can we actually do this part: find k in(nlogn) by "descending" down the Segment Tree in

In the fourth paragraph of the 1053E, the "than" in the first row should be "then".

“Problem B” Can anybody explain me,why x+y=d — diagonal?

In DIV2 Problem E, Something Strange is happening. Here: http://codeforces.com/contest/1058/submission/43418325 in Testcase 1 and same code on IDEone: https://www.ideone.com/iiTZkx Getting WA on test case 1 on Judge but produces correct output on my machine.

Also, I am interested in knowing the result of test case 5.I am using prefix sum here. My program produces 7 as result, Because no. of set bits are: 8 16 16 18 22. So, for 8, there are 0 prefix, 16 : 0 prefix, 16 : 2, 18: 2 prefix and 22: 3 prefix. Total equals to 7. Please explain how the answer is 3 for this test case?

Hi, I suggest compiling with the flag -Wall

In lines 59 and 73 you have the condition

`j > (i-66, 0)`

, maybe you forgot a max? Also, the variable`maxm`

is not initialized in 0 so it could have garbageI don't know if this is the only problem but I hope it helps

hey can anyone tell why this solution is giving WA for second task?......

when i am submitting like this it is giving AC -

int sum=pow(2,freq)-1;

link for correct solution. https://www.codechef.com/viewsolution/20327375 but when i am using this-

cout pow(2,freq)-1 ;

it is not giving AC

link...

https://www.codechef.com/viewsolution/20329958

thanks in advance..... @arpa

Function pow probably return float value, try convert to int like that: (int)pow(2,freq)-1. And use please logic operations, pow(2,freq) equal 1 << freq.

problem link https://www.codechef.com/problems/MGCSET

but why this solution is giving AC for subtask-1

when i am printing the answer like this

cout pow(2,freq)-1 ;

solution link https://www.codechef.com/viewsolution/20329958

@Alexit

thanks in advance...

because if float value >= 1e6 you print exponentially value. cout << pow(2,20)+1 << "\n"; //print 1.04858e+06 cout << (int)pow(2,20)+1 << "\n"; //print 1048577

In Div2 D, Doubled area of any triangle with integer coordinates is always integer. Can anyone explain this statement.Why is it always true?

https://www.mathopenref.com/coordtrianglearea.html — Area of a triangle when the three vertices are known.

Since all points need to be integral, the formula will always yield a whole number or a (whole number/2). Hence!

Div2E does it means when r-l>60 and sum(l,r)%2==0 and max(l,r)*2<=sum(l,r), you can always divide the ones into two groups with same size? how to prove that?

My solution of problem E:

If

i<janda_{i}=a_{j}≠ 0,a[i..j] is an Euler tour, we can deal witha[i..j] and replace it witha_{i}.Since

a[i..j) doesn't contain the same elements except 0's, we can do this operation:If there are 3 consecutive elements

a_{i - 1},a_{i},a_{i + 1},a_{i}≠ 0 anda_{i - 1},a_{i + 1}contain exactly one 0 (ora_{i - 1}=a_{i + 1}≠ 0), we can regarda_{i}as a leaf and leta_{i - 1}=a_{i + 1}(equals to the non-zero element), then removea_{i}anda_{i + 1}. It can be proved correct.After operations, combine the first and the last element to form a cycle, if there are two consecutive non-zero elements, there mustn't be any zero and no solution exists (because a tree with two or more vertices must contain a leaf). Otherwise, any two non-zero elements aren't neighbors, all the elements can be regarded as leaves, it's easy to construct.

After there aren't any

i<jthata_{i}=a_{j}, we can deal with the whole series using the same way.All operations can be done by stack in linear time.

Time complexity:

O(n).In DIV2 E, can someone explain " Let's find a way to decide whether fixed segment is good or not. It can be proven that two conditions must be met. At first, sum of bi at this segment should be even. At second, maximal element should be lower or equal to the sum of all other elements." How about this case: b1=3, b2=4, b5=5, i think this satisfy the condition, but this case is not good. Am i right?

Let's see, how we can get zero in this case. As we can move the ones we can get something like this:

11111

11110

11100

Shift the bits of b2 to two positions to the right, make the xor of b2 and b5(I mean the xor of numbers from which b2 and b5 were got) and then you can get zero as you get two numbers which contain 3 ones.

I understand, thx

How do people come up with the intuition for problems like div1 C? Once I read the editorial it's so clear but I thought for half an hour and I didn't even get to the first observation. Is "solve more problems" the only way?

Interesting problems...