Блог пользователя zoomswk

Автор zoomswk, 5 лет назад, По-английски

Thanks for participating; we hope you enjoyed the tasks! Look at the bottom of this post for some more challenges.

Feel free to ask in the comment if you have any question. If you have a different solution from ours, share it too. :D

Our approaches

Div2A
Div2B
Div2C
Div1A / Div2D
Div1B / Div2E
Div1C
Div1D
Div1E

Challenges

Div2C
Div1A / Div2D
Div1C
  • Проголосовать: нравится
  • +210
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

The contest was awesome! Thank you.

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Wow fast tutorial Thanks for your effort :)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why does the answer is 1 or -1 or 0 for Div2A while I was trying to print the value like it was given in the example test cases, 4 for example test case one and 0 for the second?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If a positive integer works, you can use any positive integer (within the bounds indeed). I'm saying that 1 is one possible answer. You can print 2 or 4 if you want!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why ans can't be 2 for positives,-2 for negative number if more and 0? doubt for -2. please help

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It can. It can be anything till it has right sign.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It wasn't accepting. should I share my code with you if you could check once ?

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            The problem with your code is where you do ceil(n/2) because n/2 is an integer divison. When n = 5, ceil(n/2) = 2 because 5/2 = 2 in integer divison and ceil(2) = 2. Instead you want ceil(5/2) = 3. So either do ceil((double)n/2) or ceil((n+1)/2) so you get the correct value to compare to.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how does the time complexity in div2 C is n^4?

»
5 лет назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

Really interesting, how many people solved problem E without using google?

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I am curious about the Div1C Challenge part. How's that possible?

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Just wondering if anyone has a solution to div1 D that runs asymptotically faster than NsqrtN.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Div1C also can be solved by using SAM.

But I still can't figure out how to solve it when m ≤ 105.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What does SAM stand for? Suffix array m______?

    Anyway, see https://codeforces.com/blog/entry/65520?#comment-495120 for now.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is 'SAM'?

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    Let , where x is an SAM node and α is a Latin letter, denote the position we will get to when we transfer x on the edge with every bit of the Morse code of α successively. We'll get a DAG G = (V, E), where V is the node set of the SAM and . Therefore, the answer is the number of routes that starts with the root of the SAM, and ends up in another node.

    Let f(x) denote the number of routes that ends up at node x. We'll solve the problem offline, so that the SAM of the whole 01-string has been built. Define a sub-SAM of a prefix of S is a subgraph of the SAM and it accepts exactly all of its substring. When we append S[i] to the sub-SAM of a prefix of length i (i.e. S[: i] in Python), the sub-SAM enlarges, and the new nodes has no edge out. So, we can run a DP to get f(x).

    Time Complexity .

»
5 лет назад, # |
Rev. 5   Проголосовать: нравится +24 Проголосовать: не нравится

An O(n) solution for Div1A/Div2D.
https://codeforces.com/contest/1129/submission/50470292

We can use the structure max-queue, which supports standard push back and pop front, and additionally tells the maximal value in the queue, in O(1).
So we first push each dist(0,j) + n * (out(j)-1) * n + dist(j, e), for each 0 <= j < n.
Then for each 0 <= i < n, in order to take the next station as the beginning, pop the frontmost value (let it be x) and push (x + n), and we consider each value in the queue is decreased by exactly 1. This means that the station we left is delayed by a circle, while the following stations are approaching by 1.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

May I ask why the Div2B Greedy solution works? Namely, min(|xi−xi+1|+|yi−yi+1|,|xi−yi+1|+|yi−xi+1|) for each step, leads to the global minimum?

Anyone can helps?

