cyand1317's blog

Codeforces Round #431 Editorial
By cyand1317, history, 7 years ago, In English

Hi, dear contestants!

With the end of Codeforces Round #431 (Div. 1 and Div. 2), some might be complaining behind the screen that problems are too tricky or hard, or have been struggling with some supposedly solvable problem... Yes, this time problems seem hard, but anyways, I hope they provided you with something, say rating, fun, ideas, or experience. I don't want to see anyone losing confidence because of failure (bad luck) in a single contest — please, don't do so.

Here are the hints, tutorials and codes for the problems. Feel free to discuss about problems in the comments, and point out if something is incorrect or unclear. Thank you!

849A - Odds and Ends

by cyand1317

Hint
Tutorial
Model solution

849B - Tell Your World

by cyand1317

Hint
Tutorial
Tommyr7's solution (first idea)
Model solution (second idea)

848A - From Y to Y

by cyand1317

Hint
Tutorial
Kalinin's solution
Model solution with knapsack (!)

848B - Rooter's Song

by cyand1317

Hint
Tutorial
Model solution

848C - Goodbye Souvenir

by adedalic

Hint
Tutorial
Model solution

848D - Shake It!

by cyand1317

Hint
Tutorial
Model solution

848E - Days of Floral Colours

by cyand1317

Hint
Tutorial
O(n^2) solution
Model solution

Behind the scene and random things (read if tired of problemsolving)

Expand

Thank you for reading. Next round? Perhaps something more traditional, who knows? Believe me, I'll try harder if this happens.

Cheers! \(^ ^)/

UPD Packages for problems are uploaded. They are in Polygon format and contain everything including statements, tests & generators, validators & checkers, and solutions. You can download them from Google Drive or Baidu Drive.

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

Comments Comments (105)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

No hints for div 1 C?

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

I would hardly call it editorial...

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

    He said in the statement "Detailed tutorials will be available later."

    Though I don't really understand, why isn't the editorial done before the contest. Why schedule the contest, before the editorial is finished?

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

      Ah, I missed that it is not its final form.

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

    "Editorials" originated as things like commentary, related discussions etc. The tutorials are not fully ready by now but I think quick hints may help some. Thank you for your patience.

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

    When someone gets too famous for the super tricky problems in his contest

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

Having real tutorials would be nice. That way we could understand what the code is based on. For example what is the idea behind 848A?

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

    First add same characters together. If you add n characters, the cost will be . Though I can't prove there can't be a better cost, you can achieve it by adding the letters one another, so you have costs 1, 2, 3, ..., n which summarized results in the formula.

    Secondly you add same character groups together for 0 cost.

    For a given k you can always greedily take the highest x which for , add x same characters, and deduct from k. Repeating this process will result in a correct answer.

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

      It is actually not hard to prove that this is minimal. We claim that if the letter i appears cnt[i] times in the string, the cost needed to concatenate all the strings will always be .

      Consider any pair of letter in the string. If they're different, they will not contribute to the cost. If they're the same, the moment the string containing the first letter is concatenated with the string containing the second letter, this pair will contribute 1 to the total cost. Other than that, this pair will not contribute to the cost. Thus, the total cost is just the number of unordered pairs of same letters.

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

      Why can we greedily deduct? I did it like given n coins make a sum m but that was obviously an overkill. How to prove that we can use greedy for this one.

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

        When you concatenate 2 strings the cost is the number of pairs (from the first string, from the second string) for each letter so the total cost is the number of pairs for each letter because each pair will be counted once.

        The greedy outputs a string of O(sqrt(n)) length.

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

          We can take a maximum of 26 letters right? So what I did was dynamic programming to find which elements (taken any numbers of time) of the set {1,3,6,10,15,21..} will add up to k. But subtracting the maximum number less than equal to k also works. I couldn't prove that the number of characters used will be less than equal 26. How to do that?

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

            You might need to take more than 26 letters... Starting from 26 * 25 / 2 + 1 in fact you need strictly more than 26 letters.

            Edit: if you meant letters as in 'a' to 'z', as I said the output is O(sqrt(n)) so it's easily less than the limit.

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

            We work backwards greedily by taking the maximal element in the set you described and subtracting it from n at every step. Then worst case n is one less than an element in the set, or for some k. Then so after each operation, we get at most the square root of what we started with. Now it should be clear that 26 letters are more than enough, since n(1 / 2)26 <  < 1 + ε where n = 105.

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

              Ok got it. Thank you very much! I did an overkill by using dp there :(

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

                I also use the dp solution, but could you please explain why the greedy algorithm is correct?

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

              Nice!

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

          how do you prove the greedy algorithm is correct?

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

            Each letter you use, transform n into O(sqrt(n)). That converges faster to 1 than dividing by 2 (that would be O(logn) letters needed) so there are enough letters.

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

      Cost of adding n characters always is n * (n — 1) / 2. I prove it like this: Lets say cost of adding n characters is f(n), then: f(n) = f(x) + f(y) + x * y, such x + y = n. By induction if f(x) = x * (x — 1) / 2 and f(y) = y * (y — 1) / 2, then f(n) = n * (n — 1) / 2.

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

        I think this is a really nice and neat proof. I have never thought about using induction to prove this conclusion. Thanks a lot for sharing such a nice idea.

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

          You're welcome. Also there is another proof that I really like it.

          Consider a graph with n vertex and no edges at first (for each character we consider a vertex). Each time we merge x characters to y characters, that mean we connect edges between those x vertex to those y one. And our cost is equal to the number of edges we draw (x * y).

          At the end the graph is complete and the total cost is equal to number of edges of a complete graph with n vertex which is n * (n — 1) / 2.

          :)

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

      actually Gauss prove that every natural number is written as at most 3 triangular numbers

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

