Привет, Codeforces!

Скоро начнется отборочный тур IX Липецкой командной олимпиады школьников по программированию, к участию в котором мы приглашаем всех желающих!

Наша олимпиада проходит уже в девятый раз. В прошлом году на финале олимпиады очно в Липецке собрались 35 команд из разных регионов России, и мы приглашаем всех желающих и в этом году!

Для начала хочется рассказать несколько новостей, касающихся нашей олимпиады. У олимпиады наконец-то появился сайт https://lscpc.ru (за который хочется отдельно поблагодарить Филиппа grphil Грибова). Также у олимпиады есть канал, куда будет публиковаться актуальная информация. На сайте уже запущена регистрация на отборочный тур. Наконец, хочется упомянуть, что всем иногородним участникам будет предоставлено бесплатное проживание и питание на базе Центра поддержки одаренных детей "Стратегия", за что можно поблагодарить компанию Яндекс!

Медалисты ЛКОШП в прошлом году

Финал олимпиады пройдет с 1 по 2 мая 2024 года в Липецке на базе Института развития образования Липецкой области. Мы приглашаем команды из других регионов приехать в Липецк и принять участие в олимпиаде очно!

Мы готовы пригласить к участию в финале от 25 до 35 команд, которым будет оплачено проживание и питание во время пребывания в Липецке. Единственное, что придется оплатить участникам самостоятельно, это проезд до Липецка. Все участники финала олимпиады получат мерч олимпиады, а призеры и медалисты, разумеется, получат призы.

Отборочный тур начнется 19 апреля в 00:00 по Московскому времени и продлится до 23:59 25 апреля по Московскому времени. Отбор и финал олимпиады проводятся на системе ejudge. Отбором является виртуальный контест длительностью 5 часов, начать который вы можете в любое удобное время до окончания отбора. Отборочный тур проходит без прокторинга, но мы настоятельно рекомендуем решать задачи самостоятельно и надеемся на честность всех участников.

Команды, в составе которых все три участника являются призерами или победителями заключительного этапа ВсОШ по информатике или медалистами ВКОШП, приглашаются к участию без написания отборочного тура.

Команда должна состоять ровно из трех человек, каждый из которых должен являться школьником на момент 1 сентября 2023 года. Разрешено формировать команды из учеников разных образовательных учреждений и разных регионов.

Для регистрации на олимпиаду вам нужно заполнить следующую форму. Перед началом тура на сайте появится возможность входа в систему ejudge. По всем вопросам можно писать в Telegram чате или на почту, указанную на сайте.

На официальном сайте Летней школы по компьютерным наукам открылся прием заявок. Школу для учеников 8-10 классов проводит факультет компьютерных наук НИУ ВШЭ совместно с Центром поддержки одарённых детей “Стратегия” в Липецке.

Отбор участников пройдет в несколько туров. Первый отборочный тур начнется 13 мая в 00:00 и продлится до 14 мая 23:59. Второй отборочный тур начнется 3 июня в 00:00 и продлится до 4 июня 23:59. Отбор проводится на платформе Codeforces.

С 15 по 29 июля 2023 года Летняя школа по компьютерным наукам примет у себя талантливых школьников из 8-10 классов, желающих добиться высоких успехов в олимпиадах по информатике. Как и раньше, школу организует ФКН ВШЭ совместно с центром поддержки одарённых детей “Стратегия” в Липецке.

Обучение в школе будет проходить в пяти параллелях: C, B', B, A' и A в соответствии с классом обучения в школе и уровнем подготовки участника. Основное внимание будет уделяться изучению алгоритмов, используемых при решении олимпиадных задач.

Участие в школе платное и составляет в этом году 38 000 рублей. Участие для школьников из Липецкой области, а также для призеров и победителей заключительного этапа ВсОШ по информатике и математике бесплатно.

Желающим принять участие в ЛШКН-2023 нужно заполнить регистрационную анкету и решить вступительные задания той параллели, в которой они хотят учиться. Всем заполнившим анкету на указанный электронный адрес будет высылаться информация об отборе в школу.

1820A - Yura's New Name

Author: FairyWinx

Preparation: FairyWinx

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        if (s == "^") {
            cout << 1 << '\n';
            continue;
        }
        int ans = 0;
        if (s[0] == '_')
            ++ans;
        if (s.back() == '_')
            ++ans;
        for (int i = 0; i < (int) s.size() - 1; ++i) {
            if (s[i] == '_' && s[i + 1] == '_')
                ++ans;
        }
        cout << ans << '\n';
    }
}

1820B - JoJo's Incredible Adventures

Author: golikovnik

Preparation: teraqqq

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--) {
        string s; cin >> s; s += s;
        int k = 0, z = 0;
        for (char c : s) {
            z = c == '1' ? z+1 : 0;
            k = max(k, z);
        }
        const int n = s.size() / 2;

        if (k > n) {
            cout << (ll)n*n << '\n';
        } else {
            const ll side_a = (k+1)/2;
            const ll side_b = (k+2)/2;
            cout << side_a * side_b << '\n';
        }
    }
}

1819A - Constructive Problem

Author: TeaTime

Preparation: golikovnik

//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
    #define debug(x) cerr << (#x) << ":\t" << (x) << endl
#else
    #define debug(x) 238;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

