swap(Gerald, Zlobober);

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.

Codeforces ориентируется не только на Россию (ведь, например, авторы бывают из разных стран).
То, что неудобно вам, может показаться удобным кому-то другому (например, Betlista выше пишет, что из-за сдвига он сможет поучаствовать, а в 19:30 бы не смог).
Из-за этого и решили уйти от "по стандарту в 19:30 МСК" — чтобы каждый пользователь смог посоревноваться в удобное для него время (пусть и не каждый раунд).
Такая же практика и на американском TopCoder, где иногда раунды проходят в 5 утра по Москве, а иногда "нормально" — вечером.

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

Итог: решил С за довольно длительное время... по D остановился на WA7. Увидел что B div2 оказалось сложной и стал думать её. И неужели не заходит вот такое решение: бинарный поиск по ответу с чекером n - a >= cnt1 && n - b >= cnt2 && n - c >= cnt1 + cnt2, где n — проверяемое количество чисел; a — количество чисел, которые не подходят первому другу; b — количество чисел, которые не подходят второму другу; c — количество чисел, которые не подходят обоим друзьям. Соответственно, a = n / x, b = n / y, c = n / ( x + y ).

UPD Решение таки зашло. Не понимаю тогда, в чем была сложность и почему эту задачу решило около 300 человек.

Код

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.

+1. Вот интересно, неужели там есть решение за 2^k (k — длина строк)? Я своё за 2^k·(n + k) упихивал ногами, руками и другими частями тела, и всё равно в ТЛ оно лезло только на Java8. Если у жюри решение медленнее 2^k, я бы с удовольствием посмотрел, как оно работает на Java7.

++

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://codeforces.net/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

O(30 × N). http://codeforces.net/contest/482/submission/8381676

А зачем их сортить, кстати?

8385070 без сортировки и без дерева отрезков. O(30 × N)