sid9406's blog

By sid9406, history, 19 months ago, In English

I was solving problem C from the Google kickstart Round H and this problem requires me to solve the below task :-

There are n points on the x-axis and two or more points can coincide . We want to arrange these n points on x axis such that they become adjacent. Each movement of 1 unit has cost of 1 unit . What is the minimum cost of doing this activity ?

My approach :- Sort the points and fix the position of the median point(if n is even you can fix any median) , then centre all other points around this median .

can somebody explain why this approach is incorrect and if you know the correct approach pls share.

Thanks

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By sid9406, history, 20 months ago, In English

I couldn't solve this problem from Codechef Long Challenge https://www.codechef.com/OCT20A/problems/DDIMMST . Can someone help me in this problem. I tried reading the editorial https://discuss.codechef.com/t/ddimmst-editorial/79385 but no help . What i don't understand is how are we able to reduce the number of edges from n^2 to 2^d*n .

This seems to be general class of problems , there is another problem that uses the same idea https://codeforces.com/contest/1093/problem/G , awoo i know this contest was long back , can you pls explain the idea behind the solution to these kind of problems.

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it