template <class T>
int calcMex(vector<T> v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  int n = int(v.size());
  for (int i = 0; i < n; ++i) if (v[i] != i) return i;
  return n;
}

bool solveTest() {
  int n; cin >> n;
  vector<int> a(n);
  map<int, int> leftOcc, rightOcc;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    rightOcc[a[i]] = i;
    if (!leftOcc.count(a[i])) leftOcc[a[i]] = i;
  }
  int mex = calcMex(a);
  if (leftOcc.count(mex + 1)) {
    int L = leftOcc[mex + 1], R = rightOcc[mex + 1];
    for (int i = L; i <= R; ++i) {
      a[i] = mex;
    }
    int mx = calcMex(a);
    assert(mx <= mex + 1);
    return mx == mex + 1;
  }
  for (int i = 0; i < n; ++i) {
    assert(a[i] != mex);
    if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) {
      return true;
    }
  }
  return false;
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t; cin >> t;
  while (t--) {
    cout << (solveTest() ? "Yes" : "No") << '\n';
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

1819B - The Butcher

Author: Tikhon228

Preparation: Kon567889

//#pragma GCC target("trapv")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <iostream>
#include <list>
#include <stack>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll INF = 1e9 * 1e9 + 100, SZ = 1100;

ll n;
vector<pair<ll, ll>> vec;
map<ll, pair<ll, ll>> blocks;

pair<ll, ll> solve() {
	set<pair<ll, ll>> widest, longest;

	for (size_t i = 0; i < vec.size(); i++) {
		widest.insert({ vec[i].first, i });
		longest.insert({ vec[i].second, i });

		blocks[i] = vec[i];
	}

	pair<ll, ll> ans = { -1, -1 };
	bool mode = 0;
	ll prevw = INF, prevh = INF, prv = -1;
	bool cringe = 0;
	while (widest.size() != 0) {
		if (mode == 0) {
			ll cur = (*widest.rbegin()).first, sum = 0;
			if (ans.second == -1) ans.second = cur;
			prv = blocks[(*widest.rbegin()).second].second;

			while (widest.size() > 0 && (*widest.rbegin()).first == cur) {
				auto it = (--widest.end());
				longest.erase({blocks[it->second].second, it->second });
				sum += blocks[it->second].second;
				widest.erase(it);
			}

			if (!cringe) ans.first = sum;
			prv = sum;
			if (prevw == INF) {
				prevh = cur;
			} else {
				prevw -= sum;
				if (prevh != cur) return { -1, -1 };
			}
		} else {
			ll cur = (*longest.rbegin()).first, sum = 0;
			if (!cringe) {
				ans.first = cur + prv;
				cringe = 1;
			}

			while (longest.size() > 0 && (*longest.rbegin()).first == cur) {
				auto it = (--longest.end());
				widest.erase({ blocks[it->second].first, it->second });
				sum += blocks[it->second].first;
				longest.erase(it);
			}

			if (prevw == INF) {
				prevw = cur;
				prevh -= sum;
				if (prevw != cur) return { -1, -1 };
			} else {
				prevh -= sum;
				if (prevw != cur) return { -1, -1 };
			}
		}

		mode ^= 1;
	}

	if (prevh == 0 || prevw == 0 || prevh == INF || prevw == INF) {
		return ans;
	} else {
		return { -1, -1 };
	}
}

signed main() {
	fastInp;

    ll t;
    cin >> t;
    
    while (t--) {
        vec.clear();
        blocks.clear();
    	cin >> n;
    
    	vec.resize(n);
    	for (auto& c : vec) cin >> c.first >> c.second;
    
    	vector<pair<ll, ll>> ans;
    
    	ans.push_back(solve());
    	swap(ans.back().first, ans.back().second);
    	if (ans.back().first == -1) ans.pop_back();
    
    	for (auto& c : vec) swap(c.first, c.second);
    
    	ans.push_back(solve());
    	if (ans.back().first == -1) ans.pop_back();
    
    	if (ans.size() == 2 && ans[0] == ans[1]) {
    		ans.pop_back();
    	}
    	cout << ans.size() << "\n";
    
    	for (auto c : ans) cout << c.first << " " << c.second << "\n";
    }
    
	return 0;
}

1819C - The Fox and the Complete Tree Traversal

Author: golikovnik

Preparation: DishonoredRighteous

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <stdio.h>
#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 200100;

std::vector<int> g[N];
int d[N], par[N];
bool onDiameter[N];

void dfs(int v, int p, int depth) {
	d[v] = depth;
	par[v] = p;

	for (auto to : g[v]) {
		if (to != p) {
			dfs(to, v, depth + 1);
		}
	}
}

void run() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n - 1; ++i) {
		int from, to;
		scanf("%d%d", &from, &to);
		g[from - 1].push_back(to - 1);
		g[to - 1].push_back(from - 1);
	}    

	dfs(0, 0, 0);
	int v1 = 0;
	for (int i = 0; i < n; ++i) {
		if (d[i] > d[v1]) {
			v1 = i;
		}
	}

	dfs(v1, v1, 0);
	int v2 = v1;
	for (int i = 0; i < n; ++i) {
		if (d[i] > d[v2]) {
			v2 = i;
		}
	}

	std::vector<int> diameter;
	for (int v = v2; v != v1; v = par[v]) {
		onDiameter[v] = true;
		diameter.push_back(v);
	}
	onDiameter[v1] = true;
	diameter.push_back(v1);
	std::reverse(diameter.begin(), diameter.end());

	for (int i = 0; i < n; ++i) {
		if (onDiameter[i]) {
			continue;
		}
		if (!onDiameter[par[i]]) {
			printf("No\n");
			return;
		}
	}

	printf("Yes\n");
	std::vector<int> ans;
	for (int i = 0; i < (int)diameter.size(); i += 2) {
		ans.push_back(diameter[i]);
		if (i + 1 != (int)diameter.size()) {
			for (auto to : g[diameter[i + 1]]) {
				if (!onDiameter[to]) {
					ans.push_back(to);
				}
			}
		}
	}

	if (diameter.size() % 2 == 0) {
		for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
			ans.push_back(diameter[i]);
			if (i - 1 >= 0) {
				for (auto to : g[diameter[i - 1]]) {
					if (!onDiameter[to]) {
						ans.push_back(to);
					}
				}
			}
		}
	} else {
		for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
			ans.push_back(diameter[i - 1]);
			if (i - 2 >= 0) {
				for (auto to : g[diameter[i - 2]]) {
					if (!onDiameter[to]) {
						ans.push_back(to);
					}
				}
			}
		}
	}

	assert((int)ans.size() == n);
	for (auto i : ans) {
		printf("%d ", i + 1);
	}
	printf("\n");
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    #ifdef PERVEEVM_LOCAL
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    run();

    #ifdef PERVEEVM_LOCAL
        auto end = std::chrono::high_resolution_clock::now();
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

