Solution of Codeforces Round #831 (Div. 1 + Div. 2) || Tutorial of Codeforces Round #831 (Div. 1 + Div. 2)

Solution of Codeforces Round #831 (Div. 1 + Div. 2) || Tutorial of Codeforces Round #831 (Div. 1 + Div. 2)

Codeforces Round #831 (Div. 1 + Div. 2, based on COMPFEST 14 Final) Editorial

1740A. Factorise N+M

Author: Pyqe
Developer: Pyqe

Tutorial

1740A - Factorise N+M

There are multiple solutions for this problem. We will discuss two of them.

One solution is to choose m=n$m=n$. This always guarantees that m$m$ is prime, because n$n$ is always prime. And we can see that n+m=n+n=2n$n+m=n+n=2n$, which is always not prime, because n>1$n>1$ always holds.

Another solution is to choose m=7$m=7$. If n$n$ is odd, then n+m$n+m$ will be an even number greater than 2$2$ and therefore not prime. Otherwise n$n$ is even. The only even number prime number is 2$2$ and it can be verified that 2+7=9$2+7=9$ is not a prime number.

Time complexity for each test case: O(1)$O(1)$

1740B. Jumbo Extra Cheese 2

Author: Pyqe
Developer: errorgorn, Pyqe

Tutorial

1740B - Jumbo Extra Cheese 2

Consider arranging the rectangles such that the i$i$-th rectangle from the left has width ai$a_i$ and height bi$b_i$. The perimeter of the connected figure will be 2(a1+a2+…+an)+b1+|b1−b2|+|b2−b3|+…+|bn−1−bn|+bn$2(a_1+a_2+\dots +a_n)+b_1+|b_1-b_2|+|b_2-b_3|+\dots +|b_{n-1}-b_n|+b_n$.

Notice that if we sort the rectangles based on bi$b_i$, the cost would become 2(a1+a2+…+an+bn)$2(a_1+a_2+\dots +a_n+b_n)$, which is the minimum possible perimeter if we cannot rotate the rectangles. This means, if we have a fixed configuration of the orientations of the rectangles, we can always permute the rectangles such that the perimeter is 2(a1+a2+…+an+max(b))$2(a_1+a_2+\dots +a_n+max(b))$.

We need to find an orientation configuration that results in the minimum value of 2(a1+a2+…+an+max(b))$2(a_1+a_2+\dots +a_n+max(b))$. We can observe that it is always more optimal to orient them such that ai≤bi$a_i\le b_i$.

Therefore, the solution is to orient the rectangles to satisfy ai≤bi$a_i\le b_i$, then the answer is 2(a1+a2+…+an+max(b))$2(a_1+a_2+\dots +a_n+max(b))$.

Time complexity for each test case: O(n)$O(n)$

1740C. Bricks and Bags

Author: Pyqe
Developer: Pyqe

Tutorial

1740C - Bricks and Bags

Firstly, sort a$a$. From now on, we will always refer to the sorted array a$a$.

Let pj$p_j$ be the index of the brick taken by Bu Dengklek from bag j$j$. We can obtain that Bu Dengklek will always take the bricks such that the configuration of p1,p2,p3$p_1,p_2,p_3$ is in the form of one of the following:

1. p1<p2<p3$p_1<p_2<p_3$
2. p1>p2>p3$p_1>p_2>p_3$
3. p2<min(p1,p3)$p_2<min(p_1,p_3)$ and min(p1,p3)=p2+1$min(p_1,p_3)=p_2+1$
4. p2>max(p1,p3)$p_2>max(p_1,p_3)$ and max(p1,p3)=p2−1$max(p_1,p_3)=p_2-1$

In fact, Pak Chanek is always able to force it such that the bricks taken by Bu Dengklek form any configuration of p1,p2,p3$p_1,p_2,p_3$ that follows one of the constraints above. Therefore, we just need to find the values of p1,p2,p3$p_1,p_2,p_3$ satisfying the constraints above such that |ap1−ap2|+|ap2−ap3|$|a_{p_1}-a_{p_2}|+|a_{p_2}-a_{p_3}|$ is maximised.

