Hi!

I'm here to introduce a new series of contests on HackerEarth, Data Structures and Algorithms (DSA) coding challenge! In this series, you will have to solve 3 problems in 1.5 hours.

The problems are classic and educational as against being creative and challenging. So, if you're learning new things, don't miss the DSA contests. These contests are similar to Codeforces Educational rounds.

We have hard problems and easy problems in this contest. After the contest, don't forget to upsolve! This will help you a lot.

The next DSA contest is on September 14, 4 AM UTC.

Authors are Devarshi (devarshi09) Khanna, Prakash (forgotter) Jha, and, Aditya (aditya123garg) Garg. I'm the tester of the round.

GL & HF!

UPDATE: I'm no longer contest coordinator at HackerEarth, contact tripti@hackerearth.com for proposing problems

Please read this blog as an update.

Hi everyone.

I want to describe the process to become a problem setter on HackerEarth. I'm eager to see new problem setters want to prepare contests. It's a great experience for every coder to hold a contest at least once. The first time when I prepared a contest (I was fifteen at that time, a high schooler student!) it was so sweet for me that I continued preparing problems on Codeforces, CodeChef, HackerEarth, Quera, Iran Olympiad of Informatics Finals and several more. Then I worked for 1.5 years in Quera as the contest coordinator, which was great. I'm continuing my job — Contest Coordinating — on HackerEarth from January.

We have three algorithmic contest every month, here is the table:

As you can see, we need a lot of problems every month. To propose a problem, follow this instruction:

• Register on Ninja Setters platform. where you can write your proposal.
• I'll check your problem soon. If approved, you should prepare test cases, solution.
• We'll have you in a contest!

Our proposal queue is almost empty, so if you propose a problem today, with a high probability, your problem will be used in August contests. Here is the compensation table:

P. S. You don't need to prepare the whole contest. A contest may have many setters, so even if you send one problem, it's welcomed.

P. S. We need an approximation problem every month. Propose it if you have some. Check the last Circuits contest for an example.

Update. It's not needed to send me a message when you register on Ninja Setters, just wait for several days, I'll add you to group such that you can start proposing problems.

Update. Users with rating less than 1600 can propose problems but the probability of acceptance is low.

Hello everyone!

Another long and exciting contest is here, June Circuits '19, a challenging challenge with 8 amazing problems, should be solved in 9 days. The contest will start on June 21, 15:30 PM UTC.

Thanks to problem setters for doing such a fantastic job, we have 7 setters involved this time (!):

• A problem by Monu monu.kumar Kumar
• A problem by Dishant Dishant_18 Trivedi
• A problem by Munish minki_6161 Sharma
• A problem by Pranjal KUMAR_PRANJAL_RAI Rai
• A problem by Nitesh nitesh_gupta Gupta
• A problem by Danylo Danylo99 Mocherniuk
• And two problem by Orap Dalgerok Andrew

I'm tester of the round, I'm completely sure that you'll enjoy too!

To make the challenge more interesting, we will add problems to the contest in this order:

• Day 0: Very-Easy, Easy-medium, Approximation.
• Day 2: Medium, Medium.
• Day 4: Medium, Medium.
• Day 6: Medium-Hard.

As usual, there will be some sweet prizes for the top five competitors:

• First place: $100 Amazon gift card + HE t-shirt.
• Second place: $75 Amazon gift card + HE t-shirt.
• Third place: $50 Amazon gift card + HE t-shirt.
• Fourth place: HE t-shirt.
• Fifth place: HE t-shirt.

Hope to see you on the leaderboard!

Hi all!

Happy Eid Fitr to all Muslims in the Codeforces community.

Hello!

Welcome to June Easy '19, from our easy and educational contest series. It's a 3-hour competition with six algorithmic tasks. We are going to hold it on Sunday at 16:00 GMT. Check contest page for more details.

I helped Danylo Danylo99 Mocherniuk, Mohammad-Mahdi Kerpoo Taheri, and, Dishant Dishant_18 Trivedi setting this round. AmirHossein amsen Pashaee and I are testers of the contest. As usual, here are the prizes for the top three contestants:

• $75 Amazon gift card
• $50 Amazon gift card
• $25 Amazon gift card

Note that prizes and T-shirts are given to top participants with ratings < 1600 (beginners).

GL & HF.

