### dragonslayerintraining's blog

By dragonslayerintraining, 4 months ago, , # 1209A — Paint the Numbers

Author: MikeMirzayanov

Consider the smallest element $x$ in the array. We need to paint it in some color, right?

Observe, that we can paint all elements divisible by $x$ in that color as well.

So we can perform the following while the array is not empty:

• find the minimum element $x$,
• assign new color and remove all elements divisible by $x$

Complexity: $\mathcal{O}(n^2)$.

# 1209B — Koala and Lights

Author: FieryPhoenix

Because each individual light flashes periodically, all the lights together are periodic as well.

Therefore, we can simulate the lights up to the period to get the answer.

The actual period can be calculated as follows:

Spoiler

However, computing the actual period is not necessary and a very large number will work (like $1000$).

Challenge: Can we bound the time even more?

# 1209C — Paint the Digits

Author: MikeMirzayanov

The sequence must split into two non-decreasing where the end of the first $\le$ start of the second.

Let's bruteforce the value $x$, so that all elements $< x$ go to the color $1$, all elements $> x$ go to the color $2$, and for $=x$ we are not sure.

Actually, we can say that all elements equal to $x$, which go before the first element $> x$ сan safely go to the color $2$, while the rest can only go to the color $1$.

So we colored our sequence and we now only need to check whether this coloring is fine.

Complexity is $10 \cdot n$.

# 1209D — Cow and Snacks

Author: FieryPhoenix

Since every animal has exactly two favorite snacks, this hints that we should model the problem as a graph. The nodes are the snacks, and the edges are animals with preferences connecting snack nodes.

Let's consider a connected component of the graph with size greater than $1$. The first animal (edge) in that component to eat must take two snacks (nodes), all other snack nodes will be eaten by exactly one animal edge. It is always possible to find an order so that no other animals takes two snacks (for example, BFS order). Thus, a connected component with $c$ vertices can satisfy at most $c-1$ animals.

Let $N$ be the number of snacks, $M$ be the number of animals, and $C$ be the number of connected components (including those of size 1). The number of satisfied animals is $N-C$, so the number of of unhappy animals is $M-(N-C)$.

Complexity: $\mathcal{O}(n+m)$

# 1209E1 — Rotate Columns (easy version)

Authors: MikeMirzayanov and _kun_

There many approaches possible, let's describe one of them.

Let's change the problem to the following:

• Rotate columns any way you want.
• Select in each row one value, maximizing the sum.

This can be done with a dp, states are (prefix of columns, mask of taken columns). Basically at each step we are rotating the current column and fixing values for some of the rows.

The most simple way to write this makes $3^n \cdot m \cdot n^2$ (for every submask->mask transition iterate over all possible shifts and elements to consider in cost function).

But if we precalculate the cost function in advance, we will have $\mathcal{O}((3^n + 2^n n^2) \cdot m)$.

# 1209E2 — Rotate Columns (hard version)

The previous solution is slightly too slow to pass the large constraints.

Let's sort columns by the maximum element in them. Observe, that it is surely unoptimal to use columns which go after first $n$ columns in sorted order (we could've replaced them with some unused column).

So we can solve the hard version with previous solution in which we consider only best $n$ columns.

Complexity $\mathcal{O}((3^n + 2^n \cdot n^2) \cdot n + T(sort))$

# 1209F — Koala and Notebook

Author: dragonslayerintraining

First split all edges into directed edges with single digit labels, creating $\mathcal{O}(m\log{m})$ dummy vertices if necessary.

Since the first edge will not be zero (no leading zeros), longer paths are always greater. With a BFS, this reduces the problem to finding lexicographical minimal paths in a DAG.

To avoid needing to compare long sequences, we will instead visit all the vertices in order by their lexicographical minimal path. This can be done efficiently by something like BFS/DFS.

The main idea is to visit sets of vertices at a time. If we have a set of vertices whose minimal paths are $P$, we can find the set of vertices whose minimal paths are $P0$ by following all outgoing $0$ edges. Then, we find the set of vertices whose minimal paths are $P1$ by following all outgoing $1$ edges, and so on for all digits. Since we ignore vertices once they are visited, this is $\mathcal{O}(m\log{m})$

