Codeforces Round 1009 (Div. 3) — Editorial

#	User	Rating
1	jiangly	3846
2	tourist	3799
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3590
6	Ormlis	3533
7	Benq	3468
8	Radewoosh	3463
9	ecnerwala	3451
9	Um_nik	3451

#	User	Contrib.
1	cry	165
2	-is-this-fft-	161
3	Qingyu	160
4	atcoder_official	157
5	Dominater069	156
6	adamant	154
7	Um_nik	151
7	djm03178	151
9	luogu_official	149
10	awoo	147

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

for i in range(int(input())):
    l,r,d,u=map(int,input().split())
    if l==r==d==u:
        print("Yes")
    else:
        print("No")

2074B - The Third Side

Editorial

Code

t = int(input())
for _ in range(t):
    n = int(input())
    sm = sum(map(int, input().split()))
    print(sm - n + 1)

2074C - XOR and Triangle

Editorial

Code

t = int(input())
for _ in range(t):
    x = int(input())
    ans = -1
    for i in range(30):
        for j in range(30):
            y = (1 << i) | (1 << j)
            if y < x and x + y > (x ^ y) and y + (x ^ y) > x:
                ans = y
    print(ans)

2074D - Counting Points

Editorial

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    int t;cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,m;cin>>n>>m;
        map<ll,ll>cnt;
        auto isqrt=[&](ll x)
        {
            ll val=sqrtl(x)+5;
            while(val*val>x)val--;
            return val;
        };
        vector<ll>a(n),r(n);
        for(ll&i:a)cin>>i;
        for(ll&i:r)cin>>i;
        for(int i=0;i<n;i++)
        {
            ll aa=a[i],rr=r[i];
            for(ll x=aa-rr;x<=aa+rr;x++)
            {
                cnt[x]=max(cnt[x],2*isqrt(rr*rr-(x-aa)*(x-aa))+1);
            }
        }
        ll ans=0;
        for(auto[x,c]:cnt)ans+=c;
        cout<<ans<<"\n";
    }
}

2074E - Empty Triangle

Editorial

Code

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    mt19937 mt(727);
    uniform_int_distribution uni(1,3);
    int tc;cin>>tc;
    while(tc--)
    {
        int n;cin>>n;
        if(n<0)return 0;
        vector<int>vec(n);
        for(int i=0;i<n;i++)vec[i]=i+1;
        shuffle(begin(vec),end(vec),mt);
        int ii=vec[0],jj=vec[1],kk=vec[2];
        cerr<<n<<endl;
        while(1)
        {
            cout<<"? "<<ii<<" "<<jj<<" "<<kk<<endl;
            int id;cin>>id;
            if(id<0)return 0;
            if(id==0)break;
            int sw=uni(mt);
            if(sw==1)ii=id;
            else if(sw==2)jj=id;
            else kk=id;
        }
        cout<<"! "<<ii<<" "<<jj<<" "<<kk<<endl;
    }
}

2074F - Counting Necessary Nodes

Editorial

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    int t;cin>>t;
    for(int i=0;i<t;i++)
    {
        int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
        vector<pair<ll,ll>>it1,it2;
        auto rec=[&](auto rec,int L,int R,int l,int r,vector<pair<ll,ll>>&v)->void
        {
            if(r<=L||l>=R)return;
            if(l<=L&&R<=r)
            {
                v.emplace_back(L,R);
                return;
            }
            rec(rec,L,(L+R)/2,l,r,v);
            rec(rec,(L+R)/2,R,l,r,v);
        };
        rec(rec,0,1<<25,l1,r1,it1);
        rec(rec,0,1<<25,l2,r2,it2);
        ll ans=0;
        for(auto[al,ar]:it1)
        {
            for(auto[bl,br]:it2)
            {
                ll a=ar-al,b=br-bl;
                if(a<b)swap(a,b);
                ans+=a/b;
            }
        }
        cout<<ans<<"\n";
    }
}

2074G - Game With Triangles: Season 2

