HellKitsune's blog

Educational Codeforces Round 17 Editorial
By HellKitsune, history, 8 years ago, translation, In English
Task A
Task B
Task C
Task D
Task E
Task F
  • Vote: I like it
  • +196
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
8 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Hints inside hint. Cool

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

Nice structure of the editorial =).

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

Yo, dawg! We heard you like hints, so we put hints into hints so you can read hints while reading hints! Thanks for editorial!

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

for C. 

  a = 'x' + a + 'y';
  b = 'x' + b + 'y';

and iterate two pointers help me.

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

Is the whole editorial going to be in this format? (spoilerception) I think it would be quite difficult to navigate.

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

    This is already the whole editorial :)

    I feel that people usually come to the editorial with specific task in mind, and not to read the whole editorial at once. This way they can just unroll the task they need, and not spoil themselves by accident glancing over the editorial of a different task :D

    Also, seeing the whole solution may be less beneficial than taking a hint and trying to still solve the problem by yourself.

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

what is open hacking ? will the non-participants be awarded with points if they are successful in hacking ?

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

For E, it seems possible to do using 2D range-update point-query:

Sort radio stations by range in increasing order.

Now, imagine each station as a point on a 2D (position, frequency) plane.

Each radio station conflicts with any radio station in the rectangle given by (p-range, f-k) to (p+range, f+k).

Simply query each new radio station, the sum of which is the answer.

Seems more painful than official solution though.

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

    This ensures that the one of the two has the other one in range but doesnot ensure the other way round

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

      If you order by range in decreasing order yes.

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

I have a good solution on problem E.But in fact,it is similar to the official solution.

(sorry,my English is poor,and I haven't written comments before.It is my first comment.)

We can sort stations by range,and now when we query station i,we guarantee ri<=rj.

We need to find how many j satisfies this i,that is,satisfies these two inequations:

xi-ri<=xj<=xi+ri

fi-k<=fj<=fi+k

You can use the 2D-segment tree to solve it.But I don't really recommend this.

We notice that k is small.So we can iterate every fj which satisfies fi-k<=fj<=fi+k.We can use segment tree to query how many j satisfies xi-ri<=xj<=xi+ri.That is,for every fj we use a segment tree to keep xj,and when we query station i,we first iterate every fj which satisfies fi-k<=fj<=fi+k,and then we query how many j satisfies xi-ri<=xj<=xi+ri on our segment tree.

We can make a discretization for every fj,or we can ask for memory dynamically.Then we won't get MLE.

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

    valorwxp

    "then we query how many j satisfies xi-ri<=xj<=xi+ri on our segment tree"

    How do you do that?

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

      We can keep a value freq in every segment tree node, where [L, R] corresponds to the node and freq means how many numbers locate between [L, R]. Thus we can query the corresponding information on the segment tree.

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

      We can use a segment tree to keep xj,and query [xi-ri,xi+ri]. If you are worried about the memory,we can make a discretization for every fj,or we can ask for memory dynamically.Then we won't get MLE.

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

    Oh,my fault,we should iterate stations from smaller ri to bigger ri,and then we guarantee ri>=rj. I said:"we guarantee ri<=rj."In fact,it is useless.

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

      I think you were right when you said ri <= rj

      Ok, you are wrong.

      If we iterate from smaller to bigger, then for xi, counting total xj such that xi-ri <= xj <= xi + ri, wont work, because even if the station xi can reach xj xj won't be able to reach xi because it has(or can have) smaller range.

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

        There is little mistake, "we should iterate stations from smaller ri to bigger ri", we should iterate stations from bigger ri to smaller ri. Then we guarantee that xi-ri<=xj<=xi+ri where j < i

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

        Yes……You are right……we should iterate stations from bigger ri to smaller ri.

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

Cannot get D solution. Help >.<

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

how to solve D,even after looking at editorial,i m unable to figure out the solution

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

    Good day to you,

    well the key observation is, "what moves can you do" if you are on coordinate x (up to N) and y (up to 3)?

    A) You can move to any other "y" {including itself} and continue to next "x", adding the proper values

    B) [if you are on y==1 or y==3], you can move to y==2, go back (as far as you can) to go to last y and return back being on it [i.e. if you was on "1", you end on "3"]. Here you add all values till the place where you made turn.

    So here it is, that is all you can do — what to do with it?

    Firstly imagine we have only "A" {B is harder}. Well, this shall be easy, it can be done by DYNAMIC PROGRAMMING [since you only move to greater 'X' and all 'Y' stuff can be solved locally]. You can move to ANY 'y' and continue to next 'X'.

    Now, we want to extend this to solve "B" too. This might seem problematic, because it is forbidden [in DP] to return BACK. We also have no information about where we left space of size 2 (to y), so we could eventually do the move [this would cost another N]. The possibility which remains is to PREDICT the moves. In fact, you don't have to "count anything or so...", you just TRY and take if better. To do such prediction, you have to stand at "y==1" or "y==3" (as mentioned above). This will SHIFT you into prediction stat (switching to "1→3" / "3→1"). You can continue with this state as far as you want, keeping "shifted state" and adding ALL three values.

    So basically, you will take maximum of:

    A) Go to any Y and go to next X

    B) Switch state and go to next X

    while adding proper values.

    This can be stored in array of size "[N][3][2]" → "[X][Y][state]" {and I guess it might be reduced even for the state}.

    Complexity will go to (N), since the calculation in each state will be around "y" (i.e. 3), so basically constant

    I'm very bad at explaining so don't hesitate to ask more questions!

    Good Luck & Have Nice Day!

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

      please elaborate part B,how your solution is ensuring that it won't miss any cases,basically i didn't get part B ,thank you :(

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

        Oh yes.. I'll try: Imagine you want to return. The (with size of 3), you can't do that with some space "inside", so you will have to go through all 3 positions. Anyway, basically, it doesn't matter what happened before and what will happen after, what you will do is clear: you will go through upper row (or vice versa lower row) and at some point you make turn, go through middle row BACK and finally go by lower row (or upper) forward.

        Reminding it doesn't matter what happened before/after — everything can be managed with "**A**" — this case only covers "3*K FULL rectangle", to which you will step on y=1 and end on y=3 (or vice versa).

        This is about what it means — now how to solve with "recursion" — you can have "bool", which states, you are in phase. If you are in this phase, you can basically do two things "I" — leave phase [so you just switch off bool] or "II" continue phase (adding all 3 fields to solution and stepping to next "X")

        PICTURE:

        Here, you can see what the "B" means (B1,B2). On right side, you might imagine, that you are on X==5, Y== 1→3 and on PHASE, then you can do two steps:

        I) Leave phase: You will continue freely with A (or enter phase again, as you want)

        II) Continue phase: You will do, what is in last figure [as you can see, it is not, what you can really do, but thanks to this notation, we can extend it this way → harder for imaginations]

        Is it more clear? :O

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

