Eva's blog

By Eva, history, 7 months ago, In Russian

Authors:
d2A: Eva
d2B: nvmdava
d1A: nvmdava
d1B: Eva
d1C: nvmdava
d1D: Eva
d1E: antontrygubO_o

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +110
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been translated by Eva (original revision, translated revision, compare)

»
7 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

How is (a|b)-b == a&(~ b) ?

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

    you may see it with an exemple :
    f(5,3) = 5|3 — 3 = 7 — 3 = 4
    binary representation : 101 &(~011) = 101 & (100) = 100

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

    A | B has all the bits where A or B have 1, set to 1.

    A | B — B has only those bits set to 1 where A has a 1 but B doesn't have a 1. If B had a 1, then A | B would have a 1 in that position and — B would set that bit to 0.

    So it is equivalent to A & ~ B

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

      i got it (a|b)-b=a&~b,but how to approach towards the answer from there

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

        Only the number which you put first is taken as it is and the others have ~ added to them. So maintain prefix and suffix of ~ &. Answer would be maximum of pref[i] & $$$a_i$$$ & suff[i] for all i. pref[i] is the value of all the elements from 1 to i-1(using the ~ & operation) and suff[i] is the value of all the elements from i+1 to n(using the same operation).

        The editorial explains it better so you might wanna read that :)

        Check this submission for reference.

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

          When you put INT_MAX as pref[0] and suff[n-1], how come it does not affect the final output? pref[i]&arr[i]&suff[i] would probably be bigger when pref[i] is INT_MAX?

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

            https://codeforces.com/contest/1300/submission/78506793 not necessary to take int_max as pre[0] && suff[n-1] it will not make any sense,check my solution(^_^)

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

              Of course it can be done without it, my question was, why the INT_MAX didn't affect the final result.

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

                int max is 2,147,483,647 in binary it is (1111111111111111111111111111111) so if it is( & with ~ar[0]) the result will be ~ar[0],think over it

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Nice. Got it. Thanks

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

          can you please explain why we are finding pref[i] & ai & suff[i]? what will it do? our purpose is to find the number which should be placed first in the series??

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can check my submission 71017457. It is based on the editorial.

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

      Understood this one rather than the editorial. Thanks!

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

    a|b can be written as: a + b — a&b

    subtract both side by b =>
    or a|b — b = a + b — a&b — b
    or a|b — b = a — a&b
    or a|b — b = a&(1-b)
    or a|b — b = a&(~ b)

    Edit : Note that 1 here represents all the bits where a is set as any set bits apart from it is out of our concern

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

      In 2nd last statement, you have used the identity that a&b — a&c = a&(b-c). How do you prove this?

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Hint : a — b = a&( ~ b)
        Although, the common element I took out was U or INT_MAX Edit : Just to clear out confusion here ,
        I didn't prove a&b — a&c = a&(b-c) ,
        rather a&U — a&c = a&(U-c) , where U is considered as all bits set

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          How is a-b = a and (not b)? Take a=5 and b=3. a-b=2 and a and (not b)=4

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

            I am mentioning this again, Note that b is a subset of a in my cases all over
            Back to real one: a&b is a subset of a

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

            This is only valid if all bits that are set to 1 in $$$b$$$ are also set to 1 in $$$a$$$

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why we are taking a common element and why are we taking it as INT_MAX? Please explain this part.

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

      Can you refer to any good resource to study bitmasking?

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

        Apart from practice sites which you can easily google,
        I really like the content of this website for bitmanipulation tricks :BitHacks

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

        CSAPP's Datalab

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

      can you share some links or material to read all these properties related to binary numbers?

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

    For (a|b), let's define those bit positions which is 1 in b as POS, what (a | b) does is to make those POS in a become 1 (0 — > 1, 1 — > 1), and what (-b) does is to make those POS in a become 0 (1 -> 0), so as a result, what (a|b)-b does is to make those POS int a become 0, which is equal to a&(~ b).

  • »
    »
    7 months ago, # ^ |
    Rev. 6   Vote: I like it -14 Vote: I do not like it

    Corrected Solution :-

    (a|b) — b

    Now, a-b = a and (not b)
    So

    a|b — b = (a or b) and (not b)
    = (a and (not b)) or (b and (not b))
    = (a and (not b)) or (0)
    = (a and (not b))
    = a & (~ b)

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

    (a|b)-b = a^b — b = ab' + a'b — b = ab' + a'b — b.(a + a') [since a+a'=1] = ab'+ a'b — ab — a'b = ab' — ab
    = a.(b' + b') [since b' = -b] = a.b'

    [here, a' means complement of a]

    hence, the proof.

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

      How

      (a|b)-b=a^b-b
      

      ?

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it -8 Vote: I do not like it

        please read the problem statement, it's clearly mentioned that "|" represents or operator

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

          https://www.imageupload.net/image/JFnTp

          See the screenshot it is having that it is a bitwise OR operation.

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

            Oh, sincere apologies for the mistake.

            so now the proof would be:

            a|b = a+b-a.b => a|b-b = a+b-a.b-b = a-a.b = a.(1-b) = a.b'

            Once again, apologies for the mistake, and thanks for pointing it out :)

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

    You can imagine it using Venn Diagram if you have heard about it.

»
7 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Please add a reference to this editorial in the round announcement post so that people can find it easily. Thanks.

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you for the wonderful contest. I really liked problem C of div2. The trick was to see what the operation is exactly doing!

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I hate when the code is not included.

»
7 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Finally became a specialist after veryyyy long time \(^o^)/

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the logic behind Div2/E solution?

I am not able to get it. Someone please help....

»
7 months ago, # |
  Vote: I like it +114 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2 D Aerodynamical was an amazing problem! Heres simple C++ implementation:https://codeforces.com/contest/1299/submission/70686672

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for very fast editorial :)

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Guys, does anyone have a non-geometric solution for Water Balance?

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

    Is not it slow to get AC?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Yes. You can see all the water tanks as a succession of groups. Initially all groups have size 1. While you can find 2 adjacent groups, such that the left group has greater average volume than the right group, merge them. Here is my solution. It's not very well written and might be hard to read.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Here is my O(n) solution based on deque.

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

      Using non-decreasing queue to solve this problem is a very simple way. Monotonic queue and monotonic stack both classical algorithms. Thank you for providing such a simple way.

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

      I like your solution. Can you give more insight on usage of 'eps'. What might happen if we will not use it.

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

        I just wanna make sure it will be true when tmp == Q.back().val.

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 3   Vote: I like it +6 Vote: I do not like it

        I think it is necessary to use 'eps' only when calculate whether two double number are equal.It mean we can't use == to calculate whether two double number are equal.If we want to calculate, we can use follow way. assume a and b are double.

        if(abs(a-b)<eps)
            cout<<"equal"<<endl;
        else
            cout<<"unequal"<<endl;
        

        In my opinion, I don't think it is necessary to use 'eps' when use < > <= >= operator. Sorry my poor English

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

    here is my solution I used stack

    Yo should notice the fact that the each number must be smaller then the next numbers

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Wish I'd noticed the simplification in C... Ended up using a segment tree on |

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

    could you explain how? I have just learned segment tree and I am unable to understand how I could use it here.

