I tried to submit NO, but what we all need is to submit security

It's about the first $$$25$$$ contest ever, the $$$15^{th}$$$, $$$20^{th}$$$ and $$$21^{th}$$$ one was unrated.

The first test case has $$$3$$$ numbers, the second has $$$1$$$, and the third has $$$4$$$. Yes, they are following the order of number pi.

314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745

Take this string into your code and you will be fine. Multiply all number in a test and get the answer.

Just try number 0.

Just try number 0 again.

Santa Claus

The color of the image is #01722B. Just copy the editorial for problem 1722B and submit.

The statement said the number are generated randomly, and $$$624$$$ is how we crack mt19937.

abcdefghijklmnopqrstuvwxyz

The letters bdfhklt are taller, and gjpqy have a "foot". Replace them with ( and ). Check if the sentence is balanced or not.

We need to say something with Please.

A Segment Tree is a data structure that stores information about array intervals as a tree. This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array. This includes finding the sum of consecutive array elements $$$a[l \dots r]$$$ , or finding the minimum element in a such a range in $$$O(\log n)$$$ time. Between answering such queries, the Segment Tree allows modifying the array by replacing one element, or even changing the elements of a whole subsegment (e.g. assigning all elements $$$a[l... r]$$$ to any value, or adding a value to all element in the subsegment).

Using pip:

from segment_tree import *
array = [3, 1, 5, 3, 13, 7, 2, 7, 2]
tree = SegmentTree(array)

t.query(1, 3, "sum") # 9
t.update(0, 10) # [10, 1, 5, 3, 13, 7, 2, 7, 2]
t.query(0, 8, "min") # 0
t.update(2, -1) # [10, 1, -1, 3, 13, 7, 2, 0, 2]
t.query(0, 2, "min") # -1

from segment_tree import *
array = [1, 2, 3, 4, 5]
t = SegmentTree(array)
t.update_range(0, 2, 6) # 6 6 6 4 5
t.update_range(1, 4, 2) # 6 2 2 2 2
t.query(0, 3, "min") # 2

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Using pip again:

fenwick_tree = FenwickTree(n)
for x in range(n):
    fenwick_tree.add(x, x + 1)

from __future__ import print_function

from fenwick import FenwickTree

n = 10

print('Note: Indexing is 0-based.')
print()

print('*******************************************')
print('* Initialize FenwickTree and update        ')
print('* frequencies one at a time.               ')
print('*******************************************')
print()

fenwick_tree = FenwickTree(n)
for x in range(n):
    fenwick_tree.add(x, x + 1)

print('*******************************************')
print('* Initialize FenwickTree using existing    ')
print('* frequencies.                             ')
print('*******************************************')
print()

fenwick_tree = FenwickTree(n)
f = range(1, n + 1)
fenwick_tree.init(f)

print('*******************************************')
print('* Calculate and print sum of all           ')
print('* frequencies                              ')
print('*******************************************')
print()

sum_all = fenwick_tree.prefix_sum(n)
print(sum_all)
print()

print('*******************************************')
print('* Calculate and print sum of frequencies   ')
print('* 2 through 8.                           ')
print('*******************************************')
print()

sum_2_8 = fenwick_tree.range_sum(2, 9)
print(sum_2_8)
print()

print('*******************************************')
print('* Calculate and print frequencies 5       ')
print('* through 9.                              ')
print('*******************************************')
print()

for x in range(5, 10):
    print(fenwick_tree[x])
print()

print('*******************************************')
print('* Retrieve and print all frequencies.      ')
print('*******************************************')
print()

print(fenwick_tree.frequencies())

This data structure provides the following capabilities. We are given several elements, each of which is a separate set. A DSU will have an operation to combine any two sets, and it will be able to tell in which set a specific element is. The classical version also introduces a third operation, it can create a set from a new element.

Yes, you are right! We are using pip again:

>>> from disjoint_set import DisjointSet
>>> ds = DisjointSet()
>>> ds.find(1)
1
>>> ds.union(1,2)
>>> ds.find(1)
2
>>> ds.find(2)
2
>>> ds.connected(1,2)
True
>>> ds.connected(1,3)
False

>>> "a" in ds
False
>>> ds.find("a")
'a'
>>> "a" in ds
True

>>> list(ds)
[(1, 2), (2, 2), (3, 3), ('a', 'a')]

>>> list(ds.itersets())
[{1, 2}, {3}, {'a'}]

