Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

ds_95's blog

By ds_95, history, 6 years ago, In English

Please help me debug my solution for this problem NEW YEAR DOMINO

My submission :14311924

My Idea :

--Treat each domino as an interval.

--Then find connected components based on intersection.

--Store range of each connected component i.e. minL,maxR.

--for each query a,b

--define cost(cc[a],cc[b]) as cost of going from one connected component to another.

--cost(cc[a],cc[b]) = minL[cc[b]]-maxR[cc[a]] (given b>a).

--However min cost = sum of costs (starting from cc[a]) to next one till cc[b] reached.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it