xzyxzy's blog

By xzyxzy, history, 7 weeks ago, In English,

Just like this:

int find(int x)
{
  if(f[x]==x) return x;
  return find(f[x]);
}
void merge(int x,int y)
{
  x=find(x);y=find(y);
  if(size[x]<size[y]) swap(x,y);
  f[y]=x;size[x]+=size[y];
}

I've knew that the complexity of merging by MAX-depth is $$$O(logN)$$$. But I can't figure out the proof that the complexity of merging by size is $$$O(logN)$$$. Can anyone help?

Read more »

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

By xzyxzy, history, 2 years ago, In English,

I'm sorry to ask a foolish problem about my submission.So I share a way to solve 808E by ternary searching.

As we can see,W[i] = 1, 2, 3. We sort the Souvenirs which have the same W[i] by their C[i]. Then we know we will just choose a prefix for each W[i].

If we get X Souvenirs that W[i] = 3,we remain (m - 3X) to get Souvenirs that W[i] = 1, 2. Let's define F[i][x] the prefix sum of Souvenirs that W[i] = x. If we get Y Souvenirs that W[i] = 2,our cost is F[X][3] + F[Y][2] + F[m - 3X - 2Y][1] (m-3X-2Y>=0).

We can try every X and use ternary searching to find the best Y.The complexity is O(nlogn).

My submission:http://codeforces.com/contest/808/submission/27174539

Read more »

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