chromate00's blog

Codeforces Round 1009 (Div. 3) — Editorial
By chromate00, 13 hours ago, In English

Well, that was a blast, certainly. I hope that you... learned a lot from the contest. I wouldn't say "enjoy the contest", I know most of you hate geometry, I get you. But please do remember that, at least I did try my best to make every problem as high quality as possible. Like, if you don't get familiar with thinking about geometry now, you might never get familiar with it in the future. Though I apologize that E was quite hard, I suggest you to upsolve or read the editorials of the tasks you could not solve. I am telling you, it will be an experience that will make you improve much more from now.

Solution codes will be posted after the open hack phase. They are now added.

Spoiler

2074A - Draw a Square

Editorial
Code

2074B - The Third Side

Editorial
Code

2074C - XOR and Triangle

Editorial
Code

2074D - Counting Points

Editorial
Code

2074E - Empty Triangle

Editorial
Code

2074F - Counting Necessary Nodes

Editorial
Code

2074G - Game With Triangles: Season 2

Editorial
Code
  • Vote: I like it
  • +84
  • Vote: I do not like it

»
13 hours ago, # |
  Vote: I like it +50 Vote: I do not like it

Geometry dash ah contest :p

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

    E :(

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

Solved E on pure luck, 310074961 The if condition is so stupid from me because earlier I was getting TLE on TC30, and then I mistakenly added the stupid if condition (which queries n-2, n-1, n) repeatedly after 50 queries which somehow got me AC which I do not deserve.

→ Reply
  • »
    »
    13 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    Worst E ever. I appreciate that the author thought of such a creative idea but still Im not conviced this was a good E

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

    I could not kill all deterministic heuristics. I was simply unable to. And, well, I tried my best, leading to an interactor that is $$$308$$$ lines long. If I want to kill all of them I could put $$$100$$$ inputs, which indeed kills the Codeforces platform before your solution

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

      Yes thats understandable, with a problem which involves probability, you always have to and unintentionally leave room for a solution which gets AC with no proof. I also take it that thats the reason why hacks are disabled because so many solutions (including mine) are so easily hackable

      → Reply
»
13 hours ago, # |
  Vote: I like it +62 Vote: I do not like it

With high probability, I can say that the number of participants who guessed $$$E$$$ without proving the bound of queries on $$$75$$$ is more than $$$75\%$$$

→ Reply
  • »
    »
    12 hours ago, # ^ |
    ← Rev. 2   Vote: I like it -26 Vote: I do not like it

    We are programmers; not mathematicians !! So, I guess it is not necessary to prove our approach during the live contest!! Y'all are free to disagree !!

    → Reply
  • »
    »
    12 hours ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    With high probability, I can say that the percentage of participants who believed their solution was wrong is more than 75%.

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

    I literally guessed it so bad

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

I didnt know x+y = x^y + 2(x&y)

how cooked am i chat

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

I submitted my solution for E just to try (actually, I thought it was wrong), but it got accepted... Why is it correct?

310125203

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

    Same with mine, can someone tell me if there is a proof for this approach or was i just lucky 310070577

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

      if i say in simple words then "probability of this question to be asked in exam is 0.0001% so you don't study that question and that question didn't come in your exams" same is for this question "probability of this question to get wrong answer is very less so you just submit it and get accepted."

      → Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think I deserved an AC for my E solution: 310075413

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

For anyone wondering about the solution of D, the reason why you can compute for all N circles at each value of x without clocking O(N*M) solution, is that you're only computing points on the circumference of the circles which is bounded by 2*pi*M.

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

    Umm.. Couldn't quite get that, can you please elaborate?

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

      For each circle do this: go from y=0 to y=r[i] and for each y calculate the maximum and minimum x that lies within this circle (this takes logn time as i used sqrt ig) and ding this for n circles each inner loop runs r[0]+r[1]+...r[n] times which is m.

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

    That's what got me stuck a lot. I tried hard to determine the exact rectangle to choose for any point on the axis. I believe if a jth point lies inside $$$k_j$$$ rectangles, then the number of points is bound by $$$m \over avg(k_1, k_2, ...)$$$, so the total number of rectangles to check is $$$O(m)$$$.

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

Why does E exist

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

I couldn't do E because I thought, "What if they use the exact test case where they are chasing my choice?".

With some probability, everything can be done in O(1) ig

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

    You receive a point that's inside your triangle and swap with a random point of your triangle. Even if the interactor tries to ruin your life, you have a very high probability of significantly decreasing the area, after swapping with one of the points

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

      lol tell that to my 18 WAs

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

        link

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

          this tragedy perhaps the implementation isnt exactly like the editorial. oh well

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

            Yeah you have to swap with the random vertex of the triangle. The point is that either the interactor gives you a good point(for any swap the area will decrease significantly), or a bad point(for some vertex after the swap the area will be almost the same), but notice that for any bad point there is some good vertex, and you have a pretty high probability of picking this vertex, and the interactor can't predict that. In other words the interactor can try to make some swap bad but there will always be some good swap.

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

Legendary

→ Reply
»
12 hours ago, # |
  Vote: I like it +12 Vote: I do not like it

It is actually possible to solve C in O(1)

https://codeforces.net/contest/2074/submission/310059528

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

    Wow can you please explain the solution? I am so curious.

    → Reply
»
12 hours ago, # |
  Vote: I like it -31 Vote: I do not like it

I wanted to comment something useful, but E isn't letting me do that.

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

    Ok listen up, for C, XOR is addition and subtraction without carry !

    → Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell me what's wrong with my solution of D, https://codeforces.net/contest/2074/submission/310145808

basically tried to fix y coordinate for each circle, to get 2 x coordinates, rest is kinda similar to the original solution.

→ Reply
»
12 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

Geometry wasn't geometrying today -.-

→ Reply
»
12 hours ago, # |
  Vote: I like it -12 Vote: I do not like it

E is a poor question. The problem states that the interactor is adaptive, which led me to mistake it for a proof problem. Because I think that as long as I can't guarantee that there are no points in my triangles, the interactor will definitely beat me.

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

    You will eventually have no points inside your triangle, after repeatedly swapping one of the points of the triangle with a point inside the triangle, the more difficult part here is that it will be fast enough(if you swap a point with RANDOM vertex). Well for any point that interactor picks, you might have a "bad swap"(after swapping, the area will be almost the same), but for at least one point of the triangle you have a good swap, and a pretty high probability of picking this point(you have only 3 points), and the interactor has no idea what point you will pick.

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

      Yeah someone with similar code like me but he cycled one before like I went from 3-2-1 he went 2-3-1 and he got wa and I got AC

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

        that is unfortunate, but technically an advanced interactor could break both of those

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

          Thank God I am safe due to no hacks XD

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

            If hacking is possible, then no one will be able to pass this problem.

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

              Yeah I believe we can make hacks for every solution that there will always be possible way to cross the 75 queries limit

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

                with good random seeded with time it would be very hard to do

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

        I just noticed that I didn't explicitly mention in the initial version of the comment that it's important to swap with the random vertex, not in some predetermined order, because the interactor can predict this order(but as you mentioned some solutions like this have passed by luck)

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

          then my passed purely by luck XD as I didn't knew about randomisation before this problem tbh.

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

      This problem itself is very creative, but perhaps due to language reasons, I misunderstood some of the hints in the problem statement. I have considered multiple times, as the solution say, using random points to shrink the triangle area to get a solution that might work. But in competitive programming, "might work" usually means "won't work," which made me hesitant to submit.

      → Reply
»
12 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

where to practice questions like E?

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

GeometryForces

→ Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

W contest! Nice problems!

→ Reply
»
12 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

anyone know any other questions like E? i want to make sure i avoid them

→ Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Mathforces!

→ Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I was solving the E question in the last few minutes and I have no idea how this solution got accepted This submission could have much much more than 75 queries in a worst case scenario

How did it get AC?? https://codeforces.net/contest/2074/submission/310144435

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

The way author hint on problem D with m bound to solve is true gold. It really saves my contest performance this time.

`the sum of radii is exactly m∗.`
`∗Is this information really useful? Don't ask me; I don't really know.`
→ Reply
»
12 hours ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

Worst E of all time. Not just because the proof of the question is too hard for a E, but also because a lot of people were able to do it on sheer luck, worsening rank.

→ Reply
»
11 hours ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

310109380 Solution of C. Why Binary search working ? Any proof? Note : suppose x^y = z. z can be x+y-1 maximum and x-y+1 minimum

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You mean my 10 WA submissions of E were all unluckily under the 1.8 * 10^-20 probility? I have tried 4 different method to change the triples which ask for. At last AC by srand() and rand()? What a poor problem

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

    Your solution is wrong because it always pops the first point and pushes the point to the back. You have to randomly choose which point to pop.

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

Very misplaced problems E should be C C should be D D should be F F should be E

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

On problem E, I ended up testing the 3 triangles formed by the inside point and each pair of the other vertices and continuing with the new triangle formed by these 3 interior points (if solution not found yet). But I'm not yet sure that this is equivalent to the editorial solution minus the probabilistic approach. Mainly because it looks like I use 4 queries to reduce the space by at least a factor of 3. If anyone can explain, I'd appreciate it!

https://codeforces.net/contest/2074/submission/310129128

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

Is it an AD of Geometry dash? it's a good game by the way ;)

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

D was nuts.

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

    Can you please help me understand the editorial or your approach (if it's not the same) for D?

    → Reply
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

here is a solution for C in O(1) //here

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

My solution to G passes with $$$O(n^4)$$$, should this happen?

https://codeforces.net/contest/2074/submission/310074015

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

It felt more like a Geometry Olympiad than a programming contest.

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

Fun fact: A very assuring hint about E's solution was that they disabled hacks and guaranteed a fixed number of test cases. This pretty much implies that the intended solution relies on random and they didn't want participants to suffer from their "weak" random solutions being hacked. Of course, even without such restrictions, the intended solution can still be random if the chances to pass are high enough, but we all know that chromate00 is too kind to let such a massacre to happen :)

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

    thanks to him my solution without randomisation passed and will not be hacked XD

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

    He (and I) believe this is the only correct way to set randomized solution problems. But ofcourse it comes at the cost of giving away information.

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

      Whats the point of such problems? what do they teach i found E extremly useless.

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

        It teaches you that randomization is sometimes useful.

        → Reply
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting observation in C:

  1. For x of form 2^k or 2^k-1, there doesn't exist any y which can give you a non-degenerate solution.

  2. For rest of the numbers, getting the leftmost closest 2^k-1 will always result in a degenerate solution.

Solution: https://codeforces.net/contest/2074/submission/310084628

Note: Got the observations by analyzing the patterns generated by brute force

Got no formal way of proving this, please let me know if anyone can help with the proof.

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

    This is what I came up with as well.

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

    Proofs:

    Let's denote x^y as z.

    1.

    1) Let x = 2^k for an integer k. y < 2^k implies that y&(2^k) = 0 = y&x. x⊕y = x+y-2*(x&y) = x+y = z. x+y <= z -> There is no y, satisfying the given conditions.

    2) Let x = 2^k-1 for an integer k. y < x implies that y&x = y. x⊕y = x+y-2*(x&y) = x+y-2*y = x-y = z. z+y = x-y+y = x <= x -> There is no y, satisfying the given conditions.

    2.

    Let x != 2^k and x != 2^k-1 for any integer k. Let i denote the most significant bit of x, j denote any other set bit of x, k denote any bit lower than i and being unset (i, j, k always exist). Then, by construction y = 2^i-1. x+y >= 2^i+2^j+2^i-1 >= 2^(i+1), z's most significant bit is i, therefore z < 2^(i+1) <= x+y holds. y < x+z holds because y < x holds by construction. x < 2^(i+1) — 2^k. z >= 2^i and y = 2^i-1 implies that z+y >= 2^(i+1)-1 and z+y > 2^(i+1) >= 2^(i+1) — 2^k > x. All conditions hold -> y = 2^i-1 satisfies the given conditions.

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

    You are right. This leads to an $$$O(\log x)$$$ solution.

    The editorial tells us that $$$y$$$ must have at least 2 on bits — one matching $$$x$$$ and one not matching $$$x$$$. Also, $$$y < x$$$.

    1. If all bits in $$$x$$$ are on, i.e. $$$x=2^k-1$$$, then y cannot exist.
    2. If only one bit in $$$x$$$ is on, it must be the MSB and $$$x=2^k$$$. Any $$$y$$$ will end up greater than $$$x$$$, so $$$y$$$ cannot exist.

    If you discount these cases, then $$$x$$$ has an on bit in MSB and some on bits and some off bits afterward.

    One easy solution for $$$y$$$ is to copy $$$x$$$, turn off the MSB (so now $$$y<x$$$), and turn on all the other bits, i.e. $$$y=2^{k-1}-1$$$ where $$$k$$$ is the bit length of $$$x$$$.

    The time complexity is determined by counting the bit length of $$$x$$$.

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

      But the bit length is just a logarithm which can be found in a single operation.

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

        Within the constraints, yes. But if we want to measure the complexity when it depends on the number of bits, it's better to assume a generalized solution, and there is no actual way to find it in $$$\mathcal{O}(1)$$$ time for an arbitrary value of $$$x$$$. The 'single operation' you mentioned is possible only because the upper bound of $$$x$$$ is specified.

        → Reply