To maximise the final score, we can see that it is always more optimal to either use the third or the fourth case for p1,p2,p3$p_1,p_2,p_3$. For the third case, it is always more optimal to maximise max(p1,p3)$max(p_1,p_3)$, so we should set max(p1,p3)=n$max(p_1,p_3)=n$. A similar logic can be used for the fourth case to see that we should set min(p1,p3)=1$min(p_1,p_3)=1$.

Therefore, the maximum final score is the maximum of these two cases:

• (ai−ai−1)+(ai−a1)$(a_i-a_{i-1})+(a_i-a_1)$ with 3≤i≤n$3\le i\le n$.
• (ai+1−ai)+(an−ai)$(a_{i+1}-a_i)+(a_n-a_i)$ with 1≤i≤n−2$1\le i\le n-2$.

Time complexity for each test case: O(nlogn)$O(n\log n)$

1740D. Knowledge Cards

Author: Nyse
Developer: steven.novaryo

Tutorial

1740D - Knowledge Cards

Let card c$c$ be the card with number c$c$ written on it. Notice that we must put the cards into the stack in (n,m)$(n,m)$ in order from card k$k$, card k−1$k-1$, card k−2$k-2$, and so on until card 1$1$.

The key observation for this problem is that, under given constraints, if we ignore cells (1,1)$(1,1)$ and (n,m)$(n,m)$ we can always move any card to any location if there is at least one empty cell. We can obtain this by considering the fact that an empty cell can "move" to any cell and can be used to rotate any 2×2$2\times 2$ square of cells. Because 3≤n,m$3\le n,m$, if we ignore cells (1,1)$(1,1)$ and (n,m)$(n,m)$, each cell is a part of a 2×2$2\times 2$ square.

Therefore we can iterate the card in the stack (1,1)$(1,1)$ from top to bottom. While iterating, one should maintain all of the cards in the board that are not in cell (1,1)$(1,1)$ or (n,m)$(n,m)$. We define those group of cards as active cards. Each time we put a move a card out of (1,1)$(1,1)$, we add the card to the active cards. Before finishing the iteration we will try to move one or more cards from the active cards to (n,m)$(n,m)$ as long as there is a card we can move. We can maintain the active cards with a priority queue or a set.

The active cards can be moved around freely if and only if there is at least one empty cell in the grid if we ignore (1,1)$(1,1)$ and (n,m)$(n,m)$. Therefore, to check whether or not we can solve the puzzle, we just need to check whether or not there exists a moment where the number of active cards exceed nm−3$nm-3$.

Time complexity for each test case: O(klogk)$O(k\log k)$

1740E. Hanging Hearts

Author: Pyqe
Developer: Zappeko

Tutorial

1740E - Hanging Hearts

We define card x$x$ to be dangling onto card y$y$ if there exists a sequence [v1,v2,…,vk]$[v_1,v_2,\dots ,v_k]$ such that v1=x$v_1=x$, vk=y$v_k=y$, and pvi=vi+1$p_{v_i}=v_{i+1}$ for all 1≤i<k$1\le i<k$. We also let dist(x,y)=k$dist(x,y)=k$ explained above. Let Di$D_i$ be the set of cards such that j∈Di$j\in D_i$ if and only if card j$j$ dangles onto card i$i$.

Let wi$w_i$ be the number on card i$i$ when it is about to get removed. To remove card i$i$, we must initially remove all cards j$j$ that are dangling onto card i$i$. Thus, we can see that wi=min(ai,minj∈Di(aj))$w_i=min(a_i,\underset{j\in D_i}{min}(a_j))$. Hence, it does not break the optimality of a solution if ai>maxj∈Di(aj)$a_i>\underset{j\in D_i}{max}(a_j)$.

In the optimal configuration, the elements of the longest non-decreasing subsequence in S$S$ comes from a sequence of cards that resembles the following:

• It consists of several sequences of cards in the form of [v1,v2,…,vk]$[v_1,v_2,\dots ,v_k]$ such that pvi=vi+1$p_{v_i}=v_{i+1}$ for all 1≤i<k$1\le i<k$.
• For any pair of cards from two different sequences, one must not be dangling onto the other.