Let's discuss the problems after the contest!

P. S. Sorry for problems occurred. Now everything fixed.

Hello everyone!

Another long and exciting contest is here, May Circuits '19, a challenging challenge with 8 amazing problems, should be solved in 10 days. The contest will start on May 24, 15:30 PM UTC.

Thanks to problem setters for doing such a fantastic job, we have:

• Four problems from Kasra KMAASZRAA Mazaheri.
• A problem from Danylo Danylo99 Mocherniuk.

Also, I helped them by adding three problems.

I, Danial Danial Erfanian, and, Javad javaD Karimi were the testers of the round, and we enjoyed solving problems, we're entirely sure that you'll enjoy too!

To make the challenge more interesting, we will add problems to the contest in this order:

• Day 0: Very-Easy, Easy-medium, Approximation.
• Day 1: Easy-Medium, Easy-medium.
• Day 4: Medium-Hard, Medium-Hard.
• Day 6: Hard.

As usual, there will be some sweet prizes for the top five competitors:

• First place: $100 Amazon gift card + HE t-shirt.
• Second place: $75 Amazon gift card + HE t-shirt.
• Third place: $50 Amazon gift card + HE t-shirt.
• Fourth place: HE t-shirt.
• Fifth place: HE t-shirt.

Hope to see you at the scoreboard!

Hello!

I'm honored to invite you to April Easy '19; it's a 3-hour competition with 6 algorithmic tasks. We are going to hold it on Saturday (Today) at 16:00 GMT (you can check your timezone here). Check contest page for more details about in-contest schedule and rules.

AghaTizi is the setter of this round and Aryan is the tester of problems. As usual, here are the prizes for the top three contestants:

• $75 Amazon gift card
• $50 Amazon gift card
• $25 Amazon gift card

Note that prizes and T-shirts are given to top participants with ratings < 1600 (beginners).

GL & HF.

Let's discuss the problems after the contest!

P.S. Sorry for the late announcement.

Hello everyone!

As the new contest coordinator in HackerEarth, I'm honored to announce, we're here with the new version of circuits contests, March Circuits '19, a challenging challenge with 8 amazing problems, should be solved in 10 days. The contest will start on March 22, 15:30 PM UCT.

This time setters around the world helped us make this round possible. We have:

• A problem from Parsa Man Abdollahi.
• Two problems from Erfan Erfan.aa Alimohammadi.
• A problem from Pranjal KUMAR_PRANJAL_RAI Rai.
• A problem from Hrudai kingofbugs Pabbisetty.
• Two problems from Imran SkullKnight Hasan.
• A problem from Ivan isaf27 Safonov.

I was the tester of the round and enjoyed solving problems, I'm sure that you'll enjoy too!

To make the challenge more interesting, problems added to the contest in this order:

• Day 0: Very-Easy, Easy, Approximation.
• Day 1: Easy-Medium, Medium.
• Day 4: Medium, Medium-Hard.
• Day 6: Medium-Hard.

As usual, there will be some nice prizes for the top five competitors:

• First place: $100 Amazon gift card + HE t-shirt.
• Second place: $75 Amazon gift card + HE t-shirt.
• Third place: $50 Amazon gift card + HE t-shirt.
• Fourth place: HE t-shirt.
• Fifth place: HE t-shirt.

Hope to see you at the scoreboard!

Good Luck & Have Fun ;)

Hello!

