Need help EQUILIBR

[jy6DLyTq]

I can give equilibrium 100 point soln in exchange of gears problem

[jy6DLyTq]

I have applied union by rank to find cycle in the graph and bfs to find the length of it.....but it gives TLE for 2nd subtask beacause everytime I need to apply bfs to find the length of node between two node for plus or minus....how should I do for 100 points

[jy6DLyTq]

I need bfs so that I can know how many gears are in between two gears for plus/minus in the final answer.....

[jy6DLyTq]

pls give me some hint so I can proceed further

[jy6DLyTq]

but when one node get many descendants then how I will assign position to them

[jy6DLyTq]

is union by rank is correct method to find cycle or should I need something else

[jy6DLyTq]

please somebody help me with gears problem

[blackmamba]

@byomkeshbakshy try using dfs to find if the given gears are connected and finding number of gears in between and thats it

[blackmamba]

https://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/
refer this

[jy6DLyTq]

but this method require dfs every time to find the number of gears I have applied bfs it ony works for 1st subtask while TLE FOR 2nd

[jy6DLyTq]

any optimization?

[jy6DLyTq]

did u get 100 points

[jy6DLyTq]

I CAN GIVE NMNMX OR EQUILBR FULL AC IN EXCHANGE OF GEARS FULL 100 POINT SOLUTION,

[shikkari]

Hey,all I am getting difficulty in 2 subtask just got 20 points.
Submission Info:
Sub-Task Task # Result
(time)
1 0 AC
(0.000000)
1 1 AC
(0.000000)
1 2 AC
(0.000000)
1 3 AC
(0.000000)
Can someone help what to do when approaches to 3*10^5;
Any help would be appreciated.:)

[iT0i3TCk]

Hey guys, I am also ready to do what @byomkeshbakshy is doing

[blackmamba]

@vishal have u done gears?

[honeybuzz]

Lol i was about to tell albertimmy MNMX for EQUILIBR but I got 100 AC in equilibr before we exchanged more messages...good for me :P
PS anyone looking for equilibr...its a very simple solution...dont overthink it...it took me 2 days of constant fight mathematics to realize that its so direct...so dont overt think it

[closed account 3UohqMoL]

@honeybuzz how did you get it ?
is it p = 2^(n-1)
q = p - n

[closed account 3UohqMoL]

no it isn't

[honeybuzz]

What?