yeah, why are they always publishing the scoring distribution in the last 10 minutes.

I hope the problems will short too :)

+Fast system test

It is nice because of many contests, but some of the contests from this summer weren't really nice. Back in autumn or winter the contests were nicer. Hopefully this will change soon because i see that people stop participating on CF. Some months ago 8000 people were registering and 5000+ were participating, but now around 3500 participate, but i love CF, it is the website were i have the most emotions while participating.

sorry for my bad english

Maybe on the russian site they say the same about russian statements when there is a non-russian setter.

i love codeforces and want to see it improve day by day, and that's why i think they really need a professional English editor because i keep seeing these kinds of grammar mistakes in many problems

yes. i was going to say the same thing. and don't forget their explanation to the sample test cases were awful too. And when i asked for an explanation (this exact same problem) they told me to read the problem statement carefully. Man, because of your awful statements, i asked you for an explanation. -_- I think they should consider that CF has become a global coding contest site and so they should give more importance in their English statements. :)

Why must you use memes incorrectly?

finally correct is it rated? question. Yes it is.

Why did you write this

Bravo :|

Are you on drugs?

Did you forget to log out your Codeforces account on your friend's laptop?

baba Khafan amsal shoma hamishe naghsheshoon kam rang bood

If one of the numbers is 0, the GCD of both of them is the other number. You shouldn't be asking questions here while the constest was running =P Try to send a clarification next time (by the way, there was an announcement about this hahaha)

write me (if you want)

1)0 2 mex = 1

2)3 1 mex = 0

"Note that after each query the array changes." So the second array will be constructed by using the XOR operator on the first array, not the original one.

Seriously??? Can people comment during the contest???

Why am I receiving negative votes on this comment ? I was asking a question regarding the pretest cases. Nothing relating to the solution :/

You can use double but don't forget epsilon

C : You only need to check parents and vertex divisors.

D can be solved by building a binary tree. Consider a tree of depth 19 where the leaf nodes represent 00...0, 00...1, ..., 11...11, i.e. all numbers of length 19 in binary. This choice is made because 2^19 is the smallest power of two larger than 3*10^5. The higher levels are represent if number p, the child nodes are 2*p and 2*p+1.

For each x (assume the set doesn't change for a moment) the smallest number not in the set is the one most similar to x (starting from higher digits) XOR x. Therefore, we start from the top most node and if possible make the choice towards that which is the same as x. If there are no viable nodes in that direction, we go the other way.

The value of each node is either true or false, false representing if the value is in the original set. As you move higher up the tree the value of the nodes are defined so node p is true if either 2*p or 2*p+1 is true.

You don't have to change the set but keep XOR-ing each successive query. Total complexity is O(n + A + m log A).

Do dfs on graph.In the dfs, Calculate the divisors of the current node.If this divisor divides atleast 'depth[cur_node] — 1' nodes on the path from root to this cur_node,then it can be a possible value for the gcd .Take maximum of all such values possible for that node — This is maximum beauty of that node.Or gcd(Parent of cur_node) is also a possible contender.Complexity — O(Nsqrt(Max_Val))..We keep an array(200005) that keeps track of how many nodevalues are divisible by a number in the path from root to cur_node.Sadly, it didn't pass pretest 7.

Check my solution: 29886456

You can do a dfs dfs(currentVertex, parent, canSkip, currentGcd) where you go to the adjacent nodes as follows: dfs(adjacent, currentVertex, canSkip, gcd(value(currentVertex), currentGcd)) and, if canSkip=true, dfs(adjacent, currentVertex, false, currentGcd). To compute the answer we must call dfs(root, -1, true, 0). You can keep a set of states to avoid repeating vertices. That is, once you have computed a particular state, add it to a set and, if you end up there again, just return and do nothing. You may also have a vector ans where, in each state, you compute ans(currentVertex) = max(ans(currentVertex), gcd(value(currentVertex), currentGcd)) and, if canSkip = true, ans(currentVertex) = max(ans(currentVertex), currentGcd).

Why does this work? Well, according to https://en.wikipedia.org/wiki/Highly_composite_number the most composite number in [1, 200000] has 160 divisors. We must note that gcd(a, b) will always give a value that is both a divisor of a and b. In our approach, this means that a vertex may only generate at most 160 new gcds. Also, we must take into account that we can skip a single vertex, so we can "inherit" the gcds from above, so a vertex may emit at most 320 values. This means that we have at most 200000 × 2 × 320 = 1.2 × 10⁸ distinct configurations. Given that we have two seconds, it seems that this may fit into the time limit. However, we must note that this is an upper bound. In practice, the numbers are much smaller. To be honest, I do not know how to bound even more these numbers. During the contest, I generated random graphs with numbers with many divisors, or random graphs with only numbers of the form 2^a × 3^b and I saw that I was not able to make it fail, no matter what I tried. I also generated arrays of numbers and computed the amount of distinct gcds I could get by ignoring zero or one numbers at a time, and I also saw that the numbers were very small.

And what is 15 ? :)

keep getting wa on pretest 7 ...

7 7 3 6 2

