Hello, Сodeforces!

We are very grateful for Your participation in our round.

Thanks to Qwerty1232 for the help with this editorial.

**Advice #0**

*Just to it. The testing system is here for the testing. Send your solution.*

**Hint #1**

If $$$(n; m) \neq (1; 1)$$$, then: - Stanley should teleport at most once - Megan shouldn't use portals at all

**Hint #2**

Stanley and Megan gonna move only toward their destinations (Stanley will increase $$$x$$$ and $$$y$$$, Megan will decrease $$$x$$$ and increase $$$y$$$.

**Hint #3**

Megan can move along one route, which is the same regardless of board size.

**Solution**

### 1715A - Crossmarket

*For convenience let's define going upward as decreasing $$$x$$$ coordinate, downward — increasing $$$x$$$, left — decreasing $$$y$$$, right — increasing y.*

One of the optimal solutions is the following:

- Megan goes upward to Stanley, she spends $$$(n - 1)$$$ units of energy for that. Then she goes right to her final destination by spending $$$(m - 1)$$$ more units of energy.
- Stanley now has a choice: he obviously has to teleport from his starting position either all the way down, or right. He chooses what will save him the most energy, so he teleports along the greater wall of the shop for the 1 unit of power.
- Then Stanley has to finish his route: he walks along the smaller side and spends $$$min(n, m) - 1$$$ more energy.

If at least one of the dimensions is not $$$1$$$, then the answer is $$$(n - 1) + (m - 1) + 1 + (min(n, m) - 1) = min(n, m) + n + m - 2$$$. In case where $$$(n, m) = (1, 1)$$$ answer is $$$0$$$.

**Normal proof**

### 1715A - Crossmarket

Obviously, except for 1 case, it is always beneficial for Stanley to use teleportation. Let the first portal he visited be $$$A$$$, and the last is $$$B$$$. It is also obvious, that teleporting for more than 1 time makes no sense, so that's why we consider, that he always teleports from $$$A$$$ to $$$B$$$ and that's it.

For the sake of convenience let's define manhattan distance between two points as $$$dist(P_1, P_2) = |{P_1}_x - {P_2}_x| + |{P_1}_y - {P_2}_y|$$$.

Consider the next few cases for the relative position of those two portals:

- $$$A_x \le B_x$$$ and $$$Ay > By$$$

Megan must make at least $$$(n-1) + (m-1)$$$ moves. The portal does not help Stanley in the $$$y$$$ direction, so he must make at least $$$(m-1)$$$ moves.

- $$$A_x > B_x$$$ and $$$A_y \le B_y$$$

Megan must make at least $$$(n-1) + (m-1)$$$ moves. The portal does not help Stanley in the $$$x$$$ direction, so he must make at least $$$(n-1)$$$ moves.

- $$$A_x \le Bx$$$ and $$$Ay \le By$$$

Megan must make at least $$$dist(A,B)$$$ moves between $$$A$$$ and $$$B$$$. Going between A and B either undoes Megan's progress in the $$$x$$$ direction or $$$y$$$ direction (depending on which is visited first), so she must make at least an additional $$$(n-1) or (m-1)$$$ moves. Stanley must make at least $$$(n-1) + (m-1) - dist(A,B)$$$ moves.

- $$$Ax > Bx$$$ and $$$Ay > By$$$

Megan must make at least $$$(n-1) + (m-1)$$$ moves. Using the portal undoes Stanley's progress in both the x and y directions, so he must make at least $$$(n-1) + (m-1)$$$ moves.

In all cases, the total number of moves is at least (n-1) + (m-1) + min(n-1, m-1).

**Proof, director's cut (or how you should not do)**

In a while, after I came up with an idea for this task, I got excited to proof it formally. I was very happy with the result — A's proof was longer than a regular editorial for Fdiv2, or even Fdiv1. A couple of days before the round Monogon told us that there is a solution much easier to understand, for which I am very grateful! But I would like to save the original version as an example, of how you should not prove the easiest task in your contest.

**Hint #1**

Greedy.

**Hint #2**

- What are the limits of $$$s$$$ with all else being the same?
- What is the number, which we can always add to a divisible by $$$x$$$, to keep the answer the same?

**Hint #3**

- $$$s$$$ is at least $$$x \cdot s$$$
- maximum reminder mod $$$x$$$ is $$$x - 1$$$.

**Solution**

**Hint #1**

Look from the perspective of joints between blocks

**Hint #2**

For each pair of adjacent different numbers, calculate how many subsegments contain them.

**Hint #3**

To apply the changes, neighboring numbers and the position of the changing number are all we need to know.

**Solution**

- С++ сode: 169162300

**Hint #1**

We can solve the task separately by bits.

**Hint #2**

What are the most useful conditions? Those, that state that bitwise or of some bits in $$$i$$$-th and $$$j$$$-th numbers is $$$0$$$ because we can null both of these bits for sure.

**Hint #3**

Solve the task separately by bits. Firstly, satisfy conditions from the second hint, then try to null the bits from the beginning.

**Solution**

- С++ сode: 169162393

**Hint 1**

For every $$$i$$$ from $$$1$$$ to $$$n$$$ find the shortest path from $$$1$$$ to $$$i$$$, ending with an air trip.

**Hint 2**

Can you solve the problem for $$$k = 1$$$?

**Hint 3**

If you have somehow solved the problem for $$$k = i$$$, how can you solve it for $$$k = i + 1$$$?

**Solution**

- С++ сode: 169162508

**Advice #0**

There is a lot of freedom, but there exists a very simple solution. If You think of something complicated such as advanced geometry, You are probably doing something wrong.

**Hint #1**

Try to think about sawtooth-like figures.

**Hint #2**

You can use only 2 queries.

**Hint #3**

The figure is periodic. Both of those queries use the same figure, but in one query it is rotated by $$$90^\circ$$$.

**Solution**

- С++ сode: 169162576

TLE on D T.T

Trash contest

no u

Wow, such a fast tutorial!

One of the best C

For experts or higher I guess

I don't think Monoblock's company is having many sales with such a complicated captcha.

Thanks for the really nice contest and also the editorial:)

