week of 1/17

---

📝 notes

1111,

---

many perf squares

link: https://codeforces.cc/contest/1782/problem/D

problem

given a sequence of

$n\le 50$ integers,

$a_i\le {10}^9$, find the maximum perfect squares in the array after you add some integer

$0\le x\le {10}^{18}$ to every element.

solution

alright, well we know

$1$ is always possible because we can just add the closest square -

$a_0$ to every element, and get

$a_0=p^2$.

how about two?

well, if they're both perfect squares then:

1. $$a_j-a_i=x^2-y^2$$
2. $$a_j-a_i=(x+y)(x-y)$$

$(x+y)$ and

$(x-y)$ are factor pairs, sooo, we'll just iterate through all possible factor pairs

$\le \sqrt{(}{10}^9)$, and do some casework given those.

3. $$f=(x+y),s=(x-y)$$
4. $$x=f-y,s=(x-y)$$
5. $$x=f-y,s=f-2y$$
6. $$x=f-y,y=\frac{f-s}{2}$$
7. $$x=f-\frac{f-s}{2}$$

try both of these differences, and report the best answer.

time complexity:

$\mathcal{O}(n^3\sqrt{{10}^9})=\mathcal{O}(n^3)$

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif
#define int ll
long long int_sqrt(long long x) {
	long long ans = 0;
	for (ll k = 1LL << 30; k != 0; k /= 2) {
		if ((ans + k) * (ans + k) <= x) {
			ans += k;
		}
	}
	return ans;
}

void solve() {
	int n;
	cin >> n;

	int ans = 0;

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		int t = int_sqrt(a[i]);
		if (t * t == a[i]) ans++;
	}
	ans = max(ans, 1LL);

	sort(all(a));
	set<array<int, 3>> check;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			check.insert({a[j] - a[i], a[i], a[j]});
		}
	}

	for (auto diff : check) {
		// diff = a[j] - a[i], diff = a^2 - b^2
		// diff = (a + b)(a - b)
		// diff <= 1e9

		for (int fc = 1; fc * fc <= (ll)(1e9); fc++) {
			if (diff[0] % fc) continue;
			// diff = fc * (diff/fc)
			int lhs = fc, rhs = diff[0] / fc;

			// a + b = lhs
			// a - b = rhs
			// b = lhs - a
			// a - lhs + a = rhs
			// 2a = lhs+rhs
			// a = (lhs+rhs)/2

			int aa = (lhs + rhs) / 2;
			int bb = lhs / aa;

			int t = (aa * aa) - diff[2];
			if (t > 0) {
				int cur = 0;
				for (int i = 0; i < n; i++) {
					int tt = int_sqrt(a[i] + t);
					if (tt * tt == (a[i] + t)) cur++;
				}
				ans = max(ans, cur);
			}

			t = (bb * bb) - diff[1];
			if (t > 0) {
				int cur = 0;
				for (int i = 0; i < n; i++) {
					int tt = int_sqrt(a[i] + t);
					if (tt * tt == (a[i] + t)) cur++;
				}
				ans = max(ans, cur);
			}
		}
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

permutation graph

link: https://codeforces.cc/contest/1696/problem/D

problem

given a permutation of length

$n\le 2.5\cdot {10}^5$, consider a graph with

$n$ nodes, where all nodes

$i,j$, where

$max(a_i,a_j)=a_i,andmin(a_i,a_j)=a_j$, or

$max(a_i,a_j)=a_j,andmin(a_i,a_j)=a_i$.

now, find the shortest path between

$a_0$ and

$a_n$.

solution

clearly, we can't construct the tree because of the tight constraint on

$n$, but we can observe that we can go as far as we can as long as we don't violate the current "max-min"ess of the current element.

thus, we could solve with the following pseudo-code.

// min
int cmx = a_p
for i from [p+1, n) ->
    if a_i < a_p -> break
    if a_i > cmx -> cmx = a_i
    
    if a_i >= cmx -> i is viable, choose max i at the end

and something similar for max.

we just have to make one opitmization, if the current element is the min/max, then, we can choose the least/greatest element from

$i\dots n$ to go to next.

we'll precompute these suffix min/maxes.

otherwise, we'll follow our other algo.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<pi> mx(n);
	pi cur = {a[n - 1], n - 1};
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] > cur.f) cur = {a[i], i};
		mx[i] = cur;
	}
	vector<pi> mn(n);
	cur = {a[n - 1], n - 1};
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] < cur.f) cur = {a[i], i};
		mn[i] = cur;
	}

	vector<int> dp(n, inf);
	dp[0] = 0;
	queue<int> todo;
	todo.push(0);
	while (sz(todo)) {
		int top = todo.front();
		todo.pop();

		// min
		if (mn[top].f == a[top]) {
			if (dp[mx[top].s] > dp[top] + 1) {
				dp[mx[top].s] = dp[top] + 1;
				todo.push(mx[top].s);
			}
		} else {
			// find first that doesn't break min,
			int cmn, cmx;
			cmn = cmx = a[top];
			int pos = top;
			int choice = 0;
			for (; pos < n; pos++) {
				if (a[pos] < cmn) break;
				if (a[pos] >= cmx) cmx = a[pos];
				if (a[pos] >= cmx) choice = pos;
			}
			if (choice > top && dp[choice] > dp[top] + 1) {
				dp[choice] = dp[top] + 1;
				todo.push(choice);
			}
		}
		// max
		if (mx[top].f == a[top]) {
			int bst = mn[top].s;
			if (dp[bst] > dp[top] + 1) {
				dp[bst] = dp[top] + 1;
				todo.push(bst);
			}
		} else {
			// find first that doesn't break max,
			int cmn, cmx;
			cmn = cmx = a[top];
			int pos = top;
			int choice = 0;
			for (; pos < n; pos++) {
				if (a[pos] > cmn) break;
				if (a[pos] <= cmx) cmx = a[pos];
				if (a[pos] <= cmx) choice = pos;
			}
			if (choice > top && dp[choice] > dp[top] + 1) {
				dp[choice] = dp[top] + 1;
				todo.push(choice);
			}
		}
	}
	cout << dp[n - 1] << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.