1819D - Misha and Apples

Author: Um_nik

Preparation: dshindov

#include <bits/stdc++.h>

#include <exception>

using namespace std;
using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> apples(n);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int x;
            cin >> x;
            apples[i].push_back(x);
        }
    }
    // vector<int> last(m + 1, -1);
    unordered_map<int, int> last;
    auto get_last = [&](int i) {
        if (!last.count(i)) {
            return -1;
        } else {
            return last[i];
        }
    };
    vector<char> can_zero(n + 1, false);
    vector<int> prev(n + 1, 0);
    can_zero[0] = true;
    int oops = -1;
    for (int i = 0; i < n; ++i) {
        if (apples[i].empty()) {
            can_zero[i + 1] = true;
            last[0] = i;
        } else {
            int nearest_pair = get_last(0);
            int new_oops = oops;
            for (int x : apples[i]) {
                nearest_pair = max(nearest_pair, get_last(x));
                new_oops = max(new_oops, get_last(x));
                last[x] = i;
            }
            if (nearest_pair != -1) {
                int nearest_zero = prev[nearest_pair];
                if (oops < nearest_zero) {
                    can_zero[i + 1] = true;
                }
            }
            oops = new_oops;
        }
        if (can_zero[i + 1]) {
            prev[i + 1] = i + 1;
        } else {
            prev[i + 1] = prev[i];
        }
    }
    // vector<char> used(m + 1, false);
    unordered_set<int> used;
    vector<int> max_cnt(n + 1, 0);
    int current_cnt = 0;
    for (int i = n - 1; i >= 0; --i) {
        bool fail = false;
        if (apples[i].empty()) {
            used.insert(0);
        }
        for (int x : apples[i]) {
            if (used.count(x)) {
                fail = true;
                break;
            }
            used.insert(x);
            ++current_cnt;
        }
        if (fail) {
            break;
        }
        if (used.count(0)) {
            max_cnt[i] = m;
        } else {
            max_cnt[i] = current_cnt;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
        if (can_zero[i]) {
            ans = max(ans, max_cnt[i]);
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

1819E - Roads in E City

Author: Tikhon228

Preparation: grphil

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

mt19937 rnd;

struct solve {

vector<pair<int, int>> r;

vector<vector<pair<int, int>>> s;

vector<int> ans;

int n, m;

static constexpr int rep = 45;

int dfs(int a, int p, int b) {
	for (auto i : s[a]) {
		if (i.x == b) {
			return i.y;
		}
		if (i.x == p) {
			continue;
		}

		int x = dfs(i.x, a, b);

		if (x != -1) {
			return x;
		}
	}
	return -1;
}

solve() {
	cin >> n >> m;
	r.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> r[i].x >> r[i].y;
		r[i].x--;
		r[i].y--;
	}

	s.resize(n);
	ans.resize(m, -1);
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		rem(i);
		for (int j = 0; j < rep; j++) {
			if (!ask_end(i)) {
				ans[i] = 1;
				break;
			}
		}
		if (ans[i] == 1) {
			add(i);
			cnt++;
			s[r[i].x].emplace_back(r[i].y, i);
			s[r[i].y].emplace_back(r[i].x, i);
		}
	}

	assert(cnt == n - 1);

	for (int i = 0; i < m; i++) {
		if (ans[i] != -1) continue;
		ans[i] = 1;

		int c = dfs(r[i].x, -1, r[i].y);
		rem(c);
		add(i);
		for (int j = 0; j < rep; j++) {
			if (!ask_end(i)) {
				ans[i] = 0;
				break;
			}
		}
		rem(i);
		add(c);
	}
	cout << "!";
	for (int i = 0; i < m; i++) {
		cout << ' ' << ans[i];
	}
	cout << endl;
	int x;
	cin >> x;
	if (x != 1) {
		exit(1);
	}
}

void rem(int x) {
	cout << "- " << x + 1 << endl;
}

void add(int x) {
	cout << "+ " << x + 1 << endl;
}

bool ask(int a) {
	cout << "? " << a + 1 << endl;
	// cerr << "? " << a + 1 << endl;
	int x;
	cin >> x;
	return x == 1;
}

bool ask_end(int i) {
	// cerr << "ask_end " << i << endl;
	int a = r[i].x;
	if (rnd() % 2) {
		a = r[i].y;
	}
	return ask(a);
}

};

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		solve();
	}
}

