And I hope that my first Div. 1 round will be on the next contest...

Same here ;-)

This is probably some hella smart & funny joke, but I just didn't get it.

Konstantin.Zakharov awesome :D one of the creative comment post i have ever seen here :D

I just hope that the round won't be "boring" :))

Sleep is for da weak.

Definitely no Chinese coders will compete in this round if they are going to participate in ICPC regional just on next day. They just need good rest.

Wait for a few hours.

Unfortunately, sleep was delayed because it coincides with codeforces round 275. here is the new time

and your first Div1 has no 1000pt problem :D

Suspense :D

i think with binary search

i solved it recursively. consider lower bound of allowed numbers to be L. the absolute minimum numbers you need to consider is cnt1+cnt2. so you look at numbers from the range [L,cnt1+cnt2+L-1]. the numbers divisible by both x&y cant be gifted. from the remaining numbers those divisible by x were gifted to second frnd and those divisible by y were gifted to first friend. now the numbers left can be gifted to either friend.After some thinking you can argue that they should be gifted to first friend and if some are left even after that then to the second. the arguement for this is based on the fact that x < y.i am sure you can think of it :). after updating cnt1 and cnt2. apply the process recursively with new lower bound as cnt1+cnt2+L (i.e. upperbound of previous process +1).

The first (n — k) numbers could be 1,2,3 ... (n — k) after which we print n, n — k + 1, n — 1,n — k + 2 .... for the rest of the numbers.

First, follow a pattern 1, n, 2, n-1, 3, n-2, ...; do it k-1 times. Than add remaining numbers in the natural order (decreasing or increasing depending on k's parity).

I printed 1 and then printed p=1+k, then decreased k by 1 and then printed p=p-k and continued the series. Like, if k=3 and and n is anything arbitrary for an instance, I printed 1 4 2 3. Notice the difference in each adjacent values. And in the end I printed all the remaining values less than n.

That one's pretty easy. The task asks you to find some array of length n so that the amount of absolute value of differences of each two consecutive elements is equal to k.

I did it that way:

Our answer:
1 n 2 n-1 ... n/2

And if we are about to print the (k+1)-th number we just print our latest number (- OR +) 1 which will make it look that way:

For example: N = 9, K = 3
1 9 2 3 4 5 6 7 8
And N = 9 K = 4
1 9 2 8 7 6 5 4 3

As you have probably noticed if K mod 2 is equal to 0 then we print our latest number - 1. Else: latest number + 1.

Pretty easy solution and easy to write down, work time: O(n)

edit: whoops, i think i'm late for a party

Not accepted yet, but I think it will be so... :) With first k elements You just can generate something like this: 1 1+k 2 2+(k-2) 3. Every needed difference will be here, k = |1+k — 1|, k-1 = |2 — 1+k|, k-2 = |2+(k-2) — 2|, k-3 = |3 — 2+(k-2)| ... And now, after that, just write the rest, n — k elements, one by one: 1+k+1 1+k+2 1+k+3 ... n-1 n. Difference between 1+k+1 and previous element is for sure not greater than k since k>=1 and previous element has to be between 2 and 1+k. Sorry for my English :)

EDIT: Aldiyar explained similar solution much better in his post, but it wasn't there when I was writing mine, sorry for doubling answer :)

A-As Usual Difficulty. B-Very Much tricky. Perfect Problem who loves math. C seems easier to most of the div2 contestants but I got lots of pain and still not sure if it will pass. D was an awesome problem. No Idea how to solve it. E- I saw factional output — pressed ctlr+F , looked for a word "expected", found it and immateriality closed the tab.

Binary search

I solved it using segment trees (sadly after the contest).

Initially set all the values to 0 and the if a query(L,R,V) comes, update all the values in the range(L,R) with (a[i] = a[i] | V where L <= i <= R).
while joining nodes in the segment tree do seg[node] = seg[2*node] & seg[2*node+1] and finally check for each query_range whether the bitwise and (&) of all the values equals to the required value i.e check value(L,R) = V . This got AC .

Some people used binary search, I did not. My approach is as follows:

1.Set the answer=cn1+cnt2 initially.

2.Then you can fulfil the requirements of the first friend by giving the numbers to him which are not acceptable by the second friend and vice versa.

