One can notice that the maximum cost of sending a letter from *i*'th city is equal to maximum of distances from *i*'th city to first city and from *i*'th city to last (*max*(*abs*(*x*_{i} - *x*_{0}), *abs*(*x*_{i} - *x*_{n - 1})). On the other hand, the minimum cost of sending a letter will be the minimum of distances between neighboring cities (*i* - 1'th and *i* + 1'th cities), more formally, *min*(*abs*(*x*_{i} - *x*_{i - 1}), *abs*(*x*_{i} - *x*_{i + 1}). For each city, except the first and the last this formula is correct, but for them formulas are (*abs*(*x*_{i} - *x*_{i + 1})) and (*abs*(*x*_{i} - *x*_{i - 1})) respectively.

567B - Berland National Library

To answer the queries correct, we need to know if the person is still in the library. For that purpose we will use *in* array of type *bool*. Also we will store two variables for the answer and ''current state'' (it will store the current number of people in the library). Let's call them *ans* and *state* respectively.

Thus, if we are given query + *a*_{i} then we should increase *state* by one, mark that this person entered the library (*in*[*a*_{i}] = *true*) and try to update the answer (*ans* = *max*(*ans*, *state*)).

Otherwise we are given - *a*_{i} query. If the person who leaves the library, was in there, we should just decrease *state* by one. Otherwise, if this person was not in the library (*in*[*a*_{i}] == *false*) and leaves now, he entered the library before we started counting. It means we should increase the answer by one anyway. Also one should not forget that it is needed to mark that the person has left the library (*in*[*a*_{i}] = *false*).

Let's solve this problem for fixed middle element of progression. This means that if we fix element *a*_{i} then the progression must consist of *a*_{i} / *k* and *a*_{i}·*k* elements. It could not be possible, for example, if *a*_{i} is not divisible by *k* ().

For fixed middle element one could find the number of sequences by counting how many *a*_{i} / *k* elements are placed left from fixed element and how many *a*_{i}·*k* are placed right from it, and then multiplying this numbers. To do this, one could use two associative arrays *A*_{l} and *A*_{r}, where for each key *x* will be stored count of occurences of *x* placed left (or right respectively) from current element. This could be done with map structure.

Sum of values calculated as described above will give the answer to the problem.

567D - One-Dimensional Battle Ships

First, we should understand when the game ends. It will happen when on the *n*-sized board it will be impossible to place *k* ships of size *a*. For segment with length *len* we could count the maximum number of ships with size *a* that could be placed on it. Each ship occupies *a* + 1 cells, except the last ship. Thus, for segment with length *len* the formula will look like (we add "fictive" cell to *len* cells to consider the last ship cell). This way, for [*l*..*r*] segment the formula should be .

For solving the problem we should store all the [*l*..*r*] segments which has no ''free'' cells (none of them was shooted). One could use (*std*: : *set*) for that purpose. This way, before the shooting, there will be only one segment [1..*n*]. Also we will store current maximum number of ships we could place on a board. Before the shooting it is equal to .

With every shoot in cell *x* we should find the segment containing shooted cell (let it be [*l*..*r*]), we should update segment set. First, we should delete [*l*..*r*] segment. It means we should decrease current maximum number of ships by and delete it from the set. Next, we need to add segments [*l*..*x* - 1] and [*x* + 1..*r*] to the set (they may not be correct, so you may need to add only one segments or do not add segments at all) and update the maximum number of ships properly. We should process shoots one by one, and when the maximum number of ships will become lesser than *k*, we must output the answer. If that never happen, output - 1.

At first, let's find edges that do not belong to any shortest paths from *s* to *t*. Let's find two shortest path arrays *d*1 and *d*2 with any shortest-path-finding algorithm. First array stores shortest path length from *s*, and the second — from *t*. Edge (*u*, *v*) then will be on at least one shortest path from *s* to *t* if and only if *d*1[*u*] + *w*(*u*, *v*) + *d*2[*v*] == *d*1[*t*].

Let's build shortest path graph, leaving only edges described above. If we consider shortest path from *s* to *t* as segment [0..*D*] and any edge (*u*, *v*) in shortest path graph as its subsegment [*d*1[*u*]..*d*1[*v*]], then if such subsegment do not share any common point with any other edge subsegment, except its leftest and rightest point (*d*1[*u*] and *d*1[*v*]), this edge belongs to every shortest path from *s* to *t*.

