Заметим, что одно действие с кубиком меняет четность количества кубиков в башне. Тогда если четности $$$n$$$ и $$$m$$$ не совпадают, то нельзя построить башню. Также если $$$n < m$$$ то башню тоже нельзя построить. В остальных случаях можно построить башню высоты $$$m$$$ за $$$m$$$ операций, а потом добавлять и удалять кубик, пока операции не закончатся.

#include <bits/stdc++.h>
using namespace std;
 
int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    cout << (n >= m && (n%2) == (m%2) ? "Yes" : "No") << '\n';
  }
}

• Good problem
• Average problem
• Bad problem

Будем перебирать префикс из $$$i$$$ бит и строить корректный ответ для числа образованного префиксом бит числа $$$x$$$. Нам интересно рассматривать только единичные биты, так как только они влияют на значение числа $$$x$$$.

Если в ответе мы уже поставили на место $$$i$$$ единицу, то нам нужно еще как-то получить к числу + $$$2^i$$$. Тогда просто обнулим $$$i$$$ бит в ответе и поставим его в $$$i + 1$$$ — как раз прибавится $$$2 \cdot 2^i = 2^{i+1}$$$.

Теперь на $$$i$$$ месте в ответе стоит $$$0$$$.

Рассмотрим что мы ставили в ответе на месте $$$i-1$$$. Если 0, то все хорошо, просто поставим $$$1$$$ на позицию $$$i$$$. Если стоит $$$1$$$, то возникла ситуация [1 1], исправим ее, сделав [-1 0 1] — на место $$$i-1$$$ поставим $$$-1$$$, на $$$i$$$ оставим 0, на $$$i+1$$$ поставим 1. К сумме прибавится $$$2^i$$$ так как $$$2^i + 2^{i-1}= 2^{i+1} - 2^{i-1}$$$ Теперь осталось разобрать случай когда на $$$i-1$$$ месте стоит $$$-1$$$. Но он невозможен, так как нашими операциями вперед мы ставим только единицы, а $$$-1$$$ ставятся позади.

Итоговая асимптотика $$$O( \log(x) )$$$ на 1 тестовый случай.

#include "bits/stdc++.h"

#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
using namespace std;
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
 
/// Actual code starts here
const int N = 100005;
 
void solve() {
    ll x;
    cin >> x;
    vector<int> res(31, 0);
    for (int i = 0; i < 30; i++) {
        if (1ll & (x >> i)) {
            if (res[i]) {
                res[i + 1] = 1;
                res[i] = 0;
            } else if (i > 0) {
                if (res[i - 1] == 1) {
                    res[i + 1] = 1;
                    res[i - 1] = -1;
                } else {
                    res[i] = 1;
                }
            } else if (i == 0) {
                res[i] = 1;
            }
        }
    }
    cout << 31 << '\n';
    for (int i = 0; i <= 30; i++) {
        cout << res[i] << ' ';
    }
    cout << '\n';
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--)
        solve();
}

• Good problem
• Average problem
• Bad problem

Попробуйте проверить, подходит ли весь массив $$$a$$$ в качестве ответа.

Сначала поймем, можно ли взять в качестве особенной подпоследовательности весь массив $$$a$$$.

Для этого найдем LCM($$$a_1, a_2, \dots, a_n$$$). Если он больше, чем max($$$a_1, a_2, \dots, a_n$$$), то очевидно такого числа нет в подпоследовательности, так как $$$LCM \geq max$$$.

После этой проверки про массив $$$a$$$ становится известно, что каждый $$$a_i \ | \ max(a_1, a_2, \dots, a_n)$$$.

Тогда переберем делители максимума и жадно проверим наличие подпоследовательности с таким LCM.

Если делать это наивно, то будет $$$O(\sqrt{C} + n \cdot d(C) \cdot \log(C))$$$, но этого уже было достаточно.

Заметим, что можно подсчитать вхождение каждого числа и проверять только различные числа. Тогда асимптотика будет $$$O(\sqrt{C} + d(C)^2 \cdot log(C))$$$.

#include "bits/stdc++.h"
 
#define err(x) cerr << "["#x"]  " << (x) << "\n"
#define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1000000007;
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
 
template<typename T1, typename T2>
inline bool relaxmi(T1 &a, const T2 &b) {
    return a > b ? a = b, true : false;
}
 