range xor queries

https://cses.fi/problemset/task/1650

remember that we can use XOR like a prefix sum, because

$x\oplus x=0$

so, we just xor the previous range, we get the XOR sum of any range in

$\mathcal{O}(1)$

mixing water

https://codeforces.cc/problemset/problem/1359/C

total oversight here, i thought that we could add any amount of hot and cold water, but we can only alternate them.

if we ever alternate between the two, and end with an even number, then the average will always be

$\frac{h+c}{2}$.

also note that we will get to a point when we get further by trying

$K+1$, so that's what we'll use for our binary search.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

void solve() {
	long double h, c, t;
	cin >> h >> c >> t;

	function<long double(int k)> rawr = [&](int k) {
		long double avg = ((h * (k + 1)) + (c * k)) / ((long double)(2 * k + 1));

		return abs(avg - t);
	};
	if (t <= (h + c) / 2) {
		cout << 2 << endl;
	} else {
		int lo = 0, hi = 1e6;

		while (lo < hi) {
			int mid = (lo + hi) / 2;

			if (rawr(mid) <= rawr(mid + 1)) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
		cout << lo * 2 + 1 << endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

ehab and expected XOR

https://codeforces.cc/contest/1174/problem/D

consider the prefix XOR of the array, the constraints require that the XOR of any two indices is not

$x$, so all

$a_i\oplus a_j\ne x$, and they aren't zero (so they can't be equal).

then, let's just build the prefix XOR, if we've already put in

$i\oplus x$, then don't put

$i$ in.

since

$n\le 18$, we'll iterate through

$2^{18}$ numbers.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, x;
	cin >> n >> x;

	vector<bool> a(2 * (1 << 18));
	vector<int> build;
	for (int i = 1; i < (1 << n); i++) {
		if (a[i ^ x] || i == x) continue;
		build.push_back(i);
		a[i] = 1;
	}

	vector<int> ans;
	for (int i = 0; i < sz(build); i++) {
		if (i == 0)
			ans.push_back(build[i]);
		else
			ans.push_back(build[i] ^ build[i - 1]);
	}
	cout << sz(ans) << endl;
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i] << ' ';
	}
	cout << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

magazine ad

https://codeforces.com/contest/803/problem/D

another binary search problem…

split the line into segments, divided by spaces and dashes.

then greedily assign these segments and check the lines required.

implementation (c++17)

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int k;
	cin >> k;
	string ad;
	getline(cin, ad);
	getline(cin, ad);
	int n = sz(ad);

	vector<string> segs;
	segs.push_back("");
	for (int i = 0; i < n; i++) {
		if (ad[i] == ' ' || ad[i] == '-') {
			segs.back() += ad[i];
			segs.push_back("");
		} else {
			segs.back() += ad[i];
		}
	}

	function<bool(int m)> ok = [&](int m) {
		int lines = 1;
		int clen = 0;

		for (string &s : segs) {
			if (sz(s) > m) return false;
			if (clen + sz(s) > m) {
				lines++;
				clen = sz(s);
			} else
				clen += sz(s);
		}
		return lines <= k;
	};
	int lo = 0, hi = n + 1;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;

		if (ok(mid)) {
			hi = mid;
		} else
			lo = mid + 1;
	}
	cout << lo << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