Now we could surely answer "YES" to such edges. Next part of the solution are much simple. If edge (*u*, *v*) do not belong to every shortest path, we could try decrease its weight. This edge will belong to every shortest path if and only if its weight will become *d*1[*t*] - *d*1[*u*] - *d*2[*v*] - 1. So, if this value are strictly positive, we should answer "CAN" considering new edge weight. Otherwise we need to output "NO".

Consider that we are placing blocks by pairs, one pair by one, starting from leftmost and rightmost places. Thus, for example, two blocks of height 1 we could place in positions 1 and 2, 1 and 2*n*, or 2*n* - 1 and 2*n*. The segment of unused positions will be changed that way and the next block pairs should be placed on new leftmost and rightmost free places. At last only two positions will be free and we should place two blocks of height *n* on them.

Any correct sequence of blocks could be builded that way. Let's try to review the requirements consider such way of placing blocks. As soon as we place blocks one by one, the requirements are now only describes the order of placing blocks. For example, requirement ''3 >= 5'' means that we should place block in position 3 only if block in position 5 is already placed (and thus it have lesser height), or we place pair of blocks of same height on them at one moment.

For counting required number of sequences we will use dynamic programming approach. Let's count *dp*[*l*][*r*] — the number of ways to place some blocks in the way that only positions at segment [*l*..*r*] are free. The height of current placed pair of blocks is counted from the segment borders itself (. Fix one way of placing current block pair (exclusion is *l* = = *r* + 1). Now check if such placing meets the requirements. We will consider only requirements that meets one of the current-placing positions. For every "current" position "<" must be true only for free positions (positions in [*l*..*r*], which do not equal to current positions), ">" must be true for already-placed positions (out of [*l*..*r*]) and "=" must be true only for second current position.

This DP could be easily calculated using "lazy" approach.

Can you please provide me test case 61 or help me with this submission getting WA. http://codeforces.com/contest/567/submission/12359031

ct map stores count of numbers from right to left, mapp stores count of x and x * k in right. I changed the order of updating of mapp, ct and ans and got AC. http://codeforces.com/contest/567/submission/12377229

in last cycle ans += mapp[ar[i] * k]; must be first line, else if ar[i]*k == ar[i] you crushing logic of solution. This is possible not only k = 1, this is possible if ar[i] = 0. You can see test#61 is it.

P.S. after this correction there is no need to separate case k = 1.

Thanks I thought ar[i] * k == ar[i] only if k == 1 and forgot ar[i] == 0.

I spent about one hour trying to find a smart solution to problem B and I failed during the contest. But after the contest ended (of course), I found a beautiful idea. I use a map and a deque. The map is used to verify if a person has already been encountered. The deque keeps track for the "events". When a new "event" occurs it is tested: if ( — x ) is encountered and x doesn't belong to the map we will push_back the (- x) event and push_front the ( + x ) event. For all other cases ( +/- x ) is pushed_back. After that, the deque will be scanned, + increases the current nr and — decreases it. The maximum value for nr is saved and finally printed. I hope this beautiful solution will solve the problem forever.

## Genius

Very easy to reason about solution!

I have a short solution too that passed during the contest here: 12371072

i had a much simpler idea. at first i checked through the list to count who was already there. then i just ran a simulation to find the answer :)

I solved problem C using DP... let dp[i][j] = the number of geometric progression with common ratio k starting from index i and with length j. now of course dp [i][1]=1. dp[i][j]=sum(dp[v][j-1]) where (v>i and a[v]=k*a[i]). one can use map to do this. the answer will be sum(dp[i][3]) where 1<= i <=n

My solution for

Dis quite similar to described above, however it have got TL. I tried to store intervals in simple ArrayList and had to loop over it for every move to find the interval where target cell belongs. This approach is probably cause of TL. I saw solutions with TreeSet and some others, but i want to ask about my approach. Is there way to store my Intervals somehow to make access faster and avoid TL? http://codeforces.com/contest/567/submission/12377419Instead of doing a linear search to find your interval, because of the way the set of intervals is structured(a number cant be in more than 1 interval) you can binary search for your desired interval.