# 1209G1 — Into Blocks (easy version)

Author: Errichto

Let's solve easier version first (we will reuse core ideas in hard version as well).

Clearly, if some two integers are hooked'' like in $1 \ldots 2 \ldots 1 \ldots 2$, then they will end up being turned into the same integer.

So when we see integer $x$ with first occurrence at $a$ and last at $b$, let's mark segment $[a; b]$ as blocked. E.g. for array $[3, 3, 1, 2, 1, 2]$ we have not blocked only the bar between $3$ and $1$, that is we have $|3, 3 | 1, 2, 1, 2|$.

Now for every such segment we have to change all elements into a common element. So the answer for a segment is segment length minus the number of occurrences of the most frequent element.

One easy implementation is as follows: blocking is "+= 1 on segment" (can be done easily in $\mathcal{O}{(n + operations)}$ in offline, then for an element $x$, put the number of it's occurrences in the position of first occurrences.

Now we only need to compute max on disjoint segments, so it can be done in a naive way.

Complexity: $\mathcal{O}(n)$.

# 1209G2 — Into Blocks (hard version)

To adjust the solution for many queries we need to create some sophisticated data structure.

E.g. we all know that mentioned above "+= 1 on a segment" is easily done with a segtree. If we maintain for every value $a_i$ the corresponding set of occurrences, it's easy to update mentioned above number of occurrences in the first position''.

So what we need to do now? We need to dynamically recalculate the sum of minimums (and the set segments to calculate minimum can change quite much due to updates).

You probably also now that we can design a segtree which supports range increments and query (minimum, number of minimums) on the segment. In a similar way we can build a structure which returns (minimum, number of minimums, the sum of largest stored counts between minimums). Just maintain a few values in each node and do lazy propagation.

Complexity $\mathcal{O}(q \log n)$.

# 1209H — Moving Walkways

Author: Errichto

Some minor tips:

• Everything is a walkway. When there is no walkway, it is a walkway of speed $0$.
• You can increase all speeds by $1$ and assume that you own speed is in $[-1; +1]$
• Energy is an entity which is $\delta$ speed $\times$ time, which is distance.

Also if you spend $x$ energy per segment of len $l$ and speed $v$, it is not important how exactly you will distribute it over the walking process. In any way, you will walk by feet $l - x$ meters in time $(l - x) / v$.

So it turns out it's better to distribute more energy to low-speeded walkways (because the denominator is smaller).

Assume that you (by default) save up all energy on any non-feet path (for feet path it's always optimal to walk with speed $\ge 1$ ($\ge 0$ after speeds hack), so now save up's).

Build an energy graphic where the Ox axis will correspond to the point you are in (not time). It will be a piecewise linear function, so it is enough to store it's value only in points corresponding to points between walkways. Iterate over walkways in the order of speed and try to steal as much energy as possible to the current walkway.

What are the limits of stealing energy?

• there is a restriction based on $l$ and $v$ (if you take too much energy, you wouldn't be able to fully walk it up)
• the graphic must still be able above $0$ at all points.

The latter condition is just a suffix minima on a segment tree.

Complexity: $\mathcal{O}(n \log n)$.   Comments (89)
 » Auto comment: topic has been updated by dragonslayerintraining (previous revision, new revision, compare).
 » How can we do D with disjoint set union?( As it was tagged in the problem page)
•  » » Happy customers are edges in some spanning forest. Computing the max size spanning forest can be done using a DSU.
•  » » » Can you help me see what's wrong with simply sorting given food preferences as pair ( also keeping minimum in pair as first ) and greedily calculating answer? I understand how people have done graph approach, but don't (yet) see what's wrong in mine.
•  » » Using dsu, every connected component will be in the same group, and then you can calculate C by counting distinct values of dsu[].
•  » » » 4 months ago, # ^ | ← Rev. 5 →   can you explain with some small example(like dry running) how it is working, that would be very helpful
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   For example: 1 2 1 3 2 3After dsu, node 1, 2 and 3 will be in the same connected component. In this component, the first animal must get two nodes(e.g. 1 2). Each of the remaining node in the component can be taken by one edge as there must be at least one edge between a node being taken already and a node that haven't.Therefore for every connect component having X nodes you can fulfill X-1 animals. This leads to the final answer that every connected component causes -1 to the number of happy animals.
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   Thank you very much for explaining , one more thing, then on the basis of this shouldn't answer can be said as (total no. of edges -(sum of no. of edges in a tree of each connected component))
•  » » » » » » Yes, it's the same as number of edge in a tree of each connected component equals node in the component — 1.
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   can't every connected component causes more than -1 as in your example , suppose we add 2 more edge that is new graph is 4 51 21 32 31 43 4here unhappy customers should be 2, correct me if I am wrong
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   For — 1 I mean happy animals = number of node in the component — 1. In your example, the number of node in the component is 4, so the number of happy animals is 3, and the answer is 5 — 3 = 2.
•  » » » » » » » ok got it, Thanks you for discussing it.
•  » »
•  » » During the union of two nodes, if they belong to the same component, we cannot fulfill that request and can increment the answer by 1.It is essentially counting the edges removing which will convert a graph into a forest.See this submission.
•  » » Another simple way of using DSU in Problem D is as follows:Consider the snacks as nodes, which are initially all disconnected. As we get a guest with two snacks, we join them together in a single component of eaten snacks. So a new guest is happy only when his two snacks are not in the same component. To implement this, simply iterate over the given list, and start joining the two snacks of each guest. Increment answer if we find a guest for which the join cannot be performed, as both of his snacks are already in the same component. My implementation of this solution: 60691357
 » One of the best editorials I've seen in the contest I registered In!
 » Why brute force on E1. Rotate Columns (easy version) doesn't work? My implementationWhen n <= m i get the max of each column, then i sort in increasing order, and sum up the last n values. When m < n i just brute force every possible shift of each column.Nice problems : )
•  » » It's totally wrong. I thought same initially ,but then i made a case where 2 max values were in the same column so they will be in different rows. So i tried to take n largest values of the whole array. This would work just fine if the row size was 3 but when the row size is 4 it is not always valid make a case with 4 rows you will get it
•  » » » 4 months ago, # ^ | ← Rev. 2 →   You are correct. The fact that a column can have the same value in different rows completely invalidates my solution. Thank you.
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 6 5 4 0 0 7 0 In this case you can't take top 4 elements 4,5,6,7 as one of them will coincide with some other max.
•  » » If you modeled the problem as a graph, where animals are edges and snacks are nodes, and looked at each connected component with $c_i$ nodes (snacks) individually, you will notice that only one animal will eat $2$ snacks (the $1^{st}$ to eat in the component), and every other snack (node) will be eaten by one animal (edge). Thus, in total $c_i-1$ animals will eat. Summing up over all the connected components gives $N-1*C$ ($C$ is the number of connected components). Subtract this from $M$ to get the number of sad animals.
•  » » 4 months ago, # ^ | ← Rev. 2 →   If you take animals as Edges and snacks as Nodes,then in each connected component of size Ci there will be Ci — 1 guests who will get to eat their favorite snacks as the 1st one will be eating 2 snacks. Therefore , if N is the total snacks and there are x number of connected components then N = Ci + C(i+1) + C(i+2) ... Cx , where Ci is the size of the connected component. Now total no. of guest that can eat their favorite snacks = (Ci — 1) + (C(i+1) — 1) + (C(i+2) — 1)+ ... +(Cx — 1) which can be written as (Ci + C(i+1) + C(i+2) ... Cx — x) , x being the total connected components , which can be further modified as N-x (because N = Ci + C(i+1) + C(i+2) ... Cx) as the total no. of satisfied guests. If M is the no. of guests then total unsatisfied guests are M-(N-x).
•  » » 4 months ago, # ^ | ← Rev. 2 →   We want to minimize the number of snacks which is eaten by same person. So at next step if possible I arranged a person whose one type of snack was already eaten. I used queue for this.
 » In $B$, I think the smallest time unit to which we must process is $120-1+max(b_i-a_i)$ (which is at most $123$).
 » Should the complexity of problem F be $O(m \log m \cdot 10)$?
 » Can someone explain a solution for G1? (Maybe a different method as compared to editorial)
 » 4 months ago, # | ← Rev. 2 →   What the minimum number of columns we need to check in E? I think i have proof of 1/4 * n.
•  » » 4 months ago, # ^ | ← Rev. 2 →   Can you provide us that proof please??.....
•  » » It is n. Think of a matrix like this: 1 1 ... 1 100 1 1 ... 100 1 ... 1 100 ... 1 1 100 1 ... 1 1 
•  » » » You are right. I forgot to say, that I consider only columns with at least two numbers, because then we may for all this columns bruteforce shifts and then greedly set another n maximal numbers among the columns where one maximum. It has the complexity $O(n ^ {n / 4 + 2})$
 » No links for the code :(
 » In problem C) Paint the digits, it says in the condition that *) Each digit is painted either with color 1 or color 2. And in the last second line, it also says that "It is allowed that either of the two colors is not used at all". Can someone explain the significance of this line?
•  » » 4 months ago, # ^ | ← Rev. 2 →   That means if it's possible u can paint the whole string(sequence) in one color. It's not necessary to use both colors. That happens when whole sequence is non- decreasing. ex. 00001111222333356789999 can be painted in 11111111111111111111111 or 22222222222222222222222 or 11111111222222222222222, etc.
 » My alternate solution for E1. Observe that if n is less than equal to 3, you can just pick the 3 maximum elements. Otherwise if it is four, observe that all the selected elements must lie in the top four in their initial row. So lets take all the 16C4 elements and check for validity on each. The maximum that we get now is the answer.
 » 4 months ago, # | ← Rev. 2 →   I used DSU to solve G1, though this technique won't work on G2 because of update queries,For every number in the input, maintain a map for the first occurrence and last occurrence, map start and end. start[a[i]] => starting index of a[i] end[a[i]] => last index of a[i] now take two temp variables, temp_start and temp_end initialized it with, temp_start = start[a] temp_end = end[a] now, iterate throughout the input list and keep expanding the temp_end if a new element is found within the previous range (temp_start, temp_end), else if the next element is outside the range, reinitialize the temp variables, like, temp_start = start[a[i]] temp_end = end[a[i]] finally, for each disjoint set, sort the number of occurrence of each number and counted n — 1 number. (convert n — 1 numbers to the most occurring nth number)https://codeforces.com/contest/1209/submission/60579121
 » Hello. For problem B, we have different starting times. Is there any mathematical formula to calculate the time after which they will repeat all over again, considering their respective starting time?
 » In C you can sort the numbers and try to add numbers greedily.
•  » » What would be your strategy for 9 8 7? Can you explain?
•  » » I did that way. here's the JAVA code : 60567746
 » 4 months ago, # | ← Rev. 2 →   For question C was it clear, that the relative ordering of elements of elements in the same color doesn't matter? It seems that the tutorial says the ordering of elements between those having same color does not matter. If that is so, wouldn't 9 8 7 be colored as 2 2 1 as opposed to not being able to color it at all?
 » can someone explain more explicitly solution outlined for E1?? Thanks in advance.
•  » » Me,too
•  » » dp[i][mask] = maximum value you can get from first i columns such that you have taken maximum from 'mask' rows. Consider i'th col and the 'last_set' of values you can take(which should be the subset of 'mask'). For every rotation see the values which occcur at position present in 'last_set'. This i naive implementation is O(4^n*n^3*m) which passes. But you can improve is by only iterating over subset of a set which is O(3^n).
•  » » » can you explain with some small example(dry run) if possible.
•  » » » 3 months ago, # ^ | ← Rev. 7 →   timeles--S_O--dyssey Can you explain the recursion of the dp[i][mask]? If I understand correctly the solution to the full problem is dp[M][2^N-1] because we want to take the maximum for all rows considering all M columns. Right? So in dp[i][mask] you need to choose a rotation for the i-th column and choose a submask of mask indicating the subset of rows in which the i-th column's values will be maximum. So the recursion for dp[i][mask] involves 2 nested for loops, one over the rotation (0 .. N-1) and one over the submasks (0 .. mask <= 2^N-1), and then iterating over the submask bits to compute the sum, and then the bits of mask which are left (i.e. mask $-$ submask) have to be solved recursively with DP[i-1][mask $-$ submask] correct? . So the complexity would be O(M * 2^N * N * 2^N * N) = O(M * 4^N * N^2), repeated 40 times, right? This would give TLE, how do you improve it to avoid TLE? Can you explain that in detail?
 » However,I'm still not able to understand the solve way written by author.Help!
 » In problem C,"a[i]<=9" is very important.Sadly,I didn't pay attention to it.So I kept thinking of a way of O(n)(Here) ,but I didn't finish it during the contest.I only solved 2 problems...
•  » » I hope my rating will become higher in the round 585.
 » 4 months ago, # | ← Rev. 2 →   We can solve E2 in $O(2^n*n^2)$.Code
•  » » Can you explain to me the E1 solution as I am new to bitmasks?
 » What is the concept behind using string suffix structures in Problem D?
 » Can someone explain E1 and E2 in a better way didn't get the editorial
•  » » I need the same
 » i tried D (div2)/ cow and snacks with this approach https://codeforces.com/contest/1209/submission/60608611what i did is made the vector pair of the favourite snacks of each person( where min(xi,yi) always the first element of each pair) then did sorting on the vector pair after that traversed once from front to count sad people with help of visited array( marked the snacks which are already eaten ) and did same thing from back and took the minimum of the bothplease help me out in this
•  » » Assume that there are two non-decreasing sequences $S1, S2$ consisting of numbers from 0 to 9.let $S1$ be $x1, x2, x3, x4$ etc.. where $x1 <= x2 <= x3 <= x4$ let $S2$ be $y1, y2, y3, y4$ etc.. where $y1 <= y2 <= y3 <= y4$ also assume that last element in $S1$ (in this case $x4$) <= $y1$for some solution to exist, the input string $Z$ must contain both $S1, S2$ in some form where it's possible to construct both $S1$ and $S2$ from sub-sequences of $Z$for example: let $Z = x1, y1, y2, x2, x3, y3, y4, x4$ notice how it's possible to construct both $S1, S2$ from $Z$ if you take the sub-sequences at indices 0, 3, 4, 7 (for $S1$) and 1, 2, 5, 6 (for $S2$)since both sequences $S1$ and $S2$ are sorted and are sub-sequences of $Z$ (only if a solution exists) then it's possible to find a digit $D$ $(0 <= D <= 9)$ using which we can construct $S1$ and $S2$ from $Z$for example: $S1 = 4 6 6 7 , S2 = 7 8 8 9 , Z = 7 4 6 8 6 7 8 9$ using $D = 7$ color every element less than $D$ with 1 and every element greater than $D$ with 2$R = ? 1 1 2 1 ? 2 2$ it makes sense then to color any elements equal to $D$ (that are before the first element with color 2) with color 2 (because we assumed that the input consists of 2 sorted sequences) and the rest of the elements equal to $D$ take color 1 therefore the resulting sequence R = 2 1 1 2 1 1 2 2finally, if $Z$ doesn't conform to the assumptions written above then a solution does not exist.
•  » » » HOW to select that D and what is the first element?Can u please explain that too
•  » » » » you find D using basic brute force (try all values of D from 0 to 9 and check if the resulting sequence is valid) if no values of D result in a valid sequence then there is no solution. What do you mean by "first element"?
•  » » » » » thanks man!!...by referring to your code I got it!....the first element ....(that are before the first element with color 2) ...now I got it ...that by the first element u meant that first biggest element to the selected d in the given string.
 » I don't get G. What's the meaning of 'blocking is "+= 1 on segment"'?
•  » » 4 months ago, # ^ | ← Rev. 3 →   I think it means "+= 1 on $[l,r)$ of a new array".E.g. for array $[3,3,1,2,1,2]$, the new array is $[1,0,1,2,1,0]$.Then we can see that a continuous positive integer segment is a "block".Sorry for my bad English.
•  » » » Thanks. I probably understood it.But this problem is still too difficult for me. :)
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   I think it is not difficult, just a little hard to think of :)
 » We can solve C in o(n) code
 » 4 months ago, # | ← Rev. 2 →   I didn't get the editorial of problem B completely. Could anyone explain why there is also a "pre-period" of 5?