As the new Contest Coordinator at HackerEarth, I'm honored to invite you to HackerEarth HourStorm #8; it's a 1-hour competition with 3 traditional (but nice) algorithmic tasks. We are going to hold it on Friday at 14:30 GMT (you can check the time here.

For traditional algorithmic tasks, you will receive points for every test case your solution passes, so you can get some points with partial solutions as well. Check contest page for more details about in-contest schedule and rules.

MazzForces is the setter of this round and I'm the tester of problems. Prepared problems were interesting and I enjoyed solving them, I hope you find them interesting too. As usual, here are the prizes for the top three contestants:

• $75 Amazon gift card
• $50 Amazon gift card
• $25 Amazon gift card

In addition, the top 5 will win HackerEarth t-shirts.

GL & HF.

Let's discuss the problems after the contest!

P.S. I'm sorry for the problem occurred on problem B (A counting problem). I was the tester of this contest; the problem was Anand has changed test cases and didn't run my solution on test cases again and his solution has a little bug, so test cases 17-29 were wrong. We apologize for this problem. Now rejudge is done.

Here are the winners:

• Gennady Korotkevich (tourist)
• Trung Nguyen (chemthan)
• Egor Kulikov (Egor)

Hello, We would like to invite the Codeforces community to the CodeChef November Lunchtime 2018 sponsored by Sharechat — a contest you will surely enjoy competing in. This is a 3-hour contest with 5 problems to work on and it’s open to programmers across the globe.

The contest problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese. In addition, there are some exciting job opportunities from ShareChat — India’s fastest growing social network for programmers across the globe. For more details, you may visit the November Lunchtime contest page.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

• Setter: Nots0fast (Rehim Memmedli)
• Tester: Arpa (AmirReza PoorAkhavan)
• Statement Verifier: Xellos (Jakub Safin)
• Editorialist: Pepe.Chess (Hussain Kara Fallah)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava

Contest Details:

• Start Date & Time: 24th November 2018 (1930 hrs) to 24th November 2018 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
• Contest link: https://www.codechef.com/LTIME66
• Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 10 school students each from Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie

(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!

Hope to see you participating!!

Happy Programming!!

P.S. As tester, I encourage you to participate in the contest, nice problems are prepared.

Hi!

Thanks to all of you participates, who made this contest possible. And thanks to Lewin and Arterm, also to the great coordinator, Nikolay KAN Kalinin, zemen, WHITE2302, and for sure MikeMirzayanov.

Test data and code solutions. It's the original packages from polygon, you can find pretests, tests, generators, validators, etc in it.

Hints

Div.2 A: Take a look at notes section.

Div.2 B: Create a circle with these points.

Div.1 B: Fix the gcd.

Div.1 C: Tag: Grundy number.

Details

Div.1 C

I want to thank my grand teacher Mojtaba moji FayazBakhsh here. Who was my teacher not only for coding but also a teacher for my life. Thanks Mojtaba! Thanks to you and all of other good teachers in the world.

Solutions

Author: Arpa

Author: Arpa

Author: Lewin

Thanks to Lewin, the writer of this tutorial.

Author: Arpa

Author: Arpa

Author: Arterm

Thanks to WHITE2302, the writer of this tutorial. I translated this tutorial to English.

Author: Arterm

Thanks to Arterm, the writer of this tutorial.

Author: Lewin

Thanks to Lewin, the writer of this tutorial.

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

Translation: What can lover (Farhad) do with the power of love? He has no choice but to hurt himself by ax because he feels jealousy to Khosrow. More information about Khosrow and Shirin story.

Good luck and see you soon ;)

Hi!

I'm honored to invite you to Codeforces Round #432, it will be held on 4th September 14:35 UTC. There will be 5 problems for each division, as usual, you have 2:30 to solve the problems. The contest was prepared by Lewin Lewin Gan, Artsem Arterm Zhuk and me.

The IndiaHacks Final Round will be held on 3rd September 12:30. Finalist must not discuss the problems after their contest.

The stories of my problems will be about Arpa, although in one problem you'll see Mojtaba moji FayazBakhsh, my great teacher.

I'd like to thank Lewin, Artsem and myself (:P) at first, then Konstantin zemen Semenov and WHITE2302 for testing the problems, Nikolay KAN Kalinin for helping us in moving the contest to codeforces and Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

The scoring distribution will be announced later.

Obviously, if you are interested in if the round is rated or not, ask in comments and get a lot of down votes.

UPD. There will be 5 problems for div.2 and 6 problems for div.1.

UPD2. Scoring Distribution: div.1: 500-1000-1250-1750-2000-2500, div.2: 500-1000-1500-2000-2500.

UPD3. Editorial is partially ready. I'll complete it soon.

Congratulations to winners:

Div.1:

1 . BaconLi

2 . dreamoon_love_AA

3 . sd0061

4 . W4yneb0t

5 . Um_nik

Div.2:

1 . miaom

2 . fzzzq2002

3 . lzy960601

4 . Lucas97 and Szymanski_w (WoW !!)

Official results

Hi!

Hints

A: Tag: Greedy!

B: Tag: Greedy!

C: For each vertex like v find ex_v, the expected length of their journey if they start from v.

D: Tag: Inclusion exclusion.

E: Find the maximum clique.

Solutions

Arpa's solution: 29412123.

Arpa's solution: 29412154.

Arpa's solution: 29412220.

NikaraBika's solution: 29458745.

Arpa's solution: 29412249.

P.S. Please notify me if there is any problem.

Hi!

Hints

A: Let Cost(k) the answer if we compress the image with k, find min Cost(k).

B: Solve the problem without first query.

C: Let the frequencies of the characters be a₁, a₂, ..., a_k. Alice loses if and only if is odd and n is even.

D: Consider adding an extra seat, and the plane is now circular.

E: Let dp_i, j be the longest path given that we've included segment i, j in our solution, and we are only considering points to the right of ray i, j (so dp_i, j and dp_j, i may be different).

F: We want to compute dp_i, j: expected value given we have seen i red balls and j black balls.

Solutions

Codes here.

P.S. Please notify me if there are any problems.

Hi !

About one month ago I asked Xu Han (admin of the Virtual judge) if it's possible to add my own problems (that aren't present in any online judge) to some contest in Virtual judge, and we worked together to find a way to do this, and here is it, you can now add your own problems to Virtual judge. Let's see how to do.

