In the last lecture of **Algorithm Gym** (Data Structures), I introduced you Segment trees.

In this lecture, I want to tell you more about its usages and we will solve some serious problems together.

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

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 165 |

3 | antontrygubO_o | 165 |

3 | Vovuh | 165 |

6 | tourist | 163 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

In the last lecture of **Algorithm Gym** (Data Structures), I introduced you Segment trees.

In this lecture, I want to tell you more about its usages and we will solve some serious problems together.

Today I want to introduce you some very very useful data structures.

In this lecture, we are trying to improve your data structures skills, stay with us and click on **read more**.

Statements of KBO preparation kamp day2 (string)

You should make a sequence *s*_{1}, *s*_{2}, ..., *s*_{n} such that *s*_{i} = *a*_{1} + *a*_{2} + ... + *a*_{i} and use a binary search to find the first element that is greater than *t* % *s*_{n} (or `upper_bound`

function in C++ ).

Source code : Here

First of all, compute sequence *f* (0-based), then consider we have a sequence *p* (also 0-based) (partial sum), initially all members are 0.

For each query, if *l* < *r*, then do :

```
p[l] = (p[l] + f[0]) % mod;
p[l+1] = (p[l+1] + f[1]) % mod;
p[l+1] = (1LL * p[l+1] + mod - 1LL * ((1LL * b * f[0]) % mod)) % mod;
p[r + 1] = (1LL * p[r+1] + mod - f[r - l + 1]) % mod;
p[r + 2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[r-l]) % mod)) % mod;
```

otherwise, do this :

```
p[l] = (p[l] + f[0])%mod;
p[r+1] = (1LL * p[r+1] + mod - ((1LL * b * f[0])%mod))%mod;
p[r+2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[0])%mod))%mod;
```

An the just run this : for every *i*, staring from 0, *p*_{i} + = *a* × *p*_{i - 2} + *b* × *p*_{i - 1} and *a*_{i} + = *p*_{i} .

Source code : Here

If we have an array *x*_{1}, *x*_{2}, ..., *x*_{m} and for each *i*, 1 ≤ *x*_{i} ≤ 60, the number of different element in the array *y*_{1}, *y*_{2}, ..., *y*_{m} such that *y*_{j} = *lcm*(*x*_{1}, *x*_{2}, ..., *x*_{j}), is at most *log*(60!) .Because *y*_{1} ≤ *y*_{2} ≤ *y*_{3} ≤ ... ≤ *y*_{m} and if *y*_{i} < *y*_{i + 1}, then *y*_{i} ≤ 2 × *y*_{i + 1}, and *y*_{m} ≤ 60! .

Actually, it is even less, like 25.

So for each *i*, you can find all these members for array *a*_{i}, *a*_{i + 1}, ..., *a*_{n} using at most 25 binary searches and save them in an array.

And if *x* = *p*_{1}^{b1} × ... × *p*_{k}^{bk} such that all *p*_{i}s are prime an *k* = the number of primes less than 60, then we assign sequence *b* to *x*. Using this, you can easily see that if *x* = *p*_{1}^{b1} × ... × *p*_{k}^{bk} and *y* = *p*_{1}^{c1} × ... × *p*_{k}^{ck}, *lcm*(*x*, *y*) = *p*_{1}^{max(b1, c1)} × ... × *p*_{k}^{max(bk, ck)}. And for check if a number is less than another one using this sequence *b*, you can use *log* function and the fact that *log*(*x*) = *log*(*p*_{1}^{b1}) + ... + *log*(*p*_{k}^{bk}), so if *log*(*x*) < *log*(*y*) then, *x* < *y*, and this is how to calculate the minimum value.

By the way, you can calculate *lcm*(*a*_{l}, *a*_{l + 1}, ..., *a*_{r}) in *O*(25) using Sparce Table.

Source code : Here

Consider, for each vertex *v* an each color *c* that there is at least one edge entering *v* with color *c*, we have the length of the shortest path from *s* to *v* such that it's last edge has color *c* (we call this *d*_{v, c}). So, with this, you can make a graph with states (*v*, *c*) and run a Dijkstra on it and it's easy update.