template<typename T1, typename T2>
inline bool relaxma(T1 &a, const T2 &b) {
    return a < b ? a = b, true : false;
}
 
double GetTime() { return clock() / (double) CLOCKS_PER_SEC; }
 
/// Actual code starts here
const int N = 100005;
 
int calc(vector<pair<int, int>> &t, int d) {
    int LCM = 0, cnt = 0;
    for (auto [j, c]: t) {
        if (d % j == 0) {
            if (LCM == 0) LCM = j;
            else LCM = lcm(LCM, j);
            cnt += c;
        }
    }
    if (LCM != d) cnt = 0;
    return cnt;
}
 
void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &i: v) cin >> i;
    ll LCM = 1;
    int mx = *max_element(all(v));
    for (auto i: v) {
        LCM = lcm(LCM, i);
        if (LCM > mx) {
            cout << n << '\n';
            return;
        }
    }
    map<int, int> cnt;
    for (auto i: v) cnt[i]++;
    vector<pair<int, int>> t;
    for (auto i: cnt)
        t.push_back(i);
    int res = 0;
    for (int i = 1; i * i <= mx; i++) {
        if (mx % i == 0) {
            if (!cnt.contains(i))
                relaxma(res, calc(t, i));
            if (!cnt.contains(mx / i))
                relaxma(res, calc(t, mx / i));
        }
    }
    cout << res << '\n';
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--)
        solve();
}

• Good problem
• Average problem
• Bad problem

Попробуйте зафиксировать особенность столбца $$$i$$$ и наличие единицы в клетке $$$i, j$$$.

Давайте зафиксируем, что значение в $$$i$$$-й строке $$$j$$$-м столбце строго единица и она единственная в столбце. Тогда вся таблица задается однозначно и XORофикатор тоже.

Тогда давайте для каждого возможного состояния XORофикатора, который строит нужную таблицу поддерживать счетчик. Тогда состояние, которое максимизирует количество столбцов, в котором стоит ровно 1 единица, имеет максимальный счетчик.

Для того, чтобы эффективно поддерживать счетчик, необходимо поддерживать хеш XORофикатора и быстро пересчитывать его при переходе в нижнюю строку.

Ответ можно восстановить просто пройдясь еще раз по таблице и считая хеш, если получился нужный, то просто вывести состояние XORофикатора.

Итоговая асимптотика $$$O(nm \log{(nm)})$$$ или $$$O(nm)$$$, если использовать hash map.

Для хеширования удобно использовать Zobrist hashing.

#include "bits/stdc++.h"
 
using namespace std;
 
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> table(n, vector<bool>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            table[i][j] = c - '0';
        }
    }
    vector<long long> rands(n), rands2(n);
    for (int i = 0; i < n; ++i) {
        rands[i] = rnd();
        rands2[i] = rnd();
    }
    map<pair<long long, long long>, int> ans;
    int res = 0;
    pair<int, int> ind_ans = {0, 0};
    for (int j = 0; j < m; ++j) {
        long long summ = 0, summ2 = 0;
        for (int i = 0; i < n; ++i) {
            if (table[i][j]) {
                summ ^= rands[i];
                summ2 ^= rands2[i];
            }
        }
        for (int i = 0; i < n; ++i) {
            summ ^= rands[i];
            summ2 ^= rands2[i];
            ans[{summ, summ2}]++;
            if (res < ans[{summ, summ2}]) {
                res = ans[{summ, summ2}];
                ind_ans = {j, i};
            }
            summ ^= rands[i];
            summ2 ^= rands2[i];
        }
    }
    cout << res << "\n";
    string inds(n, '0');
    for (int i = 0; i < n; ++i) {
        if (table[i][ind_ans.first]) {
            if (i != ind_ans.second) {
                inds[i] = '1';
            }
        } else if (ind_ans.second == i) {
            inds[i] = '1';
        }
    }
    cout << inds << "\n";
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

• Good problem
• Average problem
• Bad problem

Сначала поймем почему 2 цветов действительно достаточно.

Заметим, что отношение достижимости в графе задает Частично упорядоченное множество.

По теореме Дилуорса размер максимальной антицепи равен минимальному количеству цепей, покрывающих ЧУМ.

Заметим, что условие на достижимость пары вершин внутри любой тройки влечет ограничение на максимальный размер антицепи. Он просто не больше 2. Значит 2 цветов действительно достаточно.