1. Register on Codeforces polygon, create a problem and add statements, tests, checkers, etc.
2. Create a mashup here.
3. Add the problem to your mashup. Follow the instruction in this comment.
4. From contest panel, go to "manage inventions" → "invite users" → add vjudge1, vjudge2, vjudge3, vjudge4, vjudge5, vjudge.1, vjudge.2, vjudge.3, vjudge.4, vjudge.5, vjudge.6, vjudge.7, vjudge.8, vjudge.9, vjudge.10.
5. The problem is added to Virtual judge now!
6. To add your problem to your contest, choose "gym" from judge list and add your problem using its code (contest code + problem code, i.g. 207753A).

To see an example, here is my added problem to Virtual judge: Arpa as an ARPA :P (Hard, Fixed).

P.S. Deleting problem is not available now, but Xu Han said that he will make it available soon.

Hi.

Introduction.

We have a graph, we want to save it (and maybe run DFS on it for example); simple? Yes, but I want to show different methods for this, you can choose any of them depending on problem.

Adjacency matrix.

Simple, if graph is not weighted, save in G[v][u] if there is an edge between v and u or not.

If graph is weighted, if there is an edge between v and u save it’s weight in G[v][u], save  - 1 otherwise (if weight can be negative, use inf instead of  - 1).

Memory usage : .
Overall time complexity : (for running dfs).

// God & me

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 17;
int n, m;
bool G[maxn][maxn], mark[maxn];
void dfs(int v){
    if(mark[v])  return ;
    mark[v] = 1;
    for(int u = 0; u < n; u++)
	if(G[v][u])
	    dfs(u);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
	int v, u;
	cin >> v >> u;
	G[v][u] = G[u][v] = 1;
    }
    return 0;
}

Vectors.

It's the most common method for saving graph. For each vertex keep a vector of it’s edges, now for each edge just save it in related vectors. Use pair (or another struct) for saving weighted graph. It works similar for directed graph.

Memory usage : (Note that vector uses more memory than you need).
Overall time complexity : (for running dfs).

// God & me

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 17;
int n, m;
bool mark[maxn];
vector<int> G[maxn];
void dfs(int v){
    if(mark[v])  return ;
    mark[v] = 1;
    for(auto u : G[v])  dfs(u);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
	int v, u;
	cin >> v >> u;
	G[v].push_back(u);
	G[u].push_back(v);
    }
    return 0;
}

Dynamic array.

This method is rarely used. For each vertex count edges connected to it at first, then allocate a enough space for each vertex to save it’s adjacency-list. Note that this method is Offline.

Memory usage : .
Overall time complexity : (for running dfs).

// God & me

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 17;
int n, m;
bool mark[maxn];
int *G[maxn], sz[maxn];
pair<int, int> edge[maxn];
void dfs(int v){
    if(mark[v])  return ;
    mark[v] = 1;
    for(int i = 0; i < sz[v]; i++)
	dfs(G[v][i]);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
	int v, u;
	cin >> v >> u;
	sz[v]++, sz[u]++;
	edge[i] = {v, u};
    }
    for(int i = 1; i <= n; i++){
	G[i] = new int[ sz[i] ];
	sz[i] = 0;
    }
    for(int i = 0; i < m; i++){
	int v = edge[i].first, u = edge[i].second;
	G[v][ sz[v]++ ] = u;
	G[u][ sz[u]++ ] = v;
    }
    return 0;
}

