### Problem 189A — Cut Ribbon

The problem is to maximize *x+y+z* subject to *ax+by+cz=n*. Constraints are low, so simply iterate over two variables (say *x* and *y*) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions.

Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be *a*, *b* or *c*.

### Problem 189B — Counting Rhombi

Observe that lots of rhombi have the same shape, but are in different locations.

What uniquely determines the shape of a rhombus? Its width and its height.

Is it possible to build a rhombus with every width and every height such that the vertices of the rhombus are in integer points? No, it is possible only if the width and the height are both even.

How many places we can put a rhombus of width *w0* and height *h0* in a rectangle of width *w* and height *h*? *(w * w0 + 1)(h * h0 + 1)*

So, iterator over all even widths and heights and for each of them add the number of possible locations to the final result.

### Problem 187A — Permutations

It is easy to see that if we replace each number in the first permutation with position of that number in the second permutation, the problem reduces to sorting the first permutation.

Each time we take a number from the end of array, we can postpone its insertion until we know the most suitable position for insertion. Note that it is not good to insert a number and take it again, as we could make a better decision first time we took the number.

So, as long as the remainder of the array is not in increasing order, we should take more numbers from the end. But as soon as you have an increasing subsequence, you can insert the numbers you have taken to make the array sorted.

Therefore to solve the problem, we find the largest *i* such the numbers from *1* to *i* are in increasing order. The answer would be *n-i*.

### Problem 187B — AlgoRace

First we solve the problem when the number of allowed car changes is zero (_k=0_). Let *W(i,j,l)* be the length of shortest path from *i* to *j* with car *l*. We use Floyd-Warshal on graph of each car to find this value. Then answer for the case that we can use only one car for each pair of cities *i* and *j* is:

*ans(0,i,j) = min W(i,j,l)* for (_1≤l≤m_)

This part has time complexity *O(m*n^3)*.

For larger values of maximum number of changes (_k_), we use the following equation:

*ans(k,i,j) = min (ans(k-1,i,l)+ans(0,l,j))* for (_1≤l≤k_)

which can be computed in *O(k*n^3)* using dynamic programming.

But how large can be *k* in worst case? We know that shortest paths are simple paths (i.e. they have no repeated vertices). Because otherwise we could eliminate the path we go between two appearances of one vertex and have a smaller result. This and the fact that we change the car at most once in each vertex, guarantees in any optimal solution we will not need more that *n* car changes. Thus the order of the solution would be *O(m*n^3+n^4)*.

### Problem 187C — Weak Memory

There were many different correct approaches to this problem during the contest. But I will explain author’s solution.

First we can use binary search over the value of *q*. Now for a fixed *q* we want to check *s-t* connectivity.

Let *K* be the set of all intersections with volunteers union s and t. One can use BFS from each *k∈K*, one by one. Then build a graph *G’* with vertices *K*. For each two vertices *k1,k2∈K* add an edge between them, if their shortest distance is less than or equal to *q*. Finally use any path finding algorithm to check the connectivity. Unfortunately this solution has time (and space) complexity of *O(|K|*m)* which is not good enough.

We can optimize the above solution by initiating BFS from all *k∈K* at once. In other words during the initialization step in BFS algorithm, we push all these vertices in the queue with distance *0*. Each element in the queue also maintains its source (i.e. the source it is originating from). In BFS each time we have have a vertex *u* with source *su* and we want to set the minimum distance to a vertex *v* that is already set from a different path with source *sv*, we connect *su* and *sv* in *G’* if *d(u)+d(v)+1<= q*, where *d(x)* denotes length of the shortest path from a vertex in *K* to *x*. As we are only dealing with connectivity, this approach is correct. (Proof of correctness is left as an exercise)

BFS takes *O(m)* time and we add at most *O(m)* edges to *G’*, so the overall complexity is *O(m)* for a fixed *q*. As we used binary search to find the smallest *q*, we can solve the problem in *O(m*logn)*.

### Problem 187D — BRT Contract

We define *ti* as follows: assume a bus starts moving from *i*-th intersection exactly at the time when the light changes to green. The time it takes for the bus to get the final station is *ti*. We call the times when a green interval begins *t0* (so every *g+r* seconds *t0* occurs once)

If a bus gets to *i*-th intersection during the red phase, it should wait and then start moving at *t0*. So considering the fact that all lights are synchronized (and length of segments are fixed) if we have *ti* for *i*-th intersection, we can compute the time for the bus to get final station.

Clearly *tn* is the length of the last segments. For computing *ti* we should find the smallest *j* such that if a bus starts at *t0* from *i*-th intersection, it gets to *j*-th intersection during the red phase. So we have:

*ti=tj+d(i,j)+w*