»
7 months ago, # |
Rev. 6   Vote: I like it +28 Vote: I do not like it

I solved Div1_C with CHT.

We want to know minimal value of a[1] so we can binary search it. When we get it we should get minimal value of such a[j + 1] that (a[1] + a[2] + ... + a[j]) / j = a[1] and so on.

Now we must understand how we can efficiently binary search. Let x be value that we want to check. So this inequality should be performed:

(pf[j] — pf[i — 1]) >= x * (j — (i — 1))

Where pf[i] = a[1] + a[2] + ... + a[i] This can be represented as:

pf[j] — x * j >= pf[i — 1] — x * (i — 1)

Left part nothing else than line equation. So we can store lower CHT. When we check x for corectness we should also binary search for line at CHT that contains x.

Thus we achieve complexity O(n * log n * (log 10^6 * ε ^ -1)) where ε is needed precision.

But this solution will get TL. So we need further optimizations.

Note that answer is non-decreasing sequence. So needed x only increase. We can use pointer technique for searching line at CHT that contains needed x and than binary search at some interval.

Thus we achieve complexity O(n log (10^6 * ε ^ -1)).

This is my solution https://codeforces.com/contest/1299/submission/70688494.

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

    I'm interested in your approach. Could you tell me what is CHT?

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

    Really fascinating !!. But there is a question I want to ask:

    In your code, I saw this :

    for (int it = 0; it < 60; it++){
                ld md = (l + r) / 2.0;
                int ps = st;
                ld bas = ld(pf[i - 1]) - (ld(i) - 1.0) * md;
     
                if (ld(K[ps]) * md + ld(B[ps]) - bas >= E)
                    l = md;
                else r = md;
            }
    

    So this is where you binary search for the minimum answer x. But $$$ps$$$ seem to remain the same during this loop (equal to $$$st$$$). So you always work with line $$$K[st] * X + B[st]$$$ with every $$$x$$$ from 1.0 to 1e6. I have just learned CHT and I think each line should hold the max/min in an only interval, so different $$$x$$$ will have the max/min in different intervals, right.?

    Could you clarify this please? Thanks so much.

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

      Yes, each line should hold the max/min in an only interval. But I search for needed interval (such interval where our x lays) with pointer technique and when I found it I start binary searching.

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

        So every x from 1.0 to 1e6 get max/min at that same line? Am I missing something?

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

          No. To this interval belongs only values from [fr[st], fr[st + 1]) (or from [fr[st], +oo) if our line is last). But it makes no difference because value more than right bound we can't achieve (I think it's clear) and value smaller than left bound we can't achieve (because optimal value belongs to other interval that doesn't fit (we check this while moving the pointer)).

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

            Thanks so much! I understood it. And actually we don't need to binary search for x at all. x is the x value of cross point for line -(i — 1) * X + pf[i — 1] and line K[st] * X + B[st]. I test this with your solution and get accepted. Link

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

              I understood your optimization. Thank you too!