1819F - Willy-nilly, Crack, Into Release!

Author: teraqqq

Preparation: teraqqq

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;
using ll = long long;

const int Q = 1e5;
const int N = 20;
const int V = N*Q;

const ll LINF = 1e18;

struct MinMaxValue {
    ll min_value;
    ll max_value;

    MinMaxValue operator * (const MinMaxValue& x) const {
        if (x.max_value < 0 || max_value < 0) {
            return MinMaxValue { 0, -1 };
        }

        return MinMaxValue {
            .min_value = x.min_value + min_value,
            .max_value = x.max_value + max_value
        };
    }

    MinMaxValue operator + (const MinMaxValue& x) const {
        if (x.max_value == -1) return *this;
        if (max_value == -1) return x;

        return MinMaxValue {
            .min_value = min(x.min_value, min_value),
            .max_value = max(x.max_value, max_value)
        };
    }

    MinMaxValue& operator += (const MinMaxValue& x) {
        return *this = *this + x;
    }

    void Reset() {
        min_value = 0;
        max_value = -1;
    }
};

struct {
    MinMaxValue dig, ver, hor;
    int cnt;
    int go[4];
} nd[V];
int vc = 0;
MinMaxValue dig[N+1], ver[N+1], hor[N+1];

std::set<ll> words;

int NewVertex(int h) {
    int* go = nd[vc].go;
    go[0] = go[1] = go[2] = go[3] = -1;
    nd[vc].dig = dig[h];
    nd[vc].hor = hor[h];
    nd[vc].ver = ver[h];
    nd[vc].cnt = 0;
    return vc++;
}

tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) {
    return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0)
                   : make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt);
}

void Calculate(int v, int h, int corner) {
    auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1);
    auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1);
    auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1);
    auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1);

    nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3;

    nd[v].dig.Reset();
    if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1;
    if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1;

    nd[v].hor = ver0 * dig2 * dig3 * ver1;
    if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1;

    nd[v].ver = hor0 * dig1 * dig3 * hor2;
    if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2;
}

void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) {
    if (h == 0) {
        if (nd[v].cnt == 0) {
            words.insert(msk_save);
        } else {
            words.erase(msk_save);
        }
        nd[v].cnt ^= 1;
    } else {
        UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save);
        Calculate(v, h, corner);
    }
}

bool near_symbols[256][256];

MinMaxValue GetAnswer(int h) {
    int v = 0;

    if (nd[v].cnt == 0) {
        return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value };
    }

    MinMaxValue res; res.Reset();

    bool cycle_len2 = false;
    if (nd[v].cnt <= 1) cycle_len2 = true;
    if (nd[v].cnt == 2) {
        string s, t;

        for (ll msk =       *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]);
        for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]);
        auto flag = near_symbols[s.back()][t.back()];

        if (s.substr(0, h-1) == t.substr(0, h-1) && flag) {
            cycle_len2 = true;
        }

        int s_suf = 0, t_suf = 0;
        while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf;
        while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf;

        if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1)
                && s.back() == t[h - s_suf - 1]
                && t.back() == s[h - t_suf - 1]) cycle_len2 = true;
    }

    if (cycle_len2) {
        res.min_value = 2;
        res.max_value = 2;
    }

    while (h != 0) {
        const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3];
        const auto& dig0 = get<0>(GetState(v0, h-1));
        const auto& dig1 = get<0>(GetState(v1, h-1));
        const auto& dig2 = get<0>(GetState(v2, h-1));
        const auto& dig3 = get<0>(GetState(v3, h-1));

        if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) {
            res += dig0 * dig1 * dig2 * dig3;
        }

        --h;
        if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; }
        if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; }
        if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; }
        if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; }
        break;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, q; cin >> n >> q;
    vector<ll> v(q);

    for (int i = 0; i < 4; ++i) {
        int j = (i + 1) % 4;
        near_symbols['a' + i]['a' + j] = true;
        near_symbols['a' + j]['a' + i] = true;
    }

    dig[0] = ver[0] = hor[0] = { 1, 1 };
    for (int i = 1; i <= n; ++i) {
        dig[i] = hor[i-1] * dig[i-1] * ver[i-1];
        hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1];
    }

    int m_root = NewVertex(n); // make_root
    assert(m_root == 0);

    for (int i = 0; i < q; ++i) {
        string s; cin >> s;
        for (int j = 0; j < n; ++j) {
            v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j);
            v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j);
        }

        int w = 0;
        for (int j = 0; j < n; ++j) {
            int& next = nd[w].go[(v[i] >> (2*j)) & 3];
            if (next == -1) next = NewVertex(n-j-1);
            w = next;
        }
    }

    for (ll msk : v) {
        UpdateCount(0, n, 0, msk, msk);
        auto [a, b] = GetAnswer(n);

        if (a > b) {
            cout << -1 << '\n';
        } else {
            cout << a << " " << b << '\n';
        }
    }
}