A treap is a data structure which combines binary tree and binary heap (hence the name: tree + heap $$$\Rightarrow$$$ Treap).

More specifically, treap is a data structure that stores pairs $$$(X, Y)$$$ in a binary tree in such a way that it is a binary search tree by $$$X$$$ and a binary heap by $$$Y$$$. If some node of the tree contains values $$$(X_0, Y_0)$$$ , all nodes in the left subtree have $$$X \leq X_0$$$ , all nodes in the right subtree have $$$X_0 \leq X$$$, and all nodes in both left and right subtrees have $$$Y \leq Y_0$$$.

A treap is also often referred to as a "cartesian tree", as it is easy to embed it in a Cartesian plane.

Again, as I mentioned, Python is the most powerful language for CP, we will use pip again:

>>> import treap
>>> t = treap.treap()
>>> import random
>>> for i in range(20):
...    t[random.random()] = i
...
>>> list(t)
[0.011795687154763312, 0.0695864396266509, 0.15741892655439682, 0.18718082546304682, 0.1910965922423038, 0.22849105220538402, 0.276078590851345, 0.3166512089228003, 0.3456516881327997, 0.3543869818366584, 0.4022879538597536, 0.4519316126668157, 0.46329639459896466, 0.4873225275394878, 0.5866856381825849, 0.6403758625610735, 0.6936888466959068, 0.7843975080768091, 0.8888622013819216, 0.9047894146828958]
>>> t.find_min()
0.011795687154763312
>>> t.find_max()
0.9047894146828958

• PTIT, my university.
• Code Mely, a Vietnamese fanpage for Computer Science.

• PTIT, my university.
• Code Mely, a Vietnamese fanpage for Computer Science.

#define SZ(a) (ll)a.size()
#define FOR(i,a,b) for (ll i=(ll)a; i<=(ll)b; i++)
#define f first
#define mp make_pair
#define s second
#define p pair
#define all(C) C.begin(), C.end()

template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

vector<int> a(10);
cin >> a;
cout << a << endl;

10 is just a random number. It works for any size of the vector.

template<typename T1, typename T2> ostream& operator<<(ostream& out, const p<T1, T2>& x) {return out << x.f << ' ' << x.s;}
template<typename T1, typename T2> istream& operator>>(istream& in, p<T1, T2>& x) {return in >> x.f >> x.s;}

pair<int, int> a;
cin >> a;
cout << a;

template<typename T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

ordered_set<int> OS;
ordered_multiset<int> OMS;

template<typename T> using matrix = vector<vector<T> >;
template<typename T> using rubik = vector<vector<vector<T> > >;

rubik<int> a; // instead of vector<vector<vector<int> > > a;

template<typename T> void Unique(T &a) {a.erase(unique(a.begin(), a.end()), a.end());}

vector<int> a;
Unique(a);

ll powermod(ll a, ll b, ll m)
{
	if (b == 0) return 1;
	ull k = powermod(a, b / 2, m);
	k = k * k;
	k %= m;
	if (b & 1) k = (k * a) % m;
	return k;
}

// Prime test for large numbers

bool isPrime(ull n, int iter = 5) 
{
    if (n < 4) return n == 2 || n == 3;
	if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 0; i < iter; i++) 
	{
        ull a = 2 + rand() % (n - 3);
        if (powermod(a, n - 1, n) != 1) return false;
    }
    return true;
}

multiset<ll> LIS(vector<ll> A)
{
	ll a = A.size();
	multiset<ll> S;
	multiset<ll>::iterator it;
	FOR(i, 0, a - 1)
	{
		S.insert(A[i]);
		it = S.upper_bound(A[i]);
		if (it != S.end()) S.erase(it);
	}
	return S;
}

multiset<ll> LSIS(vector<ll> A) // a.k.a Longest Strictly Increasing Sequence
{
	ll a = A.size();
	multiset<ll> S;
	multiset<ll>::iterator it;
	FOR(i, 0, a - 1)
	{
		S.insert(A[i]);
		it = S.lower_bound(A[i]);
		it++;
		if (it != S.end()) S.erase(it);
	}
	return S;
}

Closed

Closed

4665849150760898

Hi, this is the first time I write such a blog like this. All is because of my excitement that for the first time I can solve all problems, not because I am worshiping myself or something. I know this is just a Div-3 contest, so there are many people who can solve it. But if you are stuck with some problems, feel free to read my solutions.

