Suppose two sockets $$$a$$$ and $$$b$$$ are adjacent to each other have the same color. If I plug a wire into socket $$$a$$$, then socket $$$b$$$ cannot have a wire, therefore the wire associated with socket $$$b$$$ must be plugged into its other socket.

We can then reframe the entire problem as 2SAT. Formally, let there be a variable $$$x_i$$$ for every wire $$$i$$$. Assign one of the sockets $$$x_i$$$ and one of the sockets $$$\overline{x_i}$$$. — For any two adjacent sockets $$$a$$$ and $$$b$$$ with the same color, add the constraints $$$a \to \bar{b}$$$ and $$$b \to \bar{a}$$$.

Then, any satisfying assignment to the 2SAT expression corresponds with some assignment of wires to sockets, such that every wire is connected to at least one of its sockets.

We use a divide-and-conquer style approach. Note that the operations form a tree. We do not need to keep a lot of information for each expression; note that we only require the number of substrings divisible by $$$n$$$, as well as the number of suffixes with each residue $$$\bmod n$$$ (which do not start with $$$0$$$) and the number of prefixes of each length $$$\bmod n$$$ with each residue $$$\bmod n.$$$ Note that if we concatenate two expressions, the number of substrings divisible by $$$n$$$ is simply the sum of the number of substrings divisible by $$$n$$$ in each string and the number of suffix-prefix pairs that form a substring divisible by $$$n.$$$ We can compute this from the information we stored, since each prefix length/residue combination allows a unique suffix residue from the first string to attain a residue $$$0 \bmod n.$$$ See code for more details.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int MAXN = 31;
int n, MOD;
 
 
ll binpow (ll a, ll b)
{
	ll res = 1;
	while (b > 0)
	{
		if (b % 2)
		{
			res = res * a % MOD;
		}
		a = a * a % MOD;
		b /= 2;
	}
	return res;
}
 
struct dat
{
	ll pf[MAXN][MAXN]; //number of nonempty prefixes of residue i%n with length j that don't start w/ 0
	ll sf[MAXN]; //number of nonempty suffixes of residue i%n
	ll w; //residue of full string
	ll res; //number of substrings divisible by r
	ll len; //10^length
	
	dat ()
	{
		res = w = 0;
		len = 1 % n;
		for (int i = 0; i < n; i++)
		{
			sf[i] = 0;
			for (int j = 0; j < n; j++)
			{
				pf[i][j] = 0;
			}
		}
	}
	dat (char c) 
	{
		assert('0' <= c && c <= '9'); 
		res = ((c - '0') % n == 0);
		len = 10 % n;
		w = (c - '0') % n;
		for (int i = 0; i < n; i++)
		{
			sf[i] = 0;
			for (int j = 0; j < n; j++)
			{
				pf[i][j] = 0;
			}
		}
		if (c != '0')
		{
			sf[(c-'0')%n] = 1 % MOD;
		}
		pf[(c-'0')%n][10%n] = 1 % MOD;
	}
};
 
dat comb (dat a, dat b)
{
	dat res;
	res.res = (a.res + b.res) % MOD;
	res.w = (a.w * b.len % n + b.w) % n;
	res.len = a.len * b.len % n;
	for (int i = 0; i < n; i++)
	{
		res.sf[i] = (res.sf[i] + b.sf[i]) % MOD;
		ll u = (i * b.len + b.w) % n;
		res.sf[u] = (res.sf[u] + a.sf[i]) % MOD;
		for (int k = 0; k < n; k++)
		{
			for (int l = 0; l < n; l++)
			{
				if (i == 0)
				{
					u = (a.w * l % n + k) % n;
					res.pf[u][l * a.len % n] = (res.pf[u][l * a.len % n] + b.pf[k][l]) % MOD;
					res.pf[k][l] = (res.pf[k][l] + a.pf[k][l]) % MOD;
				}
				if ((i * l + k) % n == 0)
				{
					res.res = (res.res + a.sf[i] * b.pf[k][l] % MOD) % MOD;
				}
			}
		}
	}
	return res;
}
 
