For a person who can do div 2 A and B comfortably and sometimes C, does practicing on D make sense. Will participating in div 1 virtual so that I start from div 2 C (div 1 A) help or should I stick to solving only C and D? Thank you.

# | 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 | Petr | 157 |

3 | tourist | 157 |

5 | Swistakk | 156 |

6 | Errichto | 150 |

7 | Zlobober | 145 |

8 | matthew99 | 141 |

9 | Endagorion | 137 |

10 | BledDest | 134 |

In Dinic algorithm for maximum flow, we in dfs we write the function as

```
for(int &t = ptr[source]; t < neighbours of source ; ++t)
```

I read that ptr is an array used to make finding the blocking flow in O(m) rather than O(m2). Why does this work and what is the exact use of keeping the ptr array. How does this array work?

I came across this implementation of treap split function

```
void split(pnode root, int key, pnode &l, pnode &r){
if(!root){
l = NULL;
r = NULL;
}
else if(key < root->key){
split(root->l,key,l,root->l);
r = root;
}
else{
split(root->r,key,root->r,r);
l = root;
}
}
```

where pnode is pointer to node. I have a difficulty in understanding the call to split function. if key < root->key, I understood that we need to make root as the root of the right subtree so r = root. And we need to split left child. So split(root->l,key,?,?) the doubt is why we pass l as left pointer and root->l as right pointer. Thank you

By Graham Scan O(n*n*logn) would be possible for online construction of convex hull. Can you help me with O(n*n) algorithm. Also what is the difference between 2D CH construction and 3D CH construction

And in graham scan there is a function to sort according to polar order which i did not understand. Please help.

```
bool polar_order(Point a, Point b){
//ccw is a function that returns 0 if collinear -1 if counter-clockwise and 1 if clockwise
//pivot is the lowest y-coordinate point(tie broken by lowest x-coordinate)
int order = ccw(pivot,a,b);
if(order==0)
return sqrdist(pivot,a) < sqrdist(pivot,b);
return (order==-1);
}
```

Also if there are some problems you know of convex hull, please share them. Thank you.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2017 15:01:07 (c5).

Desktop version, switch to mobile version.

User lists

Name |
---|