where *d(i,j)* is the distance between *i*-th and *j*-th intersections and *w* is the time that the bus should wait behind the red light at *j*-th intersection. The later value can be computed easily.

The only problem that remains is to find *j* for *i*-th intersection. So we start iterating over *i* for *(n-1)*-th intersection backwards and we compute *ti* for all intersections. Assume *p=g+r* and *ta=d(i,j)%p*. Now if the bus starts from *i*-th intersection at time *t0* and we have *ta>=g*, in this case we are in red phase at *j*-th intersection. Actually *ta* should be in interval [_g, g+r_).

Here we can use segment trees. That is for all intersections from *i+1* to *n*, we store some values in the tree that helps us find the smallest *j*. But we should note the value of *ta* depends on *d(i,j)* which changes as *i* changes. Thus we cannot use *ta* in the tree. Instead, we define *si* the be the distance of *i*-th intersection to the destination. So we have *d(i,j)=si-sj* and we use the value of *sj* with storing *–sj%p* in the segment tree as the key and the value would be *j* itself. In other words for each intersection we store the key-value pair *(-sj%p, j)* in the tree. According to what we said so far, to be in the red phase at *j*-th intersection we should have:

*ta=(d(i,j)%p)=((si-sj)%p)∈[g,g+r) => -sj%p ∈ [(g-si)%p, (g+r-si)%p)*

As we stored *–sj%p* in the tree, we can retrieve the smallest *j* in the above interval with a query in the segment tree.

This way we can compute *ti* for all intersections. Answering to each query in the problem can be solve in exactly the same way. So the overall complexity would be *O((n+q)logn)*.

### Problem 187E — Heaven Tour

**Step 1**. Solve the problem if the starting man is the leftmost man and the finishing man is the rightmost man.

Obviously every segment (the distance between two consecutive men) should be covered at least once. We also argue that at least *l* (the number of left tickets) segments should be covered at least three times.

*Proof*: Each time you use a left ticket to go to man *i* with *1<i<n-1*, the segment between *i*-th and (_i+1_)-th men is covered at least three times:

- Once for you should go after
*i*be in a position to come back. - Once for you use a left ticked to come back to
*i* - And once again you should go after
*i*, because you want to finish at man number*n*

Note that in the first and the last segments are always covered once, no matter what we do. But except for these two segments, every other segment can be chosen to be among the segments that are covered three times, and every combination that we choose *l* segments is feasible. (Proof it as practice) So we choose the smallest *l* segments and the problem can be solved with a simple sort in *O(n*logn)*.

**Step 2**. Solve the problem if the starting man is the leftmost man, but the finishing man can be anywhere.

To solve this problem we first fix the finishing man. With reasoning similar to that of step 1, we conclude that at least *l* segments should be covered with at least two times if they are after the finishing man or three times if they are before him. But obviously every segment after the finishing man is covered at least two times. So it is always good to waste as many left tickets as possible after the finishing man to prevent them from breaching the left side of finishing man and becoming multiple three.

So the algorithm would be: iterate over *i*, the number of finishing man, and maintain the *l-(n-i)* smallest segments to the right of finishing man as you progress. This can be implemented in *O(n*logn)*.

**Step 3**. Solve the problem if the starting man is fixed, but the finishing man can be anywhere.

Assume that the starting man is not the first man or the last man, otherwise we could use algorithm of step 2 to solve the problem. Without loss of generality assume that you finish your tour to the right side of finishing man. Therefore every segment to the left of starting man is covered at least two times and actually it is always possible to arrange visits such that every segment to right is covered exactly two times. So just like what we said in step 2, it is good to waste as many left tickets as possible in this area.

So the algorithm would be, choose to finish left or right first, then greedily waste as many bad moves (by bad moves I mean the moves that if breach to the other side will be more costly) as possible there and follow the algorithm in step 2 to solve the whole problem.

There are some special cases such as when the tour cannot be finished at all, that we left to readers find a way how to handle them.

Can anyone explain the idea for 187A in a better way? It seems to me the given solution is independent of the permutation of the second string.. How is that possible?

Thanks a lot.

UPD: I got it.. I had misunderstood the editorial's language.

I think there is something wrong with the explanation of problem B. Counting Rhombi the equation (w * w0 + 1)(h * h0 + 1) doesn't make any sense. I think the right equation should be (w — w0 + 1)(h — h0 + 1)

yes what you are saying is correct, thanks.

I am getting an error in the following code : I am trying to solve the cut ribbon problem by dp

can you pls explain the code ,i have started trying dp quetions ,i don't have any idea how to solve this ques ?

Can someone explain dp solution to 189A?

This might be helpful.

This was a great solution. Can you tell me how did you get the idea?

Cool... Thanks a lot for sharing.

anukul Please explain your solution.

