Hi !

As I had promised before, hard version of round #383 will be held on Thursday, 22nd December 15:05 UTC. There will be 4 problems, each problem is a harder version of some problem in round #383. The contest is prepared by me. Please don’t copy your codes from previous contest.

I’d like to thank myself as usual, then Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

P.S. Prepare your fast input / output streams :P

UPD. Note that the Gym is just for training.

TIME CHANGED. Really sorry, but because "Samcode 2016 round #2" will be held tonight (13 to 16 UTC), the gym will be held on Thursday.

UPD. Registration is now open. Note that problems are not sorted according the difficulty.

UPD. Contest is over. Congratulations to winners:

1. KingArthur

2. SlavaSSU

3. team CQBZ找虐组 : JeremyGuo, liujunhao, yuanxinyu402

4. vipsharmavip

5. shengdebao :-|

Editorial.

(This blog has been restored as Errichto and some other users had wanted.)

Hi !

Here is some implementation for solving RMQ (Tarjan’s algorithm) (Range Maximum / Minimum Query).

It’s very simple to implement and it’s time complexity is O((n + q)·a(n)), a() stands for Akerman inverse function used in DSU.

Problem : Given array a of n integers, and q queries, for each query print the maximum value in range [L, R].

Solution: We need a array of vectors, called assigned. assigned[r] contains queries that their R is r. When getting queries, push each query in assigned[R]. We need a dsu, first par_i is i. We need a stack, named st.

For i from 0 to n, do:
	While st is not empty and a[st.top] <= a[i]
		Set i parent of st.top in dsu and pop this element from st.
	Push i to st
	For each query assigned to i
		Answer of this query is a[root of L of this query in DSU].