Though I couldn't perform as well as I expected, the contest and the problems were interesting :)

I think convex hull trick is too complicated for div2 E, please don't add such tasks

You can also do it with D&C dp, I think this was a nice question. You learn these tricks but there aren't many "easy" questions on them because they are generally reserved for harder problems with more observation. This was a simple application and personally I got a nice Aha moment when realising I could use D&C, imo this way you get a chance to build an intuition for them

my hands finally knows about CHT by this task

You can also solve E using Divide and Conquer DP because of the square cost function

My submission

can you elaborate on the divide and conquer dp?

The objective of the D&C was to calculate the minimum distance after a flight(assuming the flight just landed at some point), so you have a set of distances you got from dijkstra in $$$dp$$$_$$$old$$$, then you calculate post flight distance for $$$i$$$, aka $$$dp$$$_$$$new[i]$$$ as $$$min_j (dp$$$_$$$old[j] + (i-j)^2) $$$

I divided this up into two parts

$$$min_{j<i} (dp$$$_$$$old[j] + (i-j)^2)$$$

$$$min_{j>i} (dp$$$_$$$old[j] + (i-j)^2)$$$

Both of these are what I solved using D&C DP, followed by more Dijkstra to calculate travel via roads

nice get the divide and conquer now,

using the optimal to cut up the array was cool wouldn't have thought of that

Can you elaborate how to solve one of those partial minimums? I was able to do that only with some crazy math.

Let $$$opt[i]$$$ be the index $$$j, j<i$$$ which gave the minimum value of $$$dp[j] + (i-j)^2$$$, then Divide and Conquer DP works iff $$$x < y$$$ implies that $$$opt[x] < opt[y]$$$, which you can see is the case here with some light maths. What you do is, if you want to calculate $$$dp[l]$$$ to $$$dp[r]$$$, let $$$mid$$$ be the middle point, you calculate $$$dp[mid]$$$ and $$$opt[mid]$$$ in $$$O(r-l)$$$, and once you calculate $$$opt[mid]$$$, it reduces the range you need to search for the rest of the elements, then you recursively do this calculate $$$dp[mid]$$$ and $$$opt[mid]$$$ for the segments that are left and right of $$$mid$$$.