Answer: NO

May be -> 22 26 2 6 7 Answer : NO

-is yet to come.

It's about 10^8, so it could be too much if your constant is big enough.

map trie ??? no need array trie was enough as highest node will be <=(1<<20)

Just got AC with n*logn*logn solution 29901340

8 13 1 4 7

If I understood correctly you are given a tree, find number of vertexes that can be endpoint of diameter.

The statement is ridiculous. They should let it be pure graph statement!

3
3 4 3
2 1
2 3

Answer is 3 4 3

3 2 5 8 1 2 2 3

Ans: 2 5 2

In a dfs keep a set of all the gcd you can make till the index you are on and then take gcd of value of current node with all element in the set and add one extra element which is total gcd till last element. As, the number of distinct gcd you will hold will always be less than cubroot(max value of node). as, a number has <= cubrt(n) divisors. so your solution would be O(n*cubrt(n))

I got the solution 10 minutes before the end of contest and wasn't able to code it :(

You can make a DFS(u, depth), depth will be the number of the vertices on the road from 1 to u. In vertex u, you will want to know for every integer i, how many vertices on the road from root to u are multiple of i, assume it's fre[i]. We will get another information, that is Max[x] = y, y will be the maximum value that be the divisor of the value of x vertices on the road from 1 to u. fre[] is easy to calculate, with every divisors v of a[u], fre[v]++, and after each increases, we update Max[fre[v]] = max(Max[fre[v]], v). So res[u] (result of vertex u) will be max(fre[depth], fre[depth — 1]). Just remember, after visiting all u's branches, you have to remake the values of fre[] and max[] to the values before you dfs to u (like how we use back-tracking to generate permutations).

My code: 29897727

RIP color

elegant solution!

It was me :P

http://codeforces.com/contest/842/submission/29883923 This is a mathematical solution.

my idea : pre store n * logn numbers first throw out the numbers until there is at most one of each . then just pre calculate the prefix of numbers in binary in an array . for example for 5 : store numbers 0000000000000001 00000000000010 00000000000000101 then the problem is simple ! think for yourself

I solved it using trie

Let A be an array of numbers that our original array doesnt consist of.

Then mex(a) = minimum element of A.

1 useful fact: after operation (a xor x) mex will be minimum of array (A xor x).

You dont need to save all changes, just xor new query with old. Like xi = xor(x0, x1, x2 .. xi).

Original array A you can store in bit trie. Now you iterate over bits, from large to small. You mission is to decrease y (the number you get from trie) xor xi. So if j-th bit of xi is equal to 1 you should go through "1" edge in the trie if you can. Similarly for "0" bit. Answer will be y (the number you find) xor xi.

Sorry for my bad English.

Greedy by bits. In fact, xor only change the priority of bits. For example, the xor number is 100010, and current number you choose is 101[0]00000, in present bit [0] is greater than [1](because of the effect of xor number). So we first check the number [101100000, 101111111], if all of the values occur, we can put a [0] here, otherwise we can only put [1]. If current bit of xor number is [0], we try [0] first. The checking can be solved by prefix sum. Finally we got the number before xor, so just print after xor. The total complexity is O(nlogn).

Used :

1. Bijection Property of function : f(x) = x^k ( k belongs to [0, 2**(n)-1] ) (XOR) : [0, 2**(n)-1] -> [0, 2**(n)-1].

2. Greedily finding the element which is not in A and closest to X.

3. Instead of modifying Array itself, modifying query's input (Xj) by taking XOR with query input (Xi's) occered so far.

int A[1000000];

int sumLR(int l, int r)
{
	return ((r>=1000000)?A[1000000-1]:A[r]) - ((l-1)<0?0:A[l-1]);
}

int main()
{
	int i,j,k,l,m,n,x,y,z,a,b,r;

	sd(n);	sd(m);

	for(i=0;i<1000000;i++)
		A[i] = 1;

	for(i=0;i<n;i++)
	{
		sd(x);	A[x] = 0;
	}

	for(i=1;i<1000000;i++)
		A[i] += A[i-1];

	x = 0;
	while(m--)
	{
		sd(y);    x ^= y;
		a = 0;
		for(i=30;i>=0;i--)
		{
			if(sumLR( a | ((1<<i) & x) , a | ((1<<i) & x) | ((1<<i) - 1)  )!=0)
				a |= ((1<<i) & x);
			else
			{
				if(((1<<i) & x)==0)
					a |= (1<<i); 
			}
		}
		printf("%d\n", x^a );
	}
	return 0;
}

It's 0.

Plus people scored 12-13 hacks on A which got them points equal to C, although both the things aren't the same.

Maybe they like repeating :)

Less ACC for A than B too!

firstly i got tle, then optimize it and changed to printf and got ac in pretest

1. Check the frequency of divisors of the node you're on. If there's at most one missing, it can be an answer.

2. As soon as a number has one missing, it might be an answer for one more node and then the rest must have this number as divisor otherwise there will be 2 missing and it won't be an answer.

So just check the current node and parent node's divisors (or send the maximum from the current node that has no missing frequency to the next nodes).