So you got one xd.

Too much red users in one blog...

Maybe the oxymoron (little big x) is intended?

x is usually name of the variables, it could create confusion too :P

No, many handles for testing not problem setting

Because 233 is a special number in Chinese... It means "LOL"(Laugh Out Loud) in English which shows a man bursts into laughter. And we use repeating "3" many times strengthen the funny meaning. 233 is a photo id in a famous forum of China. here is the photo.

There is actually going HackerRank contest "Ad Infinitum — Math Programming Contest September'14 ". It lasts 2 days :). Give it a try.

First of all, before this commented is downvoted, I would like to point out that codeforces is for developing your algorithmic knowledge. Depending on your definition of "algorithmic", math could be considered an algorithm; and this is a perfectly valid opinion. However, what is the point of competing in coding contests if all you want is math all the time. Every time you post, it's about math; nothing else. Coding contests are meant to introduce you to varied ways of thinking, not limited to math.

early sleep and early wake~ After brushing teeth and washing face, you can participate the Chinese round relaxedly

Have fun getting used to the U.S :)

newSolar BigGod is here! You are a Yellow! But you say you are only div2.....

I think it's everyone's last contest in summer in northern hemisphere :|

:|

It is already 20th of September. What kind of summer do you have?

No, if you submit during contest, it will be counted in your actual participation and rating changes will also apply. So it is better to take the entire contest as a virtual contest at some suitable later time.

The hell is your graph?

I am sure , someday , your graph will be a great inspiration for many many coders !!!

You were right. Welcome back to the hell, fella :D

The answer is "YES 1 1 1 1", right?

would it be correct if ans is YES 1 1 1 1 ?

Or
3 5 8
2 3 5

(sometimes they remove numbers from first set without checking if first set stay valid)
Edit: the answer is "NO", but some were giving for output "YES 0 1 1"

Бинарным поиском простите по чему? Остаток по модулю не монотонен.

Я делал так. Во первых научимся быстро считать сумму. Это делается за длину числа какими-то не очень сложными формулами. Если мы найдем два числа, дающих одинаковый остаток, то мы победили. Будем смотреть только на числа с остатком не больше 1000. Тогда если мы посмотрели на 1000 таких чисел мы победили. Теперь просто смотрим на все числа по очереди, и если остаток стал слишком большим, то бинпоиском находим место в котором он следующий раз переполнится через A. Так как сумма цифр одного числа небольшая, то понятно, что переполнится не сильно, и хотя бы одно новое число мы найдем.

На самом деле идея с бинарным поиском почти верная, только ответ будет не 1 R, а b R, где b — какое-то маленькое число. При этом забиваем на условие solve % a = 0 и просто ищем такие b R, что solve(b, R) = a. Очень легко реализовать. Решение

Для каждого числа необходимо найти его отражение в множестве А и множестве B (то есть сумма числа и его отражения равна a или b). Делается это за линию для каждого множества. Далее убираем все числа (и их отражение), которые имеют только одно отражение в каком-либо множестве (логично же, что в финальном ответе это число может находиться только там). Когда все такие числа убраны, возможно два варианта: у какого-то числа не осталось свободного отражения (ответ NO), либо у всех чисел есть по два отражения в каждом множестве. В этом случае можно засунуть все эти числа в любое множество и быть счастливым. Важно понять, что число может быть отражением самого себя (претест 6) (например, в множестве А с a = 4, может находиться один единственный элемент 2).

UPD: Решение верное, но после того как один раз будут убраны возможные числа, могут образоваться новые числа только с одним отражением. Поэтому необходимо провернуть операцию с удалением как максимум 10^5 / 2 раз, а это не проходит по времени. Другой вариант решения: это удалять числа рекурсивно. То есть, например, есть у нас 4 числа: a1, a2, a3, a4 (a1 + a2 = a, a2 + a3 = b, a3 + a4 = a). Можно заметить, что числа a2 и a3 имеют отражения в обоих множествах, в то время как a1 и a4 только одно отражение. Как только мы натыкаемся, например, на число a1, мы сразу можем засунуть его и a2 в первое множество, а раз у a2 было второе отражение, то у этого второго отражения уже станет на одно отражение меньше. То есть число a3, после того, как убрали число a2, тоже можно будет убрать (если, конечно, у него еще остались отражения (число a4), в противном случае ответ NO).