»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

it is one of the best Div 3 contest..i have ever seen

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

cant believe the chance of getting wrong answer at e even if you understand the solution is not zero, wasted my time thinking there must be a perfect solution .

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

somebody from codeforces please change the contest from unrated to rated for me...

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

It is technically possible to solve the problem by fixing the value of y instead of the value of x, but it is significantly more tedious to implement.

Can anyone tell me if its possible to do this? I tried this but I think we can't just keep the maximum x for a given y (the order of processing matters and we don't know exactly what should be processed first or do we?) I'd really appreciate if someone can share the solution if they solved it by fixing y instead

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

    Yes, it's possible to do. Let's begin by considering a solution where we fix $$$x$$$ from the other side. For each $$$x$$$, we have segments $$$[y_i - R; y_i + R]$$$, where $$$R$$$ is the maximum possible value (which can be find by math formula or bin search) such that the considered segment lies within circle $$$i$$$.

    Okay, then the number of points for each $$$x$$$ will be the number of points that lie in at least one of those segments. This is a standard problem of finding the length of the intersection of segments, which can be solved using a scanline algorithm. However, it is harder to do for $$$x$$$ than for $$$y$$$, because the range of $$$x$$$ is $$$[-10^9; 10^9]$$$.

    In the case of $$$y$$$, its range is $$$[-m; m]$$$. Analogously, for each $$$y$$$, we have segments $$$[x_i - R; x_i + R]$$$, where $$$R$$$ is the maximum possible value such that the considered segment lies within circle $$$i$$$. Similarly, let's find the length of the intersections of such segments for each $$$y$$$. The final asymptotic complexity is $$$O(m \log m)$$$.

    Code 310178314

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

      Great! Was too focused on doing it in real time that forgot that I can store this segments and use scanline later as well.

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