But for these sorts of problems, c++ is much much MUCH better. You almost never need extra optimizations,intervals can be represented as pairs, and the set will automatically sort the pairs without any comparators needed. You can use the set::upper_bound function to find the desired interval(1 line of code whereas you would need to binary search, taking many more lines of code).

How to apply binary search to problem C?, please.

By using map. In fact it's already a data structure with the time complexity

`O(logN)`

Python's

`dict`

and C++'s STL`unordered_map`

(I think) are O(1).Wow. Can you give a further explanation?

`dict`

and`unordered_map`

are just implementations of a hash table, which allow lookup in O(1).See: https://en.wikipedia.org/wiki/Hash_table

I did something a bit different from the intended solution (http://codeforces.com/contest/567/submission/12368255), but the intended solution still only needs write/lookup (and not sorting), so a hash table is adequate.

`std::unordered_map`

is not "ordered" (ie. you cannot do binary search on it).On top of that,

`std::unordered_map`

is really, really slow (faster than`std::map`

though). I suggest not to think of it as O(1).I'll keep that in mind :)

Is there anything faster than

`unordered_map`

for lookup in C++?No, unfortunately.

What I mean is, give it a bigger constant (say, 20,30) when evaluating your solution. Based on my own experience (I love solving State Space Search problems — which require a lot of it), it really is slow.

You can also consider writing your own implementation :)

I wrote mine just a few days ago with Simple Tabulation Hashing and Linear Probing (it doesn't support erase because of this) based on MIT Advanced Data Structures L10.

My poor implementation link in case you want to take a look.

You should have a look at this http://stackoverflow.com/questions/4846798/why-would-map-be-much-faster-than-unordered-map

It is

O(1) on average, butO(n) at worst. For`map`

it is always at worst.In practice, it is too difficult to construct a test case that can significantly slowdown an

`unordered_map`

.On codeforces, I see that the

`unordered_map`

provides at least 2 times better performance than just a`map`

.Even at worst case, you can play with

`max_load_factor`

and hash function.This is all true, but you shouldn't view hash tables as a "magical bullet", the

O(n) worst case can still strike. One needs to be aware of this.I have encountered this on CF once: I used

`unordered_map<int, int>`

as usual (with`.reserve()`

too) and received unexpected TLE. After eliminating other factors, I changed the code to`map<int, int>`

— and the solution passed.I am the one who added "sortings" and "binary search" tags to C.

The top-level idea is to enumerate the middle point (call it

a[i]),then count the total number of

a[i] /k(before i) anda[i] *k(after i).To do this,

a[i],i) and sort the sequence. You would get something like (1, 0) (1, 3) (2, 1) (5, 2) (5, 4) (7, 5) for a sorted sequence.a[i] /klies in the sequence, do 2 binary searches using (a[i] /k, 0) and (a[i] /k,i). Let this number bem_{1}.a[i] *klies in the sequence, do 2 binary searches using (a[i] *k,i) and (a[i] *k,INF). Let this number bem_{2}.ans=ans+m_{1}*m_{2}Implementation

did the same but with coordinate compression

12584852

Please ignore my ugly implementation as I am trying to get used to C++11...

But my concept is just do binary search on a vector<pair<int,int>>, no special data structure is needed :)

For problem D, simply use a map structure to record the free space (a consecutive empty square without shotpoint) on a shotpoint's left and right.

You can use the lower_bound and upper_bound functions (of map/set [IMPORTANT]) to find the nearest shotpoint, and update them.

When a shot happens a free space will be broken into 2, so calculate the sum of max number of ships of those 2 spaces and subtract it from the global sum of max number of ships.

Calculate the maximum number of ships could be placed in the space: (space+1)/(a+1)

(global sum of max number of ships = (n+1)/(a+1) before the 1st shot.)

when the global sum < k just print the current operation number and exit.

With exact same code I am getting TLE : http://codeforces.com/contest/567/submission/12382269

std::lower_bound is O(logn) if and only if you search above container with random-access iterators (you can for O(1) get any item: vector, array) and container is sorted.

Set has bidirectional iterator (you can for O(1) get only previous and next items) so std::lower_bound is O(n).

To get complexity O(logn) you need std::set::lower_bound. It is O(logn) in worst-case.

Thanks a lot! I wasn't aware of that. Got AC finally.

Another solution for D which works in