Div2B can be solved with randomized algorithm. You need to choose two points randomly and check if the line going through these points can be one of these two lines which we are looking for. All you have to do now is repeat this about 100 times and you can be 99.999...% sure that if answer is "Yes" you found it at least once.

Did anyone get AC using this method?

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

    When we have 3 leftmost points there must be a line which is going through 2 of those points.

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

    Yep , got accepted . Thanks for the idea .

    Submission

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

could not even solve A. i want to kill myself.

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

    Hello, the solution to this problem was kept on this. Think about it. If you want, I can explain 29975733

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

    Do not worry. As you practice more, you will do better. Trust yourself!

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

Can anyone please provide a more detailed explanation for div 2 D?

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

Is it editorial or just solution codes?

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

    Detailed tutorials will be available later.

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

Div2B. What if all of these 3 points are lying on 1 correct line?

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

    Then answer will be No.

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

      like (1, 1), (2, 2), (3, 3), (4, 5), (5, 6). Why no??

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

        it's yes

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

        You asked "What if all of these 3 points are lying on 1 correct line?" the case of only 3 points.

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

    doesn't matter , because we are searching the set of points which doesn't belong to that line in the solution above marked with visited[i] =false; if no points found then no; if one point found then yes; else we check the rest of points belongs to the same line and it's parallel to the first one

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

    The first idea works without modification.

    You will check the same line three times, which will find the solution if the answer is Yes, and fail otherwise, because there must be one line passing through all three points in this case.

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

Did anyone got accepted Div.1 C using sqrt query caching? i.e. blocking queries into sqrt blocks and solving the problem for each block. Time complexity of my solution is but my solution got failed (TLE).

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

    My solution with same time complexity passed(29992066).

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

      My solution is exactly the same as yours... I think the problem is I used too many vectors.

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

Could someone explain the solution to div2B? (29992706)

def chk(limit):
    return len(set(2 * yi - limit * i for i, yi in enumerate(y))) == 2

s = 2 * (y[1] - y[0]), 2  * (y[2] - y[1]), y[2] - y[0]