This was very brief but you can read more about Divide and Conquer DP here

Can someone explain the Convex Hull Trick mentioned in E? I can't figure a way to calculate the minimum for each node without iterating over all other nodes to get $$$d_{new}[v]$$$

Its a somewhat advanced DP optimisation trick that allows you to optimise dp of the type $$$dp[i] = max_{j<i} dp[j] + cost(j, i)$$$ from $$$O(n^2)$$$ to $$$O(n log(n))$$$ by looking at each of the previously computed DP values as lines with decreasing slopes. You can find tutorial videos online, this is where I personally learned it

You can also use Li Chao tree (it is just advanced segment tree) Both are data structures that allows you to find minimum/maximum of linear functions' values in O(log(n))

For D, another solution is to simply build the answer from left to right, choosing the minimum value of $$$a_i$$$ each time.

To do this, first we need to restrict which bit of each $$$a_i$$$ can be $$$1$$$. This can easily be done by looping through all the condition $$$(i, j, x)$$$:

Let call $$$allowed_i$$$ the number that has all allowed 1-bit of $$$a_i$$$, then we can see that $$$a_i = allowed_i$$$ is a solution to the conditions, and for all solution, $$$a_i$$$ is a submask of $$$allowed_i$$$.

Then we can loop from $$$1$$$ to $$$n$$$ and construct $$$a_i$$$.

For $$$a_1$$$, we want to make it as small as possible, which mean we want each bit to be $$$0$$$, if possible. We can loop through all the condition $$$(1, j, x)$$$ to check which bit of $$$a_1$$$ must be $$$1$$$. Simply, if a bit is $$$1$$$ in $$$x$$$, but $$$0$$$ in $$$allowed_j$$$, then that bit must be $$$1$$$ in $$$a_1$$$.

It's easy to see that after this process, the best $$$a_1$$$ is just all the forced bits. We can then loop over the conditions $$$(1, j, x)$$$ and force the $$$1$$$ bits on $$$a_j$$$. Just repeat this to get the answer.