P.S. Надеюсь понятно написал =)

Как вариант, стандартным для всех задач подобного вида методом — с помощью 2-SAT.

I took the following greedy approach:

for n <= 8, run recursion
else
1 * 2 = 2
3 * 4 = 12
2 * 12 = 24
5 - 6 = -1
7 - 8 = -1
-1 - -1 = 0
for i > 8 && i <= n ( i * 0 = 0 )
24 + 0 = 24

I used the following :

for n<4 print NO
for n=4/n=5 find solution by hand
for n>=6
n - (n-1) = 1
1 - 1 = 0
for all i = 5 to i = n-2
i * 0 = 0

you are left with {0,2,3,4} - just do 2*3*4+0

There are several ways to solve it. You can see that with N < 4, there is no answer. With N = 4, you can easily take (1 + 2 + 3) * 4 = 24. N = 5, 2 * 4 = 8, 3 * 5 = 15, 8 + 15 + 1 = 24. From N = 6, 4 * 6 = 24, 3 — 5 = -2, -2 + 2 = 0, 0 * 1 = 0, then for i from 7 to N, 0 * i = 0, and finally, 24 + 0 = 24.

I took special cases for 4,5,6 and

and for n>=6

used pre-created sequence for 5 and 6 based on even or odd n,

made every element n and n-1 as (n)-(n-1)=1

and multiplied all the ones in the end.

If n is even and >= 4: 1 * 2 * 3 * 4 = 24 n-(n-1) = 1, (n-2) — (n-3) = 1 and so on. So just multiply the 24 with the ones.

If n is odd and >= 4: 5 * 4 + 2 + 3 — 1 = 24 n-(n-1) = 1, (n-2)-(n-3) = 1 and so on. Same.

There is no answer if n < 4.

for n >= 6 erase all numbers except 2,3,4 using: (5 — 6 + 1) * z
for n = 4 and n = 5 — hardcoded answer

My solution was, to just use pair(value,pos) in a set, and modify the set comparing function to consider only the first value. Then just keep checking if each element has its match in either A or B. hope it passes final tests :)

Your graph is inspirational !!!

It's a bipartite matching problem ;)

Hm, i had two maps, one <int,bool> where i stored if there exists some number, and one where do i keep position of that number in initial array. Then, for every number, check map1[a-array[i]], map1[b-array[i]], if there is both do sth, if there is only one put it into the set, if there is none return -1. See my code for details UPD: It failed on systest, so this approach may be wrong

Pick a number in the list, say x. Then we are interested in whether a-x and b-x are also in the list. If

1) Neither are in the list, then partitioning is not possible.

2) If only a-x is in the list, then both x and a-x go into set A

3) If only b-x is in the list, then both x and b-x go into set B

4) If both are in the list, then this is inconclusive. We need to further check b-(a-x) and a-(b-x) according to the same rules (for example, if only b-(a-x) is in the list then all of a, a-x, b-x, and b-(a-x) go into set B).

The implementation of this is pretty straightforward, though in contest I mishandled the a=b case (which requires special handling as a-x=b-x=b-(a-x)=a-(b-x)=...). See 7882478.

hopcroft-karp bipartite matching

My solution for div2 D/div1 B:

Assume that b>a because we can switch them anyway and b=a is trivial case. Let x be the smallest value which hasn't been assigned yet to either of the sets. If there exist a value b-x, then we have to pair values x and b-x into set B because value b-x can't be paired into set A because a<b and therefore a-(b-x)<x and there exist no values smaller than x. So we know that if there exist value b-x, we have to pair it with x. If there doesn't exist value b-x, we have to pair x with a-x into set A. If we can't do that, the answer is NO. This approach can be implemented just by iterating over elements which haven't been assigned to either set in ascending order. 7874034