O((m+n)·dsu): 12380878Just process all shots in reverse order.

Can you give us an estimate on when the rest of the editorial will be posted?

Can anybody help me check my code of problem E: http://codeforces.com/contest/567/submission/12382102

Thanks!

You have a similar solution to mine. I think this might help you: http://codeforces.com/contest/567/submission/12375257

I think you have to push the vertex back into the queue even if dist[nex] == dist[cur] + d. Otherwise, the array way[] may not be updated for some vertex.

Consider the graph with two paths: S -> Z -> X -> T S -> A -> B -> C -> X -> T where the length of every edge is 1 (except edge (S, Z) and edge (Z, X) with length 2)

In this case, both are shortest paths. Yet, your code would only update way[X] but not way[T].

I think SPFA is not correct for calculating number of ways. You could count something many times. You have WA for this small test:

Yeah, thank you very much!

Is it because of the last two multiple roads?

You should change your Mod to 479001599. I found this number in this submission http://codeforces.com/contest/567/submission/12378788 of Solaris

I have no idea how the author of this submission can choose such prime number in his solution. Can someone help me explain this? Thanks in advance.

Thanks, it works!

I got WA in Problem D(i used binary search+Segment tree),i cannot understand where is my wrong.. here is my code http://codeforces.com/contest/567/submission/12385432

The ships cannot touch each other.

You didn't count it here. c+=(arr[i]-(a))/A; c+=(b-(arr[i]+2))/A; total=total-(t/A)+c;

OMG!!!

i had understood the problem C wrongly and it was so hard! but when i understand the corret form of problem i get AC in 10 mins! is it fair that i didn't go to div 1 for my bad English???? is it?

Every div1 programer need to know English?.. Very controversial to me:D

can anyone help me with some ideas about problem D ?

You can use binary search : try to put the first (l+r)/2 points and k recetangles without overlapping. If it is possible you try for greater value else you try for smaller. How you check if it is possible: Iterate over all point and check how many recentagles at most you can put between point i and point i+1. Also you should check how many recetangles you can put between 1 and a[1] and a[(l+r)/2] and n.

The second solution: You can use dsu or set. Start from behind and check if it is possible to put k recetangles when you have the first i points if it isn't possible you merge intervals [left andjacent point, a[i]] and [a[i],right adjacent point] and check it again.

in the first approach , do you mean by a[i] the "shot" number i ??

if it's the case , I don't agree with ,because "shots" are not given sorted by their position

thanks!

Yes, I mean that. You can sort shots every time — total complexity O ( n log ^2 n).

thank you !

Sorting doesn't always take Θ(

nlogn) time. In this case it might be even easier to do a step of the binary search in linear time.Adding small n logn each time would perfectly be O(nlognlogn)

you don't need to start from behind, just check the decrease of the max number of ship it can place when a shot happens (it's nlgn)

Can you please make me understand where is my solution wrong? Solution I cannot understand why my checker function is wrong??

I have spent a lot of time and I still cannot understand why this F function works Sol2

Actually what I am doing is putting the rectangles of length A between the positions.

Please help ! I am trying since yesterday!

A lot people were talking about it. You should divide with a+1 in check function ( reason- two ships can't touch each other ).

About F, I didn't read it, but also I don't believe I can help you... I am not on level to understand every solution for some F problem :)

The solution in details is to do a binary search against the array of moves — to find the first move, when it becomes impossible to put m ships on the board. As far as I see — this approach was used by the majority of div1 participants. Makes sense, as it is simple and now complex structures are needed at all.

So we have to write a function F(p), which returns whether it is possible to place the ships for a situation after move with number "p" .

The initialization step is to check F(m). If it is "true", then our result is immediately "-1". I.e. after "m" moves we are still able to place all the ships on the board.

We don't need to check the start of the moves, as according to the problem statement, initially it is possible to place the ships there.

And so we start the main loop to perform half-division search over moves. The initial interval to check is from 1 to "m". During every iteration we calculate F( (l + r) / 2 ). If it is positive, then out solution is somewhere in the right half of the current interval. If it is negative, then the solution is in the left half of the current interval. And so on.

The binary search is O(logN). The quite simple F is O(N). Thus the general time complexity is O(N * logN).

I like submission 12361499, where the concept is shown quite well.

