nvmdava's blog

By nvmdava, 4 years ago, In English

Hello Codeforces!

We are glad to invite you to the upcoming Codeforces Round #618, which will start at Feb/09/2020 17:05 (Moscow time).

Each division will consist of 5 problems and will have 2 hours to solve the problems. There will be an interactive problem in the round. Learn more about them here.

This round was prepared by rotavirus, rotavirus, rotavirus, rotavirus, antontrygubO_o and nvmdava. We would like to thank MetB, stefdasca, cfalas, gamegame, hugopm, Redux, dorijanlendvaj, imbr92, CP_Sucks, 300iq, Rahul, AryaKnight, 244mhq, manish.17, Um_nik, mblazev, pseudocoder10, aryanc403, box for testing and their invaluable feedbacks. And special thanks to MikeMirzayanov for making this round possible and antontrygubO_o for coordination of the round.

We hope that you will enjoy the problems we've set, and wish you good luck and a high rating.

Upd 1. Some of us might be online at AC discord server after the round ends.

Upd 2. Score distribution:

  • Div2: 500 750 1250 1750 2000
  • Div1: 500 1000 1250 1750 2250

The contest is over. Congratulations to the winners.

Div1:
1. jqdai0815
2. TLE
3. Radewoosh
4. zhouyuyang
5. Benq

Div2:
1. ntftxdy
2. qsmcgogo
3. ZhouShang0817
4. sarthakmanna
5. nantfaker

Editorial

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +95 Vote: I do not like it

What about rotavirus

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