•  » » Initial toggle of a bulb can be at times $1,2,3,4,5$ since input $b$ is $1 \leq b \leq 5$. So starting from time = $5$ (worst case), we have max period of $120$.
•  » » » Thanks, now I get it
 » Can somebody explain me how sorting of the string didn't result to TLE in the C problem ?
 » tbh, I cant get G2. Could anyone explain it in detail?
 » 4 months ago, # | ← Rev. 2 →   Can anyone explain me C solution?
•  » » 4 months ago, # ^ | ← Rev. 3 →   Here is my solution first you should divide the numbers into two sets the first contain all 1 and second contain all 2 to do that you should observe that the largest element in 1 set should be less than or equal to the first or smallest element in the 2 set so you can add an element to 1 set if and only if it's the smallest element in the remaining numbers so make array to store the smallest element in the array in range i+1 to n and check if element i if less than or equal to this element add it to 1 else if it is less than or equal to the last element in 2 set add it to 2 else there is no answer at the end if the the string which contain the answer if it's length is less than n the size of the array then there is no answer the time is O(n) here is the code
 » I got AC with a simpler solution for E1 here: 60699383. The idea comes from the maximum sum would be if you take the 4 maximum elements in the matrix, but you wouldn't always be able to take the maximum 4 elements such as a case like this: 2 2100 1100 1001 11 100 Through trial and error I thought that the number of collisions like these that might force me into taking a smaller element would be low, I stored the indices of the columns in which the 8 maximum elements appear and I bruteforce all possible shifts through these columns. I even tried storing the indices of columns for the 5 maximum elements and it got AC here: 60700309. If someone could provide a proof for this solution or a counter example, it would be appreciated. :)