Editorial

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
ll dp[505][505];
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    for(int tc=0;tc<t;tc++)
    {
        ll n;cin>>n;
        vector<ll>vec(n);
        for(ll&i:vec)cin>>i;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)dp[i][j]=-1e18;
        }
        auto value=[&](ll i,ll j,ll k)
        {
            return i*j*k;
        };
        for(int len=1;len<=n;len++)
        {
            for(int L=0;L<n;L++)
            {
                ll ans=0;
                ll R=(L+len-1)%n;
                if(len<=2)
                {
                    dp[L][R]=0;
                    continue;
                }
                if(len==3)
                {
                    dp[L][R]=max(0LL,value(vec[L],vec[(L+1)%n],vec[R]));
                    continue;
                }
                for(int i=(L+1)%n;i!=R;i=(i+1)%n)
                {
                    ll val=value(vec[L],vec[i],vec[R]);
                    if(i!=(L+1)%n)val+=dp[(L+1)%n][(i+n-1)%n];
                    if(i!=(R+n-1)%n)val+=dp[(i+1)%n][(R+n-1)%n];
                    ans=max(ans,val);
                }
                for(int i=L;i!=R;i=(i+1)%n)
                {
                    ans=max(ans,dp[L][i]+dp[(i+1)%n][R]);
                }
                dp[L][R]=ans;
            }
        }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ans=max(ans,dp[i][(i+n-1)%n]);
        }
        cout<<ans<<"\n";
    }
}

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'; }

Comments (152)

Write comment?

heavenly_principles

19 hours ago, # |

+60

Geometry dash ah contest :p

→ Reply

myco

16 hours ago, # ^ |