You can see my implementation here: 169201529. (Please excuse the weird syntax, I'm experimenting with it).

My implementation is $$$O(n + mlog(m))$$$ due to sorting the initial conditions, but $$$O(n + m)$$$ is achievable as we can do the work for all bits at once in this solution.

Submitted same thing, but with O(n+m) complexity: 169137143

The code now gives WA on newer tests: 169199626

I think you need to handle $$$l = r$$$ cases.

Updated.

I thought it would be a problem at some point during the contest, but then I forgot about it. Because I got AC, I thought it wasn't necessary and the thing will handle itself somehow.

glad to see that REDs also think this way.

Hello sir, I think I use the same solution with you, but why I get WA on test $$$4$$$?

My submission: 169330231

Take a look at Ticket 16079 from

CF Stressfor a counter example.Hello sir, can you help me with my solution?: 169535486 Thank in advance!

Take a look at Ticket 16085 from

CF Stressfor a counter example.Accepted!! TYSM <3 <3 <3

Hello! Could you please tell the reason for contest extended? As for me, nothing was wrong, so I'm just curious. Thanks!

During contest many contestants expirienced issues with Bad Gateway

In problem C, Can Somebody explain why to add number of segments in initial answer? i.e After adding the number of subsegments, we get the answer: 6⋅72=21,21+14=35.

consider any subarray with no joints ,the answer will be one; if there are x joints in a subarray, the beauty value is actually x+1; so the number 21 that you see is actually number of segments when we consider them without joints and the we add 14 to compensate for all the joints that could be considered;

Video Solution for Problem C and Problem D.

Hello, Can someone please explain why this failed (Problem B)? 169134990

Your solution failed because: 1. The lower bound for s would be b * k (handled properly) 2. The upper bound for s would be b * k + n * (k — 1) (your code does not handle this properly).

As, after setting first element to b * k, you can still add k — 1 to each element of the array.

Counter Test Case: 1 2 3 1 6

Correct Answer: (5, 1) or (4, 2) Your Code output: -1

Hi, anybody can explain, why my solution is wrong? WA test 4 https://codeforces.com/contest/1715/submission/169168903

Hi! It seems like you forgot that if the ith bit of (a | b) is equal to 0, then the ith bits of both a and b must be equal to zero.

An alternative randomized solution for Problem F:

Disclaimer: My solution fails on test 65, but I think it is probably an implementation error. Please correct me if this solution is just completely wrong.

The basic idea is to draw a lot of rectangles of the width of the field. Draw the first one at $$$y=0$$$ with height $$$1 \cdot \varepsilon$$$. Draw the next one at $$$y=1 + \varepsilon$$$ with height $$$2 \cdot \varepsilon$$$, and so on, each one exactly $$$1$$$ apart and $$$1 \cdot \varepsilon$$$ taller. We choose $$$\varepsilon$$$ as a very small number.

Since we have to draw one polygon we can just connect all rectangles on one side.

The square can only intersect one rectangle since they are each $$$1$$$ apart. We don't want any rectangle to only partially intersect with the square, so we offset everything by a random number between 0 and 1. This makes a partial intersection very unlikely since the height of our rectangles is very small.

With the answer to our query we can determine which rectangle the square intersects with and we know the $$$y$$$-coordinate is within the interval $$$[y_{rectangle}-1, y_{rectangle}]$$$. To determine the exact coordinate we can just query this interval and calculate $$$y$$$ with the intersection area.

We can repeat this for $$$x$$$ to get the answer in $$$2+2=4$$$ queries.

My solution is similar to yours. But I chose to randomly set a small value for the width of each rectangle, and fixed the interval between each rectangle to 1.

It passed all the test points. Here it is.169490864

I'm so sorry that I am poor in English.

Can anybody tell why my solution for D doesn't pass? It has same complexity. O((n + m) * log(x)).

Here is solution: 169156511

I have not gone through your code, but I can tell you the Test case where it fails Counter Test Case: 2 2 1 2 7 2 2 6

Correct Answer: 1 6 Your code output: 0 6

I hope this would help you :)

Ok. Thanks so much.

The evolution of $$$Div2$$$ $$$E$$$

May I take the picture away?

Sure.

can someone tell the rating of the C problem ?

I guess somewhere around 1700...

ok thanks, it is harder than the usual Div2 C problems

Agree.I felt the same XD

Excuse me, but I'm just curious about the meaning of "XD".

see the XD by rotating your device, it is text form of laughing emoji (this one)

Similar to ;) or :)

I think C was reasonable for Div 2 since the only major (intellectually) hard part was figuring out how to compute the cost at the start. Transitions between queries were really simple (albeit long) and didn't require much thinking.

Oh no! I got the solution of F during the contest, but it only cost 2 steps.So I didn't dare to write:(

A solution I thought of for E was to use a segment tree, what you would do is take the old distance and add $$$i^2$$$ to each $$$a_i$$$, doing that and taking the minimum of the array gives the answer for $$$i = 0$$$, then for moving forward from $$$i-1$$$ to $$$i$$$, you add the AP -1,-3,-5.. To the suffix and ...5,3,1 to the prefix — essentially adjusting the square terms we added. For this we of course need a segment tree that can add an AP to a range and take the minimum of all elements, can anyone confirm if that's possible? If it is can you point me to some resource?

Problem D video editorial

D does not require any graph theory knowledge at all.

Initially, there are $$$30n$$$ unknown bits.

We can do a first pass over the queries to find all bits $$$p$$$ and $$$q$$$ such that $$$p \mid q = 0$$$, which means $$$p = q = 0$$$. These are the

