Опять же, я надеюсь, что вам понравились все задачи. Делитесь своими идеями и альтернативными решениями в комментариях. Итак, разбор:
В данной задаче достаточно вывести $$$n - 3$$$, $$$1$$$, $$$1$$$, $$$1$$$. Нетрудно убедиться, что этот ответ подходит для любого $$$n \ge 4$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n';
}
return 0;
}
1665B - Техника массивного клонирования
Будем действовать жадно. Найдём элемент в исходной версии, который встречается чаще всех. Пусть этот элемент равен $$$x$$$ и он встречается $$$k$$$ раз. Тогда сделаем такую версию массива, в которой все элементы равны $$$x$$$. Для этого создадим копию данного массива, сложим все элементы, равные $$$x$$$, в один массив. Теперь повторим все действия с новой версией массива. Так продолжим до тех пор, пока не получим версию из $$$n$$$ элементов, равных $$$x$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
map<int, int> q;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++q[x];
}
int am = 0;
for (auto &[x, y] : q) {
am = max(am, y);
}
int ans = 0;
while (am < n) {
int d = min(n - am, am);
ans += 1 + d;
am += d;
}
cout << ans << '\n';
}
return 0;
}
Сначала заметим, что для любых двух различных вершин их дети независимы. Это значит, что инфекция не может распространяться между детьми двух различных вершин. Также неважно, как инфекция распространяется среди детей одной вершины, поэтому нам достаточно знать только количество вершин с одинаковым родителем.
Используя эти знания мы можем свести данную задачу к следующей: Дан массив из $$$k$$$ положительных целых чисел, где каждое число означает количество здоровых вершин с одинаковым родителем. Каждую секунду можно выбрать одно число в этом массиве и заразить его (с помощью инъекции). Также каждую секунду все заражённые числа уменьшаются на 1 (из-за распространения).
Для решения этой задачи используем жадный алгоритм. Отсортируем массив в порядке убывания и заразим все числа по порядку. Эти инъекции необходимы, потому что числа независимы. После этого каждую секунду все числа будут уменьшаться на 1, причём мы можем выбрать ровно одно число, которое будет уменьшено дополнительно на 1 (инъекцией). Этим числом должен быть выбран максимум в массиве.
Эта задача может быть решена симуляцией процесса, потому что сумма чисел в этом массиве изначально равна $$$n$$$.
#include <bits/stdc++.h>
using namespace std;
int ans;
void proc(vector<int>& a) {
if (a.empty()) return;
int n = a.size();
int last = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == a[0]) {
last = i;
} else {
break;
}
}
--a[last];
for (int i = 0; i < n; ++i) --a[i];
++ans;
while (!a.empty() && a.back() <= 0) {
a.pop_back();
}
proc(a);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
vector<int> a(n);
ans = 0;
for (int i = 1; i < n; ++i) {
int x;
cin >> x;
++a[--x];
}
a.emplace_back(1);
sort(a.rbegin(), a.rend());
while (!a.empty() && a.back() <= 0) a.pop_back();
n = a.size();
for (int i = 0; i < n; ++i) {
a[i] = a[i] - (n - i);
++ans;
}
sort(a.rbegin(), a.rend());
while (!a.empty() && a.back() <= 0) a.pop_back();
proc(a);
cout << ans << '\n';
}
return 0;
}
Решение 1
Будем последовательно узнавать остаток числа при делении на степени двойки. Изначально мы знаем, что остаток при делении на $$$2^0 = 1$$$ равен $$$0$$$. Как, зная остаток $$$r$$$ по модулю $$$2^k$$$, узнать загаданное число по модулю $$$2^{k+1}$$$? Для этого спросим про $$$\gcd(x + 2^k - r, 2^{k+1}) = \gcd(x+ 2^k - r, x+2^k - r+2^{k+1})$$$. Если $$$\gcd$$$ равен $$$2^{k+1}$$$, то новый остаток равен $$$r + 2^{k-1}$$$, иначе он остаётся равен $$$r$$$. Так мы дойдём до остатка загаданного числа по модулю $$$2^{30}$$$, т.е. получим само число. Получаем решение за $$$30$$$ запросов.
Решение 2
Рассмотрим множество попарно взаимно простых чисел $$${23, 19, 17, 13, 11, 9, 7, 5, 4}$$$. Их $$$\text{lcm} > 10^9$$$, поэтому если мы найдём остаток при делении $$$x$$$ на $$$\text{lcm}$$$, то мы найдём и само число $$$x$$$. Узнаем остаток числа $$$x$$$ по модулю каждого из этих чисел. Чтобы это сделать, для каждого $$$1 \le i \le 23$$$ будем спрашивать $$$\gcd(x + i, x + \text{lcm} + i)$$$, т.е запрос $$$(i, \text{lcm} + i)$$$. Если полученный $$$\gcd$$$ кратен какому-то числу из нашего множества, то остаток $$$x$$$ по модулю этого числа равен $$$-i$$$. После этого по китайской теореме об остатках мы можем восстановить $$$x$$$. Получаем решение за $$$23$$$ запроса.
Замечание 1: Достаточно сделать $$$22$$$ запроса, т.к. если для всех чисел до $$$22$$$ такого $$$i$$$ не было, то $$$23$$$ точно подойдёт.
Замечание 2: Можно не писать КТО в явном виде, это можно сделать проще, т.к. все модули маленькие, смотрите реализацию.
#include<bits/stdc++.h>
using namespace std;
int ask(int a, int b) {
cout << '?' << " " << a << " " << a + b << endl;
int ans;
cin >> ans;
return ans;
}
void solve() {
int r = 0;
for (int i = 1; i <= 30; i++) {
int ans = ask((1 << (i - 1)) - r, (1 << i));
if (ans == (1 << i)) r += (1 << (i - 1));
}
cout << '!' << " " << r << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#define lc 1338557220
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll x, rs[maxn], p;
vector<ll> pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};
ll ask(ll a, ll b) {
cout << "?" _ a _ b << nf;
ll x; cin >> x; return x;
}
void clm(ll x) {
cout << "!" _ x << nf;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
/* #if !ONLINE_JUDGE && !EVAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif */
// kudos for automatic wa
cin >> t;
while (t--) {
for (i = 1; i <= 23; i++) {
k = ask(x + i, lc + i);
for (j = 0; j < 9; j++) {
if (k % pw[j] == 0) rs[j] = i % pw[j];
}
}
k = 1; p = 1;
for (j = 0; j < 9; j++) {
// cout << "p =" _ p << nf;
while (p % pw[j] != rs[j]) p += k;
k *= pw[j];
}
clm(lc - p);
}
return 0;
}
Основная идея, на которой построено всё решение, заключается в том, что ответ обязательно находится среди не более чем 31 минимальных чисел. Тогда можно построить дерево отрезков на минимум, после чего для ответа на запрос необходимо не более чем 31 раз найти минимум (заменяя найденные минимумы на $$$\infty$$$), а потом посчитать все возможные попарные $$$OR$$$ среди этих 31 чисел.
Также можно построить Merge Sort Tree и применить те же рассуждения.
Доказательство основной идеи: докажем по индукции, что если все числа меньше $$$2^k$$$, то достаточно рассмотреть $$$k+1$$$ минимум.
База индукции: $$$k=1$$$, тогда все числа от $$$0$$$ до $$$1$$$, и утверждение очевидно.
Индуктивный переход:
Пусть для $$$k$$$ утверждение верно, докажем для $$$k+1$$$. Если у всех чисел в $$$k$$$-м бите 1, то в ответе тоже 1, поэтому нам надо минимизировать оставшиеся биты, а для них по предположению индукции достаточно рассмотреть $$$k + 1$$$ минимум. Если хотя бы у двух чисел в $$$k$$$-м бите 0, то в ответе в $$$k$$$-м бите тоже 0. Тогда нас интересуют только числа с 0 в $$$k$$$-м бите, и дальше нам нужно минимизировать оставшиеся биты, поэтому опять по предположению индукции даже $$$k+1$$$ числа хватит. Если есть ровно одно число с 0 в $$$k$$$-м бите, то в ответе $$$k$$$-й бит точно 1, и нам нужно найти $$$k+1$$$ минимальных по $$$k$$$ битам чисел. Но они точно содержатся среди $$$k+2$$$ минимальных по $$$k+1$$$ битам чисел, поэтому $$$k+2$$$ чисел хватит.
#include<bits/stdc++.h>
using namespace std;
const int MAXK = 31;
const int INF = (1 << 30);
vector<pair<int, int>> t;
pair<int, int> get(int v, int vl, int vr, int l, int r) {
if (vl >= l && vr <= r) return t[v];
if (r <= vl || l >= vr) return make_pair(INF, INF);
int vm = (vl + vr) / 2;
return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
}
void mod(int v, int vl, int vr, int id, int val) {
if (vr - vl == 1) {
t[v] = make_pair(val, id);
return;
}
int vm = (vl + vr) / 2;
if (id < vm) mod(2 * v + 1, vl, vm, id, val);
else mod(2 * v + 2, vm, vr, id, val);
t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &c : a) cin >> c;
t.resize(4 * n);
for (int i = 0; i < n; i++) mod(0, 0, n, i, a[i]);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
l--;
vector<pair<int, int>> b;
for (int i = 0; i < min(r - l, MAXK); i++) {
auto now = get(0, 0, n, l, r);
b.push_back(now);
mod(0, 0, n, now.second, INF);
}
int ans = (1LL << 31) - 1;
for (int i = 0; i < (int)b.size(); i++) {
for (int j = i + 1; j < (int)b.size(); j++) ans = min(ans, b[i].first | b[j].first);
}
for (auto &c : b) mod(0, 0, n, c.second, c.first);
cout << ans << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define cld complex<ld>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define all(m) m.begin(), m.end()
#define uid uniform_int_distribution
#define fast cin.tie(0); cout.tie(0); cin.sync_with_stdio(0); cout.sync_with_stdio(0);
using namespace std;
using str = string;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<typename T> bool chmax(T& a, const T& b) {return b > a ? a = b, 1 : 0;}
const uint NO = 1<<30;
template<unsigned K>
struct VebTree{
uint mn, mx;
VebTree<(K>>1)> *m[1<<((K+1)>>1)];
VebTree<((K+1)>>1)> *aux;
VebTree(){
memset(m, 0, sizeof(m));
aux = 0;
mn = mx = NO;
}
inline bool empty() const{
return mx==NO;
}
inline uint high(uint x) const{
return x>>(K>>1);
}
inline uint low(uint x) const{
return x&((1<<(K>>1))-1);
}
inline uint merge(uint x, uint y) const{
return (x<<(K>>1))+y;
}
bool find(uint x){
if(x==mn || x==mx) return 1;
return m[high(x)] && m[high(x)]->find(low(x));
}
void insert(uint x){
if(mx==NO) mn = mx = x;
else if(mn==mx) mn = min(mn, x), mx = max(mx, x);
else if(x<mn || x>mx){
uint add = x<mn ? mn : mx;
mn = min(mn, x);
mx = max(mx, x);
insert(add);
}
else if(K>1){
uint hi = high(x), lo = low(x);
if(!m[hi]) m[hi] = new VebTree<(K>>1)>();
if(m[hi]->empty()){
if(!aux) aux = new VebTree<((K+1)>>1)>();
aux->insert(hi);
}
m[hi]->insert(lo);
}
}
void rem(uint x){
if(mn==mx){
mn = mx = NO;
return;
}
if(x==mn){
if(!aux || aux->empty()) {mn=mx; return;}
else mn = x = merge(aux->mn, m[aux->mn]->mn);
}
else if(x==mx){
if(!aux || aux->empty()) {mx = mn; return;}
else mx = x = merge(aux->mx, m[aux->mx]->mx);
}
uint hi = high(x), lo = low(x);
m[hi]->rem(lo);
if(m[hi]->empty()) aux->rem(hi);
}
uint next(uint x){
if(empty() || x>=mx) return NO;
if(x<mn) return mn;
if(K==1) return mx;
uint hi = high(x), lo = low(x);
if(m[hi] && !m[hi]->empty() && m[hi]->mx > lo) return merge(hi, m[hi]->next(lo));
uint next_hi = aux ? aux->next(hi) : NO;
return next_hi==NO ? mx : merge(next_hi, m[next_hi]->mn);
}
uint prev(uint x){
if(empty() || x<=mn) return NO;
if(x>mx) return mx;
if(K==1) return mn;
uint hi = high(x), lo = low(x);
if(m[hi] && !m[hi]->empty() && m[hi]->mn < lo) return merge(hi, m[hi]->prev(lo));
uint prev_hi = aux ? aux->prev(hi) : NO;
return prev_hi==NO ? mn : merge(prev_hi, m[prev_hi]->mx);
}
};
const int G = 1e5 + 5, SZB = 300;
int a, z;
int m[G], ans[G];
int cng[G], cnt[G];
array<int, 3> que[G];
int cl, cr;
VebTree<32> veb, lox;
void add(int ps) {
int res = ++cnt[cng[ps]];
if(res==1){
veb.insert(m[ps]);
}
if(res==2){
lox.insert(m[ps]);
}
}
void rem(int ps) {
int res = --cnt[cng[ps]];
if(res==0){
veb.rem(m[ps]);
}
if(res==1){
lox.rem(m[ps]);
}
}
uint go() {
uint o = 0;
uint mn = NO;
vec<int> del;
for(int k=29; k>=0; k--){
uint x = o+(1<<k);
uint cur = veb.prev(x), sz = 0;
if(cur!=NO && cur>=o){
++sz;
cur = veb.prev(cur);
if(cur!=NO && cur>=o){
++sz;
}
}
if(sz==0) o += 1<<k;
else if(sz==1){
uint c = veb.prev(x)+(1<<k);
if(veb.find(c)) chmin(mn, c);
else {
veb.insert(c);
del.pb(c);
}
o += 1<<k;
}
}
for(uint i : del) veb.rem(i);
return min({mn, o, lox.mn});
}
void compress(){
vec<int> kek(a);
for(int q=0; q<a; q++) kek[q] = m[q];
sort(all(kek));
kek.erase(unique(all(kek)), kek.end());
for(int q=0; q<a; q++){
cng[q] = lower_bound(all(kek), m[q])-kek.begin();
}
}
void solve() {
cin >> a;
for (int q = 0; q < a; q++) cin >> m[q];
cin >> z;
for (int q = 0; q < z; q++) {
int l, r; cin >> l >> r; l--; r--;
que[q] = {l, r, q};
}
sort(que, que + z, [](array<int, 3> & p1, array<int, 3> & p2) {
int l1 = p1[0] / SZB;
int l2 = p2[0] / SZB;
if (l1 != l2) return l1 < l2;
return l1 % 2 == 0 ? p1[1] < p2[1] : p1[1] > p2[1];
});
cl = cr = 0;
compress();
fill(cnt, cnt+a, 0);
add(0);
for (int i = 0; i < z; i++) {
int ql = que[i][0];
int qr = que[i][1];
for (; cr + 1 <= qr; ) add(++cr);
for (; cl - 1 >= ql; ) add(--cl);
for (; cr > qr;) rem(cr--);
for (; cl < ql; ) rem(cl++);
ans[que[i][2]] = go();
}
for(; cl<=cr;) rem(cr--);
for (int q = 0; q < z; q++) cout << ans[q] << "\n";
}
int main() {
fast;
int z; cin >> z;
for (; z--;) {
solve();
}
}
#include <bits/stdc++.h>
using namespace std;
const size_t MEMSIZE = 1e9 / 3.8; // in bytes
constexpr size_t MX_ALIGN = alignof(std::max_align_t);
char __attribute__((aligned(MX_ALIGN))) memory[MEMSIZE];
size_t memorypos;
void * operator new(size_t n){
if (memorypos + n >= MEMSIZE) {
memorypos = MEMSIZE / 3;
}
char *ret = memory + memorypos;
memorypos = size_t((memorypos+n+MX_ALIGN-1)&-MX_ALIGN);
return (void*)ret;
}
void operator delete(void *){}
void operator delete(void *, size_t){}
struct Node{
int l, r, cnt, val;
Node *lptr = nullptr, *rptr = nullptr;
Node(int l, int r, int cnt = 0, int val = -1) : l(l), r(r), cnt(cnt), val(val){}
Node(Node* lptr, Node* rptr) : lptr(lptr), rptr(rptr) {
l = lptr->l, r = rptr->r;
cnt = lptr->cnt + rptr->cnt;
val = max(lptr->val, rptr->val);
}
void extend(){
if(!lptr && l != r){
int m = l + (r - l) / 2;
lptr = new Node(l, m);
rptr = new Node(m + 1, r);
}
}
pair<int, int> merge(pair<int, int> a, pair<int, int> b){
return {a.first + b.first, max(a.second, b.second)};
}
pair<int, int> query(int lq, int rq){
if(lq > rq) return {0, -1};
extend();
if(lq == l && rq == r) return {cnt, val};
else{
int m = l + (r - l) / 2;
pair<int, int> a = lptr->query(lq, min(m, rq)), b = rptr->query(max(m + 1, lq), rq);
return merge(a, b);
}
}
};
Node* update(Node* v, int k, int indx){
v->extend();
if(v->l == v->r) return new Node(v->l, v->r, v->cnt + 1, indx);
else{
if(k <= v->lptr->r) return new Node(update(v->lptr, k, indx), v->rptr);
else return new Node(v->lptr, update(v->rptr, k, indx));
}
}
const int N = 1e5 + 5;
int t, n, q, arr[N], l, r, curnum;
Node* roots[N];
vector<int> vec;
pair<int, int> query(int l, int r, int lnum, int rnum){
pair<int, int> p;
p.first = roots[r]->query(lnum, rnum).first - roots[l - 1]->query(lnum, rnum).first;
p.second = (p.first ? roots[r]->query(lnum, rnum).second : -1);
for(auto i : vec) if(i >= lnum && i <= rnum) p.first++;
return p;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
roots[0] = new Node(0, 1 << 30);
for(int i = 1; i <= n; i++) roots[i] = update(roots[i - 1], arr[i], i);
cin >> q;
while(q--){
cin >> l >> r;
curnum = 0;
vec.clear();
for(int i = 29; i >= 0; i--){
pair<int, int> p = query(l, r, curnum, curnum + (1 << i) - 1);
if(p.first >= 2) continue;
else if(p.first >= 1 && p.second != -1){
vec.push_back(arr[p.second] | (1 << i));
curnum += 1 << i;
}
else{
curnum += 1 << i;
for(auto &j : vec) j |= (1 << i);
}
}
cout << curnum << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> t;
while(t--){
solve();
}
}
#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) a.begin(), a.end()
using namespace std;
using ll = long long;
template<class T> bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }
template<class T> bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
void solve() {
int n; cin >> n;
vector<int> a(n); for (auto &x : a) cin >> x;
vector<unordered_map<int, vector<int>>> cnt(30);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 30; ++j) {
cnt[29-j][a[i]>>j].push_back(i);
}
}
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r; l--; r--;
int x = 0, pref = 0;
vector<int> tmp;
for (int j = 0; j < 30; ++j) {
pref*=2;
vector<int> newtmp;
int k = upper_bound(all(cnt[j][pref]), r) - lower_bound(all(cnt[j][pref]), l);
int k0 = k;
for (auto y : tmp) {
if (((y>>(29-j))&1) == 0) k++, newtmp.push_back(y);
}
if (k0 == 1) {
int id = lower_bound(all(cnt[j][pref]), l) - cnt[j][pref].begin();
tmp.push_back(a[cnt[j][pref][id]]);
}
if (k < 2) pref++;
else tmp.swap(newtmp);
}
cout << pref << "\n";
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) solve();
return 228/1337;
}
- Задача A
- Идея: shishyando
- Polygon: shishyando
- Задача B
- Идея: shishyando
- Polygon: shishyando
- Задача C
- Идея: shishyando
- Polygon: shishyando
- Задача D
- Идея: Artyom123
- Polygon: shishyando
- Задача E
- Идея: Kirill22
- Polygon: shishyando
- Перевод на английский: shishyando
- Special thanks: KAN за координирование координатора и перепроверку всего
- Ещё special thanks: NEAR за поддержку Codeforces Community!
- И ещё special thanks: всем, кто участвовал и тестировал!
Автокомментарий: текст был обновлен пользователем shishyando (предыдущая версия, новая версия, сравнить).
Thanks for the fast editorial!
Also thanks for the fast system testing!
Thanks for the fastest editorial.
Seems like fast editorials are being the trend recently. A welcoming trend, for sure.
Wow, Fast editorial
Thank you very much
Thanks for the fast editorial! And problems are so nice :)
Спасибо за контест, подскажите, когда начислится рейтинг?
через 24 часа точно будет
can someone explain D with more details
Here was my reasoning (same as first approach):
Answer? Use fact 1 ,gcd(X+ (2^(n) — x), X + (2^(n+1)-x)) = gcd(X + (2^n -x),2^n) = gcd(X-x,2^n), which is used as an indicator for next bit.
At step n+1, we know the first n bits of X, i.e. x. Propose a= 2^(n)-x; b = 2^(n+1)-x; If gcd is 2^n, then next bit is 1, else 0
still don't get it..
"Say we have learned that x = ?????01. Then, removing the last two bits (by subtracting 1) to get x', and then doing gcd with 2^2 will tell us 3rd bit."
If we remove last two bits in x, then gcd with 2^2 will be 2^2.. doesn't matter what 3rd bit is. How do we get whether 3rd bit is 0 or 1?
"if we know X starts with x in the first n bits, then doing gcd(X-x, 2^n) tells us next bit."
won't the gcd always be 2^n if you remove first n bits from X ?
You are right. To check bit n, you need gcd with 2^(n+1).
I meant to say that you need to check with gcd 2^3. If the next bit is a zero, then the gcd will give you 2^3, otherwise next bit is a one.
The rest needs a little tweaking but the idea is the same.
Thanks for the great explanation. But, I think this would need some workaround as 2^(n + 1) would exceed 2*10^9 (if n = 30).
why If gcd is 2^n, then next bit is 1, else 0
Because if the next bit was 0, it would imply that the number has another 2 as a factor. This would mean that there exists a greater divisor than 2^n, i.e. gcd >= 2^(n+1). Since this is not true, if gcd is 2^n then next bit must be 1
Basically, you should visualize the number in the binary form. Now you can check what is the kth bit if you have Y, with the propriety: X + Y has the first (k — 1) bits set. Now you can check if the kth bit is set by querying (Y + 1 , Y + 1 + 2^(bit + 1) , if this is 2 ^ (bit), then you add it to the answer, otherwise you update Y.
You can check my comment dowm, I tried to explain D clearly
Thanks for this rubbish trash boring disgusting fucking meaningless Problem C that I didn't have enough time to write E
That's because you are not good enough noob
Problem C was nice
Totally agreed, Also the question statement is still wrong. He has written ancestor in "where pi is the ancestor of the i-th vertex in the tree". By ancestor, he is meaning parent. He has not even defined this definition of ancestor.
Sonic Speed Editorial
Is there any other solution for A other than [1,n-3,1,1]||[n-3,1,1,1]??
I'm not exactly sure, but in n%4=0 case you can make a=b=c=d=n/4
Yeah, check mine. Looks like I always overlook easy solutions and complicate it more :/.. 153033103
n = odd -> x, x + 1, 1, 1 -> (x = (n — 3) / 2) n % 4 = (0) -> x / 4 each n % 4 = 2 -> x, x + 2, 1, 1 -> (x = (n — 4) / 2)
n % 4 == 2 works because (n -> 4y + 2) -> x = (4y — 2) / 2 = 2y — 1
we get => a = 2y — 1, b = 2y + 1 (2 consecutive odd numbers are co-prime)
lol.
I thought there were 4 situations when $$$n = 4k$$$, $$$n = 4k + 1$$$, $$$n = 4k + 2$$$ and $$$n = 4k + 3$$$.
k k k k;2k 2k-2 1 2;2k 2k+1 1 1or3k k-1 1 3.Then I realized the correct solution and gave up thinking of the $$$n = 4k + 2$$$ situation.
why so tight constraint(a,b<2000000000) for d? that forced to think exactly like you which is not always possible;
I mean 30 queries points to powers of two so you don't need bigger numbers.
for example, my solution:https://mirror.codeforces.com/contest/1665/submission/153069764. It is correct if you remove this idiot restriction!!!
What's weirder is that no tester was competent enough to point this out... what a waste of time.
Same! It took me some time to figure out why I was getting wrong answer on test 1 :(
Can someone please explain why my C solution doesn't work? 153069119
Failing testcase: Ticket 3684
A very educational round with a fast editorial!!! I really like it, especially for the nice E, extremely educational.
In Editorial 1 for D, shouldn't it be $$$x \pmod{2^{k+1}} = r + 2^k$$$ ?
yes
Can you please prove this? I am getting it as x%(2^(k+1)) = r — 2^k
$$$x \mod 2^{k + 1} = \left(r - 2^k \right) \mod 2^{k + 1} = \left(r - 2^k + 2^{k+1} \right) \mod 2^{k + 1} = r + 2^k $$$
It seems like my solution for C is different from the editoral, I used binary search
How do you determine if the tree can be infected in say x seconds (I understand if we can infect it in x then we can infect it in X+1,X+2,...N)? Or can you explain your approach?
In my solution I don't work on a tree, just all nodes of the same parent are put in a set (and node $$$1$$$ is alone in a set) and I make an array for the sizes of those sets, when I infect a set, it decreases by one every second, and for a set to decrease I need to inject it, so I will inject all $$$m$$$ sets first (lets say we have $$$m$$$ sets), it is obvious I want the biggest set to be injected first, so it decrease more early than the other sets, since I inject the $$$m$$$ sets I will use $$$m$$$ seconds, if I sort all sets by size, for each $$$i$$$ $$$(1 <= i <= m)$$$ set number $$$i$$$ size is decreased by $$$i$$$ elements (the size of the set is the number of non-infected nodes), so I already made the optimal move for the first $$$m$$$ sets, I already know now that for every second all sets decrease by one, so I can binary search on the number of extra second $$$x$$$, I decrease every set size by $$$x$$$, and then I get the summation of the remaining positive sizes of sets, if it is smaller than or equal to $$$x$$$ then x is valid (because I have $$$x$$$ injections) otherwise $$$x$$$ is not valid, and the answer is the $$$minimum$$$ $$$valid$$$ $$$x + m$$$
Thank you for explaining your approach...
you are welcome
Finally i understood how i can use binary search. BTW better explanation than editorial.
In my opinion,D is much easier than C,since it takes me almost an hour to solve C and WA 5 times,and it takes me half on hour to solve D.
/
Thousands of people learned today not to use stl::unordered__map in competitive programming.
Yeah I used to know about it, but I've been out of the game for so long that I completely forgot lol.
Same, it sucks that the time limits are that tight when asymptotically, one is $$$O(1)$$$ and the other is $$$O(log n)$$$
Well, personally I don't think that sucks, just something need to know for participating competitive programming. I'm competing again after three years and it's like a welcome back lmao.
I mean u could resort to gp_hash_table if u really need to use some sort of hash map
For which question? I'm new to CP and used unordered_map but didn't get any problems? What are the alternatives?
You can used custom hash in your unoredred_map for safety. see this : (https://mirror.codeforces.com/blog/entry/62393)
My solution took 46ms which is also using unordered map. Maybe your problem got TLE because of some other reason! (not sure though!)
The reason your solution passes is because you are using a slightly newer implementation (C++20 instead of C++17). Try it with C++17 compiler.
I liked the problem, I didn't like the TL constraints. I mean, it's an algorithmic contest, so when you write O(N) solution instead of the "intended" O(N*logN) you are supposed to pass. But no — since you are using the standard library of a specific implementation of specific language you fail, even though your solution is correct (and will pass, if the system used another implementation of the same language, or even if you selected another version from the drop-down).
Let's give problems that exploit specific bugs in the language implementations, yey, so smart, amazing! Too bad the Timsort bug required too large inputs to be viable for a programming contest, it would make an AWESOME problem where you need to sort numbers, but fail if you use the built-in sort.
C was interesting, but I wasn't able to solve it. Thanks for the round!
Problem B giving tle on unordered_map code while got ac using map code. I know unordered_map time complexity is O(n) in worst case and O(1) in best case so should we only use map for safer side? and how to determine where should we use unordered_map or map? thanks in advance.
I think this entry might help(?)
Thanks.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
I've also added 2 new features: Near real-time log streaming and Compressed Parameter editing without using tables.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Hi! It says that I'm violating constraints, even though I'm pretty sure I'm not: https://cfstress.com/status/3708
Oh, my bad.
Actually, constraint violation is a catch all phrase for when input file is not present. It could be either due to the fact that the generator crashed (i,e. actual constraint violation) or the submission didn't compile (with c++17). (Of course, I could write a better error message, and I'll make that improvement in future).
This was the error that occurred while compiling your submission:
It works now, thanks!
Bobrosoft I fixed the compilation error and ran it on the parameters that you had selected. Here's the counter example I received.
Thanks a lot, I was able to fix my code! Although it did make me pretty miserable, knowing how close I was to getting 5/5, but that's definitely not a flaw in the service. :D
Hi, I tried some parameters but it seems no counter example is found. Problem 1665-C, submission 153078042
Failing testcase: Ticket 4721
See first revision to find out how I created this corner case.
hey how u get to know about these failed test cases
I'm the creator of CF Stress, that finds the testcases for you. But, it's not free to use.
ohkay
153071478
https://cfstress.com/status/3803
For problem C, I couldn't find a counter test case.
For C, I couldn't find a test case that breaks this submission 153256577, (EDIT: I figured it out ~2 minutes after writing this comment lol)
For Problem C, I could not find counter test. It's failing on tc-20 Submission ID: 153299261 https://mirror.codeforces.com/contest/1665/submission/153299261
Contest ID = 1665 Problem Index = C Submission ID = 153057004
Why unordered map is giving TLE in problem B, but map works?? My solution was basically the same as the one in the editorial, only difference was it used unordered map instead of map.
https://mirror.codeforces.com/blog/entry/62393 <- this is why, probably.
Thanks! So it better to use unordered map with custom_hash or map?
Yes, either of those should work.
I have a solution E that catches ML.
Let's build a merge sort tree from tries. Then when we respond to the request, we make a descent over <= log n trues. We go from the highest bit to the smallest. Now let's say there are cnt numbers by which we can go left. Then if cnt >= 2, then we'll just go left. And if cnt < 1, then if cnt = 1, then we add this number to some array b on the left, and we ourselves go to the right. After that, the answer will be found as some b[i] | b[j]
I used same approach to find answer in the trie, but instead of merge sort tree of tries, u could use persistent trie to find cnt on the segment. This is my solution: https://mirror.codeforces.com/contest/1665/submission/153079376
It doesn't catch ML though: https://mirror.codeforces.com/contest/1665/submission/153095546. :)
UPD: sorry, I probably misunderstood your solution. I had one trie, and for each node in it, I stored all indices in the array that have the same bit prefix.
failed maine test on problem C , WA on test 20 can someone tell what's wrong in this code ?
Solution link
Failing testcase: Ticket 3709
i failed in test 20 too . can you help me to know why?
solution link
Failing testcase: Ticket 3762
Hey can you help me find a wrong test case in C failing system test 20:
Solution Link
mine is also failing on test 20 for problem c
https://mirror.codeforces.com/contest/1665/submission/153048693
please help me find counter test case
Did anyone AC problem D using the CRT solution?
153047261
I used the CRT implementation from this blog.
I'm sorry, but can you please explain the CRT solution in detail ?
Mostly i cannot understand 2 things -
Why we are using gcd(x+i, x+lcm+i)
How can we be sure that 30 queries are enough to fill all the a[i] values. Isn't it possible that the gcd we got in response isn't divisible by any of them ?
If $$$gcd(x+i, x+i+lcm)$$$ is divisible by some integer $$$y$$$, then $$$x+i \equiv 0 \mod y$$$, in other words $$$x \equiv -i \mod y$$$.
All the prime integers I’m using as modulos for the CRT (2, 3, 7, 11, 13, 17, 19, 23, 29) are less than 30, so it’s certain that for each of them, at least one integer in $$$[x, x+30)$$$ divides it.
Brilliant !! Thank You.
I had a slightly different approach to D.
At every step, I would add padding to the number and make sure that it is divisible by 2, 4, 8, ... .
For example, if the hidden number is 5, I would first check if it is even by asking (+2, +4).
Since it is not even, I must pad the number by +1.
Then, I make sure it is divisible by 4. I ask (padding, padding+4), which is (+1, +1+4). This returns 2, which means that I must further add 2 to the padding to get +3 padding.
Then, I make sure it is divisible by 8. I ask (padding, padding+8), which is (+3, +3+8). This returns 8, which means that I must further add 8 to the padding to get +11 padding.
I repeat this process until 2^30 and I can finally subtract the padding from 2^30 to get the original number.
The padding may be equal to 0. Instead of asking (padding, padding+2^n), ask (2^n * 2, 2^n).
Asking (2^n * 2, 2^n) might overflow the problem constraints. In this case, ask (2^n / 2, 2^n).
I used similar solution except with +1 and +3. This way the padding is -1 for odd number and 0 for even.
unordered_map gave TLE in problem B.. (T T)
In C
Doesn't that mean you do at most 2 operations each second?
You do two operations : then he specified the two operations, meaning you have to do them both (the two types)
Can someone please explain why my C solution doesn't work? Solution
Failing testcase: Ticket 3794
The 2nd solution for problem D is neat! Thanks!
So many fsts for test case 20 in problem C. Can anyone explain why I got fst on test 20 ? 153064962
same i also got wron gon test 20 https://mirror.codeforces.com/contest/1665/submission/153080174 link
In editorial of Problem D [Solution 1], the value of x mod 2^(k+1) should be r + 2^k and not r+2^(k-1).
I have another approach for E.Let we will solve all queries together.We will go from greater bit to lowest.If we have at least two zeros in a greater bit we have 0 in it in the answer,and we can push the query to the array of numbers,which have zeros at our bit.Otherwise,we push the query to the array of all numbers we have now.This solution works in O(nlog^2) memory and O(nlog^3) time.The every query was in 30 layers one time.Let we will count sum of the lengths of the arrays we process.It is the sum for each element of it's total count.It is at most 30*(count of nodes where element goes to both sons).But if in some node element goes to both sons,then is has 0 in this bit,and it was a query when it is the only zero.But then the sum of (count of nodes where element goes to both sons) by elements is at most number of queries at all layers(each query gives us at most 1)<=30*q,so our soluiton runs in (n+q)*30^2 memory and (n+q)*30^2*log time. (The main moment is that in each node i eliminate all elements,which are not used in queries).So we have much slower solution,but without and ideas:)
link: https://mirror.codeforces.com/contest/1665/submission/153052760
Can anyone tell me why this solution for C doesn't work? Link
I count all the nodes which must be infected, (the solution can't be less than this), I will call this count
infectthe other nodes (which can be added by spread), let's call them
spreadif infect is greater than spread, so the minimal solution is infect because all the spread nodes can be taken in the way of infecting the other cells.
Otherwise, I will just add 1 second (the first node which must be added by infection) then the remaining nodes of the tree can bed added two by two (one by infection and one by spread)
Thanks in advance for your help
Thank you.
I've figured out that I misunderstood the problem. The spread can go in parallel for more than one node for different parents at the same time.
In problem c, After updating the atleat one child of a parent as infect we use ans++ and cnt-1 to queue i think in one time we (spread+inject) so ans+=2 and cnt-2 will be inserted can anyone clarify https://mirror.codeforces.com/contest/1665/submission/153080174 link to my sol
I think my solution for 1665E - MinimizOR is hackable: 153083146 In short, I split queries bit by bit, and when I set bit to 0 I also filter the numbers.
Here's a screencast of me doing todays codeforces round:))
ENG: D could be done even simpler in my opinion!
We can find each bit of number easily!
Let's firstly note, that: gcd(p,q)=gcd(p,p-q). How can we use it? let's see that gcd(x+a,x+b)=gcd(x+a,b-a) (let's suppose b>a)
Let's each step store in 'a' inversed bits of our number 'x' (bitwise "not") + 1 (pay attention to +1!). So that x+a=2^k for some k.
So, we start with a=1, and each step 'i' (i=1 to 30) we set b=a+2^i, what's same as b-a == 2^i.
So, we see that gcd(x+a,x+b) will be same as gcd(x+a,b-a) <=> gcd(x+a, 2^i)
Then, if gcd(x+a,2^i) == 2^i, then, obviously x+a is divisible by 2^i, what means in 'a' there are first I bits of 'x' inversed +1, so because at the i-th step i-th digit of 'a' is 0 it means i-th digit of 'x' is 1
otherwise, if gcd(x+a,2^i) != 2^i, it means i-th digit of 'x' is 0 so we set i-th digit of 'a' to 1 to make it inverted 'x' <=> a+=2^i.
That's pretty much all. So, what did we do? Each step we found if the i-th digit of number is 1 or 0, so after 30 steps we find the whole number.
Code: 153089001
P.S. tried my best to explain, if you have any questions, reply to my comment!
RU: На мой взгляд, D можно было решить даже проще!
Мы можем найти каждый бит (т.е. цифру в двоичной записи) числа даже проще.
Вовпервых, отметим что НОД(p,q) = НОД(p,p-q). Как можно использовать это? Заметим, что НОД(х+а,х+b)=НОД(x+a,b-a) (возьмем b>a)
Будем хранить в 'a' противоположные загаданному числу биты +1 (обратите внимание на +1). (т.е. побитовое НЕ). Таким образом в конце мы получим a+x=2^31
Начнем с а=1, и каждый шаг цикла 'i' (i от 1 до 30) будем брать b=a+2^i, т.е. b-a = 2^i.
В таком случае НОД(x+a,x+b) == НОД(x+a,b-a) == НОД(x+a,2^i)
Теперь, если НОД(x+a,2^i)==2^i, то очевидно, x+a делится на 2^i, что значит в все биты 'a' являются побитовым нет первых i битов загаданного числа и +1, а т.к. на i-том шаге i-тый бит 'a' равен нулю, это значит что i-тый бит в загаданном числе равен единице
Иначе если НОД(х+а,2^i) != 2^i, то на i-той позиции загаданного числа стоит ноль, после чего мы должны сделать i-тый бит инвертированным i-тым битом загаднного числа, проще говоря присвоить ему единицу, т.е. а+=2^i.
Таким образом, за каждый шаг мы узнаем 1/0 на i-той позиции, что за весь цикл соберёт нам полное число.
Код: 153089001
Пы.Сы. Постарался обьяснить предельно понятно, но если у кого то всё же возникнут вопросы, отвечайте на комментарий, спрашивайте
So that x+a=2^k for some k. Why is this true?
'a' is initially 1. Each step we verify if in picked number 'x' i-th digit is 1 or 0, so if it is 1 we add 2^i to ans, otherwise we add 2^i to 'a'.
So, for example for some x=100110101, 'a' will be = 011001010 + 1 (initial value)
So, x+a will be 111111111 + 1, which is 1000000000 == 2^some k
When i=30, the value of b would be a + 2^30. But b should be <= 10^9.
Constraints: "a, b <= 2*10^9"
Be more attentive when you read constraints ;)
How can I get the key idea for the solution is that the answer always lies among no more than 31 minimal numbers? why?
I love problem E because it has so many different ways to solve it!
Can you please explain one thing about E, i.e. why keeping track of 31 min values is required ? why not just 2 most minimums ? answer would be their OR then, because they have lowest max significant bits.
Consider array $$$[1, 2, 2]$$$.
Thanks for many different solutions!
Could someone please explain me the "Other solutions" of problem E?I think I don't really understand that.
Tyyyyyy will be crooked
Can anyone help me, why is my solution for A giving WA?
for n=6, you will get 2,0,2,2 numbers should be greater than 0.
Can anyone help why my submission for problem C has FST WA on testcase 20. 153086129 I calculated the time required for injecting one sibling, then tried to spread and inject other.
Can anyone tell why in problem C the answer to the following test case should be 4 and not 5? 8 4 8 8 1 8 1
Можно, пожалуйста, пояснение по задаче D? Почему gcd(x + 2^k — r, 2^(k+1)) равен gcd(x + 2^k — r, x + 2^k — r + 2^(k + 1))??? Откуда в правой части взялось 2^k — r? И почему gcd должен быть именно 2^(k — 1)? И почему при этом остаток становится r + 2^(k — 1)??
Почитай мой коммент выше, постарался предельно ясно обьяснить, если что, готов и на вопросы ответить
Can anyone explain why my C solution is not working? submission
Problem D, we asked $$$\gcd(x+2^k-r,2^{k+1})$$$. If the result is $$$2^{k+1}$$$, shouldn't $$$x\bmod 2^{k+1}=r+2^k$$$?
Or am I mistaken?
What brief problems there are! Just like math!
I really don't understand why my solution for Problem B got TLE on test case 13 when I used hash map. And after the contest when I submitted same solution just by using simple map, it got accepted.
TLE
Accepted
https://mirror.codeforces.com/blog/entry/62393
Thankss!
average CRT D solver
I'm having some trouble figuring out my error for problem C. I tried printing the test case I got wrong (test 6 case 246) and got:
Am I missing something or shouldn't this test case be n=11 since there are 10 inputs on the second line? Original submission: https://mirror.codeforces.com/contest/1665/submission/153081192
I dont understand why i get wrong-ans in problem C test case 20. I try so hard but can't fix it.Plz help me anyone to fix.
https://mirror.codeforces.com/contest/1665/submission/153127622
Thanks.
Getting TLE on test case 5 in Java O(nlogn) solution, can someone tell what's wrong? link
spookywooky can you explain this part of your code for problem C..!
This is simulating the process. The idea is to maintain that priority_queue, where we store foreach vertex the day that all children of that vertex are finished. $$$cnt$$$ is the number of days.
Initially we put all vertex into the queue. Then, when each vertex has at least one infected child, we infect every day another child of the vertex with the most uninfected childs, and put that decremented number on the q.
Note that in the beginning, we have to add an artificial vertex, which is the parent of the root vertex. We need this, because the root vertex also needs to become infected.
Can someone please tell me where I'm making error for Problem (C)? I have implemented exactly what's the tutorial says. I had figured out the solution but failed to implement it. I have looked at my solution multiple times but don't know what I'm missing. Please help me out.
You can look at my submission: https://mirror.codeforces.com/contest/1665/submission/153271339
I have added comments for better code readability.
For problem D, wouldn't $$$x \mod {2^{k + 1}} = r + 2^k$$$ if the gcd is equal to $$$2^{k + 1}$$$? (not k — 1 as written)?
My reasoning is as follows: let $$$x = y\cdot 2^k + r$$$. Thus, the gcd becomes $$$\gcd((y + 1)\cdot 2^k, (y + 3)\cdot 2^k)$$$. If the gcd is $$$2^{k + 1}$$$, that means $$$y$$$ is odd. Thus $$$x = (y - 1)\cdot 2^k + 2^k + r$$$. Since $$$y - 1$$$ is even, $$$(y-1)\cdot2^k$$$ can be written as a multiple of $$$2^{k + 1},$$$ making $$$x \equiv 2^k + r \pmod {2^{k + 1}}.$$$
I want to know if the problem A ask you print all solution about n, how can I solve it?
I solved Problem E differently: maintain a trie of all elements of the array: also each node of the trie should store the indices which correspond to the node in the trie: so each index corresponds to $$$log(A_{max})$$$ nodes in the trie, one for each bit of the element.
Now for a query, we are initially in the root node of the trie. We want to find out the set of numbers which result in the minimum OR. If the left son ($$$0$$$ bit) of the current node has $$$\geq 2$$$ nodes in the query range, we go to that node, otherwise if it has exactly $$$1$$$ node in the query range, we add that value to our set of possibilities and go to the right son. If it has $$$0$$$ nodes we just go to the right son.
Formally, the invariant maintained is that the union of set of possibilities and the subtree of the current node stores two values which give the minimum OR. Easy to prove, that this invariant is maintained in every step.
153497046
Thanks for sharing your solution. One question though, I think the below code-snippet isn't correct without checking how many of those positions (ie.
tr[curr].pos) fall between $$$[l, r]$$$. I kind of understand why this works, because if none falls between the given range, regardless of how many of them added, they'll not be part of the answer. Therefore, my point is rather on the correctness of the algorithm. I think the correct way would be using yourcntfunction to find how many falls in the range. What do you think?thank you sooo much. you are absolutely right. the algorithm is obviously correct, but this implementation detail was wrong, the correct snippet, as you pointed out, is
I have a similar solution, but I use Wavelet tree instead of Trie: 153497046
.
Can Someone help me Why my Solution is Wrong... https://mirror.codeforces.com/contest/1665/submission/258157824
Thank you for the editorial!
Problem B. Array Cloning Technique