Meeting on the Line || Codeforces Round 823 Div2 Problem B

🔥𝐏𝐚𝐲 𝐀𝐟𝐭𝐞𝐫 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭
Newton School's 𝐅𝐮𝐥𝐥 𝐒𝐭𝐚𝐜𝐤 𝐂𝐨𝐮𝐫𝐬𝐞 𝟐𝟎𝟐𝟐 - bit.ly/FullSta...
Newton School Official WhatsApp Support Number: [phone]
-----------------------------------------------------------------------------------
📌𝐓𝐞𝐥𝐞𝐠𝐫𝐚𝐦:
📌𝐋𝐢𝐧𝐤𝐞𝐝𝐈𝐧: / newto. .
📌𝐈𝐧𝐬𝐭𝐚𝐠𝐫𝐚𝐦: / newtonschoo. .
📌𝐅𝐚𝐜𝐞𝐛𝐨𝐨𝐤: / newtonschool.co
------- 𝐀𝐛𝐨𝐮𝐭 𝐍𝐞𝐰𝐭𝐨𝐧 𝐒𝐜𝐡𝐨𝐨𝐥 -------
🔵NEWTON SCHOOL is an online Edtech company providing the highest-rated FULL STACK DEVELOPMENT PROGRAM for professionals, graduates, and women.
🌕NEWTON SCHOOL is your gateway to a high-paying tech career in 6 months with Zero fees till placement, transforming you into a rockstar full-stack developer earning 5-40 Lakh per annum salary. Newton School’s students are already working in more than 150+ top companies of India including Zomato, Unacademy, Deloitte, Nutanix, etc.
🔵To watch more videos on programming, Data Structures, Android Development, Data Science, C++, Java, React, subscribe to our channel.
- - - - - - - - - - - - - -
If you're reading this far down, hello, you look nice today :)
Meeting on the Line || Codeforces Round 823 Div2 Problem B
#NewtonSchool #NS #Fullstack #FSD #Datascience #MS #Postgrad #webdeveloper #programming #programmer #programmers #developer #coder #programmingmemes #coders #coding #frontenddeveloper #backenddeveloper #html #softwaredeveloper #hacking #python

[@jeevan999able]

Thank you, I was finding it hard to understand the editorial (binary search one )

[@competitivecoding-newtonsc9601]

Glad it was helpful!

[@ganeshchowdhary3024]

i solved it using ternary search by iterating on x0 instead of tmin. This is also cool, i learned something. Next time i will try to reverse engineer the ans :)

[@competitivecoding-newtonsc9601]

Yeah, but for that you have to prove x0 is a concave/convex function. I also had the idea for ternary search.

[@ganeshchowdhary3024]

@@competitivecoding-newtonsc9601 I did that using trail and error, it worked. I can prove it verbally that if u take any position to the left or right of optimal position. Without loss of generality, let's say at the current optimal position x0, a person who has maximal start time value is to the right of x0, then if u take any point to the left of x0, it makes the maximum value more maximum. On the other hand if u go right, it makes to the someone to the left of x0 more maximum. So it is unimodal.

[@tanmaybro3812]

can you provide the code as I was also thinking same but not able to implement.

[@TusharRaghav]

sir running the loop 30 times is not giving ans to right precision, when i ran the loop for 50 times then i got correct ans, the number range is 10^8 and error is

[@competitivecoding-newtonsc9601]

That is correct. But 30 loops were enough for me. Maybe its how i calculate x0.

[@jeevan999able]

try to set your precision to 15, and then run your loop for 30 times and check "cout

[@gurmansingh1878]

Thanks a lot..bro..
Your videos are really helpful...
Kindly continue to make such videos for future contests as well...
😃

[@competitivecoding-newtonsc9601]

Thanks Gurman

[@whoanujyadav]

5 4 7 2 10 4
3 2 5 1 4 6
for this testcase optimal ans is 4.5....
it is the codeforces testcase and ans given is 6.
codeforces editorail is also dumb.
please correct me if i m wrong.

[@competitivecoding-newtonsc9601]

Answer will be 6. Whats your logic behind 4.5?

[@solvinglife6658]

Is there an issue in the interesect function? I mean the condition is wrong I think for not interesect

[@ishaankulkarni49]

I think the condition of the intersect function is wrong. You have written a.second

[@competitivecoding-newtonsc9601]

No it's correct.

[@secondarypemail7181]

The level of the question was like Problem C in Div 2 rounds,I found it difficult to understand the question.By the way thank you for the explaination

[@competitivecoding-newtonsc9601]

Yeah, much harder than normal d2B.

[@AMITSHARMA-oh1nq]

Hats off to explanation.

[@competitivecoding-newtonsc9601]

Thanks Amit

[@Manish_Sahu]

inside intersect function, first if condition has same checks, doesn't understand.