Yeah, when the contest finished I was very angry as you said, but I learnt from you and you enforced me to learn more and be familiar with geometry, so sorry if I was angry or wrote that it was a bad contest maybe I didn't like it in the start coz I wanted to be an Expert, but now I will never forget the lesson that I should be good at geometry as the other things, so thanks so much ^_^

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

I liked this contest. I solved A-E in contest and E was awesome. Idk why people get triggered at these types of less traditional problems, they care too much about rating.

→ Reply
»
4 hours ago, # |
  Vote: I like it -6 Vote: I do not like it

Div3 is more difficult than Div2 this time.

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

Could someone can explain the editorial of F more clearly for me,I'm a Chinese and a English noob,so I would appreciate it if someone would give me a better explanation(I can read the editorial,but it's too hard for a specialist to understand).

→ Reply
  • »
    »
    97 minutes ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    i have an alternate solution that is much simpler

    for each $$$k$$$, count how many of those $$$2^{k}$$$ squares that can fit inside the range

    for $$$k = 0$$$ this is just $$$(q-p)(s-r)$$$

    for every other value of $$$k$$$:

    we must find the number of pairs $$$(u,v)$$$ so that $$$[u.2^{k};(u+1).2^{k}] × [v.2^{k};(v+1).2^{k}]$$$ fits inside $$$[p;q] × [r;s]$$$ $$$(u,v \ge 0)$$$

    which means it has to satisfy:

    $$$p \le u.2^{k}$$$ and $$$(u+1)2^{k} \le q \Leftrightarrow \frac{p}{2^{k}} \le u \le \frac{q}{2^{k}}-1$$$

    $$$r \le v.2^{k}$$$ and $$$(v+1)2^{k} \le s \Leftrightarrow \frac{r}{2^{k}} \le v \le \frac{s}{2^{k}}-1$$$

    from there finding the number of $$$(u,v)$$$ is trivial, and for each square, it would "overlap" with $$$4$$$ squares of size $$$2^{k-1}$$$, which means $$$4$$$ of them are replaced by $$$1$$$ square of this size, thus the result will be subtracted by $$$3$$$ times the number of squares

    code: 310097100

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