Really appreciate it!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Also curious about this, I strictly used |xi-xi+1| + |yi-yi+1| and that worked.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      @gtatutors-ca too:

      If we assume xi < yi for each 1 ≤ i ≤ n, then that will work perfectly!

      There are actually only six cases to consider:

      1. xi < yi < xi + 1 < yi + 1
      2. xi < xi + 1 < yi < yi + 1
      3. xi < xi + 1 < yi + 1 < yi
      4. xi + 1 < xi < yi < yi + 1
      5. xi + 1 < xi < yi + 1 < yi
      6. xi + 1 < yi + 1 < xi < yi

      In cases 1 and 6, it doesn't really matter who goes to where. The distance travelled will be the same.

      In cases 2, 3, 4, and 5, you can see that xi should go to xi + 1 and yi should go to yi + 1 for optimality.

      Does this address your question?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        This makes sense, I didn't think about all these cases. I automatically assumed case 2.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        By "If we assume xi < yi for each 1 ≤ i ≤ n, then that will work perfectly!" Did you mean xi < x_(i+1)? Cause otherwise there will be much more cases other than 6.

        Also, I can follow your idea by assuming xi<x_(i+1). But why can we make this assumption?


        Now I understand clearly, the greedy approach get the right answer!

        Many thanks!

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Oh sorry I messed up while listing the cases. Now the post is fixed. I meant xi < yi, and as you said, we cannot assume xi < xi + 1.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        still dont get u its the proof for only 1 step

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          We can consider each step independently, because no matter what our decision is (about who goes where), we will have the same problem to solve.

          If may help to realize that it doesn't matter who stays where during each step. We only need a bigger picture of where THEY are (but not where each of them individually is), and that is determined for every step at the very beginning regardless of our decision.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Even more interesting: why even Greedier solution works?

    Logic: For every pair of i-th tier shops, Sasha takes a walk to leftmost(smaller index) and Dima to rightmost(bigger index).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let's say from xi to xi+1 is a round, because either player 1 or player 2 arrived at xi+1 or yi+1 as mentioned in the tutorial, it doesn't matter how they get the next round. So in each round, we can get the minimum answer, and totally in every rounds will be the optimal answer.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

For Div1B,we let n=2000 and , and a0, a1, ..., a1997 = 0,a1998 =  - d,then a1999 = x + d.

And then the correct answer is 2000x,and Alice's answer is x + d ,the difference is 2000x - (x + d) = k,so 1999x=k+d,,so we can let d = 1999 - k%1999 to make x a integer.

Because k ≤ 109,x is about 5 * 105

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Nice! Interestingly people's approaches to this task are very varied.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    %%%

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    that's a good idea!

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    when I thought about this problem I ended up with some equations and a lot of variables but what I can see from your solution and the solution in tutorials that you assumed values for the variables then you proved that they always will produce the right result

    my question is : how did you thought about this problem do you assume the values first then try to prove them or you have some logic that force you to assume these values then you confuse your self by probing them mathematically !!?

    values like : (-1 for a0 in the tutorials ),(your 0's in the beginning of the sequence)

    Thanks in advance.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      At first,I made some mistakes about the problem,I mistakenly think that Alice's answer is k and get a WA,and then I fixed the mistakes and get this method.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        sorry, but you seem to not understand me well I just ask you about the intuition behind solving such problems , the way you thought about it to get the solution

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I'm sorry for my poor English.

          Well,there are three variables,n,x,and d.And We can find that x will be smaller when n is bigger.Because n ≤ 2000,so we want to make x smallest,so I let n=2000,and find a smallest d.And it conforms to the problem.

»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Am I the only one who in Div1B handled k ≤ 106 with outputting

1

 - k

?=)

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

About Div1D, I don't understand the part of 'The Real Thing'.Is it a complexity proof? (Well we can just update f(l,r) using bruteforce according to some accepted codes)

Anyone can help?Thanks!

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