// God & me
// "Someone like you"?! Unbelievable ... 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 1e5 + 17;
int par[maxn], ans[maxn], n, a[maxn], l[maxn], q;
vector<int> qu[maxn];
int root(int v){
    return par[v] == -1 ? v : par[v] = root(par[v]);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(par, -1, sizeof par);
    cin >> n;
    for(int i = 0; i < n; i++)  cin >> a[i];
    cin >> q;
    for(int i = 0, r; i < q; i++){
	cin >> l[i] >> r, r--, l[i]--;
	qu[r].push_back(i);
    }
    stack<int> st;
    for(int i = 0; i < n; i++){
	while(st.size() && a[st.top()] <= a[i])
	    par[st.top()] = i, st.pop();
	st.push(i);
	for(auto qi : qu[i])
	    ans[qi] = a[root(l[qi])];
    }
    for(int i = 0; i < q; i++)
	cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

Note that in above code I used path-compression technique for dsu only, size-comparing technique can be used too (but it has lower performance).

It’s obviously true, because each time for any j ≤ i, a[root(j)] is the greatest value in range [j, i].

Performance test

// God & me
// "Someone like you"?! Unbelievable ... 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 1 << 22;
int par[maxn], ans[maxn], n, a[maxn], l[maxn], q, head[maxn], prv[maxn], st[maxn], tail;
int root(int v){
    return par[v] == -1 ? v : par[v] = root(par[v]);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(par, -1, sizeof par);
    memset(head, -1, sizeof head);
    cin >> n;
    for(int i = 0; i < n; i++)  cin >> a[i];
    cin >> q;
    for(int i = 0, r; i < q; i++){
	cin >> l[i] >> r, r--, l[i]--;
	prv[i] = head[r], head[r] = i;
    }
    for(int i = 0; i < n; i++){
	while(tail-- && a[ st[tail] ] <= a[i])
	    par[ st[tail] ] = i;
	st[++tail] = i;
	for(int qi = head[i]; qi >= 0; qi = prv[qi])
	    ans[qi] = a[root(l[qi])];
    }
    for(int i = 0; i < q; i++)
	cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

// God & me
// "Someone like you"?! Unbelievable ...
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 22;
int n, q, a[maxn], ans[maxn], head[maxn], prv[maxn], l[maxn];
vector<int> v, qu[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(head, -1, sizeof head);
    cin >> n;
    for(int i = 0; i < n; i++)  cin >> a[i];
    cin >> q;
    for(int i = 0, r; i < q; i++){
	cin >> l[i] >> r;
	prv[i] = head[r], head[r] = i;
    }
    for(int i = 0; i < n; i++){
	while(v.size() && a[v.back()] <= a[i])  v.pop_back();
	v.push_back(i);
	for(int qi = head[i]; qi >= 0; qi = prv[qi])
	    ans[qi] = a[*lower_bound(v.begin(), v.end(), l[qi])];
    }
    for(int i = 0; i < q; i++)
	cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

// God & me
// "Someone like you"?! Unbelievable ... 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 1 << 22, lg = 22;
int par[maxn], ans[maxn], n, q, lg2[maxn];
int spt[lg][maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(par, -1, sizeof par);
    cin >> n;
    for(int i = 0; i < n; i++)
	cin >> spt[0][i];
    for(int i = 2; i < n; i++)  lg2[i] = lg2[i >> 1] + 1;
    for(int k = 1; k < lg; k++)
	for(int i = 0; i + (1 << k) <= n; i++)
	    spt[k][i] = max(spt[k - 1][i], spt[k - 1][i + 1 << (k - 1)]);
    cin >> q;
    for(int i = 0, l, r; i < q; i++){
	cin >> l >> r, r++;
	cout << max(spt[ lg2[r - l] ][l], spt[ lg2[r - l] ][ r - (1 << lg2[r - l]) ]) << ' ';
    }
    cout << '\n';
    return 0;
}

// God & me
// "Someone like you"?! Unbelievable ...
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 22;
template<typename Val, typename Compare = std::less<Val>, int BlockSize = 10>
class DirectRMQ {
public:
	typedef int Index;	//今のところ大きくともintを仮定している(queryとか)
	typedef char InBlockIndex;
	typedef InBlockIndex(*BlockTypeRef)[BlockSize];

	DirectRMQ(Compare comp_ = Compare()) :
		blockTypes(0), innerBlockTable(0), sparseTable(0) {
		comp = comp_;
		calcBallotNumbers();
		buildInnerBlockTable();
	}
	~DirectRMQ() {
		delete[] innerBlockTable;
		delete[] blockTypes; delete[] sparseTable;
	}

	void build(const Val *a, Index n) {
		blocks = (n + BlockSize - 1) / BlockSize;
		stHeight = 0; while(1 << stHeight < blocks) ++ stHeight;
		delete[] blockTypes; delete[] sparseTable;

		blockTypes = new BlockTypeRef[blocks];
		calcBlockTypes(a, n);
		buildInnerBlockTable(a, n);
		sparseTable = new Index[blocks * stHeight];
		buildSparseTable(a);
	}

	//[l,r]の閉区間
	Index query(const Val *a, Index l, Index r) const {
		Index x = l / BlockSize, y = r / BlockSize, z = y - x;
		if(z == 0) return x * BlockSize + blockTypes[x][l % BlockSize][r % BlockSize];
		if(z == 1) return assumeleft_minIndex(a,
			x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1],
			y * BlockSize + blockTypes[y][0][r % BlockSize]);
		z -= 2;
		Index k = 0, s;
		s = ((z & 0xffff0000) != 0) << 4; z >>= s; k |= s;
		s = ((z & 0x0000ff00) != 0) << 3; z >>= s; k |= s;
		s = ((z & 0x000000f0) != 0) << 2; z >>= s; k |= s;
		s = ((z & 0x0000000c) != 0) << 1; z >>= s; k |= s;
		s = ((z & 0x00000002) != 0) << 0; z >>= s; k |= s;
		return assumeleft_minIndex(a
			, assumeleft_minIndex(a,
				x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1],
				sparseTable[x + 1 + blocks * k])
			, assumeleft_minIndex(a,
				sparseTable[y + blocks * k - (1 << k)],
				y * BlockSize + blockTypes[y][0][r % BlockSize])
		);
	}

	Val queryVal(const Val *a, Index l, Index r) const {
		Index x = l / BlockSize, y = r / BlockSize, z = y - x;
		if(z == 0) return a[x * BlockSize + blockTypes[x][l % BlockSize][r % BlockSize]];
		Val edge = minVal(
			a[x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1]],
			a[y * BlockSize + blockTypes[y][0][r % BlockSize]]);
		if(z == 1) return edge;
		z -= 2;
		Index k = 0, s;
		s = ((z & 0xffff0000) != 0) << 4; z >>= s; k |= s;
		s = ((z & 0x0000ff00) != 0) << 3; z >>= s; k |= s;
		s = ((z & 0x000000f0) != 0) << 2; z >>= s; k |= s;
		s = ((z & 0x0000000c) != 0) << 1; z >>= s; k |= s;
		s = ((z & 0x00000002) != 0) << 0; z >>= s; k |= s;
		return minVal(edge, minVal(
			a[sparseTable[x + 1 + blocks * k]],
			a[sparseTable[y + blocks * k - (1 << k)]]));
	}
private:
	Compare comp;

	int ballotNumbers[BlockSize + 1][BlockSize + 1];
	InBlockIndex(*innerBlockTable)[BlockSize][BlockSize];

	Index blocks;
	int stHeight;
	BlockTypeRef *blockTypes;
	Index *sparseTable;

	inline Index minIndex(const Val *a, Index x, Index y) const {
		return comp(a[x], a[y]) || (a[x] == a[y] && x < y) ? x : y;
	}
	inline Index assumeleft_minIndex(const Val *a, Index x, Index y) const {
		return comp(a[y], a[x]) ? y : x;
	}

	inline Val minVal(Val x, Val y) const {
		return comp(y, x) ? y : x;
	}

	void buildSparseTable(const Val *a) {
		Index *b = sparseTable;
		if(stHeight) for(Index i = 0; i < blocks; i ++)
			b[i] = i * BlockSize + blockTypes[i][0][BlockSize - 1];
		for(Index t = 1; t * 2 < blocks; t *= 2) {
			std::memcpy(b + blocks, b, blocks * sizeof(Index));
			b += blocks;
			for(Index i = 0; i < blocks - t; ++ i)
				b[i] = assumeleft_minIndex(a, b[i], b[i + t]);
		}
	}

	void buildInnerBlockTable(const Val *a, Index n) {
		for(Index i = 0; i < blocks; i ++) {
			BlockTypeRef table = blockTypes[i];
			if(table[0][0] != -1) continue;
			const Val *p = getBlock(a, n, i);
			for(InBlockIndex left = 0; left < BlockSize; left ++) {
				Val minV = p[left];
				InBlockIndex minI = left;
				for(InBlockIndex right = left; right < BlockSize; right ++) {
					if(comp(p[right], minV)) {
						minV = p[right];
						minI = right;
					}
					table[left][right] = minI;
				}
			}
		}
	}

	//端っこのブロック用に関数内staticなテンポラリ配列を返す
	const Val *getBlock(const Val *a, Index n, Index i) {
		Index offset = i * BlockSize;
		if(offset + BlockSize <= n)
			return a + offset;
		else {
			static Val tmp_a[BlockSize];
			std::copy(a + offset, a + n, tmp_a);
			Val maxVal = Val();
			for(Index j = i; j < n; j ++)	//iでなくoffsetでは？(動作には問題ないし計算量もほとんど変わらないけれど…)(バグるのが嫌なので(今まで動いていたので)直すのは後にする)
				if(comp(maxVal, a[j])) maxVal = a[j];
			std::fill(tmp_a + (n - offset), tmp_a + BlockSize, maxVal);
			return tmp_a;
		}
	}

	void calcBlockTypes(const Val *a, Index n) {
		Val tmp_rp[BlockSize + 1];
		for(Index i = 0; i < blocks; i ++)
			blockTypes[i] = calcBlockType(getBlock(a, n, i), tmp_rp);
	}

	BlockTypeRef calcBlockType(const Val *a, Val *rp) {
		int q = BlockSize, N = 0;
		for(int i = 0; i < BlockSize; i ++) {
			while(q + i - BlockSize > 0 && comp(a[i], rp[q + i - BlockSize])) {
				N += ballotNumbers[BlockSize - i - 1][q];
				q --;
			}
			rp[q + i + 1 - BlockSize] = a[i];
		}
		return innerBlockTable[N];
	}

	void calcBallotNumbers() {
		for(int p = 0; p <= BlockSize; p ++) {
			for(int q = 0; q <= BlockSize; q ++) {
				if(p == 0 && q == 0)
					ballotNumbers[p][q] = 1;
				else if(p <= q)
					ballotNumbers[p][q] =
					(q ? ballotNumbers[p][q - 1] : 0) +
					(p ? ballotNumbers[p - 1][q] : 0);
				else
					ballotNumbers[p][q] = 0;
			}
		}
	}

	void buildInnerBlockTable() {
		int numberOfTrees = ballotNumbers[BlockSize][BlockSize];
		innerBlockTable = new InBlockIndex[numberOfTrees][BlockSize][BlockSize];
		for(int i = 0; i < numberOfTrees; i ++)
			innerBlockTable[i][0][0] = -1;
	}
};
int n, q, a[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
	cin >> a[i];
    DirectRMQ<int> rmq;
    rmq.build(a, n);
    cin >> q;
    for(int i = 0, l, r; i < q; i++){
	cin >> l >> r;
	cout << rmq.queryVal(a, l, r) << ' ';
    }
    cout << '\n';
    return 0;
}