Linked list.

This method is used when id of edges are important and works only for directed graphs (or if you can convert the undirected graph to directed). We use array for saving edges. Then, for each vertex we keep index of last added edge and for each edge consider it’s from From_i to To_i, we keep the index of last edge before this edge that From_index = From_i and name it prv_i. Then we can use head_v and prv array to find adjacency-list.

Memory usage : .
Overall time complexity : (for running dfs).

// God & me

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 17;
int n, m, from[maxn], to[maxn], head[maxn], prv[maxn];
bool mark[maxn];
void dfs(int v){
    if(mark[v])  return ;
    mark[v] = 1;
    for(int e = head[v]; e != -1; e = prv[e])
	dfs(to[e]);
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    fill(head, head + n, -1);
    for(int i = 0; i < m; i++){
	int v, u;
	cin >> v >> u;
	from[i] = v, to[i] = u;
	prv[i] = head[v];
	head[v] = i;
    }
    return 0;
}

Application: Solving flow network problems. Wikipedia: Maximum flow problem.

void add_edge(int v, int u, int vu, int uv = 0){
    to[ecnt] = u, prv[ecnt] = head[v], cap[ecnt] = vu, head[v] = ecnt++;
    to[ecnt] = v, prv[ecnt] = head[u], cap[ecnt] = uv, head[u] = ecnt++;
}
int dfs(int v, int flow = inf){
  if(v == sink || flow == 0)  return flow;
  if(mark[v])  return 0;
  mark[v] = 1;
  for(int e = head[v]; e != -1; e = prv[e])
    if(cap[e]){
      int x = dfs(to[e], min(flow, cap[e]));
      if(x)
	return cap[e] -= x, cap[e ^ 1] += x, x;
    }
  return 0;
}
int maxflow(){
  int ans = 0;
  for(int tmp; (tmp=dfs(so)); ans += tmp)
	memset(mark, 0, sizeof mark);
  return ans;
}

void add_edge(int v, int u, int vu, int uv = 0){
    to[ecnt] = u, prv[ecnt] = head[v], cap[ecnt] = vu, head[v] = ecnt++;
    to[ecnt] = v, prv[ecnt] = head[u], cap[ecnt] = uv, head[u] = ecnt++;
}
bool bfs(int source, int sink){
    memset(dis, 63, sizeof dis);
    dis[source] = 0;
    int h = 0, t = 0;
    q[t++] = source;
    while(h < t){
	int v = q[h++];
	for(int e = head[v]; e != -1; e = prv[e])
	    if(cap[e] && dis[ to[e] ] > dis[v] + 1){
		dis[ to[e] ] = dis[v] + 1, q[t++] = to[e];
		if(to[e] == sink)  return 1;
	    }
    }
    return 0;
}
int dfs(int v, int sink, int flow = inf){
    if(v == sink || flow == 0)  return flow;
    int ret = 0;
    for(int &e = ptr[v]; e != -1; e = prv[e])
	if(dis[v] == dis[ to[e] ] - 1){
	    int x = dfs(to[e], sink, min(flow, cap[e]));
	    flow -= x, ret += x;
	    cap[e] -= x, cap[e ^ 1] += x;
	    if(flow == 0)  break;
	}
    return ret;
}
int max_flow(int source, int sink){
    int ans = 0;
    while(bfs(source, sink)){
	memcpy(ptr, head, sizeof ptr);
	ans += dfs(source, sink);
    }
    return ans;
}

Usage of this method in above codes are where we use cap[e] -= x, cap[e ^ 1] += x. Because of special adding edge method, it is guaranteed that if edge e is from v to u, is its pair and it’s from u to v.

Related submission : 23115110.

Index keeping.

This method is used when index of edges is important (i.e. in queries we need to change something about edges, i.e. change weight, delete edge). Keep index of edges related to each vertex in its vector, and for each edge keep the vertices connecting with this edge (see code below).

Note that index keeping is possible and maybe easier using map (or unordered_map), but it is faster using this method. Also note that dynamic array method could be used here as well.