map<char,dat> mp;
map<char,string> adj;
 
void dfs (char c)
{
	mp[c] = dat();
	for (auto x : adj[c])
	{
		if (!mp.count(x))
		{
			dfs(x);
		}
		mp[c] = comb(mp[c], mp[x]);
	}
}
 
int main()
{
	ifstream cin("divisible.in");
	ofstream cout("divisible.out");
	cin >> n >> MOD;
	int k;
	cin >> k;
	
	for (char i = '0'; i <= '9'; i++)
	{
		mp[i] = dat(i);
	}
	
	for (int i = 0; i < k; i++)
	{
		string cur;
		cin >> cur;
		char u = cur[0];
		reverse(cur.begin(), cur.end());
		for (int j = 0; j < 3; j++) cur.pop_back();
		reverse(cur.begin(), cur.end());
		adj[u] = cur;
	}
	dfs('A');
	cout << mp['A'].res << "\n";
}

First, note that each person will work on each document for no less than $$$30$$$ minutes at a time. Thus we can split each node into two nodes which each correspond to $$$30$$$ minutes of work, having one of these nodes point to the other (representing the first and second half of the task), since both secretaries cannot work at the same time.

Now, note that at any node our answer is bounded above by the length of the longest path from our node to another node in the DAG. This is because each node in the path is constrained by the node before it. Thus an optimal solution will decrease the length of this path whenever possible. Our algorithm thus takes the two available vertices with the longest paths to any other node at each point in time.

More details are provided at https://en.wikipedia.org/wiki/Coffman–Graham_algorithm.

Although the sample input can look intimidating to properly parse, note that there are only 2 real types of expressions: "add component" (which is always the same string) and "set parameter" (which is 3 tokens, beginning with gbc.(parameter name)). Some basic string processing is enough for this.

Aside from that, we can mostly just implement the statement. Maintain the previously-placed object, as well as a large-enough boolean grid to specify if a component occupies that location (since we have $$$\leq 50$$$ components and each has $$$\leq 50$$$ width/height, a $$$3000 \times 3000$$$ grid works). For each box, find it's upper-left corner, then use width/height to determine the bottom left corner. For width/height = REMAINDER, just fill up the row/column to the end of the grid.

Additionally, in order to determine when a row/column has no free spaces (for relative gridx/gridy), maintain the count of unoccupied cells in each row and column as we update the grid. Then, a row (or column) has no free spaces if this count is $$$0$$$. We can naively loop over each box to perform this update because there are only $$$50$$$ components.

Observe that the network graph is periodic mod $$$\text{lcm}(8, 7, ..., 2, 1) = 840$$$. For any single packet, there are $$$840N$$$ states that it could be in, of which $$$840(N-1)$$$ of them are not at it's target node. Therefore, if the packet travels for more than $$$840N$$$ time steps it must be in a cycle that does not contain it's target node.

We first use this observation to identify all packets that can reach their target node, as well as the ending time when they reach their target. Since all of the packets arrive at $$$t \leq 1000$$$, we have enough time to simulate $$$N$$$ moves for $$$840N + 1000$$$ time steps. We can choose the subset of packets while performing this simulation.