But this will get TLE.

If you think about that, you don't need all states (*v*, *c*), among all these states, we just need the first two states with minimum value of *d* (for each vertex *v*).

Source code : Here

First of all, let's solve the 1-D version :

we have two sequences *a*_{1}, *a*_{2}, ..., *a*_{n} and *b*_{1}, *b*_{2}, ..., *b*_{n} and for each *i*, we know that *b*_{i} ≤ *a*_{i}. Our goal is to calculate the number of pairs (*l*, *r*) in *O*(*n*) such that 1 ≤ *l* ≤ *r* ≤ *n* and *max*(*a*_{l}, *a*_{l + 1}, ..., *a*_{r}) - *min*(*b*_{l}, *b*_{l + 1}, ..., *b*_{r}) ≤ *k* .

We use two double ended queues (deques) for this propose :

```
let mx, mn be two empty deques
l = 1
ans = 0
for r = 1 to n
while !mx.empty() and a[mx.back()] <= a[r]
mx.pop_back()
while !mn.empty() and b[mn.back()] >= b[r]
mn.pop_back()
mx.push_back(r)
mn.push_back(r)
while a[mx.front()] - b[mn.front()] > k
l ++
if mx.front() < l
mx.pop_front()
if mn.front() < l
mn.pop_front()
ans += r - l + 1
```

In this code, for each *r* we are finding the largest valid *l*, and by the way *a*[*mx*.*front*()] = *max*(*a*_{l}, *a*_{l + 1}, ..., *a*_{r}) and *b*[*mn*.*front*()] = *min*(*b*_{l}, *b*_{l + 1}, ..., *b*_{r}) .

Now let's get back to the original problem.

For each pair (*i*, *j*) such that 1 ≤ *i* ≤ *j* ≤ *m*, build arrays *a*_{1}, *a*_{2}, ..., *a*_{n} and *b*_{1}, *b*_{2}, ..., *b*_{n} such that *a*_{k} = *max*(*a*_{k, i}, ..., *a*_{k, j}) and *b*_{k} = *min*(*a*_{k, i}, ..., *a*_{k, j}) and then run the code above.

Except that C++ deque is too slow,so you should write one.

Source code : Here

For each row or column, it's not important how many times we run the operation on it, the only thing matters, is that it's odd or even.

So, assign a boolian to each row and each column, such that row number *i*'s boolian is *r*_{i} and column *j*'s boolian is *c*_{j}.

The other things are like 2-sat, except that the graph in this problem will be undirected.

For each query, if *a*_{x, y} = *b*_{x, y} so we know that so add an edge between *r*_{x} and *c*_{y} and one between ¬*r*_{x} and ¬*c*_{y}.

Otherwise, add an edge between ¬*r*_{x} and *c*_{y} and one between ¬*c*_{y} and *r*_{x} .

You can use a disjoint set with array or vector and in each step, check if a boolian like *x* and ¬*x* are in the same component, print "No" for the rest of the queries (Because when the answer to a query is No, the answer to the next queries will be also No).

Source code : Here

The other approach is to use binary search on the last step with answer "Yes" and check using a normal 2-sat (directed graph.)

Source code for this approach : Here

Use Robin-Carp. Let's consider that *h*_{i} ≡ *s*_{1} × *p*^{0} + *s*_{2} × *p*^{1} + ... + *s*_{i} × *p*^{i - 1}(*mod* *m*) .

For a query of type 2 or 3, just use a simple binary search.

For a modify query, if *y* = *x* - *s*_{p}, you should add *y* × *p*^{0} to *h*_{p}, *y* × *p*^{1} to *h*_{p + 1} and so on. You can do all these using a segment tree or fenwick (BIT).

Source code : Here

Use divide and conquer on the tree (centroid decomposition) and answer queries offline.

For conquer, imagine root is *r*. Run dfs on *r* and for each vertex, push it's distance to *r* in the vector *e*. Then sort *e* and for each vertex *v* in subtree of *r* and query *o* such that it's asking about *v* and number *l*, do this : `ans[o] += the number of members of e like p such that p + d(r,v) <= l`