I personally need more hints to solve D.

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

Nice editorial. I really liked D, the hints are great, while not telling too much :)

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

is it correct to print the longest common subsequence in problem C ?

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

    no, O(n2) is not enough

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

    Also, LCS wouldn't always be the right solution. Consider the below case:

    A: abcdef B: abxcxdef

    LCS: abcdef

    however the answer would be: abdef

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

Why the solutions are showing judgement failure?? HellKitsune

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

Could somebody please explain C to me? I really don't understand what this stands for: "For every prefix of B, count how big of a prefix of A you will require." Same with suffix.

Update: I understood now.

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

    Please share your understanding. Even i am having difficulty understanding question. Thanks.

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

      Let's count what prefix of A you need to get every prefix of B. First let's look at prefix of B 1 character long. To get that prefix you need one character that is same as the first character of B, but from prefix A. Increase your counter until you find the first character from A that is equal to this first character of B. That's p[0]. Now let's count p[1]. You need p[0] to get the first letter and you also need a character from A that is same as the second character of B. So just increase counter starting from p[0] until you find this second character. And so on... Do this for suffixes now and the rest is easy.

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

        Thanks man....i just have some doubts, which i would try to clear by myself, else would ask you. Good explaination, +1

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

One more solution for E.
Store stations in map: frequency --> set of stations.
Then sort all stations by range, from smallest to largest.
Now iterate over stations in order of increasing range.
For each station iterate over neighbour ([f - k ... f + k]) frequencies and count stations in the current range using set operations. Then remove current station from its set to avoid counting some pairs twice.
The whole solution is .

