Sorry but it's the typical one :(

I wrote it so now I have done something!

For now yes :)

Haha :)

"Wrath" will actually not be a problem, it's just the feeling that you have when the servers go down mid-contest.

"Best round ever"

sa1378 is my bro xd he won't betray us

We have a binary random variable X with Bernoulli distribution.
P(X = 0) = 1 - p — probability of an unrated round
P(X = 1) = p — probability that the round is rated

What is the probability that X = 1, given that we saw X = 0 two times in a row?

we make this unrated!

Just wrote a piece of code to answer this ultimate problem.

text = readFromURL("http://codeforces.com/top-contributed/friends/false/page/77")

if text.find("NoMoreThanANoob")
then print "Unrated"
else print "Rated"

Mission Successful

Okay so div1(div stands for division) is for people with ratings in the range 1900-9999 and div2 is for us noobs below 1900 rating.

Since you haven't played any CF rounds, you will be playing in div2 to get your rating first. Your default rating is 1500 I guess.

After the situation of past CF contest it might be improved enough :)

..... ... re ... .....

Do not be beggar! Do not look for easy ways!

Just comment wisely and you will faint , when you see your contribution.

Can't agree more, I wanted to say this but didn't dare to do it :( Negative contribution is like saying "Codeforces community will become better without you", and now I started to think if it's true.

Can I have positive contribution like others too?

Foolproof way to increase contribution:

https://snag.gy/X3qRLQ.jpg

I really like the first one ^__^

Are this names from fullmetal alchemist?)

Why only Iranian guys? Other guys also cool. People though are divided by the nation but to show discrimination on the public site is stupid.

Take a look at first comment :(

Congratulations! So how did you handle it?

the only way to change the color of our handles in codeforces

When will Christmas come?

here is the guy who tries to make his contribution -200 .

Yep, I have to wait 5-6 minutes for each submission.

Have you notice the case when there is more than one 1 in the array? The idea is that the solver can be proud of themself when they come up the solution and forget to handle this.

Same here. I don't see why the need for 10^6 max value for n (instead of the usual 10^5).

try 3 5 6 2

I was nowhere close to the solution but I think maybe n < 22 is for checking whether the condition is true for your logic

Wht's the role of a[i]?

Actually it works perfectly. If you choose one subset that does not contain the biggest element from the first array, then there is a map between elements in the first array to a bigger element in the second array (the one it becomes). Otherwise there is a map for a smaller element, so sum will never coincide.

I thinks the n up to 22, was a misleading clue to confuse contestants. I tried to come up with a 2^n dp but completely failed.

Yes it was so hard for me too.

Div1B
If any repeated elements are present then no solution
Else put b1 = a2 , b2 = a3 , b3 = a4 , ... bn = a1 (Assume a is sorted)

Div1C
consider all edges with weights <= C , then any minimum spanning tree (forest) consisting of these edges will have the same set of connected components
So have an offline solution where for each i from 1 to MAX , you first check if for all query edges with this weight if they can be added , if not then mask this query with "NO". Then forget these query edges and add actual tree edges with weight i.
This works because of the reason mentioned at the beginning.

Of course.

What will be the answer for this case? My code prints 5 for the former test case you posted. For this test case, it prints 4.

If the sequence is sorted, (I call it as a1 a2 a3 .. an), then the B seq is a2, a3,a4,a5..an,a1. Then just for every element in the A sequence, print the smallest element that is bigger than it.

The tag does say "best round ever" anyway

That's my solution and it passed pretests.

Yes, and it's easy to prove. Let's consider for convenience the permuted arrays a and b:

a1<a2<..<a(N-1)<aN
^   ^     ^      v
a2<a3<..<aN    >a1

If we take any subset that doesn't contain the last element, the sum on the lower side will definitely be bigger. So, we'd only have a problem with those that contain the last element. We need to balance a difference of aN — a1 with a subset of the values a[i + 1] — a[i] for 1 <= i < N. The nice part is that all those are positive and only if we choose them all will we be able to balance the differences (otherwise the total balance from the second part is still too small)

If you don't mind Sarvagya, Can I ask you something?

You have not given any contest from quite sometime and after each contest ends, you ask "how to solve problem X?" Do you give contests with a fake ID? Because it seems so. If yes, why?

Please don't ignore. Thanks.

I see it can be solved by generating function.

cin/cout is by default synced with scanf/printf, which caused the I/O process in C++ submissions to be pretty slow on large input if we don't switch of the sync. Personally, I'll insert ios_base::sync_with_stdio(false); on any source code files I create to switch off the default sync.

cin/cout is slow.

If you want to use cin/cout, include these three lines at beginning of your main() function.

ios_base::sync_with_stdio (false) ; 
cin.tie(0) ; 
cout.tie(0) ;

Cin/Cout is slower than scanf/printf. Keep it a rule of the thumb when n >=1e6 the IO becomes the bottleneck. Use scanf/printf or instead http://codeforces.com/blog/entry/10297

thanks for advices and explanations

My solution (it's different from author's) uses dp on tree and I can't say it's ugly. I will post a link to my submission after the system testing ends.

Here is my solution: 32407269.

sorry for that....

cin/cout is slow.

If you want to use cin/cout, include these three lines at beginning of your main() function.

ios_base::sync_with_stdio (false) ; 
cin.tie(0) ; 
cout.tie(0) ;

Let's suppose array contains count number of 1's.

• If count ≠ 0, then every non-one element has to change into one. So, ans = n - count.
• If array doesn't contain any 1, then compute in the following way.
  You have to find the minimum length of subarray, whose gcd is 1, let's say, it is p. First you have to create one 1 using (p - 1) operations on that subarray. Then, change other non-one elements into 1 also using (n - 1) operations. So, ans = n + p - 2.

You need to answer whether the i'th person will die in O(1).
He will die if there is some other person to the right j > i which can reach the i'th person.

I think this is a good thing to teach people how to use their's language from time to time =)

Race condition! :P KAN

At least you got revenge.

Actually if n > 22 then we can't check if the participant answer is correct or not.

And here is my accepted solution.

Which fails the following test:

4 4
1 4 1
1 2 2
2 3 2
3 4 2
1
3 2 3 4

Both snapshots are of div1.