TLE on D T.T

Trash contest

Wow, such a fast tutorial!

One of the best C

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 solve E using Divide and Conquer DP because of the square cost function

My submission

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]$$$

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)$$$:

• If the $$$k$$$-th bit is $$$0$$$ in $$$x$$$, then it must be $$$0$$$ in both $$$a_i$$$ and $$$a_j$$$.

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.

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

мы не можем найти лексикографически меньшее решение глобально. Тут наверное "не" лишнее.

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.

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

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

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.

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

Here is solution: 169156511

В задаче С если ее делать на питоне, в претесте 2 есть тест который выдает TL на абсолютно верный код в котором ввод делается через input(), если считывать через sys.stdin.readline(), то тест проходится. Кто нибудь подскажет это можно как то отаппелировать? А то выглядит как вполне себе некорректный тест и обидно жесть как, 1.5 часа на задачу потратил. К слову все решения этой задачи на питоне сделаны только через sys.stdin.readline()

Вот пруфы: неверное решение с input(): https://mirror.codeforces.com/contest/1715/submission/169157450 такое же но с sys.stdin.readline(): https://mirror.codeforces.com/contest/1715/submission/169171912

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

can someone tell the rating of the C problem ?

Oh no! I realized the solution of prob.F during the contest, but is only cost 2 operations, so i didn't dare to write it :(

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 only bits that must be 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 only bits that must be 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)

E is trash

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

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

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"?

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:

• Create a weighted graph
• For each vertex AND together the weights of all its neighbouring edges. This tells you what bits can be set for that vertex. Call this the available value for the vertex.
• Now go through the vertexes in order. If a vertex is its own neighbour then that gives you its value. Otherwise, OR together values for each edge:
  • If the edge goes to a lower numbered vertex, include those bits that are required by the edge but are not included in the solution for the other vertex. This can be calculated as (Edge weight) AND NOT (Other vertex value)
  • If the edge goes to a higher numbered vertex, include those bits that are required by the edge but are not available for the other vertex. This can be calculated as (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.

"С" прикольная задача, но я не понимаю, как у решивших вообще появилась такая идея решения? Что их сподвигло на конкретно это решение? Объяснение понять-то не так просто, а кто-то смог это ещё и придумать.

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.

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://mirror.codeforces.com/contest/1715/submission/169246634

https://mirror.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);

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)

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

for (int i = 0; i < k; ++i) {
        for (int i = 1; i < n; ++i) {
        }
        for (int i = 0; i < n; ++i) {
        }
    }

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://mirror.codeforces.com/contest/1715/submission/169171341

Any help will be more than appreciated.

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 :)

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

Can someone tell me why my code for problem D is failing? here's the code: https://mirror.codeforces.com/contest/1715/submission/169397612

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 - Long Way Home for some reason don't understand why this thing can be applied here: within min first square component may be considered as parameter and second square term can be extracted from min because it's being constant in query.

Could anyone help me find why this submission https://mirror.codeforces.com/contest/1715/submission/169450718 which is O(32(m+n)) gets TLE but https://mirror.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.

Why does my solution for Problem D give TLE, pls someone explain.172482735

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

I solved problem C with segtree
https://mirror.codeforces.com/contest/1715/submission/215391566
I solved a harder problem actually, I can query any segment and find its required value.

Can anyone please tell me why this solution for D gives TLE, even though the number of operations would be about 1.2e7?

https://mirror.codeforces.com/contest/1715/submission/285557915