• For each time step, add packets that appear and remove packets that have reached their target, then determine the destination node for each packet. Handle collisions when packets appear and when they are sent to their destinations.
• If two packets reach the same node at the same time, we can retroactively choose one of them to be removed from the subset (as if it never existed, so the collision doesn't happen). At the collision point, all future moves both packets make (up until they reach their targets) will be exactly the same, so we can greedily choose the one with an earlier ending time because it will cause less collisions with other packets.
• Furthermore, if the packet we chose to continue eventually is also removed due to another collision, we can be sure that the removed packet would also reach the same collision and would also be removed.

The algorithm is simply to simulate the network for $$$840N + 1000$$$ steps and handle collisions as described above. If a packet reaches its target without being removed, we add it to the answer set.

For a subset $$$A \subset \begin{Bmatrix}1, \ldots, n\end{Bmatrix}$$$ we introduce the notation

for convenience. First, note that $$$\mathcal{I}$$$ always contains $$$\varnothing,$$$ since $$$s(\varnothing) = 0$$$. As a result we cannot violate condition $$$1.$$$ Similarly, it is impossible to violate condition $$$2,$$$ since for $$$A \supset B$$$ we have

and $$$s(A \setminus B) \geq 0$$$ by non-negativity of the weights $$$w_i.$$$

We say a set $$$A$$$ is constrained if $$$s(A) \leq c$$$ and for all $$$x \not \in A,$$$ $$$s(A \cup \begin{Bmatrix}x\end{Bmatrix}) \geq c.$$$ Clearly if we can find constrained sets $$$A, B$$$ with $$$|A| \neq |B|$$$ then we have a contradiction to the third condition.

Consider the sets $$$M_{\min}$$$ and $$$M_{\max}$$$ constructed as follows:

For $$$M_{\min},$$$ iterate through the indices $$$\begin{Bmatrix}1,\ldots, n\end{Bmatrix}$$$ in non-decreasing order of $$$w_i.$$$ At each index, if adding it to the set keeps $$$s(M_{\min})$$$ at most $$$c,$$$ then add it to $$$M_{\min}.$$$ For $$$M_{\max},$$$ perform the same algorithm with the indices initially in non-increasing order of weights.

It is well known that $$$M_{\min}$$$ is the constrained set with the maximum size and $$$M_{\max}$$$ is the constrained set of minimum size. The proof is quite simple and thus is left as an exercise.

If $$$|M_{\min}| \gt |M_{\max}|$$$ then we are done. Otherwise, we know that all constrained sets have the same size; call this $$$k.$$$

We now make the following claim: If $$$|A| \gt |B|$$$ are sets which contradict property $$$3$$$, then there exist sets $$$C \supset A$$$ and $$$D \supset B$$$ such that $$$|C| = k$$$ and $$$|D| = k - 1$$$ which also contradict this property. We split the proof of this claim into two lemmas.

Lemma 1. If $$$|A| \lt k$$$ then we can construct $$$|C| = k.$$$

Proof: Since $$$|B| \lt |A| \lt k$$$ neither of these sets are constrained. Then there exist indices $$$i,j$$$ which can be added to $$$B$$$ and $$$A$$$ respectively. We can add $$$x = \text{argmin}_{u \in \begin{Bmatrix}i,j\end{Bmatrix}} w_u$$$ to both sets. The proof is completed by induction.

Lemma 2. If $$$|A| - |B| \gt 1$$$ then we can construct $$$|C| - |D| = 1.$$$

Proof: Since $$$|B| \lt k - 1$$$ there exists some element which can be added to $$$B.$$$ If this element is not in $$$A$$$ then it does not affect the validity of our contradiction. If it is in $$$A,$$$ then our pair $$$A,B$$$ is not valid by definition of property $$$3$$$.

Finally, note that two sets $$$A,B$$$ form a valid pair if and only if the minimum weight of an index in $$$A \setminus B$$$ cannot be added to $$$B.$$$ In fact, if a pair $$$A,B$$$ contradicts property $$$3,$$$ then there exists a pair $$$C,D$$$ which also contradicts the property, such that the minimum weight element in $$$C$$$ does not occur in $$$D.$$$ The proof of this claim is very similar to that of the lemmas above, and the reader is encouraged to work out the details.

So now what we are looking for is a pair of sets $$$A,B$$$, such that the minimum element of $$$A$$$ is large enough that we cannot add it to $$$B$$$. What we will do is construct the sets $$$A,B$$$ with the greatest minimum and smallest allowable final element, respectively, since if a pair $$$A,B$$$ exists then this pair is also valid.

The first set can be constructed by iterating over suffixes of the weights in sorted order and taking $$$M_{\min}$$$ of the shortest suffix which satisfies $$$M_{\min} = k.$$$ The second set is simply $$$M_{\max} \setminus {u},$$$ where $$$u$$$ is the element of minimum weight. We can construct these sets and check if they form a valid contradiction. If they do not, then the set of solutions is a matroid.

Suppose we are making the potions one by one, and for now assume we have an even quantity of substances in total. Let $$$t$$$ be the remaining number of unused substances.

Since the objective is to minimize lexicographical ordering of our chosen set, it is always best to combine the two lowest-numbered substances at any time. Greedily combine the two lowest-numbered substances, until there exists some substance $$$z$$$ such that $$$a_z = t/2$$$ (*). Once $$$a_z = t/2$$$, all remaining substances must be matched with $$$z$$$.

We can speed this up with two pointers on substance types. Let $$$x$$$ and $$$y$$$ represent the two lowest-numbered substances; we either use up all of $$$x$$$, all of $$$y$$$, or we use up enough of $$$x$$$ and $$$y$$$ so that $$$t/2 = a_z$$$ for some $$$z \neq x, y$$$, at which point we then match all substances with. This is guaranteed to be the correct solution for even $$$t$$$ since we made the lexicographically minimal choice at every step.

For the case of odd $$$t$$$, we can leave one bottle unmatched so we amend the condition (*) to $$$a_z = \lceil t/2 \rceil$$$. This is better than $$$a_z = \lfloor t/2 \rfloor$$$; in the former the last $$$a_z-1$$$ potions were not chosen greedily, while in the latter the last $$$a_z$$$ potions were not chosen greedily. Therefore, the former maximizes the prefix of potions selected greedily, so it must be the lexicographically minimal solution.

Let's call the transformed permutation $$$b$$$, and the original permutation $$$a$$$.

Observation 1:

In $$$a$$$, for every pair of indices $$$(i,i+1)$$$ where $$$i$$$ is odd, there is exactly one fixed point. This is true since every pair of these indices can contain at most 1 fixed point (because of the decreasing condition), so to get $$$n$$$ fixed points, every pair must contain exactly one fixed point.

Observation 2:

Observation 1 means that for every such pair of indices, one of them will remain after removing the fixed points. More concretely, after removing the fixed points, the array must contain: 1 or 2 < 3 or 4 < 5 or 6 and so on.

Observation 3:

Since $$$b$$$ specifies the relative order, the pair it takes the non-fixed element from is predetermined based on $$$b$$$. It must be either $$$2b[i]$$$ or $$$2b[i]-1$$$.

Solution

I claim that if $$$b$$$ has any fixed points, then the solution is impossible. Suppose $$$b[i] = i$$$. There are two choices, either $$$a_{2i}$$$ is fixed, or $$$a_{2i-1}$$$ is fixed. If $$$a_{2i}$$$ is fixed, then $$$a_{2i-1}$$$ must be greater than $$$2i$$$, but since $$$2(b[i]-1) \lt 2i$$$ it is impossible. Alternatively, if $$$a_{2i-1}$$$ is fixed, then there is no choice but for $$$2i = b[i]$$$, which does not satisfy the decreasing condition.

Otherwise, there always exists a solution by satisfying the following construction: If $$$b[i] \gt i$$$ then the fixed point must be the element on the right side of the pair, otherwise it must be the element on the left side of the pair. The rest should be clear if you've understood observations 1-3.

We use divide and conquer, using halfplane partitions passing through points to split the plane into several convex regions. The algorithm is as follows:

• Identify the highest degree point $$$p$$$ in the current set; let the degree of $$$p$$$ be $$$k$$$. Sort all other points by angle around this point. Use angular sweepline to maintain a 180-degree sliding window of points around $$$p$$$. There are $$$N$$$ such windows that matter (one for each line passing through any point and $$$p$$$).
• Let $$$S$$$ be the set of points in the window and $$$k = |S|$$$. Then, if $$$\sum_{s \in S} deg[s] \lt 2k \lt \sum_{s \in S} deg[s] + deg[p]$$$, we can partition the problem along a line passing through $$$p$$$. For now, I claim that a partition satisfying this inequality always exists (*).
  • Subproblem 1: $$$S$$$ plus point $$$p$$$, but in this subproblem assign $$$deg[p] = 2k - \sum_{s \in S} deg[s]$$$
  • Subproblem 2: All remaining points plus point $$$p$$$, but in this subproblem assign $$$deg[p]=\sum_{s\in S}deg[s]+deg[p]-2k$$$.
  • In the sample input, an example of this partition is as follows (given as a list of {node, degree} pairs):
    • $$$(1, 1), (2, 1), (5, 2)$$$
    • $$$(2, 1), (4, 3), (6, 1), (7, 1), (5, 2)$$$.
  • The partition is through node $$$5$$$ which originally has degree 4, and we assign 2 "degrees" to each partition $$$P$$$ so that $$$\sum_{s \in P} deg[s] = 2|P| - 2$$$, and it is possible to make a tree.
• Base case: 2 nodes of degree 1, which we connect with an edge.

This subdivision divides the point set through $$$p$$$ and decides the number of edges connected to $$$p$$$ from either side so that both subdivisions can make a tree. Furthermore, edges from one partition cannot intersect the other because the partitioned regions are convex and disjoint, so the subproblems are independent.

The divide-and-conquer tree is a binary tree with $$$n-1$$$ leaves, so we perform $$$n-1$$$ partition operations. Each partition takes $$$O(n \log n)$$$ time for sorting and $$$O(n)$$$ for sweepline, so overall this algorithm runs in $$$O(n^2 \log n)$$$. time.

Proof of claim (*):

The inequality can be simplified to $$$0 \lt 2k - \sum_{s \in S} deg[s] \lt deg[p]$$$. We can treat $$$2k - \sum_{s \in S} deg[s]$$$ as a periodic function $$$f(\theta)$$$ with respect to the angle of the partition line.

Consider an arbitrary partition line at angle $$$\theta$$$. If $$$0 \lt f(\theta) \lt deg[p]$$$ then we are done, otherwise WLOG suppose that $$$f(\theta) \leq 0$$$. Then, the other partition has $$$N - k - 1$$$ points, and has degree sum $$$2(N - 1) - \sum_{s \in S} deg[s] - deg[p]$$$. Then,

Thus, $$$f(\theta + \pi) \geq deg[p]$$$, so at some point $$$f$$$ crosses over from $$$\leq 0$$$ to $$$\geq deg[p]$$$. Additionally, since $$$deg[p] \geq max_{s \in S} deg[s]$$$, the quantity $$$2k - \sum_{s \in S} deg[s]$$$ can only change by $$$\pm (deg[p] - 2)$$$ between consecutive partitions. The interval $$$0 \lt x \lt deg[p]$$$ has size $$$deg[p]-1$$$, therefore if $$$f$$$ crosses over the interval at some point in $$$(\theta, \theta+\pi)$$$, then some partition must fall within the interval.

Suppose we have a set $$$X = {a_1,\dots,a_k}$$$ satisfying the problem's conditions. Then notice that $$$n - a_i = x^2 \to n-x^2=a_{i}$$$ for some integer $$$x$$$. So you can transform the problem into the following: Given the set of coins

find a subset of size $$$k$$$ such that the sum is $$$n$$$. Since there are at most $$$\sqrt{ n }$$$ coins, this can be solved with knapsack in $$$O(n\sqrt{ n }k)$$$. If implemented efficently, this might pass, however you can optimize the solution to be $$$O\left( \frac{n\sqrt{ n }k}{w} \right)$$$ using bitsets. The dp can be formulated as: $$$dp[i][j]$$$ indicates whether or not you can get to sum $$$i$$$ with a subset of size $$$j$$$. You must also maintain after adding a coin which new sums are possible, which can be implemented using std::bitset's find_first and iterating over newly set bits. Note that reconstructing the answer greedily doesn't work although it might pass.

Counterexample: 3651 4