firecrackers

https://codeforces.cc/contest/1468/problem/D

well it's never optimal to run away, if we don't have any firecrackers already placed, so we'd want to throw all of our firecrackers, and then run for as long as possible.

after we throw, we have

$a<b?b-1:n-a$ time to run, and the number of fireworks we can throw is bounded by

$|a-b|$.

so, we'll do another binary search

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

void solve() {
	// strat: drop all firecrackers, and run
	// bruh another bin search problem WHYYY

	int n, m, a, b;
	cin >> n >> m >> a >> b;
	vector<int> uwu(m + 1);
	for (int i = 1; i <= m; i++) {
		cin >> uwu[i];
	}
	sort(all(uwu));

	function<bool(int k)> check = [&](int k) {
		int time = abs(a - b) + (a > b ? n - a : a - 1);
		if (abs(a - b) <= k) return false;	// can't toss all
		// time -= k;
		// cout << time << endl;

		// k-1 + k - 2 ... 0
		int wrst = 0;
		int tt = 1;
		for (int i = k; i >= 1; i--) {
			wrst = max(wrst, tt++ + uwu[i]);
		}
		// cout << "Toss " << k << endl;
		// cout << "saved " << wrst << endl;
		// cout << time << endl;

		if (wrst <= time)
			return true;
		else
			return false;
	};

	int lo = 0, hi = m;
	while (lo < hi) {
		int mid = lo + (hi - lo + 1) / 2;
		if (check(mid)) {
			lo = mid;
		} else
			hi = mid - 1;
	}
	// LMAO
	cout << lo << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

minimax problem

for all arrays

$i,j$, define the array

$b$ as,

$b_k=max(a_{ik},a_{ij})$.

given

$n$ arrays of

$m$ integers, choose (not necessarily distinct) two arrays

$i,j$, such that you maximize

$\underset{k=1}{\overset{m}{min}}(b_k)$.

output these two arrays. (if multiple solutions exists, output any)

solution

first of all, let's fix the answer,

$k$. then, each array can be represented as a binary string with

$m$ bits, the

$j$th bit being on if

$a_{ij}\ge k$.

then, for any two arrays, if the bitwise OR of the two is equal to

$2^m-1$, we have a constructable solution.

since

$2^8\le 256$, we'll can iterate through all pairs (

${256}^2$), and check if

$i$ and

$j$ exist, and that the bitwise OR of the two equal

$2^m-1$.

time complexity,

$\mathcal{O}(n\cdot m^2\cdot \log (max{a}_{ij}))$, which will comfortable pass in time.

this problem took me

$2$ hours to solve D:

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl "\n"
#define dbg(...) 0
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;

	vector<vector<int>> val(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> val[i][j];
		}
	}

	function<pi(int k)> works = [&](int k) {
		vector<int> possible(260, -1);
		possible[0] = 0;
		set<int> ok;
		ok.insert(0);

		vector<int> inverse(n);
		// first compute existing hashes
		for (int i = 0; i < n; i++) {
			vector<bool> hsh(m);
			for (int j = 0; j < m; j++) {
				hsh[j] = val[i][j] >= k;
			}

			int aft = 0;
			for (int j = 0; j < m; j++) {
				if (hsh[j]) {
					aft += (1 << j);
				}
			}
			possible[aft] = i;
		}

		for (int i = 0; i < (1 << m); i++) {
			for (int j = 0; j < (1 << m); j++) {
				if (possible[i] != -1 && possible[j] != -1) {
					if ((i | j) == (1 << (m)) - 1) {
						return make_pair(possible[i], possible[j]);
					}
				}
			}
		}
		return make_pair(-1, -1);
	};

	int lo = 0, hi = 1e9;
	pi ans = {0, 0};
	while (lo < hi) {
		int mid = lo + (hi - lo + 1) / 2;

		pi ret = works(mid);
		if (ret.f == -1) {
			hi = mid - 1;
		} else {
			lo = mid;
			ans = ret;
		}
	}
	// cout << lo << endl;
	cout << ans.f + 1 << ' ' << ans.s + 1 << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)