Codeforces Round #371 Editorial

8 лет назад, # |

Problem 1c can be solved in O(nlogn) without dp.

→ Ответить

hccz95

8 лет назад, # ^ |

How to solve it without DP?thx

→ Ответить

8 лет назад, # ^ |

+18

For simplicity, first subtract each number by their positions i, so we need to make the sequence non-decreasing.

Now, start from beginning. Each time a modification is needed, there are two options: raise the current position up or push elements before down. It should be noticed that for each position raising up happens at most one time (probably more than one unit though).

If nearest elements already form a equal sequence then all of them should be pushed down. However, pushing down n elements does not necessarily costs n -- some of them may be raised up before. For these elements pushing down actually contributes negative one per unit (for undoing raise). Furthermore, once some elements form a continuous equal sequence, they will be equal forever so we can view them as a group.

Now we are able to construct a solution. We start moving from position 2 all the way to the end. Once we move past a position some 'event' height will be recorded. There are three different situations:

1) a[i] = a[i-1]. In this case, position i simply merges with the previous group, and the cost of pushing down that group increases by 1.

2) a[i] > a[i-1]. We don't need to modify anything now; however an event point should be added at height a[i-1] for possible traceback afterwards -- when height is reduced back to a[i-1] two groups become one.

3) a[i] < a[i-1]. This is the only case we need an modification. Now, look for the cost for pushing down the previous group. As long as the cost does not exceed one (actually it never goes below one, you can prove it), it is worth doing.

i) If that is sufficient to lower a[i-1] to a[i], we are complete. Then the cost will increase by one.

ii) Otherwise, a[i] will be raised up. In this case, however, the cost will be reduced by one since when we push down position i afterwards, before it goes back to original value we are essentially undoing raise. Finally, we create an event point at original value of a[i]; when we reach that point later, cost of pushing down increases by 2 (from -1 to +1).

For implementation: store all event points in a heap(priority queue). When pushing down is performed, refer to the top(largest) value and update. Since each position adds at most one event point, total complexity is O(nlogn).

→ Ответить

8 лет назад, # ^ |

Tip: information considering the length, or left endpoint of a group need not be stored; what happens as we move past a event point is just that cost of pushing down increases. So the only thing recorded is: at this point how much does push-down cost increase? That is good for implementation since only a pair (height, costincrement) is needed.

→ Ответить

ferrarima

8 лет назад, # ^ |

You saved my day!

→ Ответить

8 лет назад, # ^ |

Can't it happen that you need to pop several elements from the heap? When you have e.g. 1,2,3,4,5,-100000 (you can lift it up to make positive).

→ Ответить

8 лет назад, # ^ |

Read last sentence again: heap.push happens at most n times. It is fine to have multiple pops at once, but by aggregate analysis it is O(nlogn).

→ Ответить

8 лет назад, # ^ |

I implemented quite similar solution, but using map, it seems simpler for me:

20623211 AC (time O(NlogN))

Works on random and sorted sequences of length 10^6 in 1 second.

→ Ответить

8 лет назад, # ^ |

← Rev. 3 →

+11

For implementation, I want to share woqja125's AC code which is truly magical :D

Original code

Slightly polished code

→ Ответить

8 лет назад, # ^ |

Omg! Can you explain why does this work?

→ Ответить

8 лет назад, # ^ |

Amazing. Seems that there must be an much much easier explanation of this problem. Could you tell that magic idea?

→ Ответить

8 лет назад, # ^ |

See the comment below!

→ Ответить

Im_pickle_Riiiiiiiiick

8 лет назад, # ^ |

thanks a lot.
your solution is great and your explanation is very clear!

here is my implementation of the exact idea if it might help someone.

→ Ответить

Swistakk

8 лет назад, # |

+31

Will Codeforces ever stop posing questions with complexities of model solution $\text{[math]}$ when there are obvious bruteforces in O(n⁴)?! Did any of testers even tried to compare those solutions? Did you try to ensure only intended solutions pass?

→ Ответить

MrDindows

8 лет назад, # ^ |

If the bruteforce solution is so obvious, why didn't you send it?

→ Ответить

Errichto

8 лет назад, # ^ |

+18

He assumed that organizers made sure naive solutions won't pass. It's about the constant factor, not about the difficulty of coming up with that solution.

→ Ответить

kalimm

8 лет назад, # ^ |

← Rev. 2 →

1e9 in 5 seconds. I think it's obvious it will pass on CF, if you're on CF more than a year. I thought about it but I can't find a solution in that complexity, then I found the intended one. So maybe N^3 is not just a "obvious" solution? Intended one is really eaiser than that one except the implementation.

EDIT: Why "He assumed that organizers made sure naive solutions won't pass"? Organizers can make mistakes. Didn't you ever see a solution which have a more complexity than the intended one but with a simple code?

→ Ответить