For numbers up to 3 answer is 'NO'.

Solution for 4:
1 * 2 = 2
2 * 3 = 6
6 * 4 = 24

Solution for 5:
5 - 3 = 2
2 + 1 = 3
2 * 3 = 6
6 * 4 = 24

Other solutions:
N - (N - 1) = 1
(N - 2) - (N - 3) = 1
...
1 * 1 = 1
...
<- solution for 4 if N is even or 5 if N is odd

Just notice this if(n<4) no soln if(n==4) 1*2*3*4=24 if(n==5) 4*5+3+2-1=24 and for all other numbers, if n is even then you do the 4 thingy and keep doing i+1-i=1 for all the numbers, and at last do 24*1=24 as many times is you need same thing for odd n, just you would use 5 thing

You can get the 24 by using 2, 3, 4 or 1, 2, 3, 4. For the neighbor number, say, i and i + 1, we can get 1 by using - operator, and 1 can be eliminated by * with other number. Then I think you get the answer:-)

if n is less than 4, obviously no solution. Then 2 cases, if n is even, we can reduce the sequence to 1,2,3,4 (after which we just multiply each element one at a time). By subtracting n and n — 1, multiplying 1 and 1, then n — 2 and n — 3 and so on.. if n is odd, you can similarly bring it to 1,2,3,4,5, we can reduce to 2,3,4 by doing the following: 1 + 5 = 6, 6 — 3 = 3. After this we just multiply each one again. Hope its clear :)

A much easier solution is to get 1 by doing n-(n-1) and then 1-1=0. Now do i*0=0 for all i from 5 to n-2. And then do 2*3*4 = 24. For n<=6 pre calculate the ans. I hope you get it.

Haha I forgot to print "YES too :P

My solution was as follows: the n = 4 is easy, because we can just multiply 1 * 2 * 3 * 4 = 24. The n = 5 is a tiny bit trickier, but we have 4 * 5 = 20, then 20 + 2 + 3 — 1 = 24. Now, if n > 5, we can take the two largest numbers, n and n-1, and subtract n-1 from n to get 1. Now, our list is 1, 2, 3, ..., n-3, n-2, 1. If we multiply the two 1s, we are left with 1, 2, 3, ..., n-3, n-2, which is the list for n-2, a smaller case! This means that n = 6 will work, since we can reduce it to the n = 4 case, n = 7 will work, since we can reduce it to the n = 5 case, and so on.

my answer is 1*2*3*4*(6-5)*(8-7)*...*(n-(n-1))=24 for n is even 5*4+3+2-1*(7-6)*(9-8)*...*(n-(n-1))=24 for n is odd

Реши руками для N = 4 и N = 5, забей в строковые константы.

Если N < 4 то решения нет, иначе своди к случаям 4 и 5.

Это можно сделать, отрезая с конца по 2 числа — превращая их в 1 (a[i] — a[i-1]), а потом умножая эту 1 на 1, которая уже есть.

Our Little X is in upper case. Too big!!

Got butthurt? Go away.

I am not sure, but only the last problem seems to be mathematical one.

IMHO, pretests complexity is completely up to the Problem Setter.

Indeed. If it weren't for this "lexicographically smallest" than it would be doable with centroids and that kind of stuff, but it is a significant obstacle :/.

I think just like you :/

For D:

1 2 2
1

about D:

|cpp| if (n % 2) { puts("NO"); return 0; } <||

it will fall on the case

3 2 6 1 2 4

because 2-1=1.

about B: Your check for intersection doesn't look right. See if you can find your error here: if ((x >= a[j].first && x <= a[j].second) || (y >= a[j].first && y <= a[j].second))

I think it is wrong. The answer should be 0, but it is giving 1. oh! Inputs are not valid.

The nodes in the subgraphs can have at most 2 degrees. I think you didnt need such a complicated algorithm

My implementation of hopcroft-karp got Accepted in 514 ms

Solution

printf("24 + 0 = 24\n"); :((

Same story

same story got 1 wa because of that

Why would everybody use tonns of #define? It puts my bum on fire.