We will use dynamic programming on tree. Let dp[i]$dp[i]$ denote the length of the longest non-decreasing subsequence created from only doing operations to card i$i$ and all other cards dangling onto card i$i$. Then, we have two cases:

• If card i$i$ is used in the longest non-decreasing subsequence, then the maximum answer is the maximum value of dist(j,i)$dist(j,i)$ for all j∈Di$j\in D_i$.
• If card i$i$ is not used in the longest non-decreasing subsequence, then the maximum answer is the sum of dp$dp$ values of all cards j$j$ directly hanging onto i$i$ (i.e. pj=i$p_j=i$).

Time complexity: O(n)$O(n)$

1740F. Conditional Mix

Author: Pyqe
Developer: errorgorn

Tutorial

1740F - Conditional Mix

Let cnti$cn{t}_i$ denote the number of occurrences of element i$i$ in array a$a$.

We can obtain that a multiset M$M$ of size n$n$, M1,M2,…,Mn$M_1,M_2,\dots ,M_n$ where M1≥M2≥…≥Mn≥0$M_1\ge M_2\ge \dots \ge M_n\ge 0$ is good if and only if ∑ni=1Mi=n$\sum _{i=1}^n{M}_i=n$ and ∑ki=1Mi≤∑ni=1min(k,cnti)$\sum _{i=1}^k{M}_i\le \sum _{i=1}^{n}min(k,cn{t}_i)$ for every 1≤k≤n$1\le k\le n$.

We proceed with formulating a dynamic programming solution. Let dp[pos][sum][last]$dp[pos][sum][last]$ denote that we have picked a prefix P1,P2,…,Ppos$P_1,P_2,\dots ,P_{pos}$ such that ∑posi=1Pi=sum$\sum _{i=1}^{pos}{P}_i=sum$ and Ppos=last$P_{pos}=last$. Our transition is going from dp[pos][sum][last]$dp[pos][sum][last]$ to dp[pos+1][sum+x][x]$dp[pos+1][sum+x][x]$ for all x≤last$x\le last$, this can be easily handled using prefix sums. However, we still have O(n3)$O(n^3)$ states.

We can cut down the number of states by noting that n≥∑posi=1Pi≥last⋅pos$n\ge \sum _{i=1}^{pos}{P}_i\ge last\cdot pos$. That is, for each value of pos$pos$, there are only npos$\frac{n}{pos}$ values of last$last$. Since n1+n2+n3+…+nn≈nlogn$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\dots +\frac{n}{n}\approx n\log n$, the number of states is bounded by O(n2logn)$O(n^2\log n)$.

Time complexity: O(n2logn)$O(n^2\log n)$

1740G. Dangerous Laser Power

Author: Pyqe
Developer: Pyqe

Tutorial

1740G - Dangerous Laser Power

Claim: There is a construction where all portals are good.

We will proceed with the construction.

The key observation of the problem is that for a portal (i,j)$(i,j)$ to consume energy, the laser must not enter a portal with a strength greater than or equal to si,j$s_{i,j}$ before going through portal (i,j)$(i,j)$.

Let's say we already have the type settings of all lasers. Consider all possible lasers that at some point enters a certain face of portal (i,j)$(i,j)$. We can find the paths of those lasers before entering portal (i,j)$(i,j)$ by backtracking in that direction from portal (i,j)$(i,j)$.

Consider the first portal in that backtracking path that has a strength greater than or equal to si,j$s_{i,j}$. Notice that all lasers that starts from portals that are located after that portal in the backtracking path must go through that portal before entering portal (i,j)$(i,j)$. Therefore, those lasers cannot make portal (i,j)$(i,j)$ use energy, which means they can be ignored.

Using the observation above, we can see that we must only backtrack until we find a portal with a strength greater than or equal to si,j$s_{i,j}$. Observe that to get the path up to that point, the type settings we should know are only the type settings of portals with strengths smaller than si,j$s_{i,j}$.