Swistakk

8 лет назад, # ^ |

+10

"1e9 in 5 seconds. I think it's obvious it will pass on CF, if you're on CF more than a year." — wut? You sure? You oversimplified it af. It heavily depends on kinds of operations you perform and number of them, locality of memory calls etc. I didn't inspect other people O(n³ + nt) solutions, but one I have in mind performs rather something like 1e10 operations with not very local memory calls, so it is obvious for me it won't pass. Btw people's times on this task are rather high, you can't really say it is obvious it will pass if one's time ends up being 4,5/5s :). As my saying goes "Problems can be divided to two kinds. One kind when intended solution for n<=1e6 and O(n log n) gets TLE and reason for that is "you know, big constant, memory allocation and shit" and second kind when for n<=1e3 intended solution is O(n^3) and organizers excuse is "you know, computers nowadays are really fast" :).

And regarding to "EDIT". If you take a look at constraints it is kinda obvious that test preparer's duty is to defend against >=O(n^3) or >=O(nt) solutions. These are not complexities taken out of nowhere, solutions in such complexities are not something crazy. I assume organizers are well aware of that and have taken care of that, tested few solutions with optimized memory locality and shit and ensured they don't pass.

→ Ответить

kalimm

8 лет назад, # ^ |

"ensured they don't pass"

This part isn't about problemsetter. If you write smooth N^3 it will get an accepted if N<=1000. There's a lots of problem which is slower than intended one but pass like that.

→ Ответить

GlebsHP

8 лет назад, # ^ |

I agree that it sometimes happens, but for this particular problem I do not consider O(nt) solution to be obvious.

→ Ответить

-XraY-

8 лет назад, # ^ |

That's why I don't like 2d problems. Always some naive stuff or in the toughest cases nsqrtn works better than any intended solution. And you can't really understand which nsqrtn solution is better (constants are rather unpredictable).

When I was solving this problem I easily got to the online max-queries. But I forgot about the existence of 2d-sparse table and understood that no log^2 (*log from binary search) tree would pass through time limit. I think I forgot about it because I can't really remember any problem which was solved with this algorithm, and I see the reason: some stupidity always works better.

P.s. n^3 + nt solution seems pretty obvious to me and it was the first thing I got to. Totally dislike the problem. And I still don't understand why this solution passes. 1.5*10^9 min(max()) + access to 2-d array operations in 3 seconds? Maybe tests are not good enough? I saw really not optimal solutions to pass in a half time and was surprised. Tests with 10^6 queries of (1000-eps)x(1000-eps) size should be good enough. I haven't checked if there are some so maybe I'm wrong.

→ Ответить

skavurskaa

8 лет назад, # |

← Rev. 2 →

Fun fact : it's harder than the author solution, but we can solve Div2C/Div1A using trie. Here is my code which i did during the contest: http://codeforces.com/contest/713/submission/20575096

→ Ответить

8 лет назад, # ^ |

← Rev. 2 →

lol, this is also the first solution I come in mind. All you should do is reverse the input and it becomes a standard trie problem :D

PS: do not forget to add trailing zeroes at the front to fill up required length

→ Ответить

poore

8 лет назад, # |

can someone explain why we can minus every a[i] by i without changing the answer ?

→ Ответить

MedoN11

8 лет назад, # ^ |

← Rev. 6 →

This might not be fully formal, but it's the way I thought about it:

A[i] < A[i + 1] can be written as A[i] <= A[i + 1] — 1.

Let's subtract i from both sides. ( Remember i is always >= 0)

We arrive at :

A[i] — i <= A[i + 1] — i — 1.

Which can then be re-written as :

A[i] — i <= A[i + 1] — ( i + 1)

We can also work our way backward, which proves the equivalence.

Now Assume the minimum cost for getting a non decreasing sequence for a[i] — i is x.

If you can make A[i] strictly increasing with changes less than x, then we could definitely make A[i] — i non decreasing using that value as they are equivalent, which contradicts our assumption that x is minimum.

As for the other way around ( x being smaller than needed ) you can use contradiction as well.

→ Ответить

poore

8 лет назад, # ^ |

i think i got it :P thanks!!

→ Ответить

bernett

8 лет назад, # |

+14

Can someone explain the maxflow approach which was used by some participants for the Div2E/Div1C problem?

→ Ответить

ibahadir.altun

8 лет назад, # |

← Rev. 2 →

l1 ≤ r1, l2 ≤ r2. Am I the only one who have been stuck at this point?? According to the problem statement, 714A - Meeting of Old Friends, l2 cannot be smaller than l1 and same for r2. So 20579107 should get AC but it gives WA at 3rd test case. So correct me if I misunderstood something but problem statement is not corresponding to the editorial. That really effected me too much and caused me to get a great(!) motivation for other problems

→ Ответить

Nezzar

8 лет назад, # |