»
7 months ago, # |
Rev. 2   Vote: I like it +123 Vote: I do not like it

About 2E/1C, there is an arguably simpler "greedy" solution using a stack in $$$O(n)$$$

The stack algorithm

Here is my implementation 70666728

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

    Awesome!

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

    it is TLE with py3

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

      Not really. This problem is heavily IO bound, and in Python3 a lot of that stuff is slower because they changed to using unicode strings (I'm using Python2 just to easily get around that). But there are ways to make Python3 fast as well.

      For example I took your code and added my fastIO template to it 70718663, and now it runs in 1887 ms.

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

        very thanks, it`s awsome

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

    Isn't it more or less equivalent to the editorial solution? Since this is basically how you find the convex hull anyway.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Hahaha, it definitely is xD. These 78 upvotes and "Awesome!" comments xDD

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

      As stated in the editorial, the solution to the problem is a lower convex hull. So any algorithm solving this problem will find a convex hull, and in particular this stack algorithm can be interpreted as creating a convex hull.

      However I would argue that it is possible to get an intuitive understanding of the stack algorithm without thinking about it as finding a convex hull. It's this intuitive understanding that I'm trying to highlight.

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

    One stupid question, is it always possible that any problem that has solution using CHT,can also be solved by stack,if yes or no what is the reason.Thanks in advance.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome, Helped a lot !!!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the useful tutorial <3

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2B?,i didnt understand editorial

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a submission to div2E / div1C that runs in time on C++11?

I swear I'm so pressed rn:

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

    By far the majority of the runtime comes from the IO. For example see 70688591 by neal running in 249 ms. He has a custom template for printing doubles. narut tested to remove neal's fast IO template in 70694340 and now it runs in 1902 ms.

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

    As pajenegod mentioned problem here is IO. Try changing cin/cout. I'm sure printf/scanf with c++11 runs faster. E.g. -
    Printf/Scanf gets ac whereas same soln got tle on cin/cout

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

      I thought the ios:: thing at the beginning made cin/cout the same performance as scanf/printf?

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

        Still cin/cout cant match printf/scanf. We are printing more than 15e6 here. Here in c++17 printf/scanf was ~600ms faster than cin/cout on submissions I made during testing.

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

          dang it, thank you very cool

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

        It's true for ints but cin/cout is very slow on doubles.

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

    Checking for central-symmetry is equivalent to checking if each pair of opposite sides are equal and parallel. You can do this easily using integers only: no doubles needed.

    Check my code here: 71015952

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

      HINT: To prove that central symmetry is equivalent to opposite sides being equal and parallel, we can use congruence of triangles.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C could be solved by repeating the greedy We are going to keep track of the segment sum, and size Make N 1-lengthed segments. Starting from an element, make a new segment by adding elements. If the element is bigger than average, stop and make a new segment. If we complete whole thing, do this again from the newly formed segment array. If it doesn't change, print it. It looks like N^2, but it somehow passes.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it the case that the isosceles trapezium after joining accordingly will make a hexagon but is following the property of symmetric around the center. ( Div 2 : D, Aerodynamic)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Isosceles trapezium does not have central symmetry. A central symmetry is when a line passing through the center of symmetry has equal length on both sides of the polygon.

    For you case

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

i understood a|b-b is equivalent to a&-b but then what we have to do. i was unable to understand editorial. Can anyone explain me in detail. Thanks in advance.

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

    Consider 4 no.s : a b c d , Now, f(x,y) = x&~y

    The question requires: f(f(f(a,b),c),d) which is essentially val = a&~b&~c&~d.

    Notice that you have to maximize val by positioning any element at first position and remaining at any position after and for that,
    you can iterate and for any element i find ~a[0]&~a[1]...&a[i-1] & a[i] & ~a[i+1]...&~a[n-1].

    Find when this value is maximized and put the element at i at front. That's your answer

    Sample submission : Jiangly

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

      thanks a lot for this clear explanation. it always helps a lot for beginners like us

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

      for array 9 1 2 5 the output of Jiangly this code is 9 1 2 5 which has function value 8 .. but isn't maximum function value 9 is possible with array reordered as 5 1 2 9 ?

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

        5 1 2 9 gives 4 tho (Think of it like the value cannot be bigger than a[0] because of & property)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know the problem of my code.

Help me, please.thanks.

The problem is RUNTIME_ERROR.

https://codeforces.com/contest/1300/submission/70701084

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your array size is 2e4, the input size is 1e5.

    Even if Runtime error is removed, your solution will give TLE nevertheless

    Hint
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Very thanks.

      I use the quhanks.

      I use the quick sort.but still TLE

      This is my new code,what's the problem?

      https://codeforces.com/contest/1300/submission/70725391

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

        Why not use the available sort function, instead implement your own?

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

          I think the quick sort is the fast methed.

          The function , I have used.But have too many problem.

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

          I just do not understand why ,one group of 100000 data , the code is right. but five group of 100000 data , the code is wrong.

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

            your sort function is not a O(nlogn) sort when the input array is a strict increasing array like 1 2 3 4 5 6 7 ....

»
7 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I have a DP solution for 1C .

dp[i].FIR means the smallest average number of an array ai~ar (i<=r<=n)

dp[i].SEC=r

now we can update the dp in "O(n^2)" ,LIKE THIS:

for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
	      if(dp[j+1].FIR<(sum[j]-sum[i-1])/(j-i+1)){
			/* sum[i]-> Prefix Sum */
			j=dp[j+1].SEC;
			continue;
}

then if we know the smallest prefix average number from each position.The problem become much easier!

We just need to perform the operations from left to right by "Greedy".

You can also see my code in my "submissions".

Although it is like an algorithm of O(n^2),but in fact it is very fast.

Update it is O(n)

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

    It's linear O(n) because in the inner loop you merge some ranges so you need to merge n times in total

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

EDIT: Actually, never mind.

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

    Your argument proves that for any $$$(x_0, y_0)$$$ in $$$T$$$ you can embed the vector $$$\left(\frac{x_0}{2}, \frac{y_0}{2}\right)$$$ inside $$$P$$$. It doesn't prove that the point $$$\left(\frac{x_0}{2}, \frac{y_0}{2}\right)$$$ actually lies inside $$$P$$$, which is what you really need. And this is false in the general case, so your proof has to somehow involve $$$P$$$ being centrally symmetric.

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

      You're right, my mistake. Thank you!

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I think Dishwashers should never prepare contests again

»
7 months ago, # |
  Vote: I like it -31 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Div1D definitely should have been posed without this stupid condition about no cycle passing through 1 of length >3. It can be solved as noted by tfg here: https://codeforces.com/blog/entry/73664?#comment-579444 (that's not the best description, but it can be made working). First thing is that this condition is super ugly and unnatural so that it would be much nicer without it and second thing is that finally there would be something to think about in this problem making it significantly more interesting to solve as well.

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

    Sorry mr grandmaster but I don't understand tfg's solution

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

      Yeah, I understand this description might be quite cryptic, so let me explain how I think of this (or should I say "sorry ms grandmaster, I should have expected this"?)

      Delete 1 and for every connected component calculate subspace spanned by cycles in it. Now let's focus on adding edges to one of these connected components and then merge partial results (which are mappings from 374 subspaces to number of ways we can get them in this particular component) to get overall one. This merging introduces *374 overhead to complexity, but that's not something huge (and actually for smaller components we will not get all 374 possibilities, so it will be significantly less in practice).

      So how to solve it for one particular components with some edges from 1 added to it? For a fixed component we divide edges into ones from spanning tree and ones outside of it (each such gives one vector to basis). Let's assume we fix our favourite edge from 1 to that component and add it to spanning tree. Every following edge that we decide to add from 1 we treat as non-tree one and it gives us one cycle whose cost we are able to calculate and add it to the subspaces dp. So we are able to solve it if we add *n to complexity by fixing first added edge. Key observation here is that edges actually can be partitioned into 32 equivalence classes. Instead of calculating cost of the cycle directly we can fix some favourite vertex in that component r and calculate cost of new cycle as xor of costs of paths from 1 to r using first added edge and from 1 to r using new added edge. There are only 32 possibilities for cost of path from 1 to r using first added edge what adds *32 factor to complexity for particular component.

      Overall complexity for original problem was $$$O(374n)$$$ while now it is $$$O(374 \cdot 32 \cdot n + 374 \cdot 374 \cdot n)$$$, where first part comes from dp for each component and second one comes from merging results from different components (and that part should be actually significantly faster).

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

        Understood, thanks. It's sad that this possibility is wasted

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it +18 Vote: I do not like it

        Actually that's not exactly what I had in mind, you can have dp with states [i-th edge][current subspace][height of the first edge you've chosen in the current connected component or if you haven't chosen it yet]. This way it's actually O(374 * 32 * N) because you don't have an O(374) transition to merge stuff, just an O(1) transition but with an additional state.

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

        Sorry but I have a problem about Div1.D that how to caculate the number of subspaces?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    The most challenging part is the edges between nodes which are connected to 1; I don't know how for each subspace count the number of ways to delete edges adjacent to 1 such that remaining edges form this subspace

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello in 1299B, how can i avoid precision errors checking whether the midpoints of segments connecting the opposite vertexes coincide? I am receiving WA test 53

https://codeforces.com/contest/1299/submission/70740871

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Division 2-B : I'm unable to understand the editorial.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain the solution to aerodynamic? I couldnt quite get it asto why a figurewith central symmetry would be an ans.

»
7 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Not sure if anyone discussed it already, but I find the following solution for problem E (Div 2) easier and more intuitive. It is based on the fact that if the prefix is computed optimally, when you are at position i, all you have to do is to iterate from i to 1 (lets say using j) and see if you can obtain a better solution by applying the operation on the segment [j, i]. If you can, then move j, if not, then stop (since prefix is optimal, it means that it is sorted, so you dont need to check smaller indexes since they also have smaller values). Now this is just a brute force, but it can be optimized by representing a subsequence having the same value as a pair of (sum, number of elements). So you end up with O(n) complexity. 70909016

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here how I solved Div 1 B - Aerodynamic (Div 2 D) in contest:

Step 1: Use GeoGebra to plot test 3 and realized that the opposite sides are parallel.

Step 2: Go back to the statement and realized that it's also true for test 1.

Step 3: "Coincidence? Nah, I don't think so. Let's code it"

My submission: 70663347.

I still don't know how to prove it. Could someone help me?

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

    equal and parallel sides imply the central symmetry of the polygon

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in div 2 question number 2 what does this line mean k+l+2=n+1 why 2 is added

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B, is it not possible dividing the third test case array as follows which gives minimum difference as 1....? [2,20,4,16,8] and [3,17,5,13,13] such that |4-5|=1

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See the definition of median again. It says the middle element in a SORTED array. In your example you are considering an unsorted array.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try including code next time.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me understand proof behind Div2B ?
Not able to understand editorial proof.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is wrong with these codes 82719965 and 82722047 and 82720401? Please help.

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In 1300C - У Ану есть функция i have used this:-

ll a1=-1;
for(int i=32;i>=0;i--)
{
	int count=0;
	int index=-1;
	for(int j=0;j<n;j++)
	{
		if(a[j]&(1<<i)==1)
		{
		count++;
		index=j;
		}
	}
	if(count==1)
	{
		a1=index;
		break;
	}
}

what will happen if we are unable to find a1? How to take a1 for the solution ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My approach to C:-

If any bit occurs more than 1 times in the array then it will always be 0 in the final answer so we just need to take in account the bits having count 1 in each number and then sort in descending order each number according to this new value..

My submission 86092229

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the easier explainantion

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are doing this to check the jth bit
    and it works for(i=0;i<n;i++) { cin>>a[i]; x=a[i]; for(j=0;j<32;j++) p[j]+=(x>>j&1); }

    can you please explain why for(i=0;i<n;i++) { cin>>a[i]; x=a[i]; for(j=0;j<32;j++) p[j]+=(1LL<<j)&x; } this code of mine is failing ![user:dhananjay_049]

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a much easier solution for C.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Editorials are meant to help new comers who want to learn but editorial of C is not easily understood by beginners.Very poor editorial I must say.