kifk's blog

By kifk, 6 weeks ago, translation, In English

You are given a rooted tree with $$$n <= 1e5$$$ nodes. Each node has a number $$$a[i] <= n$$$ written on it. A path has a dominant element when the most frequently occuring element appears strictly more than $$$path length / 2$$$ times. Count how many paths with a dominant element there are.

Read more »

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

By kifk, history, 2 months ago, translation, In English

You are given n <= 1e6 numbers, all a[i] <= 1e6, among all pairs of indices (i, j), such that i != j you need to find the maximum value of (a[i] + a[j]) * (j — i). Only one solution involving something similar to D&C DP optimization is known to me, are there any other solutions?

Read more »

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