why servers so unfair to us...

You will be surprised.

Everyone wrote one line in each problem statement :D

You never know, you might win it.

:)

wallpapers fetish !!

Not at all, To Increase the chance to get candidates for onsite events at Host Location. I think it is just for promotion for Local Geographic.

I don't know if it's racist, but it's definitely stupid.

'Spreading wings' is the English phrase for expanding to and exploring new realms.

'Spreading legs' means sexual enticement and promiscuity.

...you can see the contest in your local time if you go to the contests tab.

Of course you can. You should click that "Register now »" and join it.

YES !!! INDIA ROCKS !!! ALL OTHER COUNTRIES SUCK !!! :) :) :)

इंडिया !!!!!!!!!!!!!!!!!!

no cheaters means no work for you :D

Yes, it's rated.

Wow, thanks :D

wow,i get the same result thank you <3

this time it was close to the real rating. good job ;)

WOW,I just get the same result.

Same result ! Thanks ;)

yeah i have no idea why i am getting runtime error

Наверное, потому что неприятность случилась в самом конце контеста, а для тех на кого она повлияла серьезно, возможно, сделают индивидуально нерейтинговый раунд, как уже было когда-то ранее.

I think the same

yes please extend time if its rated.

It has to be unrated

The time was extended, queue stabilized, I dont see any reasons to make it unrated ...

If you are checking for repetition, each of 'k' iterations could take O(n) time for comparison and O(n*log(n)) for sorting. So if the array doesn't repeat then there is a good chance that the solution would timeout.

