40 minutes left. Enjoy!

# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 159 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | PikMike | 152 |

8 | Ashishgup | 151 |

8 | Petr | 151 |

10 | 300iq | 150 |

40 minutes left. Enjoy!

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/14/2018 15:23:31 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve problem E?

Minimum answer is max degree.

If max degree ≤ 1, we can just color all edges in one color.

Else, let's split edges of the graph into two sets, such that max degree will be ≤ (max degree + 1) / 2 in each of these two sets. You can do it with euler circuit, add some dummy vertex to the left and right part, and connect with them vertices with odd degree (and maybe you need to connect them if they have odd degree). And then color the edges into two colors by order of euler circuit. Then separate all inital edges into two groups by the color. Then let's solve recursively for these two sets, and then just merge the answers.

Could you please share your implementation of the algorithm of building up the coloring? Thanks in advance and sorry to bother you.

Yes, here it is: https://pastebin.com/cdkf26cp!

Using at most X colors: https://link.springer.com/article/10.1007%2FBF00998632

Using at most C colors: http://www.dtic.mil/dtic/tr/fulltext/u2/a093097.pdf

It's weird that they put a studied problem in their contest... the problem sounded general enough for it to be well known.

Yeah, the second paper was in my to-do list, and this contest gave me an opportunity to read it. :)

Is there a way to view the first paper without paying?

Kinda illegal but everyone uses it.

Shhhh... I have one way, but you need to keep it between you and me, otherwise...

Find the pdf here. If you need any other material just look into it on sci-hub.

Ok, cuber2460 already knew about it, lets keep this between the 3 of us.

how to solve problem D for 100% ?

All you need to do is summon mkisic (task author) to the rescue :)

As mkisic is occupied by Maja, I will explain the solution.

Imagine fixating a row. Now make an array where the value of a field is the number of consecutive fields empty in the up direction. So now we have a problem of findning the sum of areas of all rectangles in a histogram. We can solve the problem in two ways, one is in

O(NlogN) using divide and conquer and the other one is using stack inO(N).I will explain the divide and conquer solution. Using segment tree we can fin the minimum in an interval. Now we want to count the sum of areas of all rectangles whose botom side is in our fixated row and whose height is smaller than or equal to the smallest element in that interval. It is not hard to come up with a formula. Now we proceed with the divide and conquer on the two intervals we get by splitting at the minimum. Notice that you have to be careful not to count some rectangles twice, but this can be easily avoided.

Insted of using the segment tree to find out those intervals, you can do a simmilar thing with a montone stack.

thanks very much ppavic . I understand solution. if it will be possible to solve problem on some judge, i will do it.

Where can I submit solutions?

Analysis mode should be here. Just make sure to choose the COCI round in the dropdown menu.

You can solve all problems here: https://oj.uz/problems/source/367

Very good oj!