Hello, Codeforces!

This Saturday VIII Lipetsk Team Olympiad, a competition for high school students from all over the country, will be held in Lipetsk. Maybe you participated in previous Codeforces rounds based on our problems (rounds 643 and 791).

The round will start at Apr/15/2023 12:05 (Moscow time) and will last for 2 hours. Please notice the unusual time. Each division will have 6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.

Problems were proposed and prepared by Um_nik, DishonoredRighteous, FairyWinx, golikovnik, teraqqq, grphil, Kon567889, TeaTime, Tikhon228 and dshindov.

I would like to thank Artyom123 for great round coordination and our testers: Ormlis, bashkort, Umi, I_LOVE_ANTON_DONBASS, Egor.Lifar, iakovlev.zakhar, Mangooste, Siberian, SomethingNew, stepanov.aa, talant, rt3, towrist, Aaeria, Alexdat2000, qxforever, Renatyss, Renedyn, sevlll777, towrist, valerikk, Tiagodfs, wiz_cs, Setsuna, ezraft, Gornak40, HunterXD, kbats183, Nathan_McKane, nik_sn, Nitelike, Tilt, ak2006, KiruxaLight, 9kin.

Of course, I would like to thank all Codeforces team for this beautiful platform!

Scoring distribution will be announced later.

I hope you will enjoy our problems. Wish you good luck and high rating!

UPD: Scoring distribution:

Div.1: 750 – 1250 – 1500 – 2000 – 2750 – 3000

Div.2: 500 – 1000 – 1750 – 2000 – 2500 – 3500

UPD: Winners!

Div 2:

• yy_chen
• dengtingyu12138
• keyurchd_11
• Lyamzin_alexandr
• 39_w_M9

Div 1:

• BurnedChicken
• Radewoosh
• turmax
• yzc2005
• tourist

UPD: Editorial is available here

Привет, Codeforces!

Скоро начнется отборочный тур VIII Липецкой командной олимпиады школьников по программированию, к участию в котором мы приглашаем всех желающих!

Наша олимпиада проходит уже в восьмой раз, и хочется рассказать немного истории. Первые четыре олимпиады проводились исключительно для команд из Липецкой области. На пятую олимпиаду были приглашены несколько команд из Челябинской области, а также по ее мотивам был проведен раунд на Codeforces. В шестой олимпиаде помимо Липецких школьников участвовала команда "Популярные блогеры", членами которой являлись школьники из трех различных регионов России. В седьмой олимпиаде к участию были приглашены команды со всей страны: в финале олимпиады в режиме Online приняли участие 28 команд из различных регионов России, а также 11 команд из Липецкой области, также был проведен еще один раунд на Codeforces. Наконец, хочется рассказать, что ждет вас в этом году!

Призеры и победители ЛКОШП в прошлом году

Финал олимпиады пройдет с 14 по 15 апреля 2023 года в Липецке на базе Института развития образования Липецкой области. В этом году мы приглашаем команды из других регионов приехать в Липецк и принять участие в олимпиаде очно!

Мы готовы пригласить к участию в финале 40 команд, которым будет оплачено проживание и питание во время пребывания в Липецке. Единственное, что придется оплатить участникам самостоятельно, это проезд до Липецка. Все участники финала олимпиады получат мерч олимпиады, а призеры и медалисты, разумеется, получат призы.

Отборочный тур начнется 20 марта в 10:00 по Московскому времени и продлится до 22:00 26 марта по Московскому времени. Отбор и финал олимпиады проводятся на системе ejudge. Отбором является виртуальный контест длительностью 5 часов, начать который вы можете в любое удобное время до окончания отбора. Отборочный тур проходит без прокторинга, но мы настоятельно рекомендуем решать задачи самостоятельно и надеемся на честность всех участников.

Команды, в составе которых есть хотя бы один призер заключительного этапа ВсОШ по информатике или хотя бы один медалист ВКОШП, приглашаются к участию без написания отборочного тура. В случае, если таких команд окажется больше 40, приглашены будут те команды, которые прошли регистрацию раньше.

По результатам отборочного тура первым 40 командам (включая команды, прошедшие без отборочного тура) будет разослано письмо с приглашением к участию в финале олимпиады. В случае отказа от участия мы оставляем за собой право пригласить следующую по рейтингу команду на освободившееся место.

Команда должна состоять ровно из трех человек, каждый из которых должен являться школьником на момент 15 апреля 2023 года. Разрешено формировать команды из учеников разных образовательных учреждений и разных регионов.

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

По всем вопросам можно писать в Telegram @perveevm.

UPD.1 Если кто-то из участников олимпиады прошлых лет хочет поделиться своим опытом или мнением об олимпиаде, добро пожаловать в комментарии!

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

UPD.3 Отборочный тур начался! Регистрация останется открытой до 26 марта. Все новые зарегистрированные команды будут верифицироваться и получать логины один или два раза в день. Если вы не получили письмо, проверьте папку "Спам". Если письма нет и там, можете написать в Telegram @perveevm.

UPD.4 Отборочный тур закончился! Публикуем предварительные списки финалистов (они будут меняться и дополняться, так как на данный момент мы ожидаем подтверждения от участников).