Therefore, the construction can be generated by calculating the type settings of the portals from the smallest to the largest strengths. In each iteration, we use the type settings of the previous portals to find the backtracking paths of the current portal. If we already know the 4$4$ backtracking paths for each of the 4$4$ directions of that portal, we can find the total energy that portal will consume in the end, which means we can find the type setting for that portal that makes it a good portal.

The naive implementation of this has a time complexity of O(n2m2)$O(n^2{m}^2)$. Notice that each backtracking path of the portals are just the merging of smaller paths. We can maintain a disjoint set data structure to handle this while maintaining the essential values needed in the calculation of the total energy consumed for each path.

Time complexity: O(nm)$O(nm)$

1740H. MEX Tree Manipulation

Author: steven.novaryo
Developer: steven.novaryo, Pyqe

Tutorial

1740H - MEX Tree Manipulation

Define MEXi(A)${\text{MEX}}_i(A)$ of a certain array A$A$ as the i$i$-th smallest non-negative integer that does not belong to the array.

Let's solve a simpler problem. Imagine that you are given an array A$A$, you are asked to append a new element x$x$ to the array, and you need to calculate the MEX of the array after the operation. It is easy to see that the new value of MEX is either MEX1(A)${\text{MEX}}_1(A)$ if x≠MEX1(A)$x\ne {\text{MEX}}_1(A)$ or MEX2(A)${\text{MEX}}_2(A)$ if x=MEX1(A)$x={\text{MEX}}_1(A)$ where A$A$ is the array before the operation.

Let (x,y,z)$(x,y,z)$ define a relationship between input and output which means:

• If the input is not x$x$, then the output is y$y$.
• If the input is x$x$, then the output is z$z$.

This means the relationship between the new element to be appended to A$A$ and the new value of MEX can be expressed as (MEX1(A),MEX1(A),MEX2(A))$({\text{MEX}}_1(A),{\text{MEX}}_1(A),{\text{MEX}}_2(A))$. Define that triple as MEXtuple(A)$\text{MEXtuple}(A)$.

Define the heavy child of vertex u$u$ as the child with the largest subtree size. If there are children with the same subtree size, choose one of them. Let's call each child other than the heavy child as a light child. In particular, the edge that connects a vertex to its heavy child is called a heavy edge.

Let Cu$C_u$ be the array that contains the values of the light children of vertex u$u$. We can see that if we maintain MEXtuple(Cu)$\text{MEXtuple}(C_u)$ we can get the relationship between the value of the heavy child and the value of vertex u$u$.

Let's consider a path in the tree that traverses through parents while only using heavy edges. Consider the relationship between the value of the vertex at the beginning of the path and the end of the path. Let's calculate the MEXtuple$\text{MEXtuple}$ for each vertex in the path other than the first one. We can see that we can get the relationship between the vertex in the beginning of the path and the end of the path using those MEXtuple$\text{MEXtuple}$ values. In fact, that relationship can also be expressed as a triple (x,y,z)$(x,y,z)$ defined above.

Let's decompose the tree into chains of heavy edges. For each chain, construct a segment tree with each node in the segment tree calculating the relationship triple (x,y,z)$(x,y,z)$ for a segment of the chain.

Suppose we want to add a new vertex. The vertices that have their values changed are the ones that lie on the path from the new vertex to the root. Observe that that path only traverses through at most O(logQ)$O(\log Q)$ different heavy edge chains. For each chain, we can get the value of the vertex at the end of the chain by doing a point update on the chain's segment tree. When we move between two different chains, we update the Cu$C_u$ for a vertex and recalculate it's MEXtuple$\text{MEXtuple}$ in O(logQ)$O(\log Q)$ time complexity using a set or another segment tree. We repeat this process until we reach the root. We can calculate that the total complexity of a single query is O(log2Q)$O({\log }^{2}Q)$.

To get the sum of the values of the entire tree after an operation, we can store two new variables in each node of the segment tree of each chain that represents the sum of the chain segment for the two possible cases of the input.

Time complexity: O(Qlog2Q)$O(Q{\log }^{2}Q)$

1740I. Arranging Crystal Balls

Author: NeoZap
Developer: errorgorn, Pyqe

Tutorial

1740I - Arranging Crystal Balls