for div2-D challenge, I am thinking about any data structure which supports us to push element in back, pop element in back and gives me the max value. if there any data structure, i think i can construct O(n).(as we can write dist(s, i) as a function of dist(0, i)).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for div2/d "that the only thing that matters is the last candy to be delivered." what do you mean by last candy for a source...is it the one which take max time to deliver to destination for a particular source

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Least time to deliver for a particular source. The one that takes the most time should be delivered before. Do you see why?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really sad that I didn't recognize that the error in my solution to Div2B was a simple overflow until after the contest ended.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how the number of over-counted sequences are calculated in 1129C - Morse Code using LCP ? can someone explain ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The number of over-counted sequences can be calculated by considering the suffix array of T. Namely, for each two adjacent suffixes in the list, we over-counted them by g(l,r) with l and r denoting the corresponding indices of their longest common prefix (LCP).

    The number of over-counted sequences is the sum of g(l, r) with l and r defined as in the above.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, but you just copied and pasted what written in editorial. Actually, I have never solved Count distinct Substrings problem using Suffix Array, but I figured out using google.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

O(n) solution for Div1A/Div2D : codeforces.com/contest/1129/submission/50443015

Let's define x[i]=n∗(out(i)−1)+dist(i,e) , where dist(a,b) and out(i) represents the same thing as in the editorial and s the current node. now, if we look for every i what is dist(s,i) we will obtain something like this:
suppose n=4;
i=1 : 0 1 2 3 | i=2 : 3 0 1 2 | i=3 : 2 3 0 1 | i=4 : 1 2 3 0 |
so, for i=1, the answer will be max(x[1]+0,x[2]+1,x[3]+2,x[4]+3) and when we move to i=2, all values decrease by 1 except for the first value, which increases by 3 => the new maximum will be either the previous maximum-1 or x[i-1]+n-1. When we get to i=3, again, the maximum will be either the previous one or x[2]+3. So we only need to check the maximum once and then we will know which is the new one in O(1) for every position.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Can someone explain the answer to Div2D, test case 6, when the starting station is 40? As far as I can understand, the only stations that we need to consider are 3 and 49, because they are the ones that need 2 rounds, since they have 2 candies. Therefore, for 3, we can choose the last candy to deliver to be 31, which is the one that is closest. Therefore, we would need 50 * (2 - 1) + (31 - 3) + (3 - 40) + 50. I add the 50 at the end, so that the distance between the starting station (40) and the station with the candy (3) is positive. In this case, the distance would be (50 + 3 - 40) = 13. This would result in a total of 91, and not 93. When we do the same operations for the second station (49), we result in an even smaller number: 50 * (2 - 1) + (50 - 49) + (49 - 40) = 78. Therefore, the answer would be 91, which is the max(91, 78. Where am I wrong?

Input
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    actually it is 39 33 that makes the situation worse...

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Oh so it's not enough to only take the stations with the maximum number of candies. I can now see why. Thank you.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I tried to solve DIV1C in online fashion. Approach: For every new input say ci (c='0' or '1') I have to add the possible number of english alphabet strings for all suffix strings that are not included yet. I used dp for computing possible number of english alphabets from i= j to 0. I used set with hashing to check if a string is included or not. The complexity of the solution is however same as in tutorial (O(m^2log(m))). But my solution is giving TLE. If someone finds something wrong, correct me please.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anybody help me with div2D i didn't understand the tutorial

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you point out where specifically you got lost in the editorial?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    ok. name source s, considering station i and destination d. let's assume, source station is 1. let's consider the station i = 5. then, let's take out(5) = 10 that means that 10 deliveries should be given from station 5. now, to give 10 deliveries, you have to cycle through station 5 for 9 times.(you know why, commonsense). and, you have to go to station 1 to station 5. then, after 9 cycle, you have to go to another cell(to delivery from 5 that's dist(5, d)).

    now, go to the greedy approach, we can't minimize the 9 cycles. what we can minimize is the distance between i = 5 and d(taking the minimum distance from i = 5 to any destination). now, is this the answer??? .... nope...

    you may got mistake on some area. you have to consider all cells not any particular cells. what we did is the minimum from s = 1 for a particular cell(i = 5). we have to do this for all.

    when we are done doing that, we have to take maximum.why??

    let's say result for s = 1 and i = 5 is 19 and result for s = 1 and i = 8 is 29. what that means?

    from s = 1, delivering all things from i = 5 costs 19, and delivering all things from i = 7 costs 29. what would we take, if we take 29, in the 19th step, we would deliver all things taken from i = 5. if we take 19, we would not consider the case of i = 7.

    So, we would take the maximum.

    and, that last thing wasn't mentioned in the editorial(to think on your own).

    if you need, you can see my code 50476745

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hate the way tutorials say something like "and having this we can compute that" without further explanation. The solution is not obvious for everyone. Like I really don't get what happenned in "The Real Thing" part in Div1D.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Problem E contains an interesting subproblem. When determining the direct children of a vertex, we are trying to discover a hidden array of booleans. To do so, we are able to query for the sum of any subset of the array's elements. The suggested approach in the editorial works within the constraints of the original problem, but is not the optimal strategy w.r.t minimizing worst-case number of queries. Is anyone familiar with literature treating this problem?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I’d be interested to know too! Do you have a better strategy? I can only think of D&C which will probably give roughly the same number of queries in the worst case (but probably much better on average).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you solve 2c in o(n^3)? Im assuming dsu but not sure how?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Spoiler
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