Same here :(

Should not it be k*1023 ? 959 xor 64 is 1023

How does this solution look like?

Points loss was the 2:00 formula for a 2:30 + 0:10 contest. Did asking that really take less effort than subtracting 2 numbers?

ranting part 2

I think that tricky tests with f = 0 or w = 0 in 768F - Barrels and boxes should be included in pretests. You can't expect people to hack this problem because in most of rooms at most 1 person solves such a problem. So you just give WA's to all people that miss that thing. And for many it was misreading the statement (understanding that both f and w are positive), not forgetting about corner case.

Let me also say something positive: I liked 768G - The Winds of Winter.

Hello not adjusted drain, my old friend. I've come to butthurt about you again.

I can't believe that not adjusted drain and bad scoring is still a thing. Completely trivial D, E worth 1750 and 2000 points and G worth 2750, sounds legit.

Notice that, x will produce an array of length 2^{⌊log(x)⌋ + 1} - 1. Let's call this number len(x)

I solved it recursively,

f(x, l, r, s) = number of ones at the intersection between the intervals [s, s + len(x) - 1] and [l, r]

If [s, s + len(x) - 1] is totally contained in [l, r] then the answer is x. If they don't intersect, the answer is 0.

Otherwise, f(x / 2, l, r, s) + f(xmod2, l, r, s + len(x / 2)) + f(x / 2, l, r, s + len(x / 2) + 1)

Answer is f(x, l, r, s = 1)

I think this solution is too complicated, though :(

Divide n by 2 until it is 0 and put that in an array in ascending order.

You can see a pattern generated by the number and the final set.

Take the index of one 1/0 in the list. Then take the highest power of two that divides that index. The expoent of the power will be exactly the index of the corresponding number that generated it in the array that we built. Therefore, if the number in the array is even, it will be 0, if it is odd, it will be 1.

Thus, we can just iterate from l to r, checking the powers of two, and adding 1 or 0 to a counter according to the prebuilt array.

i.e. suppose n is 17

the array built will be 1 2 4 8 17

suppose l is 12 and r is 16

12 is divided by 4, which is 2^2, the index 2 in the array is 4, which is even, so the position 12 in the list is 0

13 is divided by 1 which is 2^0, the index 0 in the array is 1, which is odd, so the position 13 in the list is 1

14 is divided by 2 which is 2^1, the index 1 in the array is 2, which is even, so the position 14 in the list is 0

15 gives the same as 13 (and actually every odd index)

16 is divided by 16 which is 2^4, the index 4 in the array is 17, which is odd, so the position 16 in the list is 1 and so on.

I find that this is the simplest way to solve the problem (my solution was 17 lines long). Unfortunately my solution received Runtime Error because I forgot to test when n = 0.

Expected complexity O(log N + 50 * (R — L))

int main(){
	ll n, l, r, cont = 0;
	cin >> n >> l >> r;
	if(n == 0) {
		cout << 0 << endl;
		return 0;
	}
	vector<ll> fac;
	for(ll i = n; i; (i >>= 1)){
		fac.pb(i);
	}
	reverse(fac.begin(),fac.end());
	for(ll i = l; i <= r; i++){
		int e;
		for(e = 51; e >= 0; e--){
			if(i%(1LL<<e) == 0) break;
		}
		cont += (fac[e]&1);
	}
	cout << cont << endl;
	return 0;
}

N is 2^50

any explaination please ?

I used a segment tree of multisets only.

For each vertex we want to know the list of sizes of trees that will remain after this vertex is cut. Let BIG and SMALL denote the biggest and smallest of them. It's enough to consider moving some subtree of BIG into SMALL. It's optimal to make the size of moved subtree of size as close to (BIG-SMALL)/2 as possible. Let's see how to do it.

We compute preorders and we build a segment tree of multisets. For any interval we want to know the set of sizes of subtrees with preorder in this interval. In O(log²) we can ask a structure about a size closes to some value.

There is one hard thing left: if BIG turns out not a child of our vertex but its parent and everything above, then we should differently consider subtrees starting from somewhere on the path from our current vertex to the root. If the size of subtree was X initially and our current vertex is v then cutting and moving that subtree moves size X - a. So we need a second segment tree of multisets that will store sizes of subtrees that start somewhere on a path from the current vertex to the root. As we move deeper in a tree, we should remove elements from the first structure and insert them in the second one.

EDIT: I got TLE. The complexity is with not so small constant factor. Maybe it can be implemented slightly better.

My reaction : https://ibb.co/i703Yv

I think we have to find places of 0's and put them vector (maximum amount of them are 51). Then just find count of them in range [l, r]. After print r - l + 1 - cnt. O((l - r) * 51).

UPD: This solution will get TLE and MLE. Sorry for wasting time.

it was interesting,but if you do a bit of brutforce on paper you would realize this:

1.the resulting aray for number n is composed of res(n/2)+n%2+rez(n/2) 2.the number of elements it will have is 2^(log2(N)+1)-1

this observations suggest a recursive function

so you do a q(long long number,long long l,long long r) my code is here:https://ideone.com/kFdyY1

How do you solve it?

This doesn't even call srand

if it gets accepted,i will laugh so hard

ha ha ha you get wrong on test 21

Brute forces could do the trick.

I wrote a bruteforce and found its like 1,1,2,2,2,3,3,3,3... ith value repeated i+1 times...

The Grundy number of each i is the maximum number j such j * (j + 1) / 2 <= i

For every number a[i], calculate c[i] — number of 1 bits of a[i], and then it's just like at normal NIM game, xor between all c[i], 1 <= i <= N, and if this xor sum is equal to 0, the answer it's "YES", otherwise "NO"

In dp(n, mask), we can modify mask to mask only 30 bits, because we will not subtract x (x > 30) from n more than once.
solution : 24854077

I have the same bug, I misread it as "It is guaranteed that he has at least one food box AND at least one wine barrel." :-(

I'm much more stupid. I asked a question:

"It is guaranteed that he has at least one food box or at least one wine barrel."
is it equivalent to saying that 1 ≤ f, w?
I'm asking because there is 0 ≤ f, w just before that

I got answer: It's equivalent to 1<=f+w

... and I misread that answer and understood 1 <= f, w

;_;