5 problem! may be going to be hard problems :(

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Sorry for my bad memory, but I remembered that rotavirus and rotavirus were the same person

»
4 years ago, # |
  Vote: I like it +136 Vote: I do not like it

Round prepared by Eva? I'm ready to 998244853 modulo

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Missed Newbie testers again.

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Happy to see Educational Round 82 between Round 618 and 619 !!! Back to Back Feb12 and Feb13.

»
4 years ago, # |
  Vote: I like it +578 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +128 Vote: I do not like it

There will be an interactive problem in the round.

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

First round of codeforces 1.0!

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Thanks a lot for hosting the contest on a Sunday! Let's make it a regular thing, it ensures a lot of people are able to give the contest.

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

    I like the varying times of Codeforces rounds, this way everyone gets some chances to participate. If you do it on Sundays only (or mostly Sundays), it means that a lot of people get the chance every time and other people never get the chance.

    Also, a lot of people do OpenCup rounds on Sundays.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Good luck 4 all :D

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Rounds consist of 5 problems are of high quality mostly.

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

The round to become MASTER or expert not totally sure :D

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    You will become expert or will remain CM i guess, bcz the round has only 5 problems which means difficulty is gonna be high.

»
4 years ago, # |
Rev. 2   Vote: I like it -47 Vote: I do not like it

300iq makes a round.

Interactive problem:

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

What's the score for each problem.

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

the rounds that the number mod3 is zero, are my lucky rounds!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how fast the score distribution is!

»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

A + B + C + D... Dinner.

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

2E/1C http://www.usaco.org/index.php?page=viewproblem2&cpid=419

Second solution is basically it.

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

How to solve Div.1 C(Div.2 E) in time limit?

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

    notice that it makes no sense to do updates with overlapping ranges. keep a stack with ranges of best updates (keep the sum and the amount of elements) add elements of the array 1 by 1 from first to last, while it is convenient to merge the last segment to the one before it, do so (if the average of both is less than the average of the one before the last)

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C?

So many people did that, I couldn't even think of an approach. :(

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

    Think of the operation as set difference.

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

    Same..I think i should go back being a cyan :(

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

    We need to notice that

    f(x,y) = x & (~y)
    

    The answer is

    a[0] & (~a[1]) & (~a[2])
    

    So, only the first element matters.

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

      How did you derive it ? Only thing which I could make out during the contest was that f(x,y)=x-x&y.

      P.S: I got it. I am just dumb.

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

        One observation is that the subtraction is never going to carry over any bits, since the (x | y) operation makes sure all bits of y are set.

        This lets us rewrite $$$f(x, y)$$$ in terms of bit operations only: it takes x, sets all bits of y, and finally unsets the same bits. This corresponds to x & ~y.

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

        You don't need to use f(x,y) = x & () if you know f(x,y)=x-x&y

        if specific bit exists in 0 or 2+ elements, result of this bit will be 0 anyway. so the idea is to find the largest element which contains unique bits and set it as first.

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

    Think about what the operation actually means. (x|y) — y simply means, remove all the bits from x that also occur in y.

    Now, the way the function is phrased, it means pick some value $$$a_1$$$ and remove all bits that are not unique to $$$a_1$$$.

    After recognizing this, the solution is simple. For each bit from 0 to 31, check if it is unique. Then for each number, calculate answer for this number as just sum of all set bits that are unique. Pick maximum of all this, and put that number in the first position.

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

    (X|Y) — Y means the bits which are set in X but not in Y — (1)

    Given expression can also be written as f(a1, (a2 | a3 | a4 | ....an)) Using (1)

    Now the answer is dependent on just setting the first element.

    Hope this helps :)

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

    APPROACH — Think in bit level, f(a, b) ex- f(6, 3)= f('110','11')='100' every '1' of b present in a is removed. so try to take a0 with 1's have occurrence only in that number and if their are many such numbers take the maximum one. sol — 70657021

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2. C ??

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

whats the approach to div 2 C ?? :(

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

    Let f(f(...f(a1,a2),a3...)=X.
    Following points are to be noted:-
    1. x=0,y=0 then f(x,y)=0
    2. x=0,y=1, then f(x,y)=0
    3. x=1,y=0 then f(x,y)=1
    4. x=1,y=1 then f(x,y)=0.
    Let us consider the jth bit of all a's , then jth bit of x = f(f(...f(a1[j],a2[j]),a3[j]..)).
    In order to get jth bit of x as set bit, we should arrange the elements in such a way that jth bit of a1 is 1 and jth bit of rest of the elements is 0.(WHY? Since f(f(...f(1,0),0,0...))=1).Thus our target is to have the jth bit of a's as follows, a1's=1,a2's=0,a3'=0........an's=0
    Thus in order to get the largest x, we will iterate from MSB(31st bit) and try to find which number have its jth bit as set and rest all have jth bit as 0.
    If we are not able to find then any arrangement will give 0 as answer. My solution 70646858

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem C :<

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

for div 2 D, I tried this approach: if n is even and slope of opposite sides are equal, then yes else no, can someone say what's wrong with this approach. this is my submission https://codeforces.com/contest/1300/submission/70677064

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

    should be equal and parallel

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

      Oh wow I did that and got wrong answer. Guess I must have a bug in my code. And I thought the solution is really wrong because I could not convince myself that this must work.

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

        Same for me, I assume this is due to a numerical precision issue. Anyway instead of calculating lengths of each edges I could've compared the x & y components on each vector

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

          Oh yes, it was an overflow, should just use long long all the time. Guess I do not deserve to get rating

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

      What is "equal" here?

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

        equal means the lengths are equal

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

          Okay, thanks.

          But, is it not that if two opposite sites are not same len, then some other two sides cannot be parallel?

          PS: Perhaps I better wait for editorial, thanks anyway.

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

            take a regular octagon and shift any its side by epsilon.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 13   Vote: I like it +8 Vote: I do not like it

              I didn't get this, on shifting a side by some distance, won't some other pair of opposite sides become non-parallel

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

                shift while not changing other sides' directions

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

                  got my mistake! really good question. Thanks for helping!

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

            that's exactly why I wasn't checking for the lengths to be equal

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why are almost all tasks based on math?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Div2 D the second case answer is no? It seems to me that there are always A, B in P such that for all (x, y) in T (A, B) = (x, y). Could you give me (x, y) that the vector couldn't be made by the set of points in P.

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

    Visualization for second case is in the description

»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Thanks problem setters for the problems <3

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

intersting problems. I did not prove anything and just guessed the solutions for div1 b and div1 c. They both worked haha

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What is/are the hacking cases(s) for Div1B/Div2D

»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

How to solve Div1C

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

    Build a lower convex hull with points being (i, s[i]) where s[i] is the sum of the first i values, in addition to the point (0, 0). Each edge in the convex hull represents an operation on the interval [x1 + 1, x2] where x1 and x2 are the x-coordinates of the endpoints of the edge.

    My submission: https://codeforces.com/contest/1299/submission/70681667

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

    Convex Hull (though I did not manage to submit at the end).

    You have to minimize the first element by choosing a segment $$$[1, i]$$$. Any operation on the segment $$$[l,r]$$$ which $$$1\le l\le r\le i$$$ or $$$i\le l\le r$$$ is unnecessary. Besides, if operating segment [l, r] which satisfies $$$l\le i\le r$$$ before [1, i] can cause the first element to be lower than operating [1, i] solely, then with some mathematics, you can prove that operating [1,r] is more optimal.

    Therefore, you should find $$$i$$$ such that $$$S_i / i$$$ is minimum where array $$$S$$$ is prefix sum array. Then you fill all element from $$$1\rightarrow i$$$ with $$$S_i/i$$$. Trim the subarray $$$1\rightarrow i$$$ and repeat. The solution is optimal.

    Since $$$n\le 10^{5}$$$, we can use Convex Hull trick to squeeze the solution into acceptable complexity $$$O(nlogn)$$$.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

1cc-1.jpg

»
4 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

The Div1B figure mislead me for over 1 hour.

Reading quiz orz.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks for the contest! Problems are very interesting)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are corner cases of div 2E? And why was this approach giving wrong answer: Traverse from right to left and calculate smallest average possible by including a[i] and in the process, also maintain the span of the current avg starting from current index to some index in right. If a[i] is smaller than current average, then set current avg to a[i] and span of current avg to 1. Finally print the answer with final values like this:

                DecimalFormat df = new DecimalFormat("0.00000000000000");
                double dmx=avg[0];
                for(i=0;i<n;i++){
                    dmx=Math.max(dmx,avg[i]);
                    out.println(df.format(dmx));
                }

My actual solution: https://codeforces.com/contest/1300/submission/70679283

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

How to check if a graph has a nontrivial cycle with xor zero? I only know how to do it with gaussian elimination, but that's too slow.

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

    actually the Gaussian elimination works because if there are more than 5 basis cycles, their costs are linear dependent.

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

    Actually, there's only less than 400 different vector spaces in $$$Z_2^5$$$,so after some preprocessing, you can do gaussian elimination in $$$O(1)$$$ , and do dp where state is current vector space. It works in $$$O(400n)$$$ .

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

      Coded that with an additional log and got rekt by TL :(

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

      Oh, I misread your question. As for checking, just consider an arbitrary spanning tree, and consider all cycles consisting of exactly one edge that is not in the tree. Every nontrivial cycle can be constructed by 'xor'ing the cycles of the above type. So checking if a graph has a nontrivial cycle is equivalent to checking linear independence of all cycles of the above type. This can be done by union-find.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this solution SortWithArray is getting timelimit but the same implementation with the vector got AC sortWithVector , how could this happen ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    you have declared array which has size 100001 and it should be min. 200001 because it has to store 2*n elements.

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Worst feeling ever: code general polygon similarity just to get WA due to overflow then guess the solution after 4 WA because it's div1B and people solved it fast af.

»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I wrote an easier version of div1c a couple of years ago here. The bounds for that allowed for n^2. Luckily, there was a description of how to do O(n) in the discussion.

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

    Damn, my bad, downvote this comment if you want to.

»
4 years ago, # |
  Vote: I like it +76 Vote: I do not like it

Geometry Geometry Everywhere

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

When the ratings will be available? I hope to become newbie :(

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for your contest :3 such an amazing performance, I will become purple <3

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve the precision problem of the Div2.E(Div3.C)1299C - Water Balance

When I used float to save my answer, I got WA 70681208

When I turn to double, I got TLE 70681660

So sad:(

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

    The problem said that you shouldn't read input as doubles. You can read it as integers and then convert them to doubles. E.g:

    double a[N];
    
    int x;
    cin >> x;
    a[i] = x;
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It works! Thank you very much!

      But one more question, what's the difference between them? I can't quite get it.

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

        Imagine that you don't have built-in functions to read input except one function that reads a single character, which is getchar() in C++. Try to implement a function that reads double using getchar(), and implement another function that reads int.

        You'll observe that the first one involves more operations that the second one, and also will be performing double operations instead of int operations, hence will be slower.

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

          Yes, that's right. I never thought it in such a way. It's a totally bad coding habit.

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

      Oops, It still doesn't work when n comes to 1e6. TLE again. :(

      I have changed my approach to save number, now it will output immediately instead of saving it in the array.

      Here is my code: 70690087

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

        I don't understand. It seems your solution is $$$O(n^2)$$$?

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

          You are right. How silllllly I am. I will try another way.

          Sincere thanks!

»
4 years ago, # |
  Vote: I like it +167 Vote: I do not like it

 jqdai0815 you surely hacked Rating predictor.

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can anyone tell me what went wrong with my approach for D? It failed on test 71.

I checked if polygon is symmetric. To do that, I found out the coordinates of centroid and shifted origin to centroid (hence redefined all the vertices accordingly). since our centroid is at origin, for polynomial to be symmetric, if polygon has vertex(a,b) then it must also have vertex (-a,-b).

What is wrong with this?

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

    I checked if it was symmetric too, it failed :(((

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

    Never use a map with double type as keys. Instead multiply all the coordinates by n and use integers as map keys.

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

      I don't think that's the problem, mine doesn't work either, it's probabbly the concept of the solution :(

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

      Test case where solution is failing:

      n = 6 {0,0} {2,0} {4,1} {3,2} {-1,2} {-2,1}

      So I don't think issue is with using double. I manually checked it, it does look symmetric to me, still WA.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        Well we are just very unlucky then my friend :(

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can 1D be solved without the condition「there isn't any simple cycle (i. e. a cycle which doesn't pass through any vertex more than once) of length greater than 3 which passes through the vertex 1」?

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

    Yes, you can solve it with an additional state.

    Delete vertex 1, solve for each connected component separately. For each component, do a dp that's almost the same as 1D but with an additional state being the distance to vertex 1 if it's already connected. Then you can just add the cycles when you choose to add other edges or not.

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

    If someone wants to read more elaborate description based on tfg's concise idea, I have written it down here: https://codeforces.com/blog/entry/73763?#comment-579653

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to understand problem div.2 D. It would be great if anyone could explain to me...

»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

My contest rank and overall rank now converge:)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does leaving cerr prints in your code give idleness limit exceeded and take so long to TLE? I waited 5 minutes just to fail in pretest 10 :/

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    #ifndef LOCAL
    #define cerr if(0)cout
    #endif
    
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Btw on one onsite competition I made a typo and wrote cer instead of cerr in that define, so my actual cerr in code remained usual cerr and it made the judge go crazy as well giving unreasonable judging times. It seems to be some general issue or something that is easily gotten bad.

»
4 years ago, # |
Rev. 2   Vote: I like it +66 Vote: I do not like it

Why does CF-predictor show that Δrating of jqdai0815 is +687?

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

    It seems that for somewhat reason cf predictor thinks that jqdai0815`s rating before contest is 1500 .

    2020-02-09-22-55-30

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

Div.2-C was good problem.Nice Contest!!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

div2 problem E could be solved in Monotonic stack. If one's averge is greater than the previous one, we can merge them. The problem can be solved in O(n). Besides, I want to say that is the the data of problem E is really unstrong. My friend accept the problem in O(n^2). If there are 1e6 number, and first 999999 numbers are 1000000, while the last number is 1, he won't get accept while get TLE.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

>tfw you finish writing C and then your PC crashes

It does crash from time to time but I really hoped it wouldn't happen during a contest...

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Eventually the user whose maximum rating >= 3600 became two. :)

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I have solved Div2D/Div1B during practice now using such an overkill solution. It may strengthen the understanding of Geometry, or it may be just useless. The approach seems correct for the most part, except case handling in one specific case that seems too hack-ish to be true. I have to admit, I was shooting for something slightly different where my solution would fail if it did exactly what I wanted it to do. With some accidental bug it gets accepted. I am not sure if the approach is correct but can someone either prove this correct or give a counterexample or some explanation about it?

Here is my approach:

  • For odd-sided polygons the answer is just no.
  • For even-sided polygons, I search through the consecutive lengths for periods of length $$$\boldsymbol{1 ≤ x ≤ \frac{n}{2}}\textbf{.}$$$

$$$\textbf{( i.e.,}$$$ a number $$$\boldsymbol{1 ≤ x ≤ \frac{n}{2}}$$$ such that for all $$$\boldsymbol{0 ≤ i ≤ n - 1}:$$$ $$$\boldsymbol{length[i]}\textbf{ = }\boldsymbol{length[(i + x)}\textbf{ mod }\boldsymbol{n]}\textbf{).}$$$ Or in other words, a sequence of consecutive side lengths of size $$$\boldsymbol{x}$$$ that repeats.

Obviously $$$x$$$ must divide $$$n$$$.

I output YES only if there is either a period of length $$$\boldsymbol{< \frac{n}{2},\;\;}$$$ $$$\textbf{or}$$$ if there is period of length $$$\textbf{exactly}$$$ $$$\boldsymbol{\frac{n}{2}}$$$ and $$$\textbf{no sequence of side lengths of size }\boldsymbol{< \frac{n}{2}} \textbf{ repeats.}$$$ The special handling for $$$\boldsymbol{\frac{n}{2}}$$$ I've done accidentally, but it's necessary for AC.

The 3rd testcase is an example of where there is a period of length $$$\boldsymbol{\frac{n}{2}}$$$ but no sequence of side lengths smaller than that repeats.

In the rest of the test cases. Some test cases have a period of length $$$\boldsymbol{\frac{n}{2}}$$$ and also smaller sequences that repeat. An example is Test: #62. Their answer is NO

This is my solution. I used Main-Lorentz algorithm to count the periods of all lengths by concatenating the side lengths array to itself and dealing with it as a string. It runs in $$$O(n\;log n)$$$ time. I used this implementation from e-maxx, but modified it to only count the number of repetitions of each length without caring about the starting/ending indices. Note that a period of length $$$\boldsymbol{x}$$$ if it exists corresponds to repetitions of length $$$\boldsymbol{2x}$$$. There is a period of length $$$\boldsymbol{x}$$$ if the number of repetitions of length $$$\boldsymbol{2x}$$$ is $$$\boldsymbol{≥ n}$$$ in the concatenated length array (as in, a repetition for every index of the original array).

Regardless of the exact implementation to find the period lengths and/or repeated sequences. Can someone say if this approach is correct? If it exactly mirrors the state of the convex polygon having equal and parallel opposite sides?

The weird case handling of period exactly $$$\boldsymbol{\frac{n}{2}}$$$ is due to this line in the code if(it == M.begin()) break; I break out of the inner loop for repetitions of size $$$\boldsymbol{≥ n}$$$, (originally wanted to exclude $$$\textbf{2n}$$$ and $$$\textbf{n}$$$), but I forgot to break out of the outer loop.

»
4 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Nobody:

Me: get a successful hacking attempt, only followed by jqdai0815's successful hacking attempt

Epic gamer move: get a successful hacking attempt at 1:59:58

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

About Problem 1C: https://codeforces.com/contest/1299/submission/70683614

This code can get Accepted.

But Why this code get Wrong answer on test 18 when I change eps to 1e-9?

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

And I change eps to 1e-10 will get Wrong answer on test 14 .

I thought I wanted to make eps smaller than 1e-9.

Because of 'Your answer is considered correct if the absolute or relative error of each ai does not exceed 10−9' .

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be Editorial?

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Btw, exercise in English language: find everything wrong with grammar/syntax in "how many are there such subsets, that, when removed, there is not any".

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

When will editorial be published?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have studied Div.2 E / Div.1 C editorial. But I got WA at test case #7... I think it's an overflow but I cannot find it.. Help me.. https://codeforces.com/contest/1300/submission/70754718 (Sorry for bad english and bad code)