This is not an official editorial, so the solutions might not be the best of all solutions out there, so if you have something to discuss, feel free to leave something below. Thanks for all.

vector<ll> a(7);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
ll ttl = a[6];
cout << a[0] << ' ' << a[1] << ' ' << a[6] - a[0] - a[1] << '\n';

ll n;
cin >> n;
string s = "";
ll h = 0;
FOR(i, 0, n - 3)
{
	string t;
	cin >> t;
	if (s.empty() || t[0] != s.back())
	{
		s += t;
		h = 1;
	}
	else s += t[1];
}
if (!h) s += 'a';
while(s.length() < a) s += s.back();
cout << s << '\n';

ll n;
cin >> n;
vector<ll> C(a);
for (auto &x: C) cin >> x;
ll g = 0;
for (ll i = 0; i < a; i += 2)
{
	g = gcd(g, C[i]);
}
for (ll i = 1; i < a; i += 2)
{
	ll t = gcd(g, C[i]);
	if (t == g) g = 1;
}
if (g != 1)
{
	cout << g << '\n';
	return;
}
g = 0;
for (ll i = 1; i < a; i += 2)
{
	g = gcd(g, C[i]);
}
for (ll i = 0; i < a; i += 2)
{
	ll t = gcd(g, C[i]);
	if (t == g) g = 1;
}
if (g != 1) cout << g << '\n';
else cout << 0 << '\n';

ll a, k;
cin >> a >> k;
vector<ll> C(a);
for (auto &x : C) cin >> x;
REVERSE_SORT(C);
ll ttl = 0;
FOR(i, 0, k - 1)
{
	ttl += C[i + k] / C[i];
}
FOR(i, k * 2, a - 1) ttl += C[i];
cout << ttl << '\n';

ll n;
cin >> n;
vector<ll> b(n);
for (auto &x : b) cin >> x;
ll ttl = 0;
FOR(i, 0, n - 1)
{
	ttl += b[i];
}
ll k = n * (n + 1) / 2;
if (ttl % k != 0)
{
	cout << "NO" << '\n';
	return;
}
ttl /= k;
vector<ll> ans(n, 0);
FOR(i, 0, n - 1)
{
	ll x = (i + n - 1) % n;
	ans[i] = (ttl + b[x] - b[i]) / n;
	if (ttl + b[x] < b[i])
	{
		cout << "NO" << '\n';
		return;
	}
	if ((ttl + b[x] - b[i]) % n != 0)
	{
		cout << "NO" << '\n';
		return;
	}
	if (ans[i] == 0)
	{
		cout << "NO" << '\n';
		return;
	}
}
cout << "YES" << '\n';
printVector(ans);
cout << '\n';

ll x, y;
cin >> x >> y;
if (x == y)
{
	cout << "YES" << '\n';
	return;
}
if (y % 2 == 0)
{
	cout << "NO" << '\n';
	return;
}
function<string(ll)> convert = [&](ll a)
{
	string s = "";
	ll n = 1;
	while (a)
	{
		if (a & n) s += '1';
		else s += '0';
		if (a & n) a ^= n;
		n <<= 1;
	}
	revrs(s);
	return s;
}
string s = convert(x);
string t = convert(y);
function<bool(ll, ll)> check = [&](ll m, ll n)
{
	FOR(i, m, n) if (t[i] == '0') return false;
	return true;
};
function<void()> extract = [&]()
{
	ll len = s.length();
	FOR(i, 0, t.length() - 1)
	{
		if (i + len > t.length()) break;
		if (t.substr(i, len) == s)
		{
			if (!check(0, i - 1) || !check(i + len, t.length() - 1)) continue;
			cout << "YES" << '\n';
			exit(0);
		}
	}
	if (s.back() == '0') return;
	revrs(s);
	FOR(i, 0, t.length() - 1)
	{
		if (i + len > t.length()) break;
		if (t.substr(i, len) == s)
		{
			if (!check(0, i - 1) || !check(i + len, t.length() - 1)) continue;
			cout << "YES" << '\n';
			exit(0);
		}
	}
	revrs(s);
};
s = s + '1';
extract();
s.pop_back();
extract();
while (!s.empty() && s.back() == '0')
{
	s.pop_back();
}
if (!s.empty()) extract();
cout << "NO" << '\n';

ll a, b, q;
cin >> a >> b >> q;
vec(ll) ttl;
map<ll, ll> C, first, last;
ll cnt = 0;