Let's simplify the problem such that the only possible operation for each k$k$ chosen statues is ai:=(ai−1)modm$a_i:=(a_i-1)modm$.

To solve this, we first define ci$c_i$ as the number of times we do that operation for the statues i,(i−1)modn,(i−2)modn,(i−3)modn,…,(i−k+1)modn$i,(i-1)modn,(i-2)modn,(i-3)modn,\dots ,(i-k+1)modn$. We can see that in the optimal configuration, 0≤ci≤m−1$0\le c_i\le m-1$ must hold. For it to make each element of a$a$ to be 0$0$, (ci+c(i+1)modn+c(i+2)modn+…+c(i+k−1)modn)modm=ai$(c_i+c_{(i+1)modn}+c_{(i+2)modn}+\dots +c_{(i+k-1)modn})modm=a_i$ must hold. The number of operations is equal to c0+c1+c2+…+cn−1$c_0+c_1+c_2+\dots +c_{n-1}$.

In order to extend to the original problem, we can see that for a given array c$c$, the number of operations that can be made to be equal to ∑n−1i=0min(ci,m−ci)$\sum _{i=0}^{n-1}min(c_i,m-c_i)$. So we need to find an array c$c$ satisfying the conditions above such that ∑n−1i=0min(ci,m−ci)$\sum _{i=0}^{n-1}min(c_i,m-c_i)$ is as small as possible.

We can see that a(i+1)modn−ai=c(i+k)modn−ci$a_{(i+1)modn}-a_i=c_{(i+k)modn}-c_i$. That means, if we have determined the value of ci$c_i$, the value of c(i+k)modn$c_{(i+k)modn}$ is forced. If we form an edge for each pair of indices (i,(i+k)modn)$(i,(i+k)modn)$, we will get GCD(n,k)$\text{GCD}(n,k)$ connected components. This means if we have determined the value of one vertex for each connected component, the values of the entire array c$c$ are forced. However, we must also consider possibility that at least one connected component cannot have assigned values that satisfy all of its edges. In that case, it is impossible to finish the objective of the problem.

Define d=GCD(n,k)$d=\text{GCD}(n,k)$. For each ci$c_i$, we can find the difference relationship between it and cimodd$c_{imodd}$. Therefore, to answer the problem, we must find the values of c0,c1,c2,…,cd−1$c_0,c_1,c_2,\dots ,c_{d-1}$ such that c0+c1+c2+…+ck−1=a0$c_0+c_1+c_2+\dots +c_{k-1}=a_0$ and if all the other values of c$c$ are calculated, ∑n−1i=0min(ci,m−ci)$\sum _{i=0}^{n-1}min(c_i,m-c_i)$ is as small as possible.

For the c0+c1+c2+…+ck−1=a0$c_0+c_1+c_2+\dots +c_{k-1}=a_0$ condition, using simple modular algebra, we can calculate one or more values b1,b2,b3,…$b_1,b_2,b_3,\dots$ such that c0+c1+c2+…+ck−1=a0$c_0+c_1+c_2+\dots +c_{k-1}=a_0$ if and only if c0+c1+c2+…+cd−1$c_0+c_1+c_2+\dots +c_{d-1}$ is equal to one of the values of b$b$.

Let's consider the connected component ci,ci+d,ci+2d,…$c_i,c_{i+d},c_{i+2d},\dots$. It must have nd$\frac{n}{d}$ elements. Define fi(x)$f_i(x)$ as the sum of min(cj,m−cj)$min(c_j,m-c_j)$ for all elements of cj$c_j$ in that connected component if ci=x$c_i=x$. We can easily calculate all values of fi(x)$f_i(x)$ for all connected components in O(nm)$O(nm)$.

After this, we must the minimum value of f0(c0)+f1(c1)+f2(c2)+…+fd−1(cd−1)$f_0(c_0)+f_1(c_1)+f_2(c_2)+\dots +f_{d-1}(c_{d-1})$ such that c0+c1+c2+…+cd−1$c_0+c_1+c_2+\dots +c_{d-1}$ is equal to one of the values of b$b$. This can be solved using modular knapsack dynamic programming, but the time complexity is O(nm2)$O(n{m}^2)$. We must optimise it further.