Осталось понять как явно строить эти 2 цепи.

Будем строить индуктивно. Давайте поддерживать 3 стека — последние вершины покрашенные в черный цвет, белый цвет и красный цвет соответсвенно. Они будут отвечать за цепи, которые мы строим.

Пусть мы построили цепи на $$$n$$$ вершинах и хотим построить на $$$n + 1$$$:

• Если белый или черный стеки пусты то просто добавим вершину $$$n+1$$$ в пустой стек.
• Если красный стек пустой:

• • Спросим про достижимость последних вершин из белого и черного стеков из вершины $$$n+1$$$.
• • Если достижимы обе вершины, то отправим вершину $$$n+1$$$ в красный стек.
• • Если достижима только 1 вершина то отправим вершину $$$n+1$$$ в стек, последняя вершина которого достижима из $$$n+1$$$.
• • Случай когда достижимо 0 вершин невозможен так как это противоречит условию.

• Если красный стек не пустой:

• • Спросим про достижимость последней вершины красного стека из вершины $$$n+1$$$.
• • Если она достижима, то отправим ее в красный стек
• • Если она не достижима, то сделаем вопрос про конец белого стека.
• • Если вершина из конца белого стека не достижима, то тогда обязана быть достижима вершина из конца черного стека, иначе происходит противоречие с условием задачи.
• • Покрасим вершину $$$n+1$$$ в черный стек, если достигается черная вершина или в белый стек, если достигается белая вершина.
• • Перекрасим все вершины из красного стека в противоположный цвет относительно $$$n+1$$$ вершины. Мы так можем сделать так как по построению все вершины белого и черного стеков достижимы из всех вершин красного стека.
• • не забудем очистить красный стек

При каждом добавлении новой вершины тратится не более 2 запросов. Тогда суммарно мы потратим не более $$$2 \cdot n$$$ вопросов.

В ходе алгоритма все операции производятся за $$$O(1)$$$, тогда асимптотика $$$O(n)$$$.

В качестве упражнения читателю предлагается доказать нижнюю оценку на количество запросов.

#include "bits/stdc++.h"
 
#define err(x) cerr << "["#x"]  " << (x) << "\n"
#define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1000000007;
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
 
template<typename T1, typename T2>
inline bool relaxmi(T1 &a, const T2 &b) {
    return a > b ? a = b, true : false;
}
 
template<typename T1, typename T2>
inline bool relaxma(T1 &a, const T2 &b) {
    return a < b ? a = b, true : false;
}
 
double GetTime() { return clock() / (double) CLOCKS_PER_SEC; }
 
/// Actual code starts here
const int N = 100005;
 
bool ask(int i, int j) {
    cout << "? " << j << ' ' << i << endl;
    string resp;
    cin >> resp;
    if (resp == "-1") assert(false);
    if (resp == "YES") return true;
    else return false;
}
 
void solve() {
    int n;
    cin >> n;
    vector<int> st, st2, st3;
    st = {1};
    for (int i = 2; i <= n; i++) {
        if (st2.empty()) {
            if (ask(i, st.back())) {
                st.push_back(i);
            } else {
                st2.push_back(i);
            }
        } else if (st3.empty()) {
            int ok1 = ask(i, st.back()), ok2 = ask(i, st2.back());
            if (ok1 && ok2) {
                st3.push_back(i);
            } else if (ok1) {
                st.push_back(i);
            } else if (ok2) {
                st2.push_back(i);
            } else {
                assert(false);
            }
        } else {
            if (ask(i, st3.back())) {
                st3.push_back(i);
            } else {
                if (ask(i, st.back())) {
                    st.push_back(i);
                    for (auto j: st3)
                        st2.push_back(j);
                    st3.clear();
                } else {
                    st2.push_back(i);
                    for (auto j: st3)
                        st.push_back(j);
                    st3.clear();
                }
            }
        }
    }
    if (!st3.empty()) {
        for (auto i: st3)
            st.push_back(i);
        st3.clear();
    }
    vector<int> colors(n + 1);
    for (auto i: st2)
        colors[i] = 1;
    cout << "! ";
    for (int i = 1; i <= n; i++) cout << colors[i] << ' ';
    cout << endl;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--)
        solve();
}

• Good problem
• Average problem
• Bad problem