I found the problemset of "ACM ICPC 2010-2011 NEERC Moscow Subregional" and I have tried to solve this problems but i can't found an online judge where this context is, if someone can help me, i be grateful, thanks in advance!!!

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

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

1 | tourist | 3880 |

2 | jiangly | 3669 |

3 | ecnerwala | 3654 |

4 | Benq | 3627 |

5 | orzdevinwang | 3612 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | jqdai0815 | 3532 |

9 | Radewoosh | 3522 |

10 | gyh20 | 3447 |

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

1 | awoo | 161 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | maroonrk | 153 |

5 | -is-this-fft- | 148 |

5 | atcoder_official | 148 |

5 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 144 |

9 | TheScrasse | 144 |

I recently studied this data structure, and resolved some problems, but I would like to solve other, if anyone can give me some problems, I would be grateful.

This are some problems that i solved by kdtree:

City Houses (with manhattan distance)

Counting Points (basic of kdtree)

Elizabeth's Kingdom (some dificult but very nice problem)

I need some hins for this problem "City houses", please help.

Usually, for solve problems where we have to know the number of element least that some value X, is ease use some data structure of binary search tree (like treap). But in competition is it's heavy copy this code, and usually i use for similar thing the `set`

structure. But after some time of searching, I don't find out, how can i know for a `set`

, the position of an element in the sorted list. Example:

```
//If i have in my set.
set<int>s;
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(2);
//know the sorted position of 4.
```

if i search with some method (**find**,**lower_bound** or **upper_bound**) this return an iterator of the element, but it's posible know it's sorted position.

if I use a treap, I make an function where i keep the number of element to the left and finally when i find the element, the number of elements least that X is the number of elements to the left of X in the tree. An example in my treap:

```
class treap {
struct node {
int value, key, size,cc;
node(int v, node *n):value(v){
c[0] = c[1] = n;
size = 1; key = rand() - 1;
cc=1;
}
void rz() {
size = c[0]->size + c[1]->size + cc;
}
node*c[2];
}*root, *null;
void rot(node*&t, bool d) {
node*c = t->c[d];
t->c[d] = c->c[!d];
c->c[!d] = t;
t->rz(); c->rz();
t = c;
}
void insert(node*&t, int x) {
if (t == null) {
t = new node(x, null);
return;
}
if (x == t->value){
t->cc++;t->rz();
return;
}
bool d = x > t->value;
insert(t->c[d], x);
if (t->c[d]->key < t->key) rot(t, d);
else t->rz();
}
int Upper_bound(node*&t,int x,int izq){//For know the number of element <= X
if(t==null)return izq;
if(x==t->value)
return t->c[0]->size+izq+t->cc;
bool d=x>t->value;
if(d)return Upper_bound(t->c[d],x,izq+t->c[0]->size+t->cc);
return Upper_bound(t->c[d],x,izq);
}
void Delete(node*&t, int x) {
if (t == null) return;
if (t->value == x) {
if(t->cc>1){
t->cc--;t->rz();
return;
}
bool d = t->c[1]->key < t->c[0]->key;
if (t->c[d] == null) {
delete t; t = null;
return;
}
rot(t, d); Delete(t->c[!d], x);
} else {
bool d = x > t->value;
Delete(t->c[d], x);
}
t->rz();
}
public:
treap() {
null = new node(0, 0);
null->size = 0;
null->key = oo;
root = null;
}
void ins(int x) {
insert(root, x);
}
void del(int x) {
Delete(root, x);
}
int busq(int x){
return Upper_bound(root,x,0);
}
};
```

It's posible make this in a set structure???

Recently i found a problem about geometric, that ask for how many pair of points of the set of points, are good pair, and a good pair is a pair **(a,b)** of points where the max distance between both points to any other **c** point it is greater or equals at the distance between the firsts two points ( **a** and **b**).

*as a formula:* `distance(a,b)<=max(distance(a,c),distance(b,c))`

Can be at most **2000** points.

Is ease see, that can be solve for some `O(n^2)`

whit some factor `logn`

for search a point that invalidate a pair of points, but right now i don't see how search this point. If some one can help me, thank in advance???

**UPD:** here is the problem: link

`10 ^ 4`

points. If anyone can help, I'd be grateful. thanks in advance.

Recently i saw the following fragment of code in some solutions here in codeforce and another online judges, and my question is. What is this code?

```
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
```

thank in advance!

Recently I learn the dominator tree algorithm and I will like to solve some problem about this topic, if someone can help me with some link related to that, I be grateful. Thank in advance!!

**UPD1:** I found this problem disjoint water supply from *2013 ACM-ICPC Latin American Regional Contests* maybe can be usefull, and thanks to marat.snowbear for this problems, very nice the second one.

`dp[j][t]*j`

. What mean the multiplication?, i don't understand this. Thank for your time!!!

The problem is Fence the vegetables from "2014 Caribbean Finals of the ACM-ICPC" in caribbean online judged.

I think that the minimum perimeter, is equals to:

`(maxX-minX+1)*2+(maxY-minY+1)*2`

But i dont know how find the minimum area with this perimeter. Thank for the help!!!

**Ural Championship 2015** on timus judge. If someone can help with the main idea to solve this problem, because i dont see how calculate a tree from a graph where the difference between the minimum and maximum edge are the minimum posible. Thank for the help!!!

`A*B`

or `A!`

, and searching in internet, i found how to do this using **log**, but i found the problem **Python Brute Force**, that ask for the number of digit to the following operation: `1*1!+2*2!+....+N*N!`

. I don't know how to count the number of digit to the sum of terms, like `A+B`

. Maybe this problem is just transform the operations, but i don't see how to do that. thank for the help!!!

I don't understand why the answer is find all uncovered position, because in example:

7 2

ioi

1 3

The text that can be formed is:

i o i o i _ _ (with two space in blank or uncovered position)

And the answer if we do that tutorial said, then will be:

26*26=676

But, the string **ioioioi** is obtained to in that combination, and then the first assumption it's no true, because the string **ioi** is matched in one more place that input.

thank??

I'm looking for a good tutorial about matrix exponentiation, where explain how can i solve a recurrence like this: `f(n)=f(n-1)+n*2`

I know how to use matrix exponentiation to solve a recurrence where are used anterior terms, but i don't know when the recurrence have one term that depend to the position of the term.

thank you!!!

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/21/2024 10:55:43 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|