E :(

tyristik

11 minutes ago, # ^ |

As a Geometry dash enjoyer, I wasn't able to immediately get what do you mean xD

valiii

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.

TiwoeeM

19 hours ago, # ^ |

← Rev. 2 →

+15

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

chromate00

+12

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

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

dorijanlendvaj

3 hours ago, # ^ |

I'm assuming the reason hacks are disabled is to prevent people from being hacked due seeding their random with a constant or time(0) instead of something unhackable.

Dominater069

also, it is impossible to analyze randomized algorithms without disabling hacks. (sure you can assume "reasonable number of tests" but that isn't a guarantee. There have been problems with upto 1000 tests, and problems with <= 10 tests, the scenarios are very different)

Yeah, I totally understand that, overall it was a nice problem with a good idea, although its placement could have been better

Julea

+62

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\%$$$

BaarishBoy

-38

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 !!

Kandarp08

+20

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

sleepyAdarsh

18 hours ago, # ^ |

I literally guessed it so bad

Breaker-iwnL-

+11

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

how cooked am i chat

SadArtira

Check this blog Some equations using Bitwise Operators

ShivamS01

2 hours ago, # ^ |

Thanks for sharing this blog! I also didn't know many of these properties.

Resorcinol

14 hours ago, # ^ |

it's not that complicated, you can prove this by imagining venn diagram, with x and y circles.

mahiro_zcy

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

310125203

jobin491

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

BLACKCOFFEE-420

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."

iregreteverything

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

LearningMachine

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.

benzenelovescp

17 hours ago, # ^ |

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

11 hours ago, # ^ |

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.

Baby_Bird

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)$$$.

barbarian

6 hours ago, # ^ |

I dont know my dumb a** thought the hint about M "is it really useful??" part and thought the answer is all about finding through M so i thought the max range would be is from -M to +M and I would iterate over array to find the answer, and here is where i lost the question ;(

RG04

+10

Why does E exist

NullMeowference

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

d1amondzz

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

_whimsical_

lol tell that to my 18 WAs

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

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.

HusseinFarhat

Legendary

3.1415926535897932384

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

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

theAyconic1

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

sarthakswarnkar

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.

TheArcticWolf

Geometry wasn't geometrying today -.-

wharoldy

-12

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.

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.

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

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

Thank God I am safe due to no hacks XD

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

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

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

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)

12 hours ago, # ^ |

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

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.

where to practice questions like E?

Pray to god

gentlecoder29

dont

justplaygame

9 hours ago, # ^ |

On codeforces

Ok sir

NotFound

GeometryForces

iriXium19

W contest! Nice problems!

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

Stillswarm

18 hours ago, # |

Mathforces!

phantomphreak96

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

you might want to read the other comment for why https://codeforces.net/blog/entry/140540?#comment-1254281

minuki646

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.`

Shriyansh_47

I wasn't able to solve D. Can you explain how this hint was useful in getting the solution ?

sum(r[i]) = m <= 10 ** 5. It means you can brute force sweep with fixing 1 coordinate and accumulate the other coordinate to the final answer.

My solution is fixing y, find all x fit the circle.

The intended solution is fixing x, finding all y.

91 minute(s) ago, # ^ |

got it .thnx

Xiao_2710

-25

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.

maruf004

← Rev. 4 →

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

Niazye

-8

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

Proof_by_QED

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.

In the AC submission I still use “deque”(pop front and push back), just use rand()in query.(? a[rand()+0] a[rand()+1] a[rand()+2])

EZDUBS

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

IManifold

17 hours ago, # |

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

Ibrahimfostok

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

ultimatechodu.v1

D was nuts.

yagni_99

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

belalahmed_

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

Can you please explain your solution?

plankk

98 minutes ago, # ^ |

i really don't have any proof but what I was trying to do is

I have N so I said lets try N-1 and N+1 to make the condition true so lets try N xor N-1 and N xor N+1 check if the answer satisfy the condition

sunboi

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

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

DCODER_13

it shouldn't, but still took lesser time than my $$$O(n^3)$$$ one lol (probably because of the modulo)

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

15 hours ago, # ^ |

I guess C++ can do $$$10^{10}$$$ operations per sec, lol

ar_rony1

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

djm03178

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 :)

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

-11

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.

-9

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

+13

It teaches you that randomization is sometimes useful.

5 hours ago, # ^ |

Then why are solutions that aren't random also AC? Why keep a question if you can't ensure that only truly random solutions can pass? Why not make a strong interactor that WA'S all solutions that aren't random, if you can't make it dont keep the question, or keep it in the end.

Do you really think every problem can set a constraint that only the very intended solution can pass and others can never? Let me tell you: almost every problem in the world has at least one way to solve that the authors couldn't come up with. Some kinds of problems are much harder to prevent suboptimal/heuristic solutions from passing than others, but it doesn't mean the problem should never exist, nor that it implies that the authors didn't try to prevent them at all.

Yeah right a problem can have many solutions, but it can be proven that those solutions are also right.

But a problem whose intended solution is a randomized solution,if that problem also AC's some non random solutions but WA'S some non random solution, is it a good problem? Doesn't it make it unfair?

4 hours ago, # ^ |

Authors don't have responsibility to hack every unintended solutions. If your definition of 'unfairness' is to give WA on every single solution that has some chance to be hacked, then I would say that there are many many problems that are unfair. It just can't always be prevented. You can't and shouldn't expect the authors to invest thousands of hours into a problem to test every possible heuristics just to cut out a few more unintended solutions. It's not productive.

Then why not allow hacking in E and let's how your randomization algorithm helps you there. lol

Too big to admit when someone's wrong.

I dont really know why is it so hard to comprehend that such problems where a lot of "lucky" solutions can pass aren't good problems and yes author can't spend gazillions of minutes making it good, but yeah sure can spend a couple of minutes to not keep that problem at all.

← Rev. 3 →

Your initial comment was this:

and I don't understand why a problem has to be rejected because of these 'lucky' solutions when it can definitely teach you something more valuable, if that's what you were looking for. Why do you even care if some other solutions passed or not, if you can learn something good from the intended solution?

but yeah sure can spend a couple of minutes to not keep that problem at all.

... Then you don't care about the time to invent a new problem to replace it at all?

You are right, I was blinded by my rating drop and ignored the actual reason why i am writing contests.

You regret yourself when you could not solve 1008C, while it could have been solved with randomization.

And now you complain about a task teaching you about the whole concept.

I guess you are very ironic.

I think that C has a very nice analytical solution, it was too adhoc for me.

Did you AC it via a random solution? if yes then you are just lucky.

8 minutes ago, # ^ |

Wrong. If the chance of your code to fail is less then $$$10^{-9}$$$ on one test and it actually failed — you just suck at life.

16 hours ago, # |

Interesting observation in C:

For x of form 2^k or 2^k-1, there doesn't exist any y which can give you a non-degenerate solution.
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.

rref

This is what I came up with as well.

qwertylkjhg

Proofs:

Let's denote x^y as z.

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.

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.

wsaleem

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$$$.

If all bits in $$$x$$$ are on, i.e. $$$x=2^k-1$$$, then y cannot exist.
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$$$.

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

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.

How is this code? 310027336

I think it should be good , nevertheless could you think of a case failing it?

5am__Arpit

15 hours ago, # |

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

Seriously_Its_Sameer

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 .

RaghavChawla

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

wictorynator

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

denk

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

arselium

13 hours ago, # ^ |

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

Mostafa_Alaa99

14 hours ago, # |

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 ^_^

Phantom_Dreams

12 hours ago, # |

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.

RE_ght

11 hours ago, # |

-7

Div3 is more difficult than Div2 this time.

cube_escape

10 hours ago, # |

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).

phsads

8 hours ago, # ^ |

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

thanks,now I understand it!

adicodesss

9 hours ago, # |

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

fisher199

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

aneesh2002

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

52 minutes ago, # ^ |

I believe it has to do with the fact that even if you don't choose the "good" triangle you are still likely to cut off some points. And the existence of a "bad" triangle containing almost all of the remaining points means that the "good" triangle contains very few points.

VanLam

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

darsh_sodani007

Nice Contest

sitingfake

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

lakkshyag

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):

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

goldrevboy

8 hours ago, # |

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

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...

7 hours ago, # ^ |

Cool, thanks pretty insightful

SanathK

7 hours ago, # |

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

rubbish

Most concise O(1) solution for C 310203051

m_nature

100 minutes ago, # ^ |

That's still O(log(x))

lyl_ccut

Where's the code?

Added just now

shubhraj625

solved E without caring about the limit of 75 queries

PakinDioxide

6 hours ago, # |

Why did my solution passed on Problem C and E

Problem C : 310037314 Problem E : 310096257

kakoujt

For 2074E - Empty Triangle, I don't know why this 310209003 got an AC. Maybe on luck. But it worked :)

CaptainPre

Got a question, I finished my first contest ever. Why do i see no rating in my profile?

Got 2/7 right.

For Div. 3 and Edu. Round, there will be a system test after the open hacking phase. After that, your rating will be updated.

Karim__2

for div4 and div3, it usually takes time .

Thanks @kakoujt and @karim__2

I will wait for my rating. I have completed Div 3 A,B,C(TLE). Can i try Div 2? Or would it be harder.

Yes, it would be harder .

I think div2 A is as hard as div3 B but you can try it anyway.

FZANOTFOUND

failed to solve D but it's really a good problem (I didn't notice that m<=2e5 and i thought calculate each x will get MLE :( )

NeuralG

3 hours ago, # |

Can someone tell me why did my C submission works, I feel like it worked by accident

code4dj

can someone pls help me with this I do not understand why we are looking at probabilities for problem E isn't it obvious after choosing good triangles(with least no. of hidden points) 7 times will get the desired triangle? that is in total of 7*3 queries?

106 minutes ago, # ^ |

We don't know which triangle is good and therefore choose a new triangle randomly. Otherwise, it might be the case we choose the worst triangle at each step, which will result in asking more than 75 queries. But when randomising choices, probability of such cases are very low.

NiGhT-h-MaRe

2 hours ago, # |

Nice contest to understand triangles in depth and C was really nice for a XOR question

Xing_Kong_C

For problem E, i will ask x and i,j,k three triangles formed by three points, and then get three points again, and repeat this process. I think this convergence speed will be very fast, and no heuristic algorithm is used, could someone tell me why? 310067778

This competition has made my rating increase particularly big, thanks to this div3！

Focus07

105 minutes ago, # |

My Solution to E is something like a BFS, I have no idea why it works mathematically, someone proving it would be nice, my guess is it might be doing something very close to what the editorial does. Also, for C, I brute-forced the code on my machine to find a pattern that for an x what is the smallest value of y. I noticed that the answer was always of the form (1+ 2^n)< x. If such a n did not exist the answer is -1. I iterated over all valid n's and solved the problem in log2(x).E: 310096412 C: 310115607

82 minutes ago, # ^ |

For E, I came up with the same approach 310209003, surprised by it. I cannot prove it mathematically either. I now think that it is a coincidence because:

The starting condition may not include all 1500 points
The initial triangle is split up into about 50 small triangles when reaching 75 queries. For random data, the probability of getting a triangle with no point inside it is considerable.
Possibly the problem maker did not think of this BFS approach, so it is not hacked.

Nasa_Yuzaki

64 minutes ago, # |

E is the worst CP problem I have ever seen, nothing beats a problem which depends on luck.

_Kee

47 minutes ago, # ^ |

Randomized algorithm is an important topic in adademics and you should be at least aware that good randomization can significantly reduce the running time.

SkyEyeController

48 minutes ago, # |

When I solved 6 problems：Great！Yeah！Killed the F in last 5 min before Ended！ System Test：Hello. (Rejected on the test 11 of problem D)