(using binary search).

But here, we counted some vertices for some queries more than once.

Then for each neighbor of *r* do this separately:

Run dfs on it's subtree and for each vertex, push it's distance to *r* in the vector *z*. Then sort *z* and for each vertex *v* in this subtree and query *o* such that it's asking about *v* and number *l*, do this : `ans[o] -= the number of members of z like p such that p + d(r,v) <= l`

(using binary search).

Source code : Here

Tutorial of Hello 2015 (Div.1)

Tutorial of Hello 2015 (Div.1)

Tutorial of ICPC Training[0]

Hey everbody.

**Hello 2015** is a Div.1 + Div.2 contest that will be held in gym soon. As I said, there will be 2 divisions and in each divisions, users of that division can participate ( ( - ∞, 1699] and [1700, 9999]). So, anybody who participates in the wrong division will be **out of competition** (manually).

Duration is 3 hours and there will be 6 problems in each division. Last 4 problems of Div.2 will be same as first 4 problems of Div.1 . Problems are written by me (PrinceOfPersia) and tester's M.Mahdi.

The problems will be sorted according to the estimated order of difficulty according to my opinion but I strongly recommend you to read all of the problems.(sentence from matrix :D).

Problems are more Olympiad style than ACM. I hope you enjoy them.

It takes a while to prepare all problems. So, this contest is not in the gym contests list yet.

Oh, I almost forgot this : the main character of all problems will be my friend, De Prezer :)

**UPD:** Problems are designed for single participant (as mathlover said), so **teams will participate out of competition** too.

**UPD2:** It's in the gym contests list now.

**UPD3:** For making the contest more interesting, the winner of each division, gets a kiss ;)

**UPD4:** Round was delayed by 10 minutes for some technical reasons.

**UPD5:** Contest is over.

Congratulation to all winers specially sankear who solved all Div.1 problems.

Div.1 winners :

1.sankear

2.ikbal

4.tourist

5.dreamoon

Div.2 winners :

1.cthbst

2.peterpan

3.que_roin

Now it's time to sankear and cthbst kiss each other ;)

See you in next rounds, good luck and have fun.

**UPD6:** Well, recently I'm a little busy and I'll just post some keywords and tags but maybe I'll write an editorial some time.

Div.2 A : Binary search, B : Partial sum

Div.1 A : Binary search, B : Dijkstra, C : DP,Two pointers,queue, D : 2-sat, E: Hash, Segment tree, F : Divide and Conquer.

**UPD7:** You can find the editorial here.

Announcement of Hello 2015 (Div.1)

Hello everyone.

Soon, On the night after the Halloween, there will be a Codeforces gym contest, named **Crypto cup 1.0**.

Like its name, it's a cryptography contest and for all problems, you are given some sample encryptions encrypted using a certain algorithm and you have to write a program to decrypt the given messages.

There will be 18 problems and you have 6:30 hours to solve them. I hope it will be interesting.

Problems are prepared by me (PrinceOfPersia) and tested by DamonSalvatore also thanks Swift for editing problem statements.

For practicing cryptography, we recommend SecutiryOverRide's cryptography challenges.

Also, this round needs a little Algorithm and CS knowledge.Don't forget to pay attention to problem's titles, they might be helpful ;)

Currently, problems are being prepared, so you're unable to see the contest in gym contest list yet.

**Problems are in decreasing order of difficulty.**

**UPD: Duration has been increased by half an hour, now it's 6:30 .**

**UPD2: Please note that contest will be held on November 1st, because it had overlap with Shahid Beheshti University ACM**.

**UPD3: Now it's in the Gym contests list.**

**UPD4: Registration is open.**

**UPD5: Contest is over.**

I hope you enjoyed the problems.

Congratulation to the winners who solved all the problems :

Be aware, our standard rounds are coming... ;)

Announcement of Crypto Cup 1.0

Hello.Today I opened http://codeforces.com/contest/238/standings/friends/true and saw a funny thing.

havaliza is in it about 5 times.Is that a bug or what ?

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2019 13:44:04 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|