• Not today (Родионов Валерий Витальевич, Каримов Ренат Айратович, Вильданов Руслан Юрьевич)
• Сборная СОСквы (Понкратов Александр Антонович, Пугачев Дмитрий Витальевич, Шатохин Фёдор Вадимович)
• Гильдия Единых Инфотехов (Акимов Артём Михайлович, Голов Андрей Евгеньевич, Куликовский Дмитрий Романович)
• Ищем третьего тиммейта, а то наш всё (Титов Фёдор Александрович, Ермолов Егор Владимирович, Ржевин Андрей Евгеньевич)
• К У П И Т Ь | ЫМ ИЛАБЛОД АРБУЗ (Возмилов Георгий Павлович, Терентьева Мария Александровна, Матюпатенко Максим Кириллович)
• шиз (Дрожецикй Ян Алексеевич, Скрипник Максим Алексеевич, Ермачков Ярослав Олегович)
• Голубые береты (Краснов Илья Витальевич, Пискарев Иван Викторович, Егоров Антон Юрьевич)
• Бархатные тяги (Ижицкий Тимофей Михайлович, Павлов Андрей Максимович, Никифоров Антон Владимирович)
• ЖВиШ (Сафиуллин Азат Булатович, Малов Владимир Алексеевич, Чекардов Михаил Романович)
• 11Б179! (Сергиенко Дмитрий Александрович, Губарев Александр Дмитриевич, Черный Антон Леонидович)
• Вестибубилюбибу (Чистяков Александр Вадимович, Кузнецов Степан Андреевич, Голубев Владимир Александрович)
• Акулы МШП (Паркина Ульяна Романовна, Сильвестров Василий Алексеевич, Широковских Александр Сергеевич)
• Блин, сложно (Пахомов Евгений Евгеньевич, Козлов Максим Дмитриевич, Чернов Тимофей Ильич)
• ОЦ Команда (Шкулёва Ксения Романовна, Алексеев Артём Сергеевич, Семенюк Ярослав Алексеевич)
• фан-клуб Миланы Хаметовой (Ларин Илья Александрович, Васильев Алексей Леонидович, Иванов Алексей Александрович)
• Сборная ш*** (Салыгин Егор Алексеевич, Лосев Пётр Валерьевич, Грекова Дарья Сергеевна)
• 1329: кек (Евстигнеев Георгий Дмитриевич, Клигунов Илья Дмитриевич, Кузнецов Никифор Никитич)
• на чиле (Душенков Сергей Сергеевич, Макурова Юлия Вадимовна, Жиляев Матвей Сергеевич)
• ЕГЭ по биоинформатике (Горохов Дмитрий Александрович, Колесникова Наталья Антоновна, Семиврагова Илона Сергеевна)
• Астралопетеки (Абатуров Артем Сергеевич, Кривощеков Виктор Антонович, Кутузов Артем Викторович)
• #include <bits/stdc++.h> (Овчаров Иван Евгеньевич, Ожегов Леонид Александрович, Туров Макар Олегович)
• Индюк, пингвин, крокодил (Ларичев Прохор Олегович, Волков Михаил Алексеевич, Заварин Александр Сергеевич)
• Три товарища без фантазии (Кухаренко Семён Кириллович, Сергеев Родион Владимирович, Копылов Сергей Андреевич)
• Агузки (Ныйкин Антон Игоревич, Поярков Андрей Алексеевич, Жерневский Михаил Константинович)
• Фонарный столб (Витюк Антон Юрьевич, Бычков Илья Игоревич, Хромов Адам Евгеньевич)
• прости если (Ильин Артём Денисович, Ларин Иван Олегович, Федоров Николай Андреевич)
• Povvered_by_Kv@ss (Шарапов Иван Денисович, Бицюк Андрей Александрович, Федоров Никита Александрович)
• Хинкали (Ким Артём Сенгванович, Ефимов Павел Дмитриевич, Любин Михаил Владимирович)
• Let's celebrate and write s♂me c♂de (Борцов Евгений Олегович, Хохряков Федор Павлович, Тарасов Федор Алексеевич)
• Штырь или водокачка? (Жеглов Александр Сергеевич, Дьячков Дмитрий Сергеевич, Соснов Геннадий Романович)
• Вращающиеся калиперы (Солдатов Максим Игоревич, Минасян Никита Лерментович, Лещинский Артём Владиславович)
• Квадрат зайдет? (Боровлев Пётр Александрович, Сомкин Артем Олегович, Баданов Чингис Юрьевич)
• Путёвка в мир Грибов (Насретдинов Амир Алмазович, Крылыков Максим Игоревич, Писарев Егор Дмитриевич)
• Извините, я отходил (Дегтерев Андрей Александрович, Янко Анастасия Дмитриевна, Ташланов Роман Алексеевич)

1679A - AvtoBus

Author: iakovlev.zakhar

Preparation: DishonoredRighteous

Editorial: DishonoredRighteous

1679B - Stone Age Problem

Author: Kon567889

Preparation: Kon567889

Editorial: DishonoredRighteous and Kon567889

1679C - Rooks Defenders

Author: Kon567889

Preparation: Kon567889

Editorial: DishonoredRighteous and Kon567889

1679D - Toss a Coin to Your Graph...

Author: Kon567889

Preparation: Masha237

Editorial: DishonoredRighteous

1679E - Typical Party in Dorm

Author: andr1y and welleyth

Preparation: andr1y and welleyth