FOR(i, 0, a - 1)
{
	ll x;
	cin >> x;
	cnt += x;
	ttl.pb(x);
	C[x]++;
}
FOR(i, 0, b - 1)
{
	ll x;
	cin >> x;
	ttl.pb(x);
}
	
SORT(ttl);
FOR(i, 0, ttl.size() - 1) last[ttl[i]] = i;
FORD(i, ttl.size() - 1, 0) first[ttl[i]] = i;
vector<ll> PREF = ttl;
FOR(i, 1, PREF.size() - 1) PREF[i] += PREF[i - 1];
set<vector<ll> > SORT_BY_DIST; // DIST -> TAKEN_ELEMENTS -> LAST_ELE -> FIRST_ELE
set<vector<ll> > SORT_BY_FIRST_ELEMENT; // FIRST_ELE -> LAST_ELE -> TAKEN_ELEMENTS -> DIST 

FOR(i, 0, ttl.size() - 2)
{
	if (ttl[i] == ttl[i + 1]) continue;	
	ll x = ttl[i];
	SORT_BY_DIST.insert({ttl[i + 1] - ttl[i], C[x], last[x], first[x]});
	SORT_BY_FIRST_ELEMENT.insert({first[x], last[x], C[x], ttl[i + 1] - ttl[i]});
}
SORT_BY_DIST.insert({(ll)1e18, C[ttl.back()], last[ttl.back()], first[ttl.back()]});
SORT_BY_FIRST_ELEMENT.insert({first[ttl.back()], last[ttl.back()], C[ttl.back()], (ll)1e18});

vec(ll) ans(q);
vector<p<ll, ll> > QUERIES(q);
FOR(i, 0, q - 1)
{
	cin >> QUERIES[i].f;
	QUERIES[i].s = i;
}
SORT(QUERIES);

function<ll(ll, ll)> SUB = [&](ll LAST, ll TAKEN)
{
	ll l = LAST - TAKEN;
	ll tmp = 0;
	if (l == -1)
	{
		tmp += PREF[0];
		l = 0;
	}
	tmp += PREF[LAST] - PREF[l];
	return tmp;
};
	
for (auto x : QUERIES)
{
	vector<ll> K = *SORT_BY_DIST.begin();
	while (K[0] <= x.f)
	{
		vector<ll> Q = K;
		revrs(Q);
		vector<ll> T = *SORT_BY_FIRST_ELEMENT.upper_bound(Q);
		vector<ll> P = T;
		revrs(P);
		SORT_BY_DIST.erase(K);
		SORT_BY_DIST.erase(P);
		SORT_BY_FIRST_ELEMENT.erase(Q);
		SORT_BY_FIRST_ELEMENT.erase(T);
		cnt -= SUB(Q[1], Q[2]);
		cnt -= SUB(T[1], T[2]);
		cnt += SUB(T[1], Q[2] + T[2]);
		T[2] = Q[2] + T[2];
		T[0] = Q[0];
		SORT_BY_FIRST_ELEMENT.insert(T);
		revrs(T);
		SORT_BY_DIST.insert(T);
		K = *SORT_BY_DIST.begin();
	}
	ans[x.s] = cnt;
}
	
printVector(ans);	
cout << '\n';

? - ? + ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? = 57

Possible
57 - 40 + 57 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 57

class STRO
{
	public:
		bool bigger(string a, string b) // check if a is strictly bigger than b or not
		{
			if (a.length() > b.length()) return true;
			if (a.length() < b.length()) return false;
			for(int i = 0; i < a.length(); i++)
			{
				if (a[i] > b[i]) return true;
				else if (a[i] < b[i]) return false;
			}
			return false;
		}
		
		string add(string str1, string str2) // add strings, took this from geekforgeeks
		{
		    if (str1.length() > str2.length())
		        swap(str1, str2);
		    string str = "";
		    int n1 = str1.length(), n2 = str2.length();
		    int diff = n2 - n1;
		    int carry = 0;
		    for (int i=n1-1; i>=0; i--)
		    {
		        int sum = ((str1[i]-'0') + (str2[i+diff]-'0') + carry);
		        str.push_back(sum%10 + '0');
		        carry = sum/10;
		    }
		    for (int i=n2-n1-1; i>=0; i--)
		    {
		        int sum = ((str2[i]-'0')+carry);
		        str.push_back(sum%10 + '0');
		        carry = sum/10;
		    }
		    if (carry) str.push_back(carry+'0');
		    reverse(str.begin(), str.end());
		    while(str.size() > 1 && str[0] == '0') str.erase(0, 1);
		    return str;
		}
		