About Be Positive Is it entirely necessary to select 1 or -1 for answers — I thought it did mentioned that its ok if division result is having fraction like 2.5 etc and selecting any number should satisfy as long as result is a positive number for positive and negative number for negative. Besides an example did mentioned 4 as the answer. Sorry if i am missing something .

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's not necessary to choose 1 or  - 1. If 1 is ok, 4 is ok too. Likewise, if  - 1 is ok,  - 27 is ok too.

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
A solution to Div1C Challenge!
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why in Div2C we consider going from source set S to destination set T directly without going to any other intermediate set of cells.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    because you can only build a single bridge.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The question says — "To help Alice, you plan to create at most one tunnel between some two land cells." how can one be sure of building only one bridge? why can't we build a bridge between set A and set B, and then between set B and set C, if A is the source and C is destination and B has more than 1 land cell.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        The thing is: if you need to construct a bridge from set A to set B, and then another bridge from set B and set C, you are in fact building two bridges, which is not a possible solution.

        Also, keep in mind that you can build a bridge from ANY land to ANY land, so even a bridge from point <0, 0> to <50, 50> is still a thing.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D it is not necessary to store q(i) for i < 0. f(x, R) is defined to be the number of elements which appear exactly once in the segment f[x...R]. By definition, f cannot be negative. Hence q(i) = 0 for any i < 0. It is sufficient to store q(i) for .

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your definition of what is stored in each block is different than ours (according to your code). Note that R is the right endpoint of the block, which is different from r.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve d2c in o(n3) ????

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think my solution for Div1C is m^2, can someone check it? https://codeforces.com/contest/1129/submission/50547727

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there a correct algorithm for the first paragraph of Div2/E faster than O(n ^ 2)?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Another O(n) solution for Div1A/Div2D. 50724905

Consider some station i. The front array to store maximum steps when ending with station (1~i-1). The back array to store maximum steps when ending with station (i~n).

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I was surprisingly able to solve Div1E using only questions of the following type, despite the seemingly significant loss of information:

Given a set S of vertices and another vertex v, is v on the path between two vertices of S?

My approach was to root the tree at 1, find all the leaves, then add the other vertices to the tree in random order. To add a vertex x, first sort all the vertices already in the tree by depth and then binary search to find a shallowest vertex y that is in the subtree of x (which must exist because all the leaves are already in the tree). Let z be its parent. Add x as a child of z and for every other child of z, check if it needs to be reparented to x. This can be done efficiently with divide and conquer.

It can be shown that this uses queries (expected).

Code: 50803526