Editorial: andr1y and welleyth

1679F - Formalism for Formalism

Author: iura

Preparation: iura

Editorial: DishonoredRighteous

Hello, Codeforces!

I'm glad to invite you to Round 791 which will start at May/14/2022 12:35 (Moscow time). Please notice the unusual time.

There will be 6 problems in the round. Round is based on Team Olympiad in Lipetsk which is being held for the seventh time. Problems were proposed and prepared by iakovlev.zakhar, Kon567889, iura, andr1y, Masha237, welleyth and me. I would like to thank Aleks5d and KAN for CF round coordination and testers: Um_nik, 353cerega, errorgorn, Stepavly, divanik, nnv-nick, 4qqqq, to be continued...

Of course, I'd like to thank all Codeforces team for Codeforces and Polygon beautiful platforms!

I also would like to thank golikovnik, egneeS, dshindov and Inessa Shuykova (Lipetsk teams' coach) for preparing other Olympiad problems that haven't been taken for this round.

Thanks to NEAR for supporting this round, details can be found in this post.

Note that if you are an official participant of the Olympiad, you are not allowed to participate in this round.

Scoring distribution will be announced later.

Wish you good luck and high rating!

UPD.1 Scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 3000$$$.

UPD.2 Congratulations to winners!

Official participants:

1. xiaoziyaooo

2. StickyFingers

3. mybing

4. huangweiliang

5. NewPC2022

Unofficial participants:

1. SSRS_

2. leaf1415

3. uwi

4. maspy

5. TripleM5da

UPD.3 Editorial is available here.

На официальном сайте Летней школы по компьютерным наукам открылся прием заявок. Школу для учеников 8-10 классов проводит факультет компьютерных наук НИУ ВШЭ совместно с центром поддержки одарённых детей “Стратегия” в Липецке. Отбор участников пройдёт в несколько туров, первый из которых пройдёт 15-16 мая.

С 16 по 30 июля 2022 года Летняя школа по компьютерным наукам примет у себя талантливых школьников из 8-10 классов, желающих добиться высоких успехов в олимпиадах по информатике. Как и раньше, школу организует ФКН ВШЭ совместно с центром поддержки одарённых детей “Стратегия” в Липецке.

Обучение в школе будет проходить в четырёх параллелях: C, B', B и A в соответствии с классом обучения в школе и уровнем подготовки участника. Основное внимание будет уделяться изучению алгоритмов, используемых при решении олимпиадных задач.

Желающим принять участие в ЛШКН-2022 нужно заполнить регистрационную анкету и решить вступительные задания той параллели, в которой они хотят учиться, первый отборочный тур пройдёт с 08:00 15 мая по 22:00 16 мая по московскому времени. Всем заполнившим анкету на указанный электронный адрес будет высылаться информация об отборе в школу.

Привет, Codeforces!

14 мая состоится финал VII Липецкой командной олимпиады школьников по программированию. Первые четыре олимпиады проводились исключительно для участников из Липецкой области. На пятую олимпиаду были приглашены несколько команд из Челябинска, а также по ее мотивам был проведен Div.2 раунд на Codeforces. В шестой олимпиаде участвовала команда "Популярные блогеры", членами которой являлись школьники из трех разных регионов. Наконец, в этом году мы хотим пригласить к online участию в олимпиаде всех желающих!

Краткие правила олимпиады:

1. Олимпиада проводится в двух возрастных категориях — младшей и старшей. На участие в младшей возрастной категории имеют право только те команды, в которых все участники обучаются на момент 14 мая 2022 года в 7 классе или ниже. Команды, не подходящие под этот критерий, имеют право на участие только в старшей возрастной категории.
2. Олимпиада проводится по стандартным правилам проведения командных олимпиад. Тур для старшей возрастной категории длится 5 астрономических часов, а для младшей возрастной категории — 3 астрономических часа. В каждый момент времени команда может использовать для решения задач один компьютер. Разрешено использование другой техники для связи между участниками, а также для чтения условий задач и написанного кода.
3. Разрешено использование любой печатной литературы.
4. Для возможности участия в финале олимпиады необходимо заполнить форму и выполнить задания отборочного тура. В течение некоторого времени после заполнения формы и верификации заявки на указанный адрес электронной почты будет выслана информация, содержащая ссылку на отборочный тур, логин и пароль, а также ссылку на Telegram чат для вопросов.
5. Отбор на олимпиаду и финал проводятся на базе системы ejudge.
6. Команды должны состоять ровно из трех человек, каждый из которых является школьником на момент 14 мая 2022 года. Разрешено формировать команды из учеников различных образовательных организаций и различных регионов.
7. Возможно, в день проведения олимпиады параллельно с ней будет проведен раунд на Codeforces. Участникам финала запрещено участвовать в нем.
8. Участникам, занявшим топовые места, будут отправлены памятные призы.

Мы не планируем проводить тур с прокторингом, поэтому мы не сможем контролировать выполнение первого правила, описанного выше. Однако, мы призываем всех участников к честности, чтобы получить максимум удовольствия от написания олимпиады.

P.S. Задачи трех прошлых лет можно найти здесь, здесь и здесь.

UPD.1 Если команда имеет право на участие в младшей возрастной категории, но хочет участвовать в старшей возрастной категории, то можно при регистрации указать желаемую категорию.

UPD.2 Время начала тура — 14 мая в 10:00 по Московскому времени.

UPD.3 Если в течении долгого времени вам не пришло письмо с логином и паролем, проверьте папку "Спам". Если письма нет и там, напишите мне личное сообщение на Codeforces.

UPD.4 Форма для регистрации команд закрыта. Остаются последние часы, чтобы написать отборочный тур. 11 мая будут известны списки прошедших команд. Все команды, приглашенные в финал, получат письмо с информацией.

Hello, CodeForces!

Recently I was working on a Java library that implements interaction with Polygon API. It is very useful for some my tasks and it's cool that Polygon provides an API. But I discovered that is's kinda outdated. There are some new features in Polygon for which theres is no access through the API. There are also some use cases that can't be counted as new features but it's impossible to to them using API too.

In this post I created a shortlist of some methods and enhancements that can be useful in Polygon API in my opinion. May be it's hard to implement some of them but I hope that someone from Codeforces and Polygon team will see it and may be implement some of this API methods.

1. Statement object doesn't store any field for interaction protocol in interactive problems. It's strange because some API methods can be used to work with interactive problems (for example, problem.interactor) but we cannot get interaction protocol from problem statements.

2. Linux and Windows packages downloading. There is an API method problem.package that allows to download a Standard zip package. In some cases it seems to be useful to download Linux or Windows package because they include generated tests.

3. Test object contains test input data but doesn't contain test output data. It seems that it should be easy to add this field and it can be useful too (you won't have to run generator script locally to get test output data).