// God & me
// "Someone like you"?! Unbelievable ...
#include <bits/stdc++.h>
using namespace std;


const int n = 1 << 22;
int a[n];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    srand(time(0));
    cout << n << '\n';
    iota(a, a + n, 0);
    random_shuffle(a, a + n); // used for generating random test
    for(int i = 0; i < n; i++)
	cout << a[i] << " \n"[ i == n - 1 ];
    cout << n << '\n';
    for(int i = 0; i < n; i++){
	int l = rand() % n, r = rand() % n;
	if(l > r)  swap(l, r);
	cout << l << ' ' << r << '\n';
    }
    return 0;
}

Here is the result:

Hello again, and hope you have been Joon-Joon of the round :P

I’m preparing harder version of some of the problems (Div.2 A, B, and Div.1 A, D) and I’ll put them on some gym, so if you are interested in harder version of problems please wait for about one week.

You can see and download the problem archives (pretests, tests, statements, validator, checker, solutions) here. You can see solutions in solutions folder, note that there are several codes there, there is a descriptor for each code (.desc) that shows the verdict of that code.

Preparation details:

On 25 May Batman came up with problem Div.1 D and other problems authored inchmeal.

9/25/16: Proposal sent to Gleb.

11/12/16: Answer from Gleb: Your proposal has been redirected to Nikolay KAN.