Consider the contribution of a single element cj$c_j$ to the values of fi(x)$f_i(x)$ of its connected component. Let's say the difference relationship is that ci−cj=w$c_i-c_j=w$ must hold. Notice that:

• It adds (x−w)modm$(x-w)modm$ to all values of fi(x)$f_i(x)$ for each x$x$ going up modularly from w$w$ to (w+⌊m2⌋)modm$(w+\lfloor \frac{m}{2}\rfloor )modm$
• It adds (w−x)modm$(w-x)modm$ to all values of fi(x)$f_i(x)$ for each x$x$ going up modularly from (w+⌈m2⌉)modm$(w+\lceil \frac{m}{2}\rceil )modm$ to w$w$.

We can see it as "changing slope" at most three times, namely in x=w$x=w$, x=(w+⌊m2⌋)modm$x=(w+\lfloor \frac{m}{2}\rfloor )modm$, and x=(w+⌈m2⌉)modm$x=(w+\lceil \frac{m}{2}\rceil )modm$.

This means, if we add up all contributions of each element, the number of points the slope changes in one connected component is at most 3nd$\frac{3n}{d}$. We will call these points as special points.

Consider an array c0,c1,c2,…,cd−1$c_0,c_1,c_2,\dots ,c_{d-1}$ satisfying the condition that c0+c1+c2+…+cd−1$c_0+c_1+c_2+\dots +c_{d-1}$ is equal to one of the values of b$b$. Consider the case if there exists at least two different indices i$i$ such that the value of ci$c_i$ is not a special point in fi$f_i$. Suppose the indices are i1$i_1$ and i2$i_2$. Since both of them are not special points, the slope between (ci1−1)modm$(c_{i_1}-1)modm$ and ci1$c_{i_1}$ is the same as the slope between ci1$c_{i_1}$ and (ci1+1)modm$(c_{i_1}+1)modm$. The same is true for i2$i_2$. Let's say z1$z_1$ is the increase in value of the final answer if we do ci1:=(ci1+1)modm$c_{i_1}:=(c_{i_1}+1)modm$ and ci2:=(ci2−1)modm$c_{i_2}:=(c_{i_2}-1)modm$, and z2$z_2$ is the increase in value of the final answer if we do ci1:=(ci1−1)modm$c_{i_1}:=(c_{i_1}-1)modm$ and ci2:=(ci2+1)modm$c_{i_2}:=(c_{i_2}+1)modm$. From the observation above, we can see that z1=−z2$z_1=-z_2$, which means one of them is non-positive. This means, if this is the case, we can always change the array c$c$ into another array with an equal or smaller final answer.

This means, we can always do that operation to get an array c$c$ such that there is at most one non-special point. Therefore, we can just consider those cases to find the minimum answer.

We can solve this using divide and conquer. We first call the recursive function dnc(0,d−1)$\text{dnc}(0,d-1)$. The moment we call the function dnc(l,r)$\text{dnc}(l,r)$, we have made the modular knapsack dynamic programming array if we have only considered the indices i$i$ with i<l$i<l$ or r<i$r<i$ and only considering their special points. dnc(l,r)$\text{dnc}(l,r)$ recurses into dnc(l,l+r2)$\text{dnc}(l,\frac{l+r}{2})$ and dnc(l+r2+1,r)$\text{dnc}(\frac{l+r}{2}+1,r)$. Once l=r$l=r$, we will consider that index as the one that can have a non-special point, then we can just iterate the array b$b$ and take the answer from the knapsack array.

The depth of the recursion is at most O(logd)$O(\log d)$. Each depth has insertions of O(d)$O(d)$ indices to the knapsack. Because each connected component only has O(nd)$O(\frac{n}{d})$ special points, each depth does O(n)$O(n)$ dynamic programming transitions with each transition having O(m)$O(m)$ time complexity.

Time complexity: O(nmlog(GCD(n,k)))$O(nm\log (\text{GCD}(n,k)))$

 Tutorial of Codeforces Round #831 (Div. 1 + Div. 2)