## include<bits/stdc++.h>

using namespace std;

int n,a,b,c,mem[5000]; int solve(int remain=n) { if(remain==0) return 0; if((remain<a&&remain<b&&remain<c)||remain<0) return -100005;

}

int main() { memset(mem,-1,sizeof mem); cin>>n>>a>>b>>c; cout<<solve();

}

Top down easy to understand https://ideone.com/LZEfQE

this is modified version of coin change II(min. no. of coins) to make sum.

-->>[ MY WORKING SOLUTION ]<<--(https://codeforces.com/contest/189/submission/141457270)

Some please tell why my DP solution gives

WA on test case 8The main logic of the Div2A using dp.

Can someone explain me, how to do Div 2A using DP? I cannot get the idea.

Let f(x) be the maximal amount of ribbon pieces you can get if the ribbon length is x. Clearly f(x) = 0 if x == 0 (can't get more pieces) and f(x) = max(f(x-a),f(x-b),f(x-c))+1 otherwise (try every possibility). Don't forget to treat special cases (x < 0 or x > 0 and x < a,b,c)

If you need the code: http://codeforces.com/contest/189/submission/20790014

Thanks a lot.

Really... Thanks a lot.

can you be favor on me by explaining why u added 1 in line no 8

Because the count will increase by 1.

Can you explain your code?

Its similar to the coin change problem. If you understand that problem then this one will be easy to solve.

Here is my solution to the problem

Easy. 67129763

Here's my easy to understand solution. Here dp[i] denotes the max segment possible for length i. If dp[i]=-1 it's not possible to divide the line of length i into valid segments. dp[0]=0 because it's possible to form a line of length 0 with 0 segments.

Submission

in cut ribbon why this test 4000 3 4 5 equal 1333???

x = 1332, y = 1, z = 0, such that

3 * x + 4 * y + 5 * z = 4000

52282774

bottom up dp for 189A - Cut Ribbon

can someone please explain 189-A.

I am assuming you want to understand how to use DP.

https://codeforces.com/contest/189/submission/59615572

In the above solution, I have used a recursive approach to solve the problem. bases cases are less than 0 and equal to zero. when max no. of ribbons of an 'n' is not calculated then I calculate it by subtracting each allowable length a,b,c;

thanks

189A - Cut Ribbon

Here is my solution. I don't know if it'll help anyone, but it would have helped me had I seen it. I found the other solutions a bit intimidating. o.o

Code

189A - Cut Ribbon Solution using DP:-

## include

## include

## include

using namespace std;

int a,b,c;

int max_possible_cuts(int n,vector& dp){

}

int main(){

}

Thanks your solution is very clear !

Thank you very much !!! finally your solution made it clear to me .

Can someone please explain the complexity of bfs used in the solution by peter for problem C -> weak memory. https://codeforces.com/contest/187/submission/1674683

If the graph is star-shape, each call of function

`f`

takes`O(E)`

, thus worst-case is`O(E)`

.Hi Reza, I would like to point out that there is a certain change in the bfs he used. He has added a line "if(hv[y])dis[y]=0; " . In my opinion, this should hinder the complexity of the bfs.

why in cut ribbon input 4000 3 4 5 ..the answer is 1333 ..when if i can cut 4000 in 800 pieces using c=5

It wants the maximum number of pieces from you, not minimum.

3*1332 + 4*1 + 5*0 = 4000

I am getting WA in Problem A i.e. CUTTING RIBBON.

## include <bits/stdc++.h>

using namespace std;

## define fastio ios::sync_with_stdio(0);cin.tie(0);

typedef long long ll;

int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif

}

Great Editorial!

AlgoRace — what a name xd

How to solve BRT contract ?

Problem A can also be solved with smaller memory using number theory. We can answer questions for cutting ribbon optimally using two allowed piece lengths a and b in O(max(len(a), len(b))) time and O(1) space using extended Euclidean algorithm (which gives the upper bound on time). So for every possible c, we can find the optimal a and b in such time. Assuming a <= b <= c, algorithm works in O(n / c * log(b)) time. 104185743

In 189A do we need maximum number of ribbons or we need maximum length ribbons?

If we need maximum number of ribbons then the test1(5 5 3 2)Output-(2) holds and test2(7 5 5 2)-Output-(2) fails.

If we need maximum length of ribbons then the test1(5 5 3 2)Output-(2) fails and test2(7 5 5 2)-Output-(2) holds.

Can someone explain the brute force solution ?

If you currently have a length of string 7, and have a,b,c as {2,3,5}, then you can either choose to cut the string into a smaller ribbon of length (7-2 = 5), (7-3 = 4) and (7-5 = 2). From here you again have three choices for each state and can recursively solve for it. Here is my top-down approach