print('Yes' if any(chk(x) for x in s) else 'No')
→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    you need to find out is there exisit two lines

    y = ax + b1 and y = ax + b2

    such that every points on it, and each line should have at least one point, so you could check for three cases:

    1. first point and second point at the same line
    2. first point and third point at the same line
    3. second point and third point at the same line

    (just like Tommyr7's solution (first idea) above)

    and 29992706 just try to find out if there exist b1 and b2, by counting 2b

    y = ax + b

    2y = 2ax + 2b

    2b = 2y - 2ax

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

      when you find a,b when, for example: y=7 5 8 6 9 so we have x= 1,2,3,4,5 what will you do with your function: y=ax+b ?

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

        y=ax+b is a form of line, so if you got a, b, then you got a line

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

          thank you, btw, please answer me what is the main idea of Tommyr7's solution ?

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

            I think the main idea of Tommyr7's solution is that there only have 3 cases, just the same as what I've said above.

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

When I don't believe that div2 A is solving in so simple way and write dp :D

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

The problems were good yesterday. I was only able to solve only the first problem, but I got some satisfaction upon being able to solve it. It wasn't purely implementation-based, but also needed a good observation.

Overall,

  1. Short, clean statements.
  2. Problems with some insight, not purely implementation.
  3. Model solutions enclosed in editorial in a nice format with drop down menus and hints

I appreciate the writers of this contest for these points. However, it is difficult to understand for a beginner. Some more explanation would be good.

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

Div2D:

Dancers in the same group will move on the same x + y line (a line of slope  - 1), and however collisions take place, they will keep current relative order of x and y.

What does this mean? What is an x+y line?

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

    Their coordinates will always have the same x + y during movement. If A and B have the same x + y, and xA ≤ xB holds at the beginning, it will hold throughout the whole process.

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

Div2B In the first approach, " ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]); " I cannot make the sense out of putting a[2]*2-a[3] in the second argument. In the check function, author has assumed the starting point to be 1. Ugh not making any sense to me, someone please explain!

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

    The b argument is the interception of the line. With the third case it should be a2 - (a3 - a2) = 2a2 - a3.

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

really wonderful tutorial !

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

It would take a few minutes for the tutorial to get from Polygon to CF, stay tuned.

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

in question A how can u say if n is odd and a[0] and a[n-1] is "only case" where answer is yes.there may be some other cases......

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

    If a valid way exists, then n, a1 and an are odd.
    If n, a1 and an are odd, then a valid way exists.

    So this condition is necessary and sufficient.

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

      can you prove if n is odd or even and a[n-1] is not odd there cannot exist odd number of subsets[problem:849A]

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

        The answer is No not because of this. It's because if the last element is even, in every possible way to divide the sequence we'll have a segment that doesn't end with an odd number, which makes the whole division invalid.

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

          what if n is even and a[n-1] is odd.Thanks in advance.

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

            For an odd number of segments of odd length each, the sum of their lengths has to be odd (say, sum of three odd numbers is odd, sum of five odd numbers is odd etc.). So for an even n there is no solution.

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

              what if we have a sequence like 0 1 0? we can still get segment {1} which is odd?

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

                The entire sequence need to be divided, and all resulting subsegments should meet the requirement.

                In your case there will be two more subsegments consisting of only one element 0, which are invalid.

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

Div2 D What is the custom sort doing. My implementation required a vector of tuple and two more 2D vectors of pair of ints. Can you explain what is happening in your sort. I cannot follow through.

Also a general question, I have a hard time reading and understanding other's code. Any suggestions on how you approach it?

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

    For each x + y group, before everything starts, go down the left border of the stage and go rightwards along the bottom, record the order in which you meet dancers in it.

    After everything finishes, go rightwards along the top and then go down the right border and record the order. These two orders will be the same because they're actually sorting the dancers by their order from top-left to bottom-right, that is, "initial x values" (after moving them backwards in the first place) in the tutorial.

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

How to do 849B — Tell Your World if number of lines is a variable ?

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

    Thanks for the variation, I find it interesting :)

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

    I set a more advanced version of this problem for CS Academy this summer, feel free to try it:

    https://csacademy.com/contest/round-38/task/parallel-lines/statement/

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

    Great! Thanks both of you!

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

Found a test case for Div2 B but Can not find why the answer should be "YES"

Test case:

4

5 7 11 17

Any help would be appreciated .

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

is div 2 B test case 13 wrong?

5

-954618456 -522919664 -248330428 -130850748 300848044

try excel scatter chart

Grade outputs yes, but I don't think so

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

I don't understand how to build the segtree for div1C — How should the tree handle the b.first >= l condition while the segment [l,r] remains as a continuous segment?

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

    After dividing query on log to some nodes of segtree they transform to "get sum value of all b.first >= l from all elements which are controlled by fixed node", so if you sort all b.first in fixed node you get query on suffix.

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

      Thanks for the details, now I get it. I've never thought of building the tree in this way before, I was stucked with having a fixed size node simliar to 2D BIT... =P

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

      How to take care of updates?

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