•  » » 5 elements are not enough.8 will work cause you can always get sum>=a+a+a+a with careful discussion
•  » » » Why can I always get sum >= a + a + a + a?
 » I can't get H :( Could anyone explain it please?
•  » » Sort walkways by speed increasingly. In this order, try to assign as much used energy as possible to every next walkway. That is, it's optimal to quickly walk through slow walkways. Think about $O(n^2)$ solution first. It might help to imagine a graph that shows your current energy. You want to change it in one place (for one walkway) without letting it go below $0$.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   Thank you. I have already understood it. :)I think this problem is very nice!
 » Why in problem F, in the second test case, the answer for city 3 is 12 instead of 1.12 implies 1 -> 2 -> 3 then it costs 1231 implies 1 -> 3 then it costs 13I think I don't understand this problem. If someone can explain to me what I am not understanding, I would appreciate it.
•  » » It will concatenate the edge ids.1->2->3 is 12(edge 1 and edge 2).1->3 is 13(edge 13).
•  » » » thank you very much, I thought that the identifier of an edge was the union of its ends but in reality it is the index of the edge
 » any o(N) solution for problem c?
•  » » see that
 » I tried to implement problem D using bfs but I keep getting TLE on case 23. Can somebody help me with this? Here's my code: https://codeforces.com/contest/1209/submission/60944190.
•  » » Mark nodes as visited when you put them into the queue, as opposed to when you take them out. Otherwise, you could have duplicates in your queue which increases the runtime drastically in some dense graphs.
 » In my opinion, E1 is hardest part of E2 problem lol..I managed to solve the E2 part on my on (bound on columns that matter), but I still dont understand E1 dp.
 » Trying to understand the G2 tutorial right now, but I don't get what the statement "blocking is segment +=1" means, would appreciate some help!
 » I was solving the problem E1 using simple DP, for each i from 1 to col, find the the max answer(col containing the maximum values for each row) which we will get after all possible rotation of ith column, i got WA. The part which is missing in my solution is, i am always doing this in a order of 1 to m, whereas in the editorial they are using mask for the order. I am unable to think of a counter example for my solution. WHY DO WE NEED MASK? WHY CAN'T WE JUST SOLVE IT GOING FROM COLUMN 1 TO m? please help.
 » 4 hours ago, # | ← Rev. 2 →   Problem D using DSU:Maintain a deque of pair of snacks, for printing optimal answer. Consider each disjoint set as those snacks which are already being eaten. Now consider ith favourites (0