11/15/16: Nikolay has replied, and commented about problems, saying some problems are easy, some are hard, some are ok.

I changed some of the problems, change the constraints for some others and we talked about solutions through email.

11/17/16: We switched to Telegram.

Creating tests, writing generators, writing statements, etc started in the Polygon.

12/06/16: Round #383 hold.

gKseni told me how you want to get your money and I had no idea.

gKseni told me that it is possible to transfer my money and finally May 4, 2017, I received my money through Okpay.

I have another problem set to prepare another div.1 + div.2 round, but I haven’t enough time now :(.

Paintings in problems were suggested by me, painted by Batman and edited by me. Problem stories and this editorial were suggested and written by me. KAN helped us preparing the round very much, we are thankful to him. This table for each person and for each problem shows the number of the committed changes (in polygon) he has made in preparing the problem (it is good for showing how much someone was involved in preparing).

I used Google Docs for writing everything.

Here is another table, showing the number of expected accepts (in my opinion, before the contest) and the number of accepts (after system testing).

Hints

Div.2 A: Write the last digit of 1378ⁿ for several small values.

Div.2 B : Note that if then .

Div.1 A: If the answer exists, it depends on the lengths of cycles in the functional graph.

Div.1 B: It’s similar to a simple knapsack problem, think on O(n·W) solution using dynamic programming.

Div.1 C: Build a graph and put edges between each 2 * i, 2 * i + 1 and each BF and GF.

Div.1 D: Keep a mask for each vertex, i-th bit of mask_v is true if the number of edges in the path from root to v such that letter i is written on them is odd. Now if number of bits in is 0 or 1, path between v and u is Dokhtar-kosh.

Div.1 E: Sort all of the options, then the problem becomes easier, solve the new problem with sqrt decomposition.

Details

Div.2 A

Idea, authoring, solution by Batman, preparation by Batman and me.

My and Batman ’s birth year in Solar Hijri calendar is 1378.

Div.2 B

Idea, authoring, solution by Batman, preparation by Batman and me.

Div.1 A

Idea, authoring, solution, preparation by me.

Attractive boys/girls are called Joon-Joon in Persian. Owf is a sound used when we (Persian) are interested in something, especially when we see something attractive, such as our crush :P

Div.1 B:

Idea, authoring, solution, preparation by me.

The problem authored by me 2 days before the contest :D (#FastAsFerrari). Attractive girls are called (some word similar to) “Hos” in Persian. It’s a good place to thank amsen, whose name (Hir) gave me this idea (to use word “Hos” instead of “attractive girl”).

Div.1 C :

Idea, authoring, solution by Batman, preparation by Batman and me.

“Kooft” is something make people die. “Zahre-mar” meaning is “Venom of Snake”.

Div.1 D:

Idea by Batman, authoring, solution, preparation by me.

“Dokhtar-kosh” is an adjective, used when something is very very attractive.

Div.1 E:

Idea, authoring, solution, preparation by me.

Solutions

I’d like to finish the editorial with the below poem by Hafez:

Translation: I have never seen anything that sounds better than love, it’s the relic which will remain in the universe.

Good luck and see you soon in “Round #383 hard version” ;)

Hi!

I'm honored to invite you to Codeforces Round #383, it will be held on 6nd December 14:35 UTC. There will be 5 problems for each division as usual. The contest was prepared by AmirReza Arpa PoorAkhavan and Mehrdad Batman Saberi. It's our first official contest at CodeForces.

The contest stories will be about Arpa and Mehrdad and some events happen with them in Arpa's land, in addition you will get some information about Arpa's land and girls living there (Owf (t = 1)).

I'd like to thank myself (:P) and Mehrdad at first, then Nikolay KAN Kalinin for helping me in preparing problems and Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

The scoring distribution will be announced later.

Answer for one of your common questions : -Yes, It is rated.

UPD. GL & HF. Hope you came up with Dokhtar-kosh solutions for our Dokhtar-kosh problems.

Urgent information from MikeMirzayanov: due to hardware issues, the round is moved to Tuesday 6th December, 14:35 UTC. We are very sorry this happened. More information is available in this post.

UPD. Scoring distribution: Div.1 : 500-1000-1250-2000-2500, Div.2 : 500-1000-1500-2000-2250.

UPD. Contest is over, hope you have been Joon-Joon of the round :P

Congratulations to winners:

Div.1:

1 . jqdai0815

2 . mnbvmar

3 . data_h and nuip (WoW :O)

5 . Phronesis

Sepcial congratulations to anta who solved Div.1 E.

Div.2:

1 . gilcu3

2 . toHisDream

3 . Far

4 . shpsi

5 . orz_liuwei

Editorial is ready.

Hi !

After a long delay I want to publish INOI (Iran National Olympiad of Informatics) results :

Gold medal :

1. Seyed Mohammad Hossein Nematollahi (Deemo).

2. amir azarmehr (AmirAz).

3. Mohammad Saneian (SaSa).

4. HamidReza Hedayati (ITDOI).

5. Ali Ahmadi (Kuzey).

6. Ali Shafiei (ToTLeS).

7. Iman Gholami (IMAN_GH).

8. Majid Garoosi (NikaraBika).

Silver medal (Only Top5 and last) :

1. Yara Kamkar (yarak).

2. Seyed Hossein Moosavi (mr_agha_seyed).

3. Shayan CheshmJahan (Shayan).

4. Soroosh Taslimi (Information_schema) (Thanks to Navick).

5. Mehrdad Saberi (Batman).

...

16 . Keyvan Rezaei (Navick) (I added him because of amsen's Comment :D)

I want to congratulate my best friends, Shayan CheshmJahan, Mehrdad Saberi, Seyed Mohammad Hossein Nematollahi and specially Ali Shafiei, and my other friends. And I wish the bests for my friend Yara Kamkar in next steps of life.

UPD: I found a blog describing this blog: Link.

Hi!

Most of the people know about dsu but what is the "dsu on tree"?

In Iran, we call this technique "Guni" (the word means "sack" in English), instead of "dsu on tree".

I will explain it and post ends with several problems in CF that can be solved by this technique.

What is the dsu on tree?

With dsu on tree we can answer queries of this type:

How many vertices in the subtree of vertex v has some property in time (for all of the queries)?

For example:

Given a tree, every vertex has color. Query is how many vertices in subtree of vertex v are colored with color c?

Let's see how we can solve this problem and similar problems.

First, we have to calculate the size of the subtree of every vertice. It can be done with simple dfs:

int sz[maxn];
void getsz(int v, int p){
    sz[v] = 1;  // every vertex has itself in its subtree
    for(auto u : g[v])
        if(u != p){
            getsz(u, v);
            sz[v] += sz[u]; // add size of child u to its parent(v)
        }
}

Now we have the size of the subtree of vertex v in sz[v].

The naive method for solving that problem is this code(that works in O(N ^ 2) time)

int cnt[maxn];
void add(int v, int p, int x){
    cnt[ col[v] ] += x;
    for(auto u: g[v])
        if(u != p)
            add(u, v, x)
}
void dfs(int v, int p){
    add(v, p, 1);
    //now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
    add(v, p, -1);
    for(auto u : g[v])
        if(u != p)
            dfs(u, v);
}

Now, how to improve it? There are several styles of coding for this technique.

1. easy to code but .

map<int, int> *cnt[maxn];
void dfs(int v, int p){
    int mx = -1, bigChild = -1;
    for(auto u : g[v])
       if(u != p){
           dfs(u, v);
           if(sz[u] > mx)
               mx = sz[u], bigChild = u;
       }
    if(bigChild != -1)
        cnt[v] = cnt[bigChild];
    else
        cnt[v] = new map<int, int> ();
    (*cnt[v])[ col[v] ] ++;
    for(auto u : g[v])
       if(u != p && u != bigChild){
           for(auto x : *cnt[u])
               (*cnt[v])[x.first] += x.second;
       }
    //now (*cnt[v])[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.

}

2. easy to code and .

vector<int> *vec[maxn];
int cnt[maxn];
void dfs(int v, int p, bool keep){
    int mx = -1, bigChild = -1;
    for(auto u : g[v])
       if(u != p && sz[u] > mx)
           mx = sz[u], bigChild = u;
    for(auto u : g[v])
       if(u != p && u != bigChild)
           dfs(u, v, 0);
    if(bigChild != -1)
        dfs(bigChild, v, 1), vec[v] = vec[bigChild];
    else
        vec[v] = new vector<int> ();
    vec[v]->push_back(v);
    cnt[ col[v] ]++;
    for(auto u : g[v])
       if(u != p && u != bigChild)
           for(auto x : *vec[u]){
               cnt[ col[x] ]++;
               vec[v] -> push_back(x);
           }
    //now cnt[c] is the number of vertices in subtree of vertex v that has color c.
    // note that in this step *vec[v] contains all of the subtree of vertex v.
    if(keep == 0)
        for(auto u : *vec[v])
            cnt[ col[u] ]--;
}

3. heavy-light decomposition style .

int cnt[maxn];
bool big[maxn];
void add(int v, int p, int x){
    cnt[ col[v] ] += x;
    for(auto u: g[v])
        if(u != p && !big[u])
            add(u, v, x)
}
void dfs(int v, int p, bool keep){
    int mx = -1, bigChild = -1;
    for(auto u : g[v])
       if(u != p && sz[u] > mx)
          mx = sz[u], bigChild = u;
    for(auto u : g[v])
        if(u != p && u != bigChild)
            dfs(u, v, 0);  // run a dfs on small childs and clear them from cnt
    if(bigChild != -1)
        dfs(bigChild, v, 1), big[bigChild] = 1;  // bigChild marked as big and not cleared from cnt
    add(v, p, 1);
    //now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
    if(bigChild != -1)
        big[bigChild] = 0;
    if(keep == 0)
        add(v, p, -1);
}

4. My invented style .

This implementation for "Dsu on tree" technique is new and invented by me. This implementation is easier to code than others. Let st[v] dfs starting time of vertex v, ft[v] be it's finishing time and ver[time] is the vertex which it's starting time is equal to time.

int cnt[maxn];
void dfs(int v, int p, bool keep){
    int mx = -1, bigChild = -1;
    for(auto u : g[v])
       if(u != p && sz[u] > mx)
          mx = sz[u], bigChild = u;
    for(auto u : g[v])
        if(u != p && u != bigChild)
            dfs(u, v, 0);  // run a dfs on small childs and clear them from cnt
    if(bigChild != -1)
        dfs(bigChild, v, 1);  // bigChild marked as big and not cleared from cnt
    for(auto u : g[v])
	if(u != p && u != bigChild)
	    for(int p = st[u]; p < ft[u]; p++)
		cnt[ col[ ver[p] ] ]++;
    cnt[ col[v] ]++;
    //now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
    if(keep == 0)
        for(int p = st[v]; p < ft[v]; p++)
	    cnt[ col[ ver[p] ] ]--;
}

But why it is ? You know that why dsu has time (for q queries); the code uses the same method. Merge smaller to greater.

If you have heard heavy-light decomposition you will see that function add will go light edges only, because of this, code works in time.

Any problems of this type can be solved with same dfs function and just differs in add function.

Hmmm, this is what you want, problems that can be solved with this technique:

(List is sorted by difficulty and my code for each problem is given, my codes has heavy-light style)

600E - Lomsat gelral : heavy-light decomposition style : Link, easy style : Link. I think this is the easiest problem of this technique in CF and it's good to start coding with this problem.

570D - Tree Requests : 17961189 Thanks to Sora233; this problem is also good for start coding.

Sgu507 (SGU is unavailable, read the problem statements here) This problem is also good for the start.

HackerEarth, The Grass Type This problem is also good for start (See bhishma's comment below).

246E - Blood Cousins Return : 15409328

208E - Blood Cousins : 16897324

IOI 2011, Race (See SaYami's comment below).

291E - Tree-String Problem : See bhargav104's comment below.

1009F - Dominant Indices : 40332812 Arpa-Style. Thanks to Tanmoy_Datta.

343D - Water Tree : 15063078 Note that problem is not easy and my code doesn't use this technique (dsu on tree), but AmirAz 's solution to this problem uses this technique : 14904379.

375D - Tree and Queries : 15449102 Again note that problem is not easy :)).

716E - Digit Tree : 20776957 A hard problem. Also can be solved with centroid decomposition.

741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths : 22796438 A hard problem. You must be very familiar with Dsu on tree to solve it.

For Persian users, there is another problem in Shaazzz contest round #4 (season 2016-2017) problem 3 that is a very hard problem with this technique.

If you have another problem with this tag, give me to complete the list :)).

And after all, special thanks from PrinceOfPersia who taught me this technique.

Hi !

Today while solving 356D - Bags and Coins I needed a function for bitset in order see what is the first set bit.I asked M.Mahdi and he told me about bs._Find_first(). for example:

bitset<17>BS;
BS[1] = BS[7] = 1;
cout<<BS._Find_first()<<endl; // prints 1

After more research , we found bs._Find_next(idx). This function returns first set bit after index idx.for example:

bitset<17>BS;
BS[1] = BS[7] = 1;
cout<<BS._Find_next(1)<<','<<BS._Find_next(3)<<endl; // prints 7,7

So this code will print all of the set bits of BS:

for(int i=BS._Find_first();i< BS.size();i = BS._Find_next(i))
    cout<<i<<endl;

Note that there isn't any set bit after idx, BS._Find_next(idx) will return BS.size(); same as calling BS._Find_first() when bitset is clear;

UPD One question, bitset is 32 or 64 times faster than bool array?

Hi!

I thought that unordered_set is faster than set, because set complexity is logarithmic in size and unordered_set complexity is constant time in average.(source: cplusplus.com)

But today I saw this:

TLE(>2000 MS) with unordered_set: 15494816

Accepted(155 MS) with set: 15494846

Also my other solution(witch I submitted during the contest) with unordered_map hacked :'(

Now my question is : Is unordered_set faster than set?

UPD: I have accepted(15497282).unordered_set time was better than set(15494846) : 93<155.

Only with adding this line:s.max_load_factor(0.25);s.reserve(500);.

UPD2: it seems that it is better to use a power of 2 in reserve(i.e. s.reserve(512)).(Thanks from keyvankhademi)

Hi!

One of the C++ programmers problems is to work with integers greater than 2^64-1 (we can save 0to 2^64-1 in unsigned long long int). So I want to share the best Bignum implementation I have ever seen (Link) with CodeForces Community.

Its specifications are as follows:

• Supported operations: + , -, / , * , % , ^(pow) , gcd , lcm , abs.

• It is able to work with Standard Input/Output streams.

• It can cast data to long long, string.

• It uses fast multiplication.

source.(but I have edited that and added pow and size().)

UPD1 (September 2016): Bug in void operator=(long long v) is now fixed. Thanks to amsen.

Hi!

I am in virtual contest and I'm seeing this in my friends standings.

What is the problem?

P.S. top10 in contest:

Hi!

After my previous post about unordered_map now I want to explain hash functions.

std::hash.

C++ STL has one hash function in library <functional>. You can use it for this data types:

template<> struct hash<bool>;
template<> struct hash<char>;
template<> struct hash<signed char>;
template<> struct hash<unsigned char>;
template<> struct hash<char16_t>;
template<> struct hash<char32_t>;
template<> struct hash<wchar_t>;
template<> struct hash<short>;
template<> struct hash<unsigned short>;
template<> struct hash<int>;
template<> struct hash<unsigned int>;
template<> struct hash<long>;
template<> struct hash<long long>;
template<> struct hash<unsigned long>;
template<> struct hash<unsigned long long>;
template<> struct hash<float>;
template<> struct hash<double>;
template<> struct hash<long double>;

For example:

hash<int>hi;
int x=69;
cout<<hf(x)<<endl;
hash<long double>hld;
long double y=69.6969696969;
cout<<hld(y)<<endl;
hash<vector<int> >hv;
vector<int>v({69,69,69,69});//v→ 69,69,69,69
cout<<hv(v)<<endl;

Hand-made hash functions.

There are many ways to create hash function for your struct. For example:

struct reval{
  vector<int>v;
  int n;
  string s;
  size_t hash(){//size_t is alias of unsigned int
    hash<string>hs;
    hash<long long>hll;
    hash<int>hi;
    hash<vector>hv;
    long long ans=hs(s);
    ans<<=32;
    ans|=hi(n);
    ans=hll(ans);
    ans<<=32;
    ans|=hv(v);
    ans=hll(ans);
    return ans;
  }
}

A simple example:(be careful;it is only a sample and it isn't good hash function of course)

struct reval{
  vector<int>v;
  int n;
  string s;
  size_t hash(){//size_t is alias of unsigned int
    hash<string>hs;
    hash<int>hi;
    hash<vector>hv;
    return hs(s)+hv(v)+hi(n);
  }
}

A trick:

struct S{
  string first_name;
  string last_name;
};
namespace std{
    template<>struct hash<S>{
        size_t operator()(S const& s) const{
            size_t h1=hash<string>()(s.first_name);
            size_t h1=hash<string>()(s.last_name);
            return hash<long long>()( (h1<<32)^h2 );
        }
    };
}
int main(){
    S s;
    s.first_name="MohammadSina";
    s.last_name="PakSeresht";
    cout <<"hash(s) = "<<hash<S>()(s)<<endl;
}

Note1: You can use hash<type>()(variable), like this:

int x=69;
cout<<hash<int>()(x)<<endl;

Instead of:

int x=69;
hash<int>hasher;
cout<<hasher(x)<<endl;

Note2: please be careful about combining two hashes. There are two good ways:

1-x*P+y mod M(when P is prime number (like 43) and M is less than 2^32 and not a power of 2 (like 10^9+7)).

2-hash<long long>()((x<<32)^y) or hash<long long>()(x*1000000007LL+y).

UPD: Tricks to make unordered_map faster added.

Hi!

What is unordered_map?

It is a data structure like map but it is more than 4 times faster than map.you can use it in C++11 with including #include<unordered_map>.for example:

#include<unordered_map>
using namespace std;
int main(){
  unordered_map<int,int>mp;
  mp[5]=12;
  mp[4]=14;
  cout<<mp[5]<<' '<<mp[4]<<endl;//prints: 12 14
}

Lets explain it more.

How it works?

Focus on unordered_set for simplify.You can imagine that it has vector of vector like vector<vector<type> > mp. Every time you insert value V in that, it calculate its hash(I will explain how it works), let hash(V)=K; it inserts V into mp[K] (formally it calls mp[K].push_back(V)).When you call mp.count(V) it searchs for V in mp[K].

map VS unordered_map (and set VS unordered_set)

1-unordered_map is more than 4 times faster

Focus on problem 527E - Страсти в дата-центре, it seems that it is good to use unordered_map instead of map.

My submission with map: 14269000 Time:484 MS.

My submission with unordered_map: 14269381 Time:358 MS.

Another good sample to show how fast is unordered_map is problem 178C3 - Бобер и разрешение коллизий:

My submission with map: 15781810 Time limit exceeded on test 36 .

My submission with unordered_map: 15774685 Accepted (Time:966 MS).

2-unordered_set (and unordered_map) is not sorted

Please note that set (and map) is sorted, for example *(s.begin()) is always smallest number in the set; but in unordered_set it isn't. similarly there isn't lower_bound and upper_bound in unordered_set (and unordered_map similarly).

Creating hash function for structs

Now, one other problem remains, you can try to compile this code:

unordered_map<pair<int,int>,int>mp;

You will get Compilation Error! Why? See this page for unordered_map supported types. For unsupported types, you have to create your own hash function for use. For example lets see how we can create a hash function for pair<int,int>.

As you know any int value is between -2^31+1 to 2^31-1.so if we create function that for every pair<int,int> returns distinct value in type size_t(alias of unsigned int), it will be done. It is pretty easy: x.first^(x.second<<32) is good. but be careful about overflow ;for having good hash function we use hash<long long>.The code is looks like this:

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};
unordered_map<pair<int,int>,int,HASH>mp;

Now you have a unordered_map of pair<int,int> (it isn't problem what is second member, in example it was int).Creating hash function for other structs is same.

How to test unordered_map is faster than map?

You can test that for N=10^6, unordered_set(unordered_map) is more than 4 times faster than set(map) ;with this code:(compile code with command: g++ file.cpp -std=c++11 -O2)

#include <bits/stdc++.h>
using namespace std;
unordered_set<int>s;//replace it with set for test.
int main(){
  auto T=clock();
  s.reserve(32768); //updated !
  s.max_load_factor(0.25); //updated !
  for(int i=0;i<1000000;i++)
    s.insert(i);
  cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
}

Note1: Let your hash function H(V), it is better that H(V) returns distinct value for every distinct V, it makes unordered_map faster; but if you can't do that it doesn't problem. The only problem is that unordered_map becomes slower(however it is better than map).

Note2: Please be careful about your hash function time complexly! it is fun to use this hash function:

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    size_t ans=0;
    for(int i=0;i<x.first;i++)
      ans+=x.second;
    return ans;
  }
};

UPD I will explain hash<type> in my next post.

UPD It seems that sometimes unordered_map becames so slow.but it can improve with this two lines of code:

unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);

With this two lines unordered_map become about 10 times faster. You can replace 1024 with another suitable power of two.(it depends on number of insert s you will do).

Hi!

COCI (CROATIAN OPEN COMPETITION IN INFORMATICS) will be held saturday.

Let's discuss about problems after contest.

Hello

it will be good for all programmers :)

https://sercantutar.github.io/infint/

Geek trick: you can paste all InfInt.h to top your code for sending it for CF or another programming sites :D