kaldiuo's blog

By kaldiuo, history, 11 months ago, In English,

I was thinking of this problem.

You have a matrix of size n by n (n<=10^5). You have to support q<=10^5 operations of 3 types (online):

  1. Given (i, l, r, x), set a[i][l...r] to x

  2. Given (l, r, x), set a[1...n][l...r] to x

  3. Given (i, l, r), find the minimum of a[i][l...r]

Is there any way to support these operations efficiently?

Read more »

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

By kaldiuo, history, 17 months ago, In English,

As you guys might know, global warming exists despite Trump's constant denial. Therefore, as a competitive programming community, we need to try our best to counter global warming.

What I suggest is that in addition to time limit, memory limit, and file size limit, we should also have a energy limit. For example, if someone writes shit inefficient code with Python (Proof), they should definitely get a Energy Limited Exceeded verdict to remind them of how much harm that they are doing to Mother Earth. Furthermore, in addition to penalties for things like re-submissions, Codeforces should also have penalties for amount of energy used.

Another possible option is to make the constraints for problems smaller. If we change the time limit to 0.01s from 2s, that means we save 200x energy for each submission!!! We will definitely reduce climate change and save the world for our future generations!!!

Read more »

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

By kaldiuo, history, 18 months ago, In English,

There are q<=5*10^5 online queries of 2 types for a set of integers:

  1. Add an integer 1<=x<=10^9 to the set
  2. Remove an integer from the set
  3. Find the minimum element >=x that isn't present in the set

Is there a way to efficiently process these queries?

Read more »

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

By kaldiuo, history, 18 months ago, In English,

It is well known that given points (x, y) and you need to calculate the Manhattan distances between them, instead of using |x1-x2|+|y1-y2| you can first convert all points (x, y) into (x+y, x-y) and the distances will become max(|x1-x2|, |y1-y2|) (also known as Chebyshev distance). Can this trick apply to higher dimensions?

Read more »

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

By kaldiuo, history, 20 months ago, In English,

Suppose that we have a divide and conquer algorithm f(n) such that O(f(n))=O(min(a, b)+f(a)+f(b)) where a+b=n, then what is the worst time complexity of f(n) (explicitly)?

Read more »

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