vovuh's blog

Editorial Codeforces Round #Pi
By vovuh, history, 9 years ago, translation, In English

567A - Lineland Mail

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(xi - x0), abs(xi - xn - 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(xi - xi - 1), abs(xi - xi + 1). For each city, except the first and the last this formula is correct, but for them formulas are (abs(xi - xi + 1)) and (abs(xi - xi - 1)) respectively.

Author solution

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  + ai then we should increase state by one, mark that this person entered the library (in[ai] = true) and try to update the answer (ans = max(ans, state)).

Otherwise we are given  - ai 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[ai] == 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[ai] = false).

Author solution

567C - Geometric Progression

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

For fixed middle element one could find the number of sequences by counting how many ai / k elements are placed left from fixed element and how many ai·k are placed right from it, and then multiplying this numbers. To do this, one could use two associative arrays Al and Ar, 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.

Author solution

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.

Author solution

567E - President and Roads

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 d1 and d2 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 d1[u] + w(u, v) + d2[v] == d1[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 [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.

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 d1[t] - d1[u] - d2[v] - 1. So, if this value are strictly positive, we should answer "CAN" considering new edge weight. Otherwise we need to output "NO".

Author solution

567F - Mausoleum

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 2n, or 2n - 1 and 2n. 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.

Author solution

  • Vote: I like it
  • +73
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you please provide me test case 61 or help me with this submission getting WA. http://mirror.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://mirror.codeforces.com/contest/567/submission/12377229

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Genius

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very easy to reason about solution!

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D is 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://mirror.codeforces.com/contest/567/submission/12377419

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Instead 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).

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Python's dict and C++'s STL unordered_map (I think) are O(1).

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow. Can you give a further explanation?

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is O(1) on average, but O(n) at worst. For map it is always at worst.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    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) and a[i] * k (after i).
    To do this,

    1. Represent a number in the sequence by (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.
    2. To find out how many a[i] / k lies in the sequence, do 2 binary searches using (a[i] / k, 0) and (a[i] / k, i). Let this number be m1.
    3. To find out how many a[i] * k lies in the sequence, do 2 binary searches using (a[i] * k, i) and (a[i] * k, INF). Let this number be m2.
    4. ans = ans + m1 * m2

    Implementation

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Another solution for D which works in O((m + n)·dsu): 12380878

Just process all shots in reverse order.

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Thanks!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    5 6 1 5
1 3 100
1 2 40
2 3 60
3 4 5
4 5 7
4 5 7
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should change your Mod to 479001599. I found this number in this submission http://mirror.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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    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;

    → Reply
»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me with some ideas about problem D ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you !

          → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it -8 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Adding small n logn each time would perfectly be O(nlognlogn)

            → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My O(nlognlogn) solution got TLE. :/

      → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        An edge exists in all shortest paths iff. it is a bridge in the shortest path graph

        → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    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://mirror.codeforces.com/blog/entry/19590?#comment-244086

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        Yes.

        I took a look. Your submission runs in O(V2).
        Reason: V Extract-Min & Relaxations, and Each iteration runs in O(V)
        => V * O(V) = O(V2)

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Oh btw I really enjoyed the problemset.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for upd!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No. The number of ways can be something like 250000.

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    His idea is pretty interesting.
    I am not sure if I understood it correctly, but here it goes:

    1. Consider any valid shortest paths (Suppose the length of which is D).
    2. As we traverse through the edges,
      The distance traversed starts from 0 (Starting vertex) to D (Terminal).
    3. Now we consider an edge (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).
    4. For each edge, treat "d(u) to d(v)" as an interval [d(u), d(v)]
    5. Recall (2) the distance traversed starts from 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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        d(3) = 9 actually.

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              my soln: http://mirror.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 ?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                You can perhaps look at the author's solution.

                → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    1. Store all edges which are part of shortest path

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

    3. Sort the segments O(E lg E)

    4. Loop through segment, keep track the rightmost distance R you get so far, for each segment [l,r] check if l < 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)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply