kazuma_desu's blog

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

Hi!

I am currently reading some paper which states that 2-List Coloring problem (i.e the list of colours for every vertex is of size at most 2) is polynomial time solvable for planar graphs. The paper provides some references for the proof but they are nowhere to be found on the internet. I have tried a lot to come up with a proof myself but haven't been successful. I am hoping someone here can share a proof for it.

Also, I read somewhere that not only for planar graphs, it is polynomial time even for general graphs.

Thanks!

Read more »

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

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

Hi! I need some ideas for the following problem.

Given an initial array of zeros and target array, and operation of adding 1 to range [l, r]. Find the minimum number of steps to reach the target array.

I am looking for a solution which is better than O(n^2).

Thanks!

Read more »

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

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

Can someone share their ideas on the following problem?

https://www.codechef.com/problems/CHN16H

The problem is from ACM-ICPC 2016 Chennai Onsite Round.

Thanks!

Read more »

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