		string sub(string str1, string str2) // substract strings, also from geekforgeeks
		{
		    if (bigger(str2, str1)) swap(str1, str2);
		    string str = "";
		    int n1 = str1.length(), n2 = str2.length();
		    reverse(str1.begin(), str1.end());
		    reverse(str2.begin(), str2.end());
		    int carry = 0;
		    for (int i = 0; i < n2; i++) 
			{
		        int sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
		        if (sub < 0) {
		            sub = sub + 10;
		            carry = 1;
		        }
		        else
		            carry = 0;
		 
		        str.push_back(sub + '0');
		    }
		    for (int i = n2; i < n1; i++) 
			{
		        int sub = ((str1[i] - '0') - carry);
		        if (sub < 0) {
		            sub = sub + 10;
		            carry = 1;
		        }
		        else
		            carry = 0;
		 
		        str.push_back(sub + '0');
		    }
		    reverse(str.begin(), str.end());
		    while (str.size() > 1 && str[0] == '0') str.erase(0, 1);
		    return str;
		}
		
		string mul(string A, string B) // multiply strings
		{
			reverse(A.begin(),A.end());
			reverse(B.begin(),B.end());
			string C;
			C.resize(A.length() + B.length(),'0');
			for (int i = 0; i < A.length(); i++)
			{
				int c = 0;
				FOR(j, 0, B.length()-1)
				{
					c += ((A[i] - '0') * (B[j] - '0') + C[i + j] - '0');
					C[i + j] = (char)(c%10 + '0');
					c/=10;
				}
				if (c > 0) C[i + B.length()] += c;
			}
			reverse(C.begin(),C.end());
			while (C.size() > 1 && C[0] == '0') C.erase(0, 1);
			return C;
		}
		string div(string number, ll divisor) // divide 1 string with 1 number, the version for divide two strings in down below
		{
		    string ans = "";
		    ll idx = 0;
		    ll temp = number[idx] - '0';
		    while (temp < divisor) temp = temp * 10 + (number[++idx] - '0');
		    while (number.size() > idx) 
			{
		        ans += (temp / divisor) + '0';
		        temp = (temp % divisor) * 10 + number[++idx] - '0';
		    }
		    while (ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
		    if (ans.length() == 0) return "0";
		    return ans;
		}
		bool bigger2(string a, string b) // check if a >= b, not strictly greater
		{
			if (a.length() > b.length()) return true;
			if (a.length() < b.length()) return false;
			FOR(i, 0, a.length() - 1)
			{
				if (a[i] > b[i]) return true;
				else if (a[i] < b[i]) return false;
			}
			return true;
		}
		string dv(string a, string b) // divide as two strings, use binary search
		{
			if (bigger(b, a)) return "0";
			if (a == "0") return "0";
			string l = "0";
			string r = a;
			string mid, mid2;
			while (bigger2(r, l))
			{
				mid = add(r, l);
				if ((mid[mid.length() - 1] - '0') % 2 == 1) mid[mid.length() - 1]--;
				mid = div(mid, 2);
				if (mid == "0") break;
				mid2 = mul(mid, b);
				if (bigger(mid2, a)) r = sub(mid, "1");
				else l = add(mid, "1");
			}
			return r;
		}
		string md(string a, string b) // find a % b
		{
			if (bigger(b, a)) return a;
			if (a == "0") return "0";
			if (b == "1") return "0";
			string l = "0";
			string r = a;
			string mid, mid2;
			while (bigger2(r, l))
			{
				if (mid == "0") break;
				mid = add(r, l);
				if ((mid[mid.length() - 1] - '0') % 2 == 1) mid[mid.length() - 1]--;
				mid = div(mid, 2);
				mid2 = mul(mid, b);
				if (bigger(mid2, a)) r = sub(mid, "1");
				else l = add(mid, "1");
			}
			mid = mul(r, b);
			mid = sub(a, mid);
			while (mid.size() > 1 && mid[0] == '0') mid.erase(0, 1);
			if (mid == b) return "0";
			return mid;
		}
		string strgcd(string a, string b) // find gcd(a, b)
		{
			if (a == "0") return b;
			return strgcd(md(b, a), a);
		}
};

STRO STR;