SRM 721 will be held today.(in less than 18 hours)

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

1 | tourist | 3496 |

2 | moejy0viiiiiv | 3288 |

3 | W4yneb0t | 3218 |

4 | TakanashiRikka | 3178 |

5 | Petr | 3173 |

6 | izrak | 3109 |

6 | Um_nik | 3109 |

8 | anta | 3106 |

9 | ershov.stanislav | 3105 |

10 | dotorya | 3089 |

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

1 | rng_58 | 172 |

2 | csacademy | 169 |

3 | Swistakk | 158 |

4 | Petr | 157 |

4 | tourist | 157 |

6 | Errichto | 151 |

7 | Zlobober | 145 |

8 | matthew99 | 141 |

9 | Endagorion | 137 |

10 | BledDest | 134 |

SRM 721 will be held today.(in less than 18 hours)

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2017 20:43:08 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|

Remainder: Contest starts in 4 hours, registration is open now.

Reminder: Contest starts in 1 hours. Now # of registerants is 351.

Were you the writer?

I'm not the writer.

How to solve Div 1 250?

I used binary search to find element on day d1.

If both left and right sum will turn out larger than needed, decrease high, and vice versa for smaller. If one is larger, the other smaller no solution is possible.

Left and right sum with one given element can be checked by computing min and max possible sum with n*(n+1)/2

Wow, that was probably the easiest SRM I have participated in.

Could someone explain how the Div1 800 could be converted to Max-Flows?

Instead of moving tokens one by one at each time, you can imagine you move all tokens simultaneously, since if two tokens cross while moving, you can just uncross them.

Here's the max flow graph.

Create two nodes for every (node, time) pair (let's denote this

a(n,t),b(n,t), meaning nodenat timet). Create a source and sink. All edge capacities in the following will be 1.xwith a token, connect source toa(x, 0).xwithout a token, connectb(x,t) to the sink.x,y) and every timej, 0 ≤j<t, connectb(x,j) toa(y,j+ 1) (and similarlyb(y,j) toa(x,j+ 1).xand every timej, 0 ≤j<t, connecta(x,j) tob(x,j), andb(x,j) toa(x,j+ 1).The max flow in this graph is the answer.

You need two classes of nodes

a,bbecause you need to encode the constraint "every node only has 1 token at each time".How does having two classes of nodes resolve the constraint issue while one class itself couldn't?

This is encoded in the edge

a(x,j) tob(x,j).This separation into two classes is a trick that essentially assigns capacities to vertices. See https://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_flow_problem_with_vertex_capacities

how to solve div2 500?

I will try to give a hint. Probably, that will be enough.

Every time you see a large problem space, you don't want to go through all of that space, but you want to consider only special points.

In the case of this problem the space is the days: [1, 2, 3, ..., d1 + d2].

We don't want to go through all of that space, but we want to consider only one special place.

Is there a reason to require that the graph in Div1 Hard is specifically a tree other than making the contestants explore the possibility of the solution being some kind of dynamic programming?

Good question! One (admittedly weak) reason is that it is a natural way to reduce the number of edges in your flow graph, which helps in doing worst-case analysis for the maxflow algorithm (Dinic runs in time E^(3/2) for unit-capacity networks, for example).

I've won the match!

Aijuuuuuuuuuuuuuna would say some gauchos criollos in my area :) !!!! Poder gaucho FTW!

I misread div1 B and started thinking about this problem:

Given

nandd, what is the maximum number of pairs that can have a distancedbetween them?Does it have a nice solution?

Any idea about div2 500 problem ( RememberWordsEasy ) ?

Vary the number of words (say d1) learnt on the last day of the sem1 from 0 to w1. Let the number of words learnt in the first day of the sem2 be d2. Given d1 words learnt on the last day, let the maximum number of words learnt in sem1 be hi, and minimum be lo. For w1 words to be learnt in the first sem, the sufficient condition is hi >= w1 >= lo. For each d1 vary d2 from d1-1 to d1+1. Find a similar hi and lo here as well for sem2 and check conditions.

To find hi and lo for a given w [words read on first day(or last)] and d [the number of days], hi = w + w+1 + .. (w+d-1)/2. And lo is w + w-1 + .. max(w-i+1, 0) ..d terms. So you get hi and lo in O(1). So the only thing that takes time is varying d1 from 0 to w1.

Hello, this comment can be off topic to this blog, sorry for that.

When I enter TopCoder Arena I can't read problems, it keeps loading, is there any way to fix it? Is problem in my internet/pc?

Thanks in advance.

Why did cgy4ever stop posting about SRM announcements?