My O(nlognlogn) solution got TLE. :/

Since E and F editorials aren't up yet, could anyone explain the approach?

Problem E

Problem F

I think Problem E needs more explanation.

In case you don't understand the discussion, reply below and I'll explain :)

It needs some graph theory facts.

PLease explain Problem E. I have been struggling hard since an hour to understand the editorial

I have explained his ideas in my other comment below.

My solution is based on this fact (This should be easier if you have some graph theory knowledge):

Very nice problems, vovuh, especially C, E and F which I liked very much, looking forward to your next round! :)

For E, let dist_s[i] be the distance from s to i and cnt_s[i] be the number of shortest paths from s to i. These values can be computed using Dijkstra's algorithm, check my submission for more details. Then, let dist_t[i] be the distance from i to t and cnt_t[i] be the number of shortest paths from i to t. Those values can be computed by reversing the edges and running Dijkstra's algorithm from t.

After that, there are some cases to be considered for each edge (from[i], to[i], length[i]), let's assume that shortest is the distance between s and t, which is dist_s[t] and dist_t[s] and current is equal to the current length which is length[i]+dist_s[from[i]]+dist_t[to[i]]:

1) If current is equal to shortest, then the edge will be used for sure only if all shortest paths from s to t pass through this edge. So if cnt_s[t] is equal to cnt_s[from[i]]*cnt_t[to[i]], then the answer is YES. Otherwise, we need to decrease it's length by 1, so if length[i]>1, then the answer is CAN 1. Otherwise, the answer is NO.

2) If current is greater than shortest, then we need to make current equal to shortest-1 so if current-(shortest-1)<length[i], then the answer is CAN (current-(shortest-1)). Otherwise, the answer is NO.

Note that the cnt_s and cnt_t values may be really really big so in the topic I read about taking them modulo some number, and maybe taking them modulo two different numbers is a better idea, it makes the chance of collision lower. By the way, when I used 10^9+7 as MOD, I got WA and when I changed it, the verdict became accepted. However, I doubt the author solution uses MOD so it will be good to see it soon.

For F the best I found is this comment by Errichto — http://codeforces.com/blog/entry/19590?#comment-244086

can anyone helps me in Problem E ... i think my approach is right but im getting a WA on case 37 : 12402935 any help is appreciated :)

Am I supposed to do Dijkstra with priority queue? I get TLE on the first test case with N=100000 & M=100000 otherwise.

[submission:1000776999]

Yes.

I took a look. Your submission runs in

O(V^{2}).Reason: V Extract-Min & Relaxations, and Each iteration runs in

O(V)=> V *

O(V) =O(V^{2})Tried solving the C problem using two binary searches per index for find the number of terms a/k on left and a*k on the right. Ofcourse over a sorted sequence of the input data, sorted by size then by id if values are equal. Wondering why it timed out. http://codeforces.com/contest/567/submission/12399316

try this 200000 1 1 1 1 1 1 1 1 1....

Oh btw I really enjoyed the problemset.

later possible any means for example 2 hours later , 2 months later , 2 years later and 2 centuries and now what do you think?

Thanks for upd!

can any body help please, what is the bug in my solution for E ,does number of ways fit in long long? here

No. The number of ways can be something like 2

^{50000}.The more correct way to do this is to module the number by one or several(just to be safe) big prime number(s). This is still incorrect nonetheless, but has a very small error rate.

thanks. actually after trying 1000001447 as modulo i got AC.

someone please explain this part of problem E. How to find whether a given edge is visited for sure by the president vs may or may not case.

"Let's build shortest path graph, leaving only edges described above. If we consider shortest path from s to t as segment [0..D] and any edge (u, v) in shortest path graph as its subsegment [d1[u]..d1[v]], then if such subsegment do not share any common point with any other edge subsegment, except its leftest and rightest point (d1[u] and d1[v]), this edge belongs to every shortest path from s to t."

His idea is pretty interesting.

I am not sure if I understood it correctly, but here it goes:

`D`

).The distance traversed starts from

`0`

(Starting vertex) to`D`

(Terminal).`(u, v)`

on the shortest path graph.Suppose the shortest distance to u is

`d(u)`

and the shortest distance to v is`d(v)`

This edge essentially allows us to go from`d(u)`

to`d(v)`

.`d(u)`

to`d(v)`