P.S. The only problem is that STL set cannot quickly count number of elements less than x. Thus this solution is painless only if you have your own set implementation with subtrees' sizes stored in nodes of BST.

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

    Very nice and simple solution! I implemented your solution with GCC's order statistics tree and got AC.

    http://codeforces.net/contest/762/submission/24472173

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

      Thank you! I didn't know about these cool GCC extensions :) I should definitely learn about them!

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

      In your solution ans should store total number of bad pairs. Could you please tell why you did ans-n instead of outputting ans.

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

Please explain D,i still don't understand.

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

    Let me try to explain my solution.
    Any vertical cut (segment between cells) in the grid can be intersected by any simple (that is, without self-intersections) path only in 5 ways (two first are top-down and bottom-up):

    
1a),1b)    2)     3)      4)
--|-->   --|-->  
<-|---          --|-->
--|-->                  --|-->

    Now you can maintain dynamic programming array dp[i, way],
    where i is x-coordinate of the cut and way is one of 1a), 1b), 2), 3) or 4).
    dp[i, way] is the largest sum of cells located to the left of the cut
    that can be traversed by a simple path intersecting the cut in the way way.

    For example, let's consider the way 2). If you draw all the possible cases on the paper, you should get

    The answer will be dp[n, (4)].

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

      can please you explain 1a & 1b a bit more clearly and what about going to the left? thanks for your kind help

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

        Let's consider any simple path going from top-left cell to
        bottom-right one. Surely it must intersect our cut. But in what way?
        If it intersects the cut only once, then it can be only the case 2), 3) or 4).
        Can it intersect the cut exactly twice? Of course no, because the path must
        end in the bottom-right corner. So it intersects the cut one or three times.

        In the latter case (3 times) the first intersection is left-to-right,
        the second is right-to-left and the third is again left-to-right.

        At first glance each of these intersections could happen in any of three
        rows, for example, the first in the 2nd row, the second in the 1st row
        and the third intersection in the 3rd row. But if you take a sheet of
        paper (and I strongly advise you to do so) and try to draw
        a (simple!) path connecting top-left cell with bottom-right one and intersecting
        the given cut in the described way you will certainly fail.
        In fact, there are only two ways to perform such intersection.
        The first looks like "top-down zigzag" and the second one like
        "bottom-up zigzag". These are cases 1a) and 1b) and there are no more cases.

        There is no need considering "going to the left" because we
        are talking about all possible simple paths connecting two given cells.

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

Easy to implement solution for E:

Time complexity: N * logN * (logN + K).

It is based on the idea of 2D interval querying, but taking into account problem restrictions uses Fenwick tree with map as a value(in this map — frequency is a key). Using the fact that map is ordered we can get all needed values with frequency = [f — k ... f + k] in logN + K instead of logN * K.

http://codeforces.net/contest/762/submission/24558456

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem F: "Now let's enumerate subtrees (rooted ones!) of T". Does The author mean "isomorphisms of T"?.

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

can Someone Explain What this error implies in java: Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).* I am new in programming as well as new in codeforce In advance Thankyou

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

    Just add public final keyword before the class keyword. like : 

    public final class <Class_Name>
{
...
}
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What might be the approach for problem D if instead of a 3xN, it was a NxM problem?

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

An alternative solution to Task E : 1. Sort the array on the basis of ri. 2. For each possible frequency, have an ordered set (It will store the x-coordinates). 3. Start traversing from highest to lowest ri, and for each frequency between [fi-k,fi+k], count the number of elements xj satisfying xi-ri<=xj<=xi+ri. The only those coordinates of elements would be present in the set whose r>=ri. After traversing through the frequency range, add the current xi to the corresponding set. My Solution

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hate to necropost, but I need some help, can anyone help me figure out why my code gets MLE here? https://codeforces.net/contest/762/submission/194307712

I am using 1e4 wavelet trees and the total memory consumed should be O(N) (N = 1e5), so I have no clue why this exceeds the memory limit. Any help is appreciated.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Didn't want to necropost, but have a question.

In problem C one may leave different strings to be the subsequence of $$$a$$$, with the same minimum deleted length. For example, if $$$a$$$ is abcdcba and $$$b$$$ is abdcdba, the answer may be any of abcdba or abdcba. I've tried some AC solutions, some of them output the first, and the others output the second.

But in both statement and output section of English and Russian statement(I use machine translate to read Russian), I did not see any words about multiple solutions.

I wonder whether the problem has such a testcase with this kind of input, and whether the checker checks correctly. Could you(or, anyone) please tell me(if I do not misunderstand the problem statement) the answer and fix the statement? Thanks in advance.

→ Reply