### DarthKnight's blog

By DarthKnight, 4 years ago, ,

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.

• +322

By DarthKnight, 5 years ago, ,

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.

• +608

By DarthKnight, 5 years ago, ,

### Div.2 A — Cursed Query

You should make a sequence s1, s2, ..., sn such that si = a1 + a2 + ... + ai and use a binary search to find the first element that is greater than t % sn (or upper_bound function in C++ ).

Source code : Here

### Div.2 B — Troynacci Query

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, pi +  = a × pi - 2 + b × pi - 1 and ai +  = pi .

Source code : Here

### A — LCM Query

If we have an array x1, x2, ..., xm and for each i, 1 ≤ xi ≤ 60, the number of different element in the array y1, y2, ..., ym such that yj = lcm(x1, x2, ..., xj), is at most log(60!) .Because y1 ≤ y2 ≤ y3 ≤ ... ≤ ym and if yi < yi + 1, then yi ≤ 2 × yi + 1, and ym ≤ 60! .

Actually, it is even less, like 25.

So for each i, you can find all these members for array ai, ai + 1, ..., an using at most 25 binary searches and save them in an array.

And if x = p1b1 × ... × pkbk such that all pis 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 = p1b1 × ... × pkbk and y = p1c1 × ... × pkck, lcm(x, y) = p1max(b1, c1) × ... × pkmax(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(p1b1) + ... + log(pkbk), 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(al, al + 1, ..., ar) in O(25) using Sparce Table.

Source code : Here

### B — ShortestPath Query

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 dv, 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

### C — Subrect Query

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

we have two sequences a1, a2, ..., an and b1, b2, ..., bn and for each i, we know that bi ≤ ai. Our goal is to calculate the number of pairs (l, r) in O(n) such that 1 ≤ l ≤ r ≤ n and max(al, al + 1, ..., ar) - min(bl, bl + 1, ..., br) ≤ 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(al, al + 1, ..., ar) and b[mn.front()] = min(bl, bl + 1, ..., br) .

Now let's get back to the original problem.

For each pair (i, j) such that 1 ≤ i ≤ j ≤ m, build arrays a1, a2, ..., an and b1, b2, ..., bn such that ak = max(ak, i, ..., ak, j) and bk = min(ak, i, ..., ak, j) and then run the code above.

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

Source code : Here

### D — TROY Query

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 ri and column j's boolian is cj.

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

For each query, if ax, y = bx, y so we know that so add an edge between rx and cy and one between ¬rx and ¬cy.

Otherwise, add an edge between ¬rx and cy and one between ¬cy and rx .

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

### E — Palindrome Query

Use Robin-Carp. Let's consider that hi ≡ s1 × p0 + s2 × p1 + ... + si × pi - 1(mod m) .

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

For a modify query, if y = x - sp, you should add y × p0 to hp, y × p1 to hp + 1 and so on. You can do all these using a segment tree or fenwick (BIT).

Source code : Here

### F — Tree Query

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]

• +90

By DarthKnight, 5 years ago, ,

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)

• +157

By DarthKnight, 5 years ago, ,

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 :

Complete standing

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

Announcement of Crypto Cup 1.0

• +132

By DarthKnight, 5 years ago, ,

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 ?