" as an interval [d(u),d(v)]`0`

to`D`

.If an interval doesn't overlap w ith other intervals (from other edges),

then this means that if we would like to "pass through" any value of distance ,

this edge is the only way to go, which means this edge always exists in the shortest paths.

Hope this helps.

Hey thanks for replying. Couldn't understand the 5th point in your explanation. For example in the first test case: going from Node 1 to node 2 has cost 2. Then d(1) =0 , d(2)= 2, so the interval is [0,2], which is present no where else. But d(2)= 2, d(3)=7 , so interval is [2,7], which is also no where else present. So how do we make d(2),d(3) edge as an edge which is not always mandatorily visited vs only the d(1),d(2) as mandatorily visited by the president ?

d(3) = 9 actually.

[2, 9] overlaps with the interval [d(2), d(4)] = [2, 10]

Hey, thank you for the reply.

But if we search every edge with every other edge to find whether it is getting overlapped or not then wouldn't it cause a E^2 complexity , which is greater than E*log(V).

Also can u please suggest a method and the data structure for such verification ?

I think Sweep Line Algorithm should work here.

Basic idea is sort the intervals, first by starting point then by ending point.

Then scan the edges from left to right.

Complexity would be

O(ElogE) =O(ElogV).I didn't solve the problem this way, so I cannot really go into details on this. In case I made a mistake, let me know :)

my soln: http://codeforces.com/contest/567/submission/12425879

I submitted solution to E by checking each edge with every other edge. As we discussed, it is giving time limit exceeded for 19th case , which has 10^5 size of n.

I think, I am almost close to getting an AC. Just need a little help to cross the time limit barrier. Can u please explain how you solved, this interval verfication phase of the problem ?

Like I said, I didn't solve the problem this way.

You can perhaps look at the author's solution.

Problem E: can some one please help me understand how to improve the performance of my code ? I have used dijkstra's algo two times, 2nd time to get shortest dist from destination to other vertices,which takes 2*E*logV.

Now finding the interval that overlaps is taking E*E=E^2. How can i improve it better to reduce the time taken to identify whether a particular edge is for sure visited by the president vs not for sure case?

http://codeforces.com/contest/567/submission/12426802

You are checking overlap intervals online, while I did it offline, as said in the editorial, given a set of segments [l,r], we want to see if there is any other segments intersect it.

One way to do this is as follow:

Store all edges which are part of shortest path

Convert them into segments [l,r] as said in the editorial

Sort the segments O(E lg E)

Loop through segment, keep track the rightmost distance

Ryou get so far, for each segment[l,r]check ifl < R, it is being intersected if it's true O(E)After this, the remaining segments are those without intersecting, which you must pass through it, total with O(E lg E)

can anyone explain this line in the editorial of problem D

Each ship occupies a + 1 cells, except the last ship. Thus, for segment with length len the formula will look like (we add "fictive" cell to len cells to consider the last ship cell). This way, for [l..r] segment the formula should be http://codeforces.com/predownloaded/da/ab/daabfbc41456dfe3fc74f8b0eba284b1893a8abd.png .

why we have to use n+1 / (a+1) instead of (n/a). And also each ship occupies only a cells right..why it is a+1.

Ships cannot touch

can anyone explain how this code works? (author's D solution)

`auto it = xs.lower_bound(mp(x, -1));`

At the problem F! Which sequences are answer for the first test case

From problem E after building the shortest path graph, we could simply find all bridges in that graph assuming it is undirected. Those would be the edges that would be "YES". My accepted solution doing the same: http://codeforces.com/contest/567/submission/27506292

The shortest path graph (call it G) would be a directed acyclic graph. We need to find all edges such that their removal would lead to no path from S to T. If we consider the undirected version of the G (call it U) then a bridge in U would also be a bridge in G. Further a bridge in U would always lead to two components that seperate out the nodes S and T. Hence a bridge in U would be a YES.

We need to prove the reverse i.e. an edge marked YES in G would be a bridge in U. Say in U we remove an edge marked YES. This should lead to two components, for if it didn't then there should be a back edge connecting the two components containing S and T, but since G is a DAG this isn't possible

Getting TLE for C. I have used DP, I dont know if I can optimize more using recursive DP. Please help me out:

http://codeforces.com/contest/567/submission/38002243