Interesting problems ,had to use high school geometry . I liked all the problems even though I wasn't able to solve last 3 problems

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

I love these ``heuristic'' problems! Really forces one to think outside of the box in terms of how to approach them.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

does someone know the proof for the solution failing with probability 1.8e-20 in problem E

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, I think we only need to check all numbers with the binary form 11...11.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Contest

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

problem G grind me a lot lol, i found that dp range can solve, but after all i can't find the dp transition state:LL

→ Reply
»
107 minutes ago, # |
  Vote: I like it +2 Vote: I do not like it

For C, i found a solution which runs in O(1) (or O(k) where k = complexity for builtinclz(), ive heard that its practically constant time):

int msb(int i)
{
    return i ? __builtin_clz(1) - __builtin_clz(i) : -1;
}

void xortriangle(int x)
{
    int y = x + 1;  // if all bits are set, then x + 1 only has 1 bit set;
    if (!(x & (x - 1)) || !(y & (y - 1))) cout<<-1<<'\n';
    else cout<<((1 << msb(x)) - 1)<<'\n';
}

basically if number has only 1 set bit or all bits are set then its not possible, since xor then is like regular addition there so triangle will always be degenerate there else i just used a slightly smaller number with all set bits, since xorring with that is guaranteed to result in some xor result which will be less than the sum

→ Reply
»
94 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

chromate00 As someone who has tried problem setting before, really curious as to how you made the test cases for E.

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

    Experimenting with multiple points on the same parabola helped create decent test cases. Some other test cases include points forming spirals, rounded to integer coordinates. It was a nightmare trying to make tests strong enough while keeping the non-collinear condition. We almost considered removing that condition...

    → Reply
»
38 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Who else solved E without random probability! I couldn't prove but this worked https://codeforces.net/contest/2074/submission/310087663

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

Most concise O(1) solution for C 310203051

→ Reply
»
22 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Where's the code?

→ Reply