I don't understand Div2D/Div1B , so can anyone help me to explain this problem more clealy ? (sorry for my poor English :((( )

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

Tutorial for 848B-Rooter's Song

Two points in the second paragraph, maybe it shall be...?

(xi-ti, 0) -> (xi, -ti)

(0, yi-ti) -> (-ti, yi)

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

Anyone who knows how to solve div1.C by Wavelet Tree?

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

I have got a better algorithm on div1.E.

At first we get a recursion, just like what the tutorial says.

Let g0(x) = g(x) * x2, g1(x) = g(x) * (x + 1)2, g2(x) = g(x) * (x + 2)2.

Then we use the generated function of sequence g0, g1 and g2,

as well as sequence f0, f1 and f2

Then we get equations below.

F0(x) = G0(x) + G0(x)F0(x)x + G1(x)F1(x)x3

F1(x) = G1(x) + G1(x)F0(x)x + G2(x)F1(x)x3

F2(x) = G2(x) + G1(x)F1(x)x + G2(x)F2(x)x3

Solve it, we get

We just need to calculate the first n+1 numbers of sequence f0, f1 and f2, so we can solve the equations modulo xn + 1,

The complexity is just O(nlogn), better than the algorithm mentioned above.

Here is my code.

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

    How do you solve the equations?

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

      The equations are all linear! Just like guass' algorithm, function G0(x), G1(x), G2(x) are all constants. At first we solve the previous two equations, we got F0(x) and F1(x), then there is F2(x).

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

    I had thought of solving the problem with polynomial multiplicative inverse, but due to my lack of familiarity with it, I kept the current constraints and the model solution. (Apparently I have a weak mind > <)

    Sorry for necroposting, but kudos! It's great to see a solution more elegant than the original one.

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

      BM: code

      Time complexity: $$$O(16^2 \cdot \log n)$$$

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

        Super cool! My solution was beaten again OvO

        Did you prove a finite order of recurrence first or find it through trial-and-error?

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

          It seems that there exist a matrix fast power solution by using these 3 formula(because G0(x)、G1(x)、G2(x)all can be calculated with Linear recursion):

          F0(x) = G0(x) + G0(x)F0(x)x + G1(x)F1(x)x3

          F1(x) = G1(x) + G1(x)F0(x)x + G2(x)F1(x)x3

          F2(x) = G2(x) + G1(x)F1(x)x + G2(x)F2(x)x3

          so what BM get in fact is matrix's Characteristic polynomial,then it is proved.

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

Did anyone got accepted Div.1 C using treap inside each node of segment tree? I am getting TLE with that approach, I expect the time complexity to be O((N+Q)log^2(N))

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

    I know your comment is pretty old, but here is my AC submission of Div1 C using segment tree of treaps 110138332. Hope it helps someone

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

I have a question for div1E, when calculating the final answer.

ans += g[i — 1] * (i — 1)_ * (i — 1)_ * f0[n — i — 1]_ * i _;

The basic idea of counting rotations without duplication is multiplying (i-1) if the second opposite pair appears at index i. However I thought this could lead to counting one answer multiple times. For example, consider n=9 (18 flowers) with opposite pairs of (1,10),(4,13),(8,17) This would be counted 3 times because the second opposite pair appears at index 4. However if you rotate two units, it becomes arrangement with opposite pairs of (1,10),(3,12),(6,15) which will also be counted because its second opposite pair appears at index 3.

If I misunderstood the solution, can someone help me?

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

    The original arrangement is counted three times: rotated by 0, 1 and 2 units anti-clockwise, respectively. The derivative you mentioned is the original one rotated by 2 units clockwise, hence it's not included in this case but counted in its own case instead.

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

For Div2 C, this can also be used. Each number can be represented as the sum of 3 triangular numbers. ( A variation of the 3 squares theorem ) Just find 3 squares such that their sum is equal to 8*n+3.

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

I cannot help expressing my gratitude to the author,especially [Prob.E Shake it].Because the words expressed so clearly and I think the problem gave me much great thoughts.

→ Reply