3.Let the friend with more requirement of numbers be friend1(cnt1>cnt2).Then you can give the numbers in the range [1,answer] not already given to any of them to friend 1. Then if his requirement is done you can give the remaining numbers to friend 2.

1. If you see that both friend's requirement is done then you can print the answer else you can increment answer by sum of remaining requirements of both friends and repeat from step 2.

Code http://mirror.codeforces.com/contest/483/submission/8394005

i solved taking a long long a = cnt1+cnt2, & then checking if a — (a)/(x*y)>= cnt1+cnt2; if false, then a+=(cnt1+cnt2-(a-(a)/(x*y))), and so on. becouse the numbers that are multiples of x*y cant be taken as answer in any of the two cases. You have to check in the same way if there are enough numbers int the interval that aren't divisible by x, and the same whith y.

Totally agree, especially if you submit in Scala :(

In C, it's necessary to kill off O(nm2^m) solutions.

Yes, I got TLE just because of using scanner in Java instead of buffered reader. 2 seconds would have been better

I agree.Let's hope that no source with correct idea will get TLE.It wouldn't be nice...

no math lol

I don't think that's considered math? At least to me it seems like simple logic.

You can use Custom invocation to see how long it would take on their servers.

My 50*2^20 got TLE, so I'm guessing no.

If so then 1s TL is not enough for such tight constraints.

Maybe it was meant to work in 50*20*2^20 =(

You maybe mean "C and D".

Not only that .This is the condition in DIV2 ->

WA22 is the case n = 1. My solution printed 1 while the answer is clearly 0. I saw lots of solutions which failed this test.

Binary search the answer..... to check whether we can distribute the presents between the friends using a certain v, we can use inclusion-exclusion. this might help : there are exactly n/p numbers between 1 to n which are divisible by p.

hope it helps.

Only the last "Passed pretests" submit is counted.

because you cheated it

I had O(N * 2 ^ string length)

O(L*2^L) as mentioned in a comment above. Turns out the idea behind such solution is way harder than authors thought. I think O(N * 2^L) also passes, but most of the solutions were something like O(N*L*2^L) and failed.

L — string length

interesting for me too, after ends I wrote O(2*m*n), so TL.

I used segment tree to find possible answer and another segment tree to check that answer is correct.

Segment tree with updates on segments. 8393603

For each constraint ... We iterate over the bits of q ... if the ith bit is turned on ... then it means that all elements in the range (l,r) have this bit turned on as well ... else if the ith bit is turned off ... then it means that at least one element in the range(l,r) has this bit turned off.

So for all the turned on bits ... We turn on this bit on all the elements in range(l,r)

After that for the turned off bits ... We check that the range(l,r) contains at least one position where this bit is turned off.

We can use either segment tree or cumulative sum and binary search to implement this idea.

you used sync_with_stdio(false) and printf together , which will do unexpected thing

anyone who saw your comment must be already refreshed his/her browser.

SOLVED

Video is private.

10 7 3 5

your solution output — 17

right answer — 18

http://mirror.codeforces.com/blog/entry/14387#comment-194124 http://mirror.codeforces.com/blog/entry/14387#comment-194131

Segment tree,I guess.

I will try to explain by posing a different problem:

Given m queries of the form a, b, p; Add p to each element between arr[a] to arr[b]; Length of the array is n.

Trivial solution will do it in O(m * n);

To optimize, what you can do is, add p to arr[b]. And add -p to arr[a-1];

Those two units of information is enough to let you know that you want to add p from arr[a] to arr[b].

Keep on doing that for all m such queries.

Finally, do, something like:

arr[n-1] += arr[n];
arr[n-2] += arr[n-1];
arr[n-3] += arr[n-2];
...
...
arr[2] += arr[3];
arr[1] += arr[2];
arr[0] += arr[1];

So, just one final loop like above can add p to all elements between arr[a] to arr[b] for all such m queries.

Complexity is: O(m + n)

Try it on paper.

translating maybe. the last time I saw the solution of two last problems were written in Russian

You can read the editorial in the google's web cache : http://webcache.googleusercontent.com/search?q=cache:vSOKoA-5IqwJ:codeforces.com/blog/entry/14417+&cd=1&hl=es-419&ct=clnk&client=iceweasel-a

Factor of luck