Memory usage : (Note that vector uses more memory than you need).
Overall time complexity : (for running dfs).

// God & me

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 17;
int n, m;
int first[maxn], second[maxn];
vector<int> g[maxn];
void dfs(int v){
    if(mark[v])  return ;
    mark[v] = 1;
    for(auto e : g[v]){
	int u = first[e] == v ? second[e] : first[e];  // or simply first[e] + second[e] - v, or first[e] ^ second[e] ^ v;
	dfs(u);
    }
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
	int v, u;
	cin >> v >> u;
	g[v].push_back(i);
	g[u].push_back(i);
	first[i] = v, second[i] = u;
    }
    return 0;
}

Example: Consider you need to change weight of edges online, this is simple using index keeping method, but it isn’t possible with other methods (at least it will be harder). Related submission : 20776118.

Application: Finding Euler tour. Wikipedia : Eulerian path. Blocking edges is easier with this method, that’s what we need in Euler tour finding. Related submissions : 21395473, 21636007.

Comparison.

I used Codeforces polygon for comparing and generated 16 random graphs:

• #1 to #4 : n = 10⁶, m = 10⁶

• #5 to #4 : n = 10⁵, m = 10⁶

• #9 to #8 : n = 10⁴, m = 10⁶

• #13 to #16 : n = 10³, m = 10⁶

It's really strange for me that vector uses less memory than dynamic array while testing, can someone explain the reason? Here is the link to codes and generator.

UPD: I found the answer, I missed that in dynamic array method we are saving edges in pairs, and keeping the sz array in addition (thanks to ATofighi).

As usual I’d like to finish the post with a poem:

بی سبب هرگز نمی‌گردد کسی یار کسی
یار بسیار است تا گرم است بازار کسی

By: Parto biza’ee arani.

Translation: No one becomes friend with another one without reason. People are like shops, a shop is full of customers while it has goods.

P.S. Kindly write in comments (or use private chat in case of necessary) if something is wrong.

Hi!

I've recently found Spoj ToolKit. It's features:

• Random number, array, string, tree, graph generation.
• A big database of correct solutions to check if your output is correct for custom input.

Let's help this website by adding more correct solutions to its database.

Hello again, It’s Arpa as usual :P. Hope you enjoyed from the Gym, and it’s here is the editorial.

Problem packages are available here. Solutions are available here separately.

Preparation details:

The problems authored by me when the main contest was authoring. Here is a table, showing the percentage of expected accepts (in my opinion, before the contest) and the number of accepts.

Difference from main problems

A : n is bigger, binary_pow will not work. You need to calculate in a faster way.

B : n and also numbers are much bigger, simple xor will not work.

C : n is bigger, simple LCM will not work because the answer would become really large.

D : Number of alphabets are 26 instead of 22, so it isn’t possible to allocate an array with size 2^z (z = 26).

Hints

A : Write the last digit of 1378ⁿ for several small values. Calculate in a fast way.

B : Note that if then . Use trie.

C : If the answer exists, it depends on the lengths of cycles in the functional graph. Factorize numbers and calculate LCM.

D : Keep a mask for each vertex, i-th bit of mask_v is true if the number of edges in the path from the 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. Give an id to each mask.

Details

First accepts: A : retired_coder, C : wrinx.

Funniest code : shengdebao ’s code : 23229169. He was managing to get accepted in problem C, with a solution :O.

Solutions

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

Translation: No one knows the value of good friend as I know, fish will know the value of water when it falls on the beach.

Goodbye ; )

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.

Hi!

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

It’s very simple to implement and its 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 an 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
		The answer to 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 the above code I used the 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:

Update (Feb 2025): The above method is actually . Refer to this blog for algorithm.

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 . EvenImage

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 - Деревянные запросы : 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 - Братья по крови возвращаются : 15409328

208E - Братья по крови : 16897324

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

291E - Древесно-строковая задача : See bhargav104's comment below.

1009F - Доминирующие индексы : 40332812 Arpa-Style. Thanks to Tanmoy_Datta.

343D - Водяное дерево : 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 - Дерево и запросы : 15449102 Again note that problem is not easy :)).

716E - Цифровое дерево : 20776957 A hard problem. Also can be solved with centroid decomposition.

741D - Помеченное буквами дерево Arpa и забавные пути Mehrdad : 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 - Монеты и мешочки 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?