onlybits thatmustbe 0 in order to satisfy the statements (you can hypothetically set all remaining bits to 1 and this will satisfy the statements, but likely will not be lexicographically least).Then we can do a second pass over the queries to find all bits $$$p$$$ such that $$$p \mid 0 = 1$$$ or $$$p \mid p = 1$$$, which means $$$p = 1$$$. The former can arise due to forced 0 bits from the first pass, while the latter can arise from statements where $$$i = j$$$. These are the

onlybits thatmustbe 1 in order to satisfy the constraints (though you can't simply turn all remaining bits into 0 this time, since our remaining equations have the form $$$p \mid q = 1$$$).With the fixed bits out of the way, we can greedily clear all non-fixed bits of $$$a_1$$$ to 0. If any of these bits were involved in an equation of the form $$$p \mid q = 1$$$, then the other bit in the equation becomes fixed to 1 to satisfy it. We can then repeat for $$$a_2$$$ and so on.

Runtime: $$$O(m + n)$$$, with a constant 30 iterations for everything.

My Submission: 169185957 (I checked for $$$i = j$$$ and $$$p \mid q = 0$$$ while reading the statements)

SpoilerE is trash

No

About C, It confuses me that where n*(n+1)/2(in the tutorial is 6*7/2)comes from?

In my opinion, it is easier to have an initial array filled with the same number. The initial answer is $$$n \cdot (n+1)/2$$$ since that is the number of subarrays, and each subarray will have an awesomeness of 1. After that, we only have to know how to handle the changes after each operation.

Thanks!I think I get that.

when i looked at my submission after contest, i was surprised when i saw

`wrong answer Statement not true: (i, j, x) = (78387, 31267, 38016256)`

after that i used

`assert`

to check if the limit on every bit is satisfied. to my surprise, the`assert`

doesn't happen.can anyone tell me why? the submission id is 169192815

There are $$$q$$$ statements, but your solution reads $$$n$$$ statements only.

ohhhhhh thanks!!

when i noticed it, i really laughed out very loud

In problem E, could anyone explain the Dijkstra part mentioned in the editorial? How to transfer from "ending with air travel" to "ending with a usual edge"?

My solution of E:

Let's just use Dijkstra algorithm with only roads. Now repeat next thing k times:

For each v:

dp[new_layer][v] = min(dp[previous_layer][v], minimum_of(cost_of_flight + dp[previous_layer][from]))

Run Dijkstra on updated distances

Answer for vertex i after k repeats is dp[k][i]

Submission using Li Chao tree for finding minimum_of(): 169168040

What does it mean to "Run Dijkstra on updated distances"?

How is it different from normal Dijkstra?

It is not any different. You have some precounted distances, use them instead of INF you use usually and run usual Dijkstra

Great contest! I like A,C and F personally.

The system tests of problem

`D`

are too weak. Will it be retested?I used a slightly different approach to D that didn't require a seperate pass for each bit:

(Edge weight) AND NOT (Other vertex value)(Edge Weight) AND NOT (Other vertex available value)This gives each vertex its smallest possible value subject to the values given to previous vertexes, so gives the lexically smallest possible sequence of values.

See my solution 169149168

I think one could create a similar solution without creating a graph by doing two passes through the data, which might be more efficient.

My last comment is wrong. On the second pass one needs to go through the array values (vertexes) in order, and to know the final values of all lower numbered adjacent vertexes before calculating the value of current vertex, so this needs full adjacency information (i.e a graph).

The time complexity between 169232632 and 169236193 is the same. The only difference is I scanned in increasing order instead of decreasing order. I wonder whether it is a trick to cut down time.

This solution is easy for problem A.

C++ Code... https://codeforces.com/contest/1715/submission/169123715

which topic this problem belongs to ? as i want to learn more about it to solve similar problems

No topic

Greedy and Math

In problem E,

I'm facing a weird issue, when I initialize the distance to all the arrays with >= 1e14, it gives WA on test case = 37, otherwise, it passed all the test cases.

https://codeforces.com/contest/1715/submission/169246634

https://codeforces.com/contest/1715/submission/169246972

Can someone help me?

All that I'm changing between the two submissions is

`for(int i=2;i<=n;i++) dist[i] = ll(1e14);`

[Removed, as it was an in invalid test case].

The test you provided isn't valid because $$$k$$$ must be at least $$$1$$$. In fact, when $$$k$$$ is at least $$$1$$$, taking a direct flight from $$$1$$$ to $$$n$$$ is always an option, so the answer is bounded by $$$(n - 1)^2 < 10^{10}$$$.

My guess is that you overflow in your

`HullDynamic`

class.`k`

s and`b`

s can both overflow int, and so multiplication might overflow long long:`(x->b - y->b) * (z->m - y->m)`

UPD: Changed

`long long`

s to`int128`

in your HullDynamic class, AC now: 169286182Thanks mate.

Why in authors code of

C.Monoblock, they used (n — (i + 1) + 1) instead of (n-i)? As both will give same answer. Why to use (n — (i + 1) + 1). (In for loop)for our understanding...

What's that in C++ code for E?

Can anyone help me find out why my solution didn't pass for D ?

Here's my solution: for each index 1<= i <=n, let's find the bits that must be set to zero. Now let's iterate over the array starting from the last element, for each element we will only consider the statement that include another element with smaller index. For each statement that include that element, let's set to 1 all of the bits that are set to 1 in the OR value and can be set to 1 in the current index, the other bits will be set to 1 in the other element since we can't set them in the current one.

Here is a link to my submission: https://codeforces.com/contest/1715/submission/169171341

Any help will be more than appreciated.

Simple counter:

Your code gives 0 1 1, answer should be 0 1 0.

Problem F: Life will be harder if the query polygon must have all of its points lying inside the field. (This is the problem statement came from my misunderstood :)).