I managed to get the idea of problem D but the TL seems really strict, my 2D sparse table got accepted with 49xxms out of 5000ms...

→ Ответить

tom

8 лет назад, # ^ |

← Rev. 2 →

Your code can be a few times faster if you change dp[N][N][11][11] into dp[11][11][N][N]. In init() you iterate over i and j jumping every 11 * 11 elements and missing cache very often.

→ Ответить

devils_here

8 лет назад, # |

Please explain the DIV-2E/DIV-1C solution. I am not able to understand from the tutorial.

→ Ответить

suksyr

8 лет назад, # |

In the problem B.How can I read the answer after flush in c++?

→ Ответить

astoninfer

8 лет назад, # ^ |

← Rev. 2 →

simply using scanf or cin to get input from stdin

→ Ответить

haleyk100198

8 лет назад, # |

Problem 1E looks pretty similar to this.

→ Ответить

stoyan_malinin

8 лет назад, # |

I solved problem B differently. I used Binary Search to find the answer.

→ Ответить

stoyan_malinin

8 лет назад, # ^ |

This is the source: http://codeforces.com/contest/714/submission/20612613

→ Ответить

Mr.Adnan

8 лет назад, # ^ |

:O oppss!!! such a great solution!

mine- http://codeforces.com/contest/714/submission/20585222 :|

→ Ответить

sbansalcs

8 лет назад, # ^ |

Overkill

→ Ответить

8 лет назад, # |

Does anybody know a judge with this Div1C problem but with larger constraints (e.g. N = 10⁵)?

→ Ответить

8 лет назад, # |

+83

There is a very short (10 lines!) and fast O(nlgn) solution for Div1C, proposed by woqja125 :

Start by subtracting i from all A[i]. We'll define fi(X) = Minimum operation to make A[1 .. i] monotonically increasing, while keeping A[i] <= X. it's easy to see that the recurrence is —

Min(Y <= X) |Ai — Y| if i == 1
Min(Y <= X) (f(i-1) (Y) + |Ai — Y|) otherwise.

Observation : fi is an unimodal function, which have a nonpositive integer slopes. Denote Opt(i) as a point X which makes fi(X) minimum.

We will maintain those functions and calculate the minimum. we examine two cases :

Case 1 : Opt(i-1) <= A[i]. In this case, Opt(i) = A[i], and every point under A[i] have +1 slope.

Case 2 : Opt(i-1) > A[i]. This case is tricky. every point over A[i] have +1 slope, and every point under A[i] have -1 slope. Opt(i) is the point where slope of fi is changed into -1 -> 0. When observing the function, Fi(Opt(i)) = F(i-1)(Opt(i-1)) + Opt(i-1) — A[i]. We can simply assume that Fx(Opt(x)) = 0, and add this to our answer.

Since applying this operation doesn't contradict above observation, the correctness of this algorithm can be easily proved by induction.

To implement this, we can maintain a priority queue, which holds every point where slope changes by +1. It turns out that implementing this can be "extremely" easily done by O(nlgn).

implementation

→ Ответить

hongjun-7

8 лет назад, # ^ |

Awesome! Thank you for your clear and helpful explanation.

→ Ответить

surajghosh

8 лет назад, # ^ |

← Rev. 2 →

can anyone explain the recurrence formulation again ? I am having a hard time understanding it ? what is Y ?

→ Ответить

FundamentalEq

8 лет назад, # ^ |

can you please explain the above algorithm in a more detail.Thanks in advance :)

→ Ответить

idy002

7 лет назад, # ^ |

← Rev. 2 →

We know f(opt(n)) is the final answer.

we only need to maintain f(opt(i)) for every i then we will get it.

we can find that :

when a[i] >= opt(i-1), f(opt(i)) will equal to f(opt(i-1))
when a[i] < opt(i-1), f(opt(i)) will equal to f(opt(i-1)) + opt(i-1) — a[i]

so if we know opt(i-1) when we add a[i], we can get f(opt(i)).

Let's consider how to maintain the information of fi to get opt(i)

In fact, we only need to know the slopes of every segment and then the point that slope become 0 will be the opt(i).

We save some "key points"(may overlap) in a sorted list, and the slope at position x is the number of "key points" that greater than x.

when a[i] >= opt(i-1), we only add a[i] to the sorted list
when a[i] < opt(i-1), we only need to move a rightest "key point"( which is equal opt(i-1) ) to the position a[i]. after that we add another a[i] to the list. You will find that we keep the property above to be unchanged.(because it means we add -1 to slope of (-oo,a[i]) and +1 to slope of (a[i],opt(i-1)] )

We only need a heap to maintain the sorted list.

→ Ответить

codgician

6 лет назад, # ^ |

Awesome solution. But can you please explain why do we have to push t two times when Q.top() > t? I'm having a hard time to understand that.

→ Ответить