[@competitivecoding-newtonsc9601]

No they are different, first check is if first segment lies before second and second check is if second segment lies before first .

[@rohandsouza9147]

Good explaination!

[@competitivecoding-newtonsc9601]

Thanks Rohan

[@ganeshchowdhary3024]

See Umnik solution for B. He avoided doubles by multiplying the positions and ti values by 2 initially.

[@competitivecoding-newtonsc9601]

I will read the solution. He just scaled the problem by x2, but how will this avoid doubles? That means in original matrix, x0 will either be integer or integer+0.5?

[@ganeshchowdhary3024]

@@competitivecoding-newtonsc9601 One point to note that, the answer for the original problem is either an interger or integer/2. SO it will be of the form 0.5+x or x. For the scaled problem, we find the x0 for the scaled values => it would be 2*(x0 for actual problem) because the algorithm is same and every time 2 is carried as multiplier. So in the end to output the ans for original problem, we just multiply by 2. It helps to avoid doubles because in binary search we divide by 2. I mean mid=l+(r-l)/2

[@nikhilsingh3928]

Can you tell why you have taken 30 iterations?

[@rishikeshpawar3230]

Thanks Sir, for solution. Why 30 iterations will do the job ? How we can figure out this number ? Any predictive calculations ?

[@rishikeshpawar3230]

I could understand, log2(1e8) is [26, 27]. Is the reason you took 30 ? I guess so

[@competitivecoding-newtonsc9601]

You want upto 10^-6 decimal precision, this is 10^14 ( 10^8 •10^6 precision, so around 50 will be enough ). But in this case, even 30 worked.

[@akairc730]

thanks a lot~

[@competitivecoding-newtonsc9601]

No worries

[@sawvikdipto3087]

12:38 second. Please anybody explain line 22 . Is there any difference between the conditions on the two sides of OR operator ?

[@competitivecoding-newtonsc9601]

One means first segment lies before second, and other means second lies before first.

[@sawvikdipto3087]

@@competitivecoding-newtonsc9601 Thanks for fast reply, but I have not found any difference between the syntax. both are a.second

[@kevinmartin1892]

Not able to get why long long used in calculation of diff and mid. Meanwhile if we replace long long by long double this code gives wrong solution. Apart from your explanation is nice :)

[@competitivecoding-newtonsc9601]

I think it leads to precision issues.

[@MrsAhmed-lr1sp]

Brother, can you please tell mewhich model of graphical pen you are using?

[@competitivecoding-newtonsc9601]

Wacom ctl-672

[@garvitgoyal3527]

can you pls tell that why we have taken 30 iterations

[@competitivecoding-newtonsc9601]

Around 30 iterations, gives you a precision of 10~(-7).

[@akshayrahangdale8511]

Can u provide the boiler plate ?

[@competitivecoding-newtonsc9601]

Boiler plate for ?

[@akshayrahangdale8511]

@@competitivecoding-newtonsc9601 for CP

[@Live-hh6li]

I tried ternary search on Answer assuming there will be a V type graph of start time × X°
and I have find a valley point.
But it failed.
Is my assumption wrong?

[@stunnerhash]

Thats what i tried doing but it failed

[@competitivecoding-newtonsc9601]

That should work I think.

[@abdullahalmamun3589]

I saw someone solved this problem with ternary search. You can found this one on the comment section of editorial blog.

[@Live-hh6li]

@@abdullahalmamun3589 Ya I read it

[@ganeshchowdhary3024]

It is correct, i did the same and it worked for me during contest. May be some bug in ur implementation.

[@kannank4269]

Why it is while ( 30-- )?

[@competitivecoding-newtonsc9601]

Read about binary searching on doubles.

[@kannank4269]

@@competitivecoding-newtonsc9601 👍🏼

[@ganeshchowdhary3024]

@@competitivecoding-newtonsc9601 We can also using while(Math.abs(r-l)>=eps) right? I already read on double long back. We can either using iterations until 100 or use epsilon. By the way it matches ur cf id :)

[@sarthakgokhale7367]

@@competitivecoding-newtonsc9601 why abs(high-low)>=eps is not working and can u tell why u choose iterations of 30

[@nikhilsingh3928]

where i can read that? I am not finding it on google@@competitivecoding-newtonsc9601

[@GANESH-jp8hm]

Can someone provide me problem D's solution

[@competitivecoding-newtonsc9601]

Try to read the editorial.

[@GANESH-jp8hm]

Could some one provide me problem D's solution

[@competitivecoding-newtonsc9601]

Try to read the editorial.

[@ketanraghunathraut7615]

D when?

[@competitivecoding-newtonsc9601]

Never, cause i havent solved it yet lol.

[@ketanraghunathraut7615]

@@competitivecoding-newtonsc9601 ohh, even I managed only A,B,C . Waiting for D .