rockstar_an is the best, thanks to him I'm an Expert.

PS : He is my dad :)

Thanks my son.

Best father-son duo. Tears :')

Best duo.

Problem F is brilliant! Liked it very much :)

Can anyone help me find out why my solution didn't pass for D ?

I think I have written as what have been talked in blog. I have tried to fix it, but I failed.

My submission：169346279

Take a look at Ticket 16078 from

CF Stressfor a counter example.Thanks.

I disagree with Advice #0. You should always consider risk of wasting time on implementation of solution. And thinking about proof and trying to prove may save you from that.

For those who 1715E - Долгий путь домой for some reason don't understand why this thing can be applied here: within

minfirst square component may be considered as parameter and second square term can be extracted fromminbecause it's being constant in query.Could anyone help me find why this submission https://codeforces.com/contest/1715/submission/169450718 which is

`O(32(m+n))`

gets TLE but https://codeforces.com/contest/1715/submission/169452067 which could be`O(32 * 32(m+n))`

passes? The only difference is that I changed from a two-dimension vector to one-dimension vector, where bit information are added in edges instead of one-bit-one-graph. I have been thinking for the whole night. Thx...In author solution for problem E why is it: while (ll.size() >= 2 && l.intersect(ll[ll.size() — 2]) <= x.back())

and not: while (ll.size() >= 2 && l.intersect(ll[ll.size() — 2])

>=x.back())won't the authors solution remove lines from the Convex Hull that actualy need to be in it.

Figured it out.. brain fart

We are searching for Min not Max .

Interestingly, D has similar idea to https://codeforces.com/problemset/problem/1594/D, but you have to do it 30 times

I solved problem

Cwithsegtreehttps://codeforces.com/contest/1715/submission/215391566

I solved a harder problem actually, I can query any segment and find its required value.

There is a small typo in your template, it's "WEIRD" not "WIERD". Please fix it as it might cause denial of judgement verdicts.

Can someone help with C, I can't understand the explanation of how we count the sum of beauties of subarrays(answer) using this "the sum of beauties over subsegments is equal to the sum over all joints of the number of subsegments containing a particular joint, plus the number of all subsegments." Why does it work?