4. There is no methods that allow to work with Contest Groups. I suppose that Contest Group is a relatively new feature and that's why there is no methods for it.

5. We cannot commit problem changes using API (may be it's done in this way for some security reasons).

6. We cannot build packages using API.

7. We cannot manage access to problems, contests and contest groups via API (may be it's done in this way for some security reasons).

8. We cannot create problems and contests, and add problems to contests using API.

9. To be continued...

May be this list is incomplete, so I will be glad if someone add some points into it in the comments. I hope that someone from Codeforces team (MikeMirzayanov? geranazavr555?) will see this post and comment it.

Привет, Codeforces!

26 мая состоится ставшая традицией Шестая Липецкая командная олимпиада школьников по программированию. Первые четыре года участниками нашей олимпиады становились только Липецкие команды. В прошлом году в качестве эксперимента мы решили пригласить на олимпиаду несколько команд из Челябинска, а также провели по задачам олимпиады Div.2 раунд. В этом году мы решили расширить круг наших участников и пригласить к дистанционному участию школьные команды из других регионов! Для кого-то это может стать неплохой тренировкой перед олимпиадами следующего сезона, а для кого-то просто последним командным контестом в уходящем учебном году...

В нашей олимпиаде есть две возрастных категории: 3-7 классы и 8-11 классы. С контестом прошлого года для 8-11 классов можно ознакомиться здесь. Для участия необходимо являться школьником и подходить под указанные ограничения по классам. Для регистрации на олимпиаду нужно заполнить форму. Перед регистрацией обязательно ознакомьтесь с правилами участия. Для того, чтобы соревнование было честным по отношению к участникам, пишущим его очно в Липецке, для дистанционных участников 8-11 классов предусмотрен обязательный прокторинг.

Ждем ваших регистраций!

UPD. Соревнование завершилось, оба контеста добавлены с тренировки Codeforces: 3-7 классы, 8-11 классы.

Задачи были придуманы и разработаны DishonoredRighteous, egneeS, iura, Petr1Furious, Darui99, Villen3tenmerth, Masha237, LevP.

Отдельное спасибо за тестирование задач, критику и полезные комментарии Um_nik, iakovlev.zakhar, Nybik, golikovnik и Slamur.

Author's solution: 80407149

Author's solution: 80407200

Author's solution using formulas: 80407222

Author's solution using prefix sums: 80407239

Author's solution: 80407273

Author's solution: 80407303

Author's solution using ternary search: 80407326

Author's solution: 80407360

Hello, Codeforces!

I'm glad to invite you to Round 643 which will start at 16.05.2020 14:35 (Московское время). Please notice the unusual time.

There will be 6 problems in round, one of them will be interactive. If you are not familiar with interactive problems, you can learn about them here.

Round is based on Team Olympiad in Lipetsk which is being held for the fifth time. Problems were prepared by fake123, iura, Masha237, Villen3tenmerth, Inessa Shujkova (Lipetsk teams' coach) and me. I would like to thank antontrygubO_o for CF round coordination and testers: KAN, I_love_Tanya_Romanova, vepifanov, Merkurev, golikovnik, Ekler and some other people who asked me not to write about them :)

Of course, I'd like to thank all Codeforces team for this beautiful platform!

Scoring distribution will be announced later.

Wish you good luck and high rating!

UPD.1 Scoring distribution: $$$750-750-1250-1500-2000-3000$$$.

UPD.2 Editorial is available here.

UPD.3 Congratulations to winners!

Official participants:

1. NaimSS

2. tianxiawoyou

3. Lomk

4. wisteria0410ss

5. TheOneYouWant

Unofficial participants:

1. risujiroh

2. jiangly

3. 244mhq

4. hitonanode

5. turmax

UPD.4 Full problemset from the olympiad is available on gym: Пятая Липецкая командная олимпиада школьников по программированию. Финал. 8-11 классы