good luck.

Don't worry :) This bug will be fixed soon.

Hard rounds are good because you always learn something new.

That's not interesting and cool if you ask this question Do you think it's funny? Or you are so cool? Why the hell people don't understand this shit :/

why retired ?

why 36 upvote?? :(

Yah, same happened with me

bbb, ans=YES

anyone who gave up and start reading comments and blogs!

They are not the same.

How do you find such problems? Did you do it before or did you make a google search?

перебор

You can make them all multiples of 2.

If gcd is greater than 1 the answer is 0, otherwise the only solution is to transform all the numbers to even numbers so they are dividable by 2.

The best-case scenario is to take the biggest K. After that I try to randomize the solution's sequence of length K, but TLE ....

Fix k to floor(n / 2) + 1, then sort the array with a or b together. then choose 1,3,5,...,n (maybe one more number which optimize the answer, it depends on the parity of 'n') for array a obviously bigger than sum / 2. There is two condition now:

1. if sum of b(all of the index we chosed) is also fit the condition, print answer
2. if not, then (2, 4, 6, ...) + (one optimize the two sum) must fit the condition

I almost solve it in time and submit in the last minute, but i forget to output k.....TT

if gcd is 1, make all the numbers even.

I proved this:

a[i] = t*k1, a[i+1] = 2*k2 where gcd( a[i], a[i+1] ) = 1, then you can't make their gcd > 1 in less than two moves :)

Proof:Let's show that it can't be made in only one move.

b[i] = a[i] — a[i+1] = t*k1 — 2*k2,
b[i+1] = a[i] + a[i+1] = t*k1 + 2*k2

b[i+1] = b[i] + 4*k2.

Assume b[i] = c*k2, for b[i] and b[i+1] to have gcd > 1 in this move itself. Notice that b[i] is odd.

b[i] = t*k1 — 2*k2, b[i] = c*k2. This meaans t*k1 = (c+2)*k2.

gcd(k1, k2)=1 from our initial condition that gcd=1. This means t=k2. But this contradicts the same assumption.

2 7 14

Maybe n=2, a={3, 3}. Case of gcd(a1, a2,..., an) > 1, the answer is 0.

n = 3
1 1 1 => 3
1 1 2 => 1
1 2 1 => 4
1 2 2 => 2
2 1 1 => 1
2 1 2 => 2
2 2 1 => 2
2 2 2 => 0

fonmagnus I also had the same mistake . What I did was pick max in A and B alternatively . It passed 7 but failed in pretest 8 :).

Btw I think I got my mistake for 8 and tried submitting it but contest ended as my internet was a bit slow.

I also checked that if I choose k-1 largest values in sorted A, what is the minimum value in the remaining sorted A that I can choose, and I discard all values( along with their Bs ) that are lesser than this smallest value.

1 1

NO

всплакнул)

Something like abccba. Answer is NO.

I guess it like this: abcba

Answer is YES.

If string was already palindromic, it would be NO, since the problem says exactly one letter, not <= one letter. I also spent quite a while on this same bug :(

omg that thing worked

so full explaination:

check if the gcd of the seq is > 1 than ans is: YES 0

else: go through the seq and do the operation once on pairs where both nums are odd

go through the seq again and do the operation twice on pairs where one num is even and one num is odd

answer is: YES

Here's the approach Link Try to prove it yourself first. It will be fun.

Consider cases where adjacent numbers are even,even; odd,odd; even,odd; odd,even and see how the operation affects them.

Link

What are you so happy about? Is 94 some lucky number? :)

I used random_shuffle to solve it. In the example:

100000

1 1 1 1 ... 1 1 1 2

2 1 1 1 ... 1 1 1 1

We could easily find out that we should choose as many numbers as possible.

So we choose 50001 numbers.

Also, we could find out that we must choose number 2.

So, the possibility of choosing the number 2 in the array A is:

1-C(99999,50001)/C(100000,50001),approximately 1/2.

So, the possibility of choosing the right answer is 1/4.

We can see that the possibility is actually very high. I hope that my solution could help you:)

У тебя — на переполнении.

Check mine.

Actually it is some constructive + working with different cases.

Start with sorting all items by weight in B's in descending order, then declare all even-indexed (0, 2, ..) elements as "set1" and other as "set2".

First observation: total in B's of "set1" is greater or equal then total of "set2", and the equality is only possible for even n and all B's equal.

Second observation: total of "set1" minus total of "set2" is no more than largest (first) element of "set1", (draw a pic).

Then calculate total in A's of "set1" and "set2" and declare one as answer, possibly adding one element from the other set. (For details check mine solution -- it is checking all cases).

What's the complexity of that? how many time it spends finding the solution and why did you decide to code it? I mean, what was your insight?

Here is another randomized solution!!! http://codeforces.net/contest/798/submission/26560973

look at it :p . I found this pretty cool!

Can anyone calculate the probability of getting the right answer? I think it's cool, and I didn't work this algorithm out during contest. Maybe we can prove this algorithm is right? (if the probability of getting